Advent of Code 2021 - Day 12

hello explorers and welcome to another video today we are going to tackle day 12 of advent of code but first i want to thank yay neswa which is my latest patreon um supporter which has now the access to the private discord and i'm really happy to be chatting to him um so let's just jump right into this day 12 passage pathing with your submarine subterranean subsystem subsisting sub optimally the only way for you to getting out of this cave anytime soon is to find a path yourself not just a path the only way you know to find the best path is to find all of them unfortunately the sensors are still mostly working and you build a rough map of the remaining caves your puzzle input so here we have a little puzzle output this is a list of how all the caves are connected you can start at the cave name start and your destination is the cave named end an entry like bd means that the cave b is connected to d that is that you can move between them so the above cave system looks like this your goal is to find the number of district pa distinct paths from that started start and end at end and you 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 b it would be a waste of time to visit all small caves more than once but big caves are large enough that it might be worth visiting them multiple times so all paths you can find should visit small caves at most ones and can visit big caves a number of times given these rules there are 10 paths through the cave system yeah each of the line above list a corresponds to a single path and the caves visited at that path are listed in the order that they are visited and separated by commas note that in this cave system cave d is never visited by any path to do so cave b should be needed to be visited twice once the on the way to cave d a second time the returning from kvd since b is small this is not allowed a slightly larger example has 19 paths and then an even larger one has 226 paths and the example that they gave was even larger so it would have 10 000 paths or so but i don't think there is a million paths famous lost works words so i will try to handle this with a lot of clausts so let's go back here and we will uh create a new package that we call and we are back i think it was the dashing cave project that was the problem can't really have a dash in something that it's dotted and so let's call this a cave and we have a path and the path we should have something that is a set of the strings only this is once these are the small caves you can call them small caves uh visited visited small caves new hash set so that's one thing that we need here in our path and we also need to have the string lost visited so that's the last point we visited let's do a private here boolean at the end false we can have a public path we create a new path and this could have a set of strings these are the caves so i think we will set these to final all of these so no values because these will be something that we set in our string last visited so here we will have uh visited small caves is a new hashet this is the small caves we will add the last visited this last visited will be last visited and if end is equals to last visited then we are at the end so that would be pretty much that right and we only want to add to small caves if last visited and to lower case is equal to last visited or is equal to lost receiver because i don't think that we have a last visit that is lowercase right so if this is uh lowercase we will add it to a small case what's the problem here it might not have been it's initiated here the first thing we do oh this of course great point there so now we have a way of progressing forward here with our path we need to [Music] have this at the end we need to have a get lost visited [Music] and that's pretty much it um we also need to have a public boolean have been at and then string cave and if visited small caves contains this cave then we have already been there so that's not allowed and i think we can build in this this little function here and if cave is lowercase then we return that value else we return false so we don't need to have any idea if it's a larger small cave um so that is pretty much our cave system then we need to have a um i don't know if we need to have that as a single class but we need to have all the paths that is visitable all the cave in cave transitions so let's do a hash map of string and then a set of string new and okay transition new hash map that's all the cave transitions and when we read in a line here [Music] yes then we will so for each test split we will also split the line on dash and that will be our string line array let's not do it more complicated than that and here we take that line array and check if it contains the key [Music] line array zero if it contains that key if it's not contains that key and we also want to do the same for line when that's the problem here it's always true at the moment it is a cave transition put um this and a new hash set so if we haven't seen any of these endings sled yet we will create a new hash set if cave transition i believe that the end will always be on the right hand side and the start will always be on the left hand side so if this this one is if start equals this first cave transition here [Music] no i don't really need to do that because i can i can't move back to start again that's not not the thing and so i can have a cave transition back all of them can be back and forth and so let's just add these so uh cave transition get line array zero one and then here add line array one and now we need to have one cave transition that goes in the opposite direction like that [Music] [Music] so let's create a little system out here just to have a hole where we can put our break point and we need to run the right day of course so let's do that date well now let's do the this one so now we have cave transitions we have start which only goes to a and b is that correct we can go up here so start can go to a and b correct and then we have a which can go to four different direction we can go to b c [Music] uh d esc and start and also end yes and um then we have b here yeah it can go to d and go to a it can go to start and go to end yeah so i think that we have a good cave transition map here um so what i want to do is to create a list of path in the cave new um all paths new uh arraylist or should we do a set of all puffs oh i don't think that would matter um let's see here while um not all at end what a good boolean boolean not all at end um false not all at end equals to true um so let's see here we have all the paths but we want to create one new path here we want to add a new path and that path new path should have a new hash set so no visited paths yet and last visit that should be starch so that's our starting point and then for all paths we will do something if p is at the end then we will continue else here not all attempt equals the false let's see here not all at end that should be true falls true so so now we have figured that one out yeah and if um we aren't at the end we will have the get lost visited we will have our cave transitions when we will get that last visited and this in turn will be a set so we should have a four loop of this um string set for all the caves that we want to visit and [Music] get all the small caves of course so here we want to go through all the paths again and let's see here we have this cave transition that we want to go to and yeah we want to take this path and see if we have been at this cave um if we have not been at that cave we will visit that cave uh so um we will create a new path so i believe that we'll have um a new list of uh path new paths arraylist so that's the new paths that we will have of this and um all paws will be loop off so we'll switch it there so here we can say new path add a new path and this path should have all the old paths all the old visited caves and the new one like that so that's pretty much it so let's see what's happening at the first iteration here what can't we be there let's go there though can't be there either what oh it was because i already was debugging so let's go to the first part here so let's see here with the new paths we had two new last visited a and last visit b and they are beginning at start that looks very promising then we have a couple of new ones here last this is the b last visited c and so on so let's go down here and see what the end result was all paths equal to zero that's not what i wanted um if this path is already at the end we don't want to remove it we just want to add the old path to to the new array so let's see here so now all paths are 10. so 10 different paths through and i believe that that was what we were expecting so that's very good all paths and size so now we can just print out the size of all paths and that is 10 which is extremely well extremely well done sir so let's do a little bit of a harder one okay so here we have one of those where the start is on the wrong side yeah but we don't care because we didn't take that into account so we put in this little larger example here and started off we got 19 which was the right answer for that one if we take the little bit larger one here put that in we got 226 which is the right answer so that means that we might be able to just take the data set the large one and run that too and get 5178. if we put that in here you get a gold star i get a gold story everybody gets a gold star and we sold it right after reviewing the available paths you realize that you might have time to visit a single small cave twice specifically big caves can be visited any number of times and small caves can be visited at most twice the remaining small caves can be visited at most once uh a single small cave can be visited most twice and remaining small caves can be visited most once however the caves named start and end can only be visited exactly once each once the uh you leave the start cave you may not return to it and once you have reached the end cave the path must end immediately now there are 36 possible paths through the first example above um a slightly larger example above has 103 paths through it and the even larger example has 3509 spots through it okay how many paws through these cave systems are there okay so one of the caves we can visit twice um and let's see here um i think this is just a path issue so let's go back to the test data here and like that and we will take the really small example first and get that squared away um so let's try that with our test data here see oh didn't i copy it copy paste so there we have a really small data set so in the path here we check if we have been at and um last week to the lower case yeah and we add to the small caves which is fine we can add multiple times to the small caves that's no problem private string multi-cave that should be null so uh have been at if this has been the case uh [Music] and if uh [Music] multicam is null then we want to have a special case here and if visited then multi k will be this cave [Music] else return uh let's see here we we have this yeah so else we've done that which we already do down here so here we will return hooks so if multicave have been there we will set that cave and then we will not do that again so if we do that yeah we can do that because if multicave is null and start is not equal to cave and end and the amount of those should be true as well let's do some organization here so none of these need can be true what like that really good that they tell you that that could never happen um so if none of these are true then we can do that uh what do we end with up with then we end up with something that takes forever to run again um we are doing the test set so let's see here um we go here yes we are not at the end so let's go here b multi cave is null if we have visited b um so do we ever end up there there we end up in this specific case where we have b ah wait a minute wait a minute wait a minute um we need to have this propagated uh string multi-cave of course and we can put that as our first thing as well of course and then we need to have one get multi-cave and we need to have here when we create we need to get the multi-cave and put that into the path of cost or else we will never propagate that value to our new objects um yeah so the multi-cave here is now or the multicast should be stopped it doesn't really matter on the start object because so let's see here no um there we had a multi-cave then we weren't um so let's see here so that has ended this don't have any multi k that one has ended and that one has ended i would like to see at least one has a multi-cave none of them have it didn't i set the multicam up here no i didn't this multi-k equal to multi-cave [Music] 29 is that correct [Music] 36 so that's not correct um so do we have an example here we have one example right yes and let's go down here with all the paths yeah remove that one there we go so i have 29 paths we only do a difference if we can even do this and if that is the case we will return false because we haven't visited that cave yet and after that we have re visited that cave and we get 29. let's see here private and here we do this pulse string is equal to path string plus last visitor plus an extra comma so and then we'll go here and do a string half string and so much things get fast string so here we will p get past string and i think now that we have done this so many times i think we should have a public path with a path p and then the last visited up here so add more one more and then we can have one that is just those two so everything up here will come from this one p get multi k or p multi k p path string we can remove these getters because we don't use those anymore and we also want to do all of these of course in this path um let's see here we have the first one where we remove this null value that will be correct and here down here we will just say i want to give you the current path and the next part here so here we can do p and last visited is something that we add to yeah i think that is what we do so then we don't need this one either if we run that through and down here we will have a for loop of of all paths and then system out line p gets path for that part think string and down here we will have one get five string so now we should be able to print out all the results and we have a bunch of these but we don't have the start value why don't we have the start value um because we have the last visited start up here oh wait a minute yeah of course we want to do that here as well but we only have the last visitor nope so now we have all the paths that we think are correct so let's go through these and see what we are missing so here we have a bunch that i have not visited for some reason and the result was 36 so these are all the ones that i've been missing uh and the one that i have been visiting twice is b right so why don't i visit b again when i end up in is it that i have been good question good question um but i think we should be able to find the first one here pretty easily so if we go here we should have one that is this first part here when that is available to us then we should be able to um and i think we also need to say that a two string of this one is just puff string i don't want anything else yeah it can be like that so um you could do it like this we have two puffs and continue a bunch more and what we are looking for is a b a c a a b a c a b a c a so that's one that we want to look into when we use that one why don't we get the new values there so here if we go here now then we should have a b a b and there we have a b a c a so this one if we now get a b in this cave here so this one should be allowed so here multicave is already b how is that possible um so we need to go back and look at the paths again here so now we have those now we have a b this should not have a multi k yes and if we go to the next one uh aba so that has a multi kobe that means that that has a multi-cable b of as well of course because those are the same objects that's not good that's no good yes yes yes of course so [Music] um i have a phone multicam and we will set that here instead and i will have a get found multicam um like that and we need one more of these string found decay and we will do this path last visited multi-cave is equal to found multi-tape there we will set it eventually and here if p no that doesn't work either oh my god yeah so that could be still it but we need a different function here get a multicam and that will have is multicam yes so let's see here and here we'll return true answer return force so here if p is multi-cave then we will do that else we will do that and here we should add um c to the multi cable system let's see what that does for us we get 36 we did get did get 36 so that's good um because if we are handling the same uh thing then the the current path we have here would had the multi-cave in it and then when we added other multi caves that would just add to that one so we would destroy this immutability that we had so now we had to first check is have you seen this before and if it's a multi-cave then we need to add that um but it will not be a multi-cave it's not if it's not valid so let's see here if we take the little larger example here so the values we are looking for is one hundred and three and three thousand five hundred and nine so with this example it should be one hundred and three and let's see that's 103 and the little larger example here should be three thousand three thousand five hundred and nine which looks reasonable as well so let's do the full list eventually here let's go over to the data set and see what the result will be and we get 130 0.94 so let's see if that is the correct value yes you get a gold star i get a gold story everybody gets a gold star so let's see what we did here we had first off this cave transition where we went through the full data set and took each part where we went from one cave to another cave and then we will create transitions so we have both the path from that cave to another cave and from the other cave back to this cave so we have both directions here and we put that into a long hash map of cave transitions because we are using sets up here we will not get any duplicates in either direction and then we will create a list of all the paths that we want to visit and we will put in our start path into the um list and then we will go until we have found all the paths that end in the end so if we end up in the end then that's a good path and when every path has ended at the end position then we are done and here we will create a new list of paths so we will only keep the ones that could progress or is already at the end and first off when we go through all the paths and realize that we have some that already already reached the end we will just put those back into new paths and then if we if this is not not one that have reached the end we will set this value to true so we will continue this while loop and then we will go through each of the cave transition for the last visited cave for this specific path and if we have been there or if we haven't been there then we will check if this is a possible multi-cave position which means that we haven't we have been here once but not twice and we haven't been twice to any of the other small caves then we will add the information about this cave as a multi-cave and also the last position and all the other things in this path or else we will just create a new path with the last position here and then we will set the all paths to new paths and then reiterate on the next one we have some debugging here we will print out all the path strings and also the path as size if we look at the path we have different values here so first off we have a bunch of constructors and first we have a bunch of data of course we have the set of all the visited paths so no duplicates here we have the last visited and if we are at the end we have the multi-cave information for that single one small cave that we can visit twice and offer also posturing for debugging if we want to set this specific multi-cave if we have found one of those so this was the line that we had up here where we had three arguments so the path the last visited and the multicam and in that case we will run the mo the standard constructor and then add the found multi-cab otherwise we will uh have a constructor which takes the last path add lost visited to that path uh and then we'll set multi-k we'll set if we are at the end and we will also add to the small caves if this is a lowercase value and the first one where we are at start we can make this a lot simpler but i just add an empty set here and then i will add this start value if it's lower case and it is probably and at the end it will never be and so on but now we'll add to the path string so this could have been much easier but it's a copy paste thing next up we have this function where we check if we are have been at the cave so first off we need to check if this is a lowercase value if not then we can visit as mono many of those as we want but if it's a lowercase cave we also want to check if this is a possible multi-cave and if we haven't been at the multi-cave yet this isn't the start or end position and it's post it's uh available in the visited caves then we will return false else we will return visited caves here so that's the setup here in order to find if we have been at this position we also have a function to check if we are if this is a multi-cave and it it needs not to have been visited as a multi-cave before of course it's not should not be the start or end position and it should be a cave that is already visited and is a small cave then we will return through else it's not a multi cave so we return false and then we have a bunch of these getters and also two string so we have easier debugging so that was day 12. uh it was a lot of things to juggle with classes and so on but i think i figured it out pretty quickly i had a few gotchas there i hope that you learned something from this i hope that you liked this video give it a like share it with your friends and colleagues if you haven't subscribed yet please do that if you solve this in a totally different way leave a comment in the comment section down below and i really hope to see you in the next video [Music] [Music] [Music] you

Channel: Daniel Persson

Views: 402

Keywords: advent of code, advent of code 2021, advent of code in java, java jdk 17, challenge, कोड का आगमन, कोड 2021 का आगमन, Aufkommen des Codes, advento do código, advent of code day 12, advent of code 2021 day 12

Id: w0d8Wvagzmo

Length: 53min 39sec (3219 seconds)

Published: Sun Dec 12 2021