Advent of Code 2021 in C++ - Day 12 - Passage Pathing

day 12 passage pathing with your submarine subterranean subsystems subsisting suboptimally the only way you're getting out of this cave anytime soon is by finding a path yourself not just a path the only way to know if you've found the best path is to find all of them fortunately the sensors are still mostly working so you're you build out a rough map of the remaining caves your puzzle input for example start to a start to b a to c a to b b to d a to end b to end this is a list of how all the caves are connected you start in the cave named start and your destination is the cave named end an entry like bd means that cave b is connected to kfd that is you can move between them okay so i think these are bi-directional links so the above case system looks roughly like this okay we've got a little map your goal is to find the number of distinct paths that start at start end and end and don't visit small caves more than once there are two types of caves big caves written in uppercase like a and small caves written in lowercase like lowercase b it would be a waste of time to visit any small cave more than once but big caves are large enough that it might be worth visiting them multiple times so all the paths you find should visit small caves at most once and can visit big caves any number of times given these rules there are 10 paths through the example cave system start to a to b to a to c to a to end okay so we're spending time going through a multiple times just like it said similarly start a to b to a to end which is a sub path basically of the first path it just doesn't have the ca stuff uh when you go start a b end we need to start a n we can start b end okay got it so we're really finding every every single path this is like a a graph problem uh okay note that this cave system kfd is never visited by any path to do so kfb would need to be visited twice once on the way to kfd and a second time returning from kfd and since cave b is small this is not allowed right we have another example it has more paths and then we have an even bigger example how many paths through the cave system are there that visit small caves at most once okay well let's start with the small input and see what we can do so i'll go ahead and take that i'll copy that into my my into my input file uh let's begin by renaming solve puzzle count distinct paths and start doing some input parsing or const auto line in input uh auto segments let's call them caves actually equals utilities split string and we're splitting on that dash symbol we should always get back two caves right utilities verify else crash caves dot size equals two why is this upset with me it's not anymore okay then i think we need to keep track of our graph so let's go ahead and just create an unordered map of it's going to be strings to strings no it's going to be strings to a stood vector of strings and so what we're going to do is we're going to map from each location to what its valid connections are so start we'll have connection to a and b a will have connections c b end and start so on and so forth in fact i don't think i need to capture start because we'll never explore it but we'll figure it out these should be stood strings all right so for each of our segments or caves rather we need to this shouldn't be a vector let's make this an unordered set that will be faster to look things up so let's do graphs try and place just graph rather graph try in place of caves zero and we will create a new unordered set of stood strings we'll do the same thing for one and then let's actually go and populate our connection we'll get the set we just created or the existing set if there already is one and we'll insert the connection i don't know why i keep typing graphs maybe i should call it cave map or something else whatever it's graph it's fine and this shouldn't be graph this should be caves right there we go all right i think that is going to read all of our input and build our graph but let's check and make sure i'll also put a little comment here just because i think we might be writing a fair amount of code okay from start we can get to a and b is that correct that is correct uh from end we can get to a and b as well okay so i think we have our graph built now and everything's fine cool so now that we have our graph we need to actually go and explore it and i think the way that we're going to do this is we are going to go through from our current location to every connection that's available and start building up paths and we're going to keep building on those paths until they either reach a dead end where we can no longer make progress or where we hit the end so to do that we're going to track a result value which is going to be a vector of strings that i'm going to call finished paths this is where we're going to store all of our paths where we have made it all the way from start to end and i'm also going to keep a vector of vectors of strings so this is going to be a vector of paths uh this should also be a vector a vector of strings because we're going to have multiple paths and this needs to be stood string so let's call this previous paths and we will start by initializing previous paths to a vector that just has starred in it so we will start from our starting position and then then do some exploration and now we're going to need a loop to do that or i could do this recursively but i'm going to do this iteratively tonight i think uh let's make more comments setup or initial search and i'll put this here let's actually call it setup initial search state and we're gonna have a boolean uh b search complete equals false while not b search complete we're gonna do some stuff and what is the stuff that we're gonna do well we're going to start by creating a new result called current paths uh within that we need to look at each previous path that we have so we'll do four const auto previous path in previous paths we're gonna need to do something with its connections so let's do const auto connected caves actually before we can do that we need to figure out where we are on the current path on the previous path and the location we're going to be at the previous path is always going to be the last element so let's do const auto current location equals previous path of previous path dot size minus one and we're always going to have at least one element because we have start in our initial set so that should work i think this is going to give us back start uh then what we need to do is get our connected caves and to do that we are going to say graph at uh what is it going to be current location right so that's going to give us a an unordered setback which should have all the connected caves then we need to go through each cave in connected caves uh and we're gonna do something with it i don't know what yet but let's uh let's make sure this does what i think it is i i what i think it does i think this is going to give us start uh and then we're gonna get two connected caves which are a and b which are connected to start okay so far so good all right so let's start thinking thinking through we have a few cases here we have the like connection is start case we have the connection is small cave case we have connection is big cave and we have connection is end and we need to do something different for each of those uh if we have a start connection we just need to ignore it uh in fact maybe i should pull start out of uh my graph but i'm just gonna check for it for now i think so we're gonna say if cave is start continue and do nothing uh if it's a small cave we're gonna have to figure out if it's a duplicate i'm actually gonna come back to this case i think uh but i think what we can do to figure out if we are in this case is just check whether the first letter is uh lowercase uh that will work unless it's end i think so let's say uh let's handle the end case we're gonna say if cave is end uh going to create a copy of previous path we are going to append or push back rather the cave to that and then we are going to add it to finished paths because it's now done and i know i just need the count of finish paths but i want to i want to keep track of all of them um at least for now in case they're relevant to us in part two so that should solve for the end case i think okay small cave and big cave we need to figure out let's do big cave first i'm going to say auto current path equals previous path because we want to start from a copy of it we're going to say currentpath.pushback of cave so just like we did for our finished path here and i also think i want to keep track of all of our current paths i'm already doing that right yes so each iteration through the search i'm building up a new set of current paths why is this upset it's not undefined it's right there i don't know why that's mad we'll figure it out in a second i'm going to comment this out for now okay that might be why it's mad all right so uh current paths dot pushback current path so that adds it to our list of current paths and is that all we need to do for big caves i think it might be i think after we finish a full iteration of our search we are going to just replace previous paths with current path or current paths rather so as we search each time we're getting a new set of paths that go deeper uh if we hit the end it's removed from the search now we need to handle the small cave case because the small cave case could result in a dead end i think right now what's going to happen is my search is never going to terminate because it's going to just bounce back between um small caves right now but let's let's actually look at an iteration and just see if it does kind of what we expect given that we know that it's currently wrong so i set my break point on previous paths and current paths i can inspect those and what we'll see is that previous paths is start and current paths are going to be start a and start b which makes sense so the next time around the loop we're going to be starting from the cave a and the cave b and in fact we see start a c which makes sense we see start a b which makes sense we see start we still see oh that's previous paths let's look at two and three we see start ba we see start bd and do we have any finished paths yet we do have two finish paths which are start a end and start bn so i think that's what i expect um as we continue to run through this what i think we're going to see is that current paths just kind of bounce back and forth which is going to not terminate and give us the wrong answer yeah so start b-a-b uh we're we're just going to keep ping-ponging back and forth so so that's not what we want we do have to actually handle small caves correctly so to do that we're going to say if cave of 0 which is going to be the first character in the cave string is greater than or equal to a and less than or equal to z we know we have a small cave and we need to do something and this should be safe because we checked for end already here and i think we want to just do a search and see if we've already visited this cave so let's say b already visited and that's just going to be stood find of current sorry it's going to be previous path i haven't created current path yet previous path dot begin previous path dot end and we are looking for cave and if that does not equal previouspath.end then we know that we've already visited it if we have already visited it we have hit a dead end and we just continue here so that path is basically going to get thrown away because we're not going to make it to the the spot where we extend the current path and then i think just falling through to our big cave logic uh we're gonna do the right thing so it's no longer connections big cave it's connection is big cave or unvisited small cave uh all right let's let's clean this up a little bit i don't need these comments actually i think this is pretty clear okay so that should go all the way through and i the last thing i need to do is figure out what to do with my search here i'm going to say b search complete equals true and here if we find another path to explore we'll say b search complete equals false and then our loop will just keep going around until we never hit this block at which point we should have found all of the solved paths and we will exit out so then i think the last piece that we need is to return the size of finished paths all right let's set a break point on that last line and see what finished paths look like uh it looks like i've only got four right now which i don't think is the right answer so what do we see we see start a end we see start b end we see start a b end and start ba end but wasn't there like 10 of them i think and it was supposed to bounce back and forth so what have i screwed up here because we're missing the the case where we went start a c a end for example so i'm guessing something here is wrong but i'm not sure what let's set a break point and find out all right so in this case we are adding b in this case we are adding c we've got so much junk in the debug view there so previous path was start a here we're going c we're saying current path goes to c start ac so that that looks like it does like what we wanted here and that gets pushed back into current paths right yep start ac did i where did i mark current paths so it is at the start of the search which is correct i want to see where it gets excluded specifically all right so start bab we throw it away on b which is great start bd we throw it away on b which is great current path right now has size four start aca so this still looks correct this still looks correct so now i should see aca end as a valid one on my next iteration right it did not why [Music] why why why why why i never finished my search so something here is wrong [Music] ah it is because i am doing this at the wrong point i need to do it here at the start so basically i wasn't finishing my search because i was resetting it every time through rather than uh here so i was stopping if any of my previous paths hit a dead end rather than if all of my previous paths hit a dead end now when we look at finished paths i bet we get the right answer let me clear these break points and take a look at finished paths yes now we have 10. okay so 10 was the answer that we expected i believe yes all right let's test the other input cases here we'll try this and i'm just going to run it here uh we now get 19 is 19 the right answer 19 is the right answer and then we have a larger example that has 226 paths uh 226 that looks correct great okay let's get our input and see if we have successfully solved part one it is slower now 3400 is the answer that took almost a full second to run that is correct before we move on to part two let's make this a little bit faster here um i think i'm doing a whole bunch of unnecessary copies right now and this is going to be the biggest one so rather than just doing an equals assignment i am going to do a swap which will exchange the internal memory of our vectors and basically current paths will become previous paths previous paths will become current paths current paths will go uh out of scope and uh then die and that should be a fair bit quicker so let's see uh that brings our time down so that took us from like 700 milliseconds down to like 600 ish milliseconds uh what else are we doing that's slow let's let's take a quick look here in the uh profiler i just want to see if we look at uh not read all lines in file account distinct paths is what i want to look at so we're we're spending about six percent of our time doing the find operation which makes sense uh we're spending a fair amount of time adding the string to our current path and then adding current paths to or adding current paths to our new vector of current paths but i think we need that and we're swapping this is actually okay i am going to switch over to release mode and we'll see what kind of time it takes all right now it takes like 10 milliseconds so we got an order of magnitude faster by uh simply switching from debug to release and getting rid of all of the helpful error checking in the um stl okay so that's part one onward to part two after reviewing the available pass you realize that you might have time to visit a single small cave twice specifically big caves can be visited any number of times a single small cave can be visited at most twice and the remaining small caves can be visited at most wants however the caves named start and end can only be visited exactly once each once you leave the start cave you may not return to it and once you reach the end cave the path must end immediately good news we did this um without implementing them as small caves we just did that because they're special uh now the 36 possible paths to the first example are yada yada yada yada okay and then they have answers for the other examples given these new rules how many paths through this cave system are there okay so this is just more complicated because we have the visit a single small cave twice rule so to do that the first thing i'm going to do is i'm going to do a quick little refactor i'm going to call it uh bool b revisit one small cave we will say false for solution a we'll say true for solution b and we'll also take it here uh revisit one small cave all right then all we need to do here uh is revisit this language so if already visited and not be revisit one small cave then we're gonna continue uh and actually hold on i'm gonna do this here instead [Music] okay otherwise we need to figure out have we already visited a different small cave and so to do that i think all we're going to do is we're going to walk through our current path or walk through previous path rather and for each small cave we're going to check if there's another instance of that small cave already here so to do that we're going to say for const auto uh existing cave in previous path uh we want to check actually i don't want to do that i want to do for it i i don't want to do a range based for loop here i think i need the index so if for in i i is less than uh previous path dot size [Music] plus plus i and i'm actually going to start on one so that we skip over start hey everybody this is editor new cutting in my initial implementation here was pretty scuffed i knew the logic that i wanted to write in my head but for whatever reason my brain just couldn't see what i was actually writing anyways i've left the debugging in here because i think it might be useful and instructive for figuring out how to diagnose these types of problems feel free to skip ahead with the chapter marker if you're uninterested uh we know that end isn't going to be here because if end was here it would have already been unfinished paths and we'd be done so if it starts with a lower case we know for sure it's a small cave then i think we need to say i need another boolean here i'm going to say auto b already visited a small cave uh and we'll set that to false then what we're gonna say is b already visited small cave equals going to say small cape twice actually how did i name my variable here i named it revisit okay so let's actually say b already revisited a small cave naming things is the hardest part of this we're gonna do a find operation here and it's gonna be previous path dot begin plus i um so we're gonna start i plus one we're gonna start one past our current our current location and then we're going to search between that and the end and we are looking for cave and if that does not equal previouspath.end then we have found another instance of the same cave and if that happens we don't need to search anymore we're done and then finally if we have already revisited another small cave we know we can't revisit the current small cave that we're evaluating so i think just to continue will work the same as it would have up here i'm going to go all the way back to the starting example here in my input see if this is correct would not shock me to learn i made a mistake all right so we went from 10 paths to 18 paths is that correct no that is not correct there should be 36 possible paths so let's figure out why i want to see the case where i'm failing out here i wonder if i have screwed this up we'll see uh let me switch back to debug mode here so i can actually debug it alright so already revisited a small cave right now let's look at what we're trying to add we're trying to add c to previous path but previous path already has c in it so that for sure should fell out that makes sense uh here's another case we're trying to add b in this case it's oh wait wait wait wait wait wait wait wait that's not right it shouldn't fail out okay all right so we've got abd here b should be valid uh so what is my search actually looking at previous path what is my eye here oh my goodness oh my goodness okay uh this should be const auto previous cave equals previous path by it turns out you have to actually um you have to actually search for the thing that you want to search for i was just always comparing to the the current cave that we're looking at adding all right let's try this again get rid of our break points okay now we get 30. that's still not right it should be 36. okay let's see where we're messing up now so this logic is still not quite right okay now we are bailing out our previous path is bdb and we're looking at adding d so that makes sense that we would bail out in this case we're trying to add d we've already visited b twice that also makes sense to bail out in this case we are looking at revisiting c this case should not fail out so let's see what our logic is here so i is currently one previous path dot begin we are going to be searching i'm still searching for the wrong thing y'all i'm just uh i'm just struggling on this one got like too much state to keep track of okay now we get 36. let's go back to release mode okay so this sample works uh let's go to the slightly longer example see what that is 103. is that the right answer uh where was it yeah 103. okay even larger example let's see what this one is uh 3509 that's also correct all right finally let's try our real input i think i've got it right now that just that took me a while that should have been easier 84 870. all right that's the right answer all right so let's quickly summarize what we did first we built a graph by reading in our input and making all of the connections and that's just a map of strings into an unordered set and in retrospect this could now be a vector because it turned out we didn't actually need any of the properties that set provided but whatever it's done then we set up our initial search state we have finished paths which is going to store all the final paths this also could just be a count because it turned out we didn't need the full details of the paths but we have them and it works uh we created a previous path variable and we initialized that with our initial search state which is just a single path with the location start then we began our search and the way our search works is we go through all of the previous paths we find our current location which is the last position on each previous path we look at the caves that are connected to current location if it's start we throw it away we're not going back to start if it's end we know that we have reached the end of the previous path and we put that into finished paths and we no longer need to search it if it is a small cave we need to check whether or not we've already visited it if so we then check whether or not we are revisiting small caves once if we are revisiting we will continue to the next code block but if we are not revisiting one small cave we we know that we can't go back to that small cave and we just skip it um so this this search path is effectively a dead hand uh if we are revisiting one small cave then we need to make sure that this is the first time we are visiting a small cave we do that by walking through all the small caves currently in our path and searching for other instances of that same small cave if we find one then we know that we're at a dead end and uh we we don't revisit the current small cave that we're evaluating otherwise we move on to our logic that is shared between valid small caves and big caves which is to just append the current connected cave to our current path add that current path to our set of current paths then we update previous paths with the value of our current paths and keep searching at the point where we no longer find a valid big cave or small cave along our path to enter we stop setting b search complete to false and then we exit out knowing that we have found all possible paths that's it i will see you all for day 13.

Channel: Riot Nu

Views: 75

Keywords: programming, c++, cpp, software engineering, coding, code

Id: ex1KJkPY1Ho

Length: 34min 31sec (2071 seconds)

Published: Sun Dec 12 2021