Passage Pathing [Day 12 - Advent of Code 2021]

all right this is zoe xpf looking at day 12 advent of code 2021. i actually saw this one yesterday while sitting in the middle of an airport um so i couldn't record a video while solving it but i thought i'd go back and probably make the same mistakes i made yesterday so we'll give it a shot here and see how it goes the challenge is called passage pathing basically i'm going to get a list of connected cave rooms and so you can go this means you can go from start to a or a to start you know a to c or c to a so you can take this and make kind of a map that looks like this and so the goal is to find the number of distinct paths from start to end that don't mis visit small caves more than once so it defines you know a is all caps so it's a big cave b is in lower case so it's a small cave so you can only visit each small cave once but you can visit the big caves a in this case as many times as you want and so that's why you get things like start a end start a c a end start a b end but you're never going to get start b d because once you go to d you can't go back to b again so you're at a dead end it's not a path anymore um so that's what they lay out here they show all those paths um they actually give us three different examples in this one so here's another path um again you can see the big caves like hn and ln um and small caves um we've got 19 paths this one has because it's got more big caves i think maybe just more paths 226 pads so the question is how many pads can you go through your puzzle input visiting small caves at most once all right so let's uh jump over to python um so normal thing here got my template started um lines equals so the first thing i need to do is run over my list of um lines and create i'm going to create a dictionary and so i'm actually going to use um a default dick for this one and what that let me do let's see so i'm going to i'll say paths equals default dict list and so basically i'm going to have this default dict so if i try to reach something that doesn't have a key it's just going to return an empty list and this is going to be really convenient now because i don't want to check every time does this key exist if not create it and then add something and if it does just add something i can just you know work with it and add something to it so now i'll loop over my lines and what i'm going to do is i'm going to say a comma b just generic my two things let's um them 12 example one um and so all i need to do here is line dot strip because i want to get rid of the new line dot split on dash that should give me an a and a b and then what i'll do is i'll say paths sub a dot append b and paths sub b dot append a and what this is going to do is it's going to create a dictionary for me um or a list for me here let's see a dictionary so python 3 day 12 12 ex 1 is what we were looking at from collections not from default dict but import dos vault dict and let's add the dash i here so we can see what do we have now for paths so you can see here you know if i put in start in fact i can do that paths of start it can go to a and to b and that's it matches what i have here if i put in capital a it goes back to start it can go to c b it can go to the end etc um so now i can for any node i can find out the nodes it can visit it can't visit um i'm going to add a bit more logic here and the fact that based on the fact that start is one you can never go to um so what i'm gonna do is say if um there should be no case where start is appended here there should be no case where end you never leave end so i don't ever want a to be end here i don't ever want b to be start so i'll say if a not equal end and b it's not equal start because if either of those the case i don't i just want to ignore it um don't do that and then same thing here if b is not equal end and a is not equal start and do that and i think that's all i need for there now um that'll just give me a little bit cleaner um halves let's check it out so basically now start goes to a and b but a doesn't go back to start you never go back to start so that's what i want and there is no end in here anymore i used to have an end could go to a or b but now i don't need that anymore so that looks good um okay so what how am i gonna how am i gonna traverse this cave and this is a really useful case for recursion i think i did a recursion in day 11 as well so we'll define a function def walk and we'll just have it say you know pass in visit um and so what i'm going to do is i'm going to check the last element in visited so if visited uh sub negative one equals end basically i'm done let's just print visited uh and then we will return and so now if i'm not at the end if i'm in some cave i want to see which caves can i go to so i will do um for the uh pave in my uh paths sub visited minus one like that get the last you know so i'll get the last cave on my list and i will see where can i go next now loop over each of those options um it's what i can do now is i can say so if node or not cave uh if not cave in visited that means i haven't gone to the cave yet or uh cave dot upper equals cave so basically if it's an uppercase because if it's uppercase i'm going to go either way and if it's not the visible list i'm going to go then i'm going to do walk of visited plus pave so i'm just going to basically call the function again and i'm going to go check out that cave and that is it i don't have any counting going on here but i think that's all i need to um to start with to at least get started on um okay so i never reached end here um i wonder why let's see um oh i never i never called a function so the last thing i need to do walk and um what i'll do here is i'll just say visited equal ah that's that seems messy let's just come back here and to start i'm going to go into a list that just has start in it try that again clearly i made a typo um 23 this visted try that again and cool that printed out all these different paths i can go to um to get to the end um let's see i'm curious to know how long that is because what what in the end what i'm going to be looking for is a count so i could just solve it this way where i print all the print all of them and print it into word count 10 sounds like the right answer um here it is yep 10 paths that looks pretty good um just to show how i would count you know i could i could literally just solve it now um in fact so we could do example 2 is 19 example 3 is 226 so example 2 is 19 example 3 is 226 and so i'm looking for how many in my puzzle input 4659 4659 i could just solve it that way that works perfectly fine um but just when you're working with recursive functions it's nice to know how to do this so if i just called walked on end if i started an end um then i want to return one here and excuse me that's the tricky kind of edge case for a second but you know i'm going to return in this case i'm just going to return one in the other case here where any case where i am going into other caves i'm going to start by keeping a count start at zero and then for each of these i'm going to say count plus equals you know the number of paths that go down that way um so if i start in start and i come in here that's not going to happen i'll then loop over start and start's going to go to a or b and so when i eventually so i'll go to a by calling walk on start plus a and come back up here and i'll come down again and i'll loop through and one of the things i'll go to is visited of start of start a exit or end and that'll return one which will add to my account another one i'll go to is like uh start a b which then itself will call exit and that'll return up to here and so that these things will loop into the account here that's probably the hardest part of recursion to conceptualize i'm not sure i'm explaining it great but at the end here i can just return count so if it's end return one if it's not end take try all all the rooms um that you can go to and uh each time you know collect all the paths that came back and at the end return that count um and so with that i can do print uh let's do double there part one put that in there close u close u and now we no longer want the word count and we get the same number so we got our 46.59 um so i think that was probably not the best explanation of how you collect recursion but it's worth playing with sometime if you ever want to see how that works you can put some debugging and sort of step through this and see how things go let's jump back over here we're on to part two now you realize actually instead of visiting not being able to visit any cave more than once um you can you can realize you might have time to visit a single small cave twice and i misread this at first when i was originally solving this went down a big rabbit hole it's not you can visit each small cave twice once you visit any small cave twice the rest of the rooms um you can only go the rest of the small ones you can only go into once um it's also they are very explicit here you don't ever go to start again or to end again so there are now 36 possible paths so let's let's try this here we're going to do something very similar let's see come down here yank this paste um i don't want that anymore so get rid of that um and we're just going to call this walk two and it's going to be very similar um but this time we're just gonna change our logic a little bit so walk make that two make that a two okay so what is walk two gonna look like well if we're at the end node we're in the same place where before we're we're done let's return one and move on um we're going to still loop over all of our caves and this time just the logic is going to get a little bit more um this if statement it's this stuff right here we're going to change um so let's talk to let's think through the different logic here uh first of all we can do if um no uh i don't know i was gonna call this node i think i must call it that yesterday cave.upper equals cave so if it's uppercase i'm visiting so right count plus equals walk to visited plus save and that's that looks good else if actually let's let's simplify here and this will make it easier to follow i just do an else so now i know i have a lowercase node okay let's let's find let's find out how many times i've been to that node how many times is it is equal to i'm going to make a list comprehension here so i'll do n for n uh in cave and not in k in uh visited if n equals cave so this will give me a list of all of the everything in my visited string but only if it's the current uh cave that i'm looping through and so then if i do len now i'll know how many times have i been to this cave before um and so if times visited equals zero never been to that cave before then no matter what i'm gonna go to it so i'm gonna say count plus equals walk to visited plus cave else and not just else else if um and this is where i need some way to track uh you know have i visited am i done with my small my extra small room and so i'm going to actually add something here small done else if not small done count plus equals walk to visited plus pave comma and so how we oh let's we can close it off here um get rid of this because i'm not using that at all so i need to be able to track this small done and so basically when i call it originally i'm going to uh walk to tama i've not done my small yet and we'll put it up here in the yep we added it here so now when we go here small done is going to be the same as whatever it was before so let's leave it and same here small done didn't change um because i i haven't visited the room before so i visited for the first time my little extra check is not complete if i get to this point where i know it's a lowercase room because i got to here i know the times visited is greater than zero i've visited it before but i'm still gonna go then then uh now i'm going to say small done my small done is true so now any paths that come off of this will not be able to revisit ace will not be able to revisit so once it's small you know if i visited before and small done is already marked true then just nothing's going to happen i'll just keep looping over that and so that's actually all i need there to finish i think let's give it a try let's start with our start with our test input 36 was that what we were looking for i think it is um 36 possible paths awesome um let's see so the next one is 103 and then 3509 103 so it's looking pretty good um we'll do our puzzle input it's quite long but 148 962 148 962 and that's where we get the stars um so again this is a really cool example of the power of recursion um could you could do this without recursion the other alternative would be as you loop over these paths you still keep lists of different paths you're going down and you maybe create a cue somewhere and so you just do a while you add it to the queue and then do a while cue you know well this list of paths to check um and then you remove it from the queue you loop through that while loop remove the first one um add any add back so it's like um let's see so you might have a queue that looks like let's just um you might have a queue this it will start with start right and then you're going to remove start from the queue and you're going to say well now i want to add start dash a and start dash b okay let's see let's go so we have start then you're going to remove start dash a from the queue and while i put that there so you move start finish a and at the end of the queue you add start dash a dash and where can a go i've already forgotten let's add this um there we go oops i do not mean to be moving it minus i have sub a so a can go to c b and n so we're going to add c dart dash a dash b and start dash a dash end so now we'll try all those and then we'll remove start dash b from the queue back at the beginning of our loop and we will add start dash b dash and we come down here and we find out you know okay slash a start dash b dash d and start dash b dash end okay and then we come to the front we remove our first one from the queue so what can c go to so you can go back to a so we will remove this from the front of the queue and we will add start dash a dash c a and where our loop is done and then we're back here where can b go and we work through this and eventually we're going to reach some at the end any time we reach something that has end we can put it into a different list and we'll store that list and the length of that list we will return so i don't know if that was helpful to watch you know sort of pseudo manually walking through this creation of this queue but you can see how you can create a while loop and just keep going and eventually this queue will reach an end point where you're not adding anything new in it and um you know it eventually goes down to zero and then you'll have your list of ones that are done um so i like but i think recursion is just much cleaner there um so and you can see you know we solved this in really not that many lines here even for the more complicated one and the short one was much shorter so anyway thanks for sticking around to the end hopefully you enjoyed this challenge and i will talk to you next time [Music] you

Channel: 0xdf

Views: 65

Keywords:

Id: 4eFMPQLswpU

Length: 19min 36sec (1176 seconds)

Published: Mon Dec 13 2021