Advent of Code 2021 - Day 12

okay welcome everyone to day 12 of advent of code about to begin here i'm doing this one again at midnight one comes out my time problem is set up because this running here i'll go ahead and run to make sure inputs ready this is ready we should be all good to go once this problem begins here in a second all right now with the submarines subterranean systems uh subsisting sub optimally that's a lot of s's uh the only way you're getting out of the cave anytime soon is by finding a path yourself not just a path the only way to know that you found the best path is to find all of them forcing sensors are still mostly working you can build a rough mapping of the remaining caves your puzzle input for example um this is a list of how all of the kids are connected you start in the cave the name starts and your destination is the cave name end uh and an entry like b means that the cave be kind to that okay um your goal is to find the number of distinct paths that start at start and end to end you don't visit them all and don't visit all the small case more than once um wait your goal is to find the number of distinct paths that start at start and end at end and don't visit small caves more than once there are two types of caves big caves are in uppercase a and small caves written in lowercase b it'd be a waste of time to visit any small cave more than once but big kids are large enough that might be worth visiting multiple times um that's all the powers you can find visiting small case at uh once visit given these rules are a 10 pass to this example case system oh start a to b to a to c to a and these what is okay cases by that path are listed in uh the order they are visited and separated by commas note that in this cave system k d is never visited by any path um wow this is okay note that the in this case the kd is never visited by any path to do so uh kb we need to visit by uh it was one twice yeah okay okay how many past this key system are there so we're actually gonna be going right back to where we were yesterday again with the uh whoops with our breath first search essentially it's gonna be the same thing just a little bit changed um to start this first we need to build up all of the paths um so this is just gonna be a map i guess we can do why not uh okay so we're just gonna have i think this is the best is just to do a map here of string to string this is going to be the paths uh hashmap come on no import path please thank you um i'll go through our inputs and inputs and then we're going to do is we're going to do paths puts i'm actually going to split this first path parts equals s dot um let's just trim to make sure it's not really necessary to trim it but we're going to just to be safe um it's not that it's this and it's going to be 0 2 1. there we go so there's our map that should build this all up um there's a small case of most ones so basically we just have to go from start to end and visit okay so what we're going to do is how do you understand obviously it's a breadth first search is what it is i guess the bread first search is going to be it could be recursive actually instead of doing bread first could do it in that case actually where curse might be better here um this is called public uh return a list of uh strings is what's this asking for um account so we'll just list the strings it's fine um this is going to be um a move called a move i guess i don't know or navigate sure i don't know um it's going to take in we'll make this just a uh a public kind of look up table so it's going to take in the um position and from this position we're going to determine all of the patterns that we can take to the end is what we're going to do for um but we're also going to need a list of visited so we could have probably done this with the um the where we had the past few days with the bread first search but we're gonna do this slightly different and that we're gonna do a recursion um so listen because i'm just calling navigate and we're going to start at start and it's going to be a empty list here and we're going to get um out of this we need all the paths it can take and what we should be calling is just lap paths size so this is where the bulk of the work is going to be done what we're going to do is we are going to get a list oh wait this can't work because um it's gonna have the same key multiple times um so map won't work um so i guess we're gonna need to make a class then uh sure polish's path uh that's public string start public string and or no let's do it this way this will be easier well not easier this will be better um we're gonna do paths wow uh get our defaults this that's not what i had to do um grab this and then add on this yeah get our default i think i think that's what it is because the default gets oh i know why this is happening because yeah we're sorry i forgot this is how this worked it gets this good call from the constructor it's weird don't worry about it i'm i'm just i totally forgot my code worked there we go we're good now okay okay okay so now we can call don't add paths parts i just spent a lot of time trying to remember how my code worked okay so now we should be good um so if i do this well if this was still there um so we should get it to where this will now put the size of it and this time i'm going really soft okay we're working out all right so now let's navigate what we're gonna do is we're gonna have this navigate um list of string this is going to be the uh the paths i guess uh what can i get i read this please thank you um so here's me all of our paths um and then we're going to go on the paths and we're going to get this position and so this is going to be for string um call this destination i guess this is where we're going to go to the station we're going to do um visited we're going to go ahead and add this destination in just because i know this doesn't always work um oh this is um paths to return by the way um we're gonna have to ignore the upper case but for now this is fine um add it and then we're gonna go ahead and call paths um to return we're gonna set equal to navigate i guess give it a destination and giving it visited [Music] um yeah and then we're gonna have to go this is gonna be kind of to edit them all um is this is not totally needed i don't really need to do this um [Music] all right let's just make this easier on myself and we'll just have it do this um so this is going to be int um paths to go let's just leave it as past return um it's gonna be equal to zero and every time well yeah we're gonna have pass the return be equal to what we get back adding it on no just adding that on right yeah there's one three one path it's gonna populate up right well i could like think about this for a second no plus one no this is a one sorry that starts is the one okay all right so this should work the only thing we need now is we need to filter out all of the little ones um so we need to do here is we need to check if um destination um it's only the the lower case letters is what we care about um so if we just do a chart at zero if it is greater than or equal to a um and less than or equal to z uh what you need to do is need to check if visited contains this destination and if it does skip it where it's going to continue just skip this location we don't want anything to do with it so i'm actually just going here because if you've already visited it we don't want to visit again um should we add a check [Music] here of if past return is still equal to one meaning we have nowhere to go this is dealing with if we have uh in this case the example we get to this one we're not going to go anywhere we're going to go back to but starting with business we never want to go so the path is one we're going to return oh and the well actually we'll just do if check up here if position is at the end and just return one that should be what we need i have no idea oh again no pointer with pads again i thought i fixed this it's because there's got to go we got to also know the reverse of the paths okay so this goes away because we also need the reverse of every path gotcha so when we do this we also need to do this there we go 12 seems wrong you know what what if we did this what if we did a list of a list of strings what if we did this um still do that that's still fine and then if we're the end we just return whoops return a new arraylist um because we have oh can i type n please end holy right and then get rid of this i'm gonna go through all of our paths and what this is going to give back is now a list of a list so this is going to be the sub paths of this destination and we have to do is go through every list on here and do um add to position zero i guess i don't know i could just do this adding on to the end of it just add on to the end the destination and then we just return this don't we i'm sorry to return and then to return would get all of these we would add all these on because these are the sub paths or this one path wait no this isn't done here no no no no sorry mess no no no no no i don't know if this is i don't know if there's any better for understanding wise because that's where we're going and then we move it out here oh i didn't copy it i should have copied that bit of code and then now here go through all the two returns and add on this one here yeah it's not the only place you can get creative if you get to an end um so now we just need to filter out the empty ones because we only want we don't want empty one to be returned this should continue um because all right we're just running the same issue right can i just okay let's fix it okay i was getting over that um this 10 so 10's right okay this looks awful i'll fix that later um so 10's right for that one 19 is right for that one okay let's try our input then somehow this is working don't ask me how somehow this is working don't ask me how uh the available pass you realize that you might uh have time to visit every single small cave twice specifically big caves can be visited any number of times so locating visited at moose twice and the remaining small caves can be visited uh wait wait a single small cave may visit almost twice and the remaining small caves can be visited the most however the caves names start and can be visited exactly once uh once you leave this with our key we may not return to it and once you leave the encampment return another 36 possible you can visit one of the small caves twice oh what we can do um so we do part one part two if we allow twice what we can do is visit it here we would just not add it we would do it once where we go through all of them with it out added boy actually no no no no because we could use this allowed twice here so what we would do so this is um we can allow twice okay well it's going to be um allowed twice and true and then leave the two return and then we'll go through this again after we add it and you can't allow twice wait no you can't allow twice because right you can't allow twice because it's there right right um and this is still going to be allowed twice so four four one three if it still works oh this should only be here if it's allowed twice the only time we should be running this really wait no no no no sorry this one's the only one we allow we do if we can allow twice right not this one the other one is this one yeah did we just do it somehow no okay um so what we need to do is actually pull this off we need to take this this is going to be and we need to remove the ones out of here that don't include it so 4 into i equals to add dot size minus one while we are greater than equal to zero i minus minus um lists string um uh should we just do another for the uh so we have a boolean remove equals true um so for string s and to add get i if s um so we're just looking for if it has this so if s uh equals where we're destination 2 right no not destination but we're currently opposition right yeah if it equals that remove equals nope remove is false because we have now visited twice in this case we only remove the ones where we don't see this come up again so now we can just check if remove um this wants me to break right well we can actually just not do this remove we can just remove it here we can just do to add remove oh no we can't do that right because we have to have another breakout here oh no we don't know we can just do to add remove i this will break out of there and then we'll keep going okay and so now we should have the edited version of now where it occurs twice 42 is still too high better but still too high um and it can't be um and it can't be start hey no we're too far 32 no wait cause i'm doing this backwards i'm totally doing this backwards i don't know why um right i'm doing this backwards i don't know why i thought that this was supposed to be like that oh if remove there we go why i thought i could put that there i don't know 44 that seems the right to be above again okay so yes i still have duplicates what i'm guessing or what i have found i still do good so i need to go through i make it just the dirty way of just going through and removing them all um and just doing i guess just do this way um i mean i i yes i could play around with more i'm sure it makes more efficient but let's just get it working for now um list and to return um oh wait oh i can't do um let's do it this way i guess this is not pretty but just go with it um you just do a check here if l dot contains all from two rib turn um i if uh let's do list if l1 does not equal i wanted to make sure that the same list oh my goodness yeah this isn't pretty at all um l1 uh remove nope no remove please give me the right answer we thirty two okay so we got 36 this is just ugly but we've gone 36 um let's just try mine i guess i don't know yeah we're gonna have it should be too slow isn't it i don't know if it's this i mean well it has to be this it's just but if i move it what if i accept it what if i move it out here um this isn't pretty i i wish i could figure out a way to not have these duplicates happen but uh it works it's not amazing to have these duplicates here oh it finally finished different it took a really long time i'd be really sad if this is wrong that's right okay well unfortunately i don't know this i'm just this is kind of where i just i don't know enough i'm not good enough in this space this had a problem i'm just i don't know i don't know i'm getting duplicates in the first place i feel like i'm just missing something um it's late um i'm just kind of calling today just a loss for me i got it right but in terms of being able to go through and teach and whatnot i'm just going to have to go and take the l on this one hopefully so you got kind of um enjoyed watching my process of fixing of trying to do this um hopefully to everyone who's out there um learning to program hope this shows you that we're all human and that's uh we're not all gonna get these um even if you haven't broken over while you're still not gonna be able to understand all them and kind of get them right i guess i mean like i got this in the end but this is far from the best way to do it um sometimes you just you can't do it all so i i would just i would go through and try to explain what i'm doing but i just don't feel like it's worth me doing it i don't feel like it's a good um teaching point for me especially when i don't really understand this so i'm gonna call this there i'm gonna put this up there feel free to comment below on what i can do to do better or what's uh what's wrong with my code here or if you have um a better solution algorithm let me know but um editing rates that's day 12 um there's been better hopefully day 30 goes well but i'll see you tomorrow for day 13 at any rate so thanks for watching peace out [Music] [Applause] [Music]

Channel: TurkeyDev

Views: 504

Keywords: programming, java, advent of code, advent calendar, computer science, advent of code 2021, 2021, coding, learn to code, teaching, introduction, what is advent of code, holiday season, christmas, learn programming, computer programming, how to learn programming, java tutorial, java programming, java for beginners, advent day 12, advent of code day 12, day 12, advent calendar 2021

Id: mVr68NYCadU

Length: 31min 44sec (1904 seconds)

Published: Sat Dec 11 2021