2021 advent of code - day 12 solutions

hello and welcome to another advent of code problem this one is a graph problem so i'm going to show you how i usually represent graphs in code and then show you how we're going to solve this all right so our inputs today and we actually have there are three sample inputs in the in the problem but we're only going to look at two of them uh just because the third one is kind of long and i think these two are good enough uh the inputs are the edges of a bi-directional graph so wherever you see a dash that means you could go either direction so this this means you could travel from start to a or a to start well a to start's actually invalid and we'll see that later uh but i guess if you saw this go from capital a to c or little c to capital a [Music] and for part one we can visit a lowercase only once so if we ever reach lowercase c we can never go back to lowercase c on that particular path but you can revisit uppercase paths as much as you need to and the question asks us to compute all of the paths that go from start this node here to end this node here um and yeah uh so let's just start i'm going to make a separate function for this just because we have to call it twice uh we'll call it compute we'll take in a string and we'll return an integer for the number of paths that we're doing and the way that i like to represent crafts involves a dictionary that maps the node to all of the nodes it can go to so i'm basically keeping track of just the edges and for this i'm going to use a default dict with a set in the middle of it so the key is going to be the start and the set is going to be all of the destinations that are possible for line and s dot split line so we're just going to do the parsing now uh source dest equals line dot split on the dash and since these are bi-directional this means that we're going to insert all of the we're going to insert dest into source and we're going to insert source into test do that really quick uh edges source dot append dust and edges just dot append source that's really all we need to do to represent our graph here once we have that it's just a traversal problem we can either do depth first or breadth first when i solved this live i did it breath first so i might as well do a depth first here why not and we're going to use basically the same pattern that i used when doing a depth first search on the basin problem where i have a list of paths of course in that one it wasn't paths it was current positions and we were able to store state elsewhere but we're going to store our state directly in our path here and we're going to start at start and we're basically just going to [Music] you know use this same pattern again not using recursion just because i find this a little bit easier to understand what's going on basically we're going to keep track of what we need to do in here loop while there's still things remaining and pop off each path and process it one at a time okay so once we have a path we want to be able to consider all of the next places it can go and fortunately we have a mapping of edges here so it's really easy to look that up or a candidate in edges path negative one so this is going to get the last element of our path and we're going to figure out where we can go from there and our conditions for part one is we can go to any path if it is uppercased or we have not visited it in our current path so if candidate is uh if not lower um or uh the candidate is not in our path that means we can continue this path onwards so we can do to do dot append and just uh splat our path in here as well so this is this is special syntax for splatting the current path and appending this tuple i could also have written it as math plus and i can't that also works as well but i kind of like the star syntax so that's why i'm going to use it okay so that covers kind of our iteration case we also need to consider the end case and we also need to count the paths at the end uh all paths equals a set and we know a path has completed if the last element of the path is end because that is our destination so if path negative one is equal to end i believe that means that we're done all paths dot add path and we can just continue uh because we know once we reach the end there's no point in doing further iteration there so this is kind of our termination case and so after that we can just return the length of all paths and that should get us our solution for part one let's try that out print one input one computes input one uh and if we do this twice two let's see what that gets us assuming i don't have typos of course i have typos set that append yes this is not a pen this is add i always mix up those and 10 and 19. that is what we expect for part one cool so that's part one um just to recap i used a map to sets to represent edges and then depth first search here and to switch this from depth first to breath first you could change this from a list to a queue or collections.deck and then instead of doing pop you would do pop left that way you always put things on to the end and pop things from the beginning uh so you get your your your q your depth first there all right let's do part two part two says we can only visit a lowercase uh we can only visit one lowercase item twice and actually when i was solving this this threw me off i thought it was just that you could visit any lowercase twice meaning you'd have two dupes per path but you can only dupe a cave once and again you can still revisit any uppercase and because start is lowercase there's a new stipulation here that you cannot revisit start so if you ever see start while continuing you have to ignore it and it still asks what are all of the paths from start 10 oh i forgot to do the sample data let me get that real quickly see 20 21 day 12 part two not going to look at the solution there and 36 and 103 36 103 okay cool all right so i'm just going to adjust this solution directly um and so we're going to break we're going to break the part the part 1 code but that's fine i solved mine separately okay so we can still revisit any uppercase we need to keep track of whether we have visited a lowercase twice or not and what we could do is just like make a function that recomputes this over and over down here i didn't really like that when i solved mine so i kept a separate piece of state inside of this uh stack here that represented whether i had doubled up a cave or not yet so i could just quickly check this value [Music] and in theory save myself some time double cave so we're going to initialize that to false we have not visited a double cave yet and we are going to adjust our continuation down here we actually don't have to change this at all um and we don't want let's let's do this first we cannot revisit start if candidate equals start we'll just continue not going to bother revisiting it if it's uppercased we can if elif and it is upper then we know we can just continue all paths or not all pass to do dot append and we have a tuple that's star path and candidate and we also have our boolean uh we don't actually modify it here because we're just uppercase double cave um i think that's right number parentheses yep a little bit tricky when dealing with a couple of tuples here so be careful with the prince there we cannot revisit starts we've done all we've done both of these we just need to handle this uh so we can just say if the candidate is not in the path we already know this is the first visit if cans not in path then we can also just do i guess we can just do or cans not in path um these are these are the same case we don't actually modify this at all otherwise if um we have not seen a uh double cave well if not double cave and path dot count canned is equal to one so in this case we have not seen our double cave yet but we have seen exactly one of the candidate already then we can do and start path canned and true so basically only allowing us to duplicate an item if we have not already duplicated an item and once we have done that i think that's part two let's run that we should get 36 and 103 and we do cool so there's a little a little bit of fiddly logic here it did actually take me quite quite a bit of time to come up with this idea but um i think it's fairly fairly easy to understand i kind of don't like having a boolean just floating there without a name so i might i might change this tuple element to be a named tuple that would make this a little bit easier to understand what's going on um just because this would have a name rather than just kind of floating of course we give it a name down here so it's it's not the worst um but yeah and and again an alternative is just recomputing whether you've double caved in here uh one approach to that might be using a counter to see if you have anything that's you know anything that's doubled already but no this works anyway hopefully you find this useful and i'll see you around for the next day you

Channel: anthonywritescode

Views: 484

Keywords:

Id: dlPoe04FoQk

Length: 11min 5sec (665 seconds)

Published: Sun Dec 12 2021