Advent of Code in Haskell 2023 - Day 17 - Attempt 1

all right welcome to today's a of code well yesterday's a of code we're doing day 17 today um we did day 16 yesterday we're still catching up but uh we had a sneak peek at this yesterday and we did the parsing but we figured out that we would need to do some [Music] um path finding algorithm stuff and uh 40 minutes didn't seem me enough to get it done so I decided just to do it uh now in one day and and let's see how it goes um all right so we cated up the parsing so we are taking this example text here paring it into an array and uh you can do arrays in has schol uh they can even be mutable they can have you can do mattresses it's not too bad actually but um um obviously they're a bit diff more difficult to work with because you you know have like built in Syntax for a race as you do with lists but it can all be done where there's a will there's a way so let's remind ourselves what we are doing uh uh so we're kind of we released the lava and now it's flowing down and we want it to flow faster so we put it in something called a crucible uh which is this kind of thing it's just a big pot basically and uh we're we're taking that down and we want to find the one that involves at least heat loss and uh so we get this and then uh what we want to do is we want to get from this top corner here to this bottom corner here but we want to do it in a way that minimizes the Heat lots um and the way we're going to do it is that we're going to look at the numbers here and pick the shortest path according to these numbers which is just a Dess algorithm I Str algorithm and um we're probably do something like a star actually which is dyra but with some extra her istics which makes it a bit faster um so dyra what does d so what do you how do you do dtra uh what you do is that you um you have a graph like this and then you have some neighbors and so you basically yeah exactly so you mark all nodes is unvisited and then you have all the unvisited nodes and then you have a tentative distance such as zero for initial node and to Infinity for all other nodes now during the run of the algorithm the T to distance so then you just get the shortest path so it's basically breath first search um but with a uh with distances instead of just always picking some neighbor [Music] okay and through the current compar one currently assigned to the neighbor and assign [Music] it compare okay so I assign every a tentative distance I set it to zero for our initial node and to Infinity for all other nodes dur run the algorithm dis of node the length of the shortest path discovered so far since initially no path is known to any other Vortex it's going to be infinity and uh then we just find the shortest distance um okay so let's H now my mouse start working again let me plug it in and plug it plug it out plug it in again I Mouse which stopped working and it started working uh but then it stopped working again and now I'm back to this one uh which works again but it keeps stopping keeps dropping out but I think I get a new mouse for Christmas so don't worry about that um so let's keep this to the side and um don't worry about the copyright on this picture cuz I took it actually let me see um we are going to I want to put it like this and then we want this one over here and then we make this example a bit smaller cuz it doesn't really matter okay so D we're going to take in the array of in comma in in and we are going to um make a copy of it I think uh for the distances data. [Music] array okay and can I map over the array it's full foldable it's a funter okay and accessing arrays and this is LMS ah of course I can't easily update the array uh let's see we'll go Mr array so we have mutable arrays as well um so let's do this so dtra is going to be take it in the initial array and we are going to take in the initial Noe and we're going to take in the Target node so now we're just going to do a dtra uh uh simple Tyra and then afterwards we're going to do this cuz we can only move uh three in a row at the start so we're just going to do that a bit later so this is going to be um Monet M SD array something like that uh M we can actually just make it an IO thing IO in cuz now we're going to have a bunch of side effects ah let's make it STD of int I like that better so I want to see so St array is the it's going to be an [Music] st [Music] and so I kind of forgot how to do these let me see um in so now we're going to do n extra is equal to do so we're going to say run St do now this run SD comes from the St monad which is in um import control. mad. uh we have some mutable arrays also import data. m array. m [Music] array Mr array and we're going to say import data. array. MRA m r a s m m a let's see [Music] qualified how's everyone doing today um run St and we are we want the Mona array so we want to say here do um [Music] X is um ma do new array and we want we're going to have it the same dimensions let's see R init Target run St do so so r. bounds um [Music] R so Converse so Tha yes I think I can just actually convert a mutable array into a mutable array so I can just do X is ma dos [Music] R and I think it's going to complain now that it's not return zero it doesn't it won't know what H value will the be [Music] so because uh it's saying so not it's supposed to be ins but it doesn't know the s so I think I want the add s array and then I need the language GSC 2021 does this one work [Music] um oh maybe I have to do m. SD array um it doesn't want that either so what is this data. array. SD import data. arr.st what what is this save h hogo data. array. [Music] S.C they save API of only oh okay I think it's uh going to be [Music] fine but um let's see now it's complaining I [Music] think Stu array has kind star are okay yes St [Music] array the state variable argument for the St type let me see can I just do um run SD array here cannot okay and then um and made. freeze [Music] X because it's saying this okay array in comma int [Music] int okay so now this one is is an sray as and then it's it allows me to just return it cool what do I get if I do read file read file example print. pars do lines so here this returns an array in in so if I do okay I want going to do this actually just need the [Music] arate cuz I know I'm going to go from the top left to the bottom left and where init is equal to in it comma Target is equal to r. bounds r [Music] and now let's print Parts into T [Music] extra oh it just works okay cool uh then I can probably do um so I can saw the array and then I can I can also do um uh let's see I don't need to Sol the array I can just do uh this is a ma do new array and I want it to be Bounds at bounds and I want everything to be uh so the enum type class so I want it to be just Max in right uh enum is the bounded [Music] class and let's see enum Max bound it's called bounds Max [Music] bound Max bound at int and now it doesn't know what to do so it's saying new array um let's see what is the type of X here s array s at s array s okay so it's a big a here and it doesn't like this because [Music] um so let me see if I can find the S inside here uh let's see this is going to be St array s in comma in [Music] right [Music] h no ST int int int right so this is going to be the S and in I think let me see as kind uh what do you want okay um what do you want here new8 okay okay A a z So Okay add in Comm is ADD um SD yes nice so now because I I bound the and the S there so now this is all Max int cool okay let's go back to D St Mark all noes as Mark all notes unvisited okay now I also want to modify I want to set the um read array right array exactly so I just want to say here uh right array this H 0 comma 0 [Music] Z so then we just set the distance of this one to zero and then create a set of all the unvisited not call the unvisited [Music] set let me see um so on the St monad I have some state right and I can do stuff with that [Music] state uh and I can have the SF and then let's just do here scene is s new import data. array. no import data. SD ref who says you can't do imperative programming it's also the best imperative programming language in our high school let's see a SD R and now we have data do set already this is going to be set. empty and now it doesn't know what scene is to be but uh Mark all notes create a set of all the unvisited notes called the unvisited set okay okay assign to every not a tentative distance Z for inial infin noes okay so um for the UN current node consider all of its unvisited neighbors and calculate their tentative distances through the current node okay um let me see let N is equal to map maybe so we have here x so Point p is a point map may be um f to left right up down where um let a p where F okay so let's first write the F here f is equal to move FP is equal to move this is FP d k mve of M D of [Music] um y comma X then we check that um you it [Music] add i y IX and Target is equal to i t oh t y TX okay so just have to check that I is less than or equal to is bigger than equal to [Music] I it just make it like this case so it should be larger than equal to iy and X should be larger than equal to IX [Music] and um and then we should have y less than equal to T Y and X less than or equal to TX and they should go to Just y x otherwise we go to nothing and now map maybe is not imported uh cuz we don't import data Maybe import data Maybe map maybe okay so now we have the [Music] neighbors okay uh so this is the initialization initialization do I need this x here yes do um run SD array so let me just say that [Music] can I do something like this just to get the [Music] um he doesn't like this what is the type of this uh return ah okay let's just grab the SD here from the X not like it takes long so then we initialize it and then what are we going to do how's the audio and everything by the way I hope it is good looks good on my end but let's see okay now um so we write the discs 0 0 then we say go is equal to H so we have this go ding ding ding ding [Music] ding go empty is equal to um tests of [Music] Target tests um M A why doesn't it like this I think it's just bang um do what is it so go TS do I have to do M go uh next so uh okay the current the tentative distance of a node V is the length of shortest path cover so far between consider all of its unvisited neighbors I calculate their tentative distances through the current Noe so then we do here um where let me see uh nay of next let NS equal n of next and um map r. um and to [Music] at why can't I how can I couldn't match expected type array in in all right why so what is the type of of go go takes a list of int comma int and returns uh STD as um int okay so here we're going to do thiss bang and H Target okay so how do I access is Mr array uh I have to do read array right is sorry so I'm going to do this uh m a. read array Target okay that one works okay good okay uh ma a. read array discs um these is equal to ah I need to do this actually these so this is two okay DS map M um and then this one is was type of this so this is just a list of inss and what is can I do uh zp with [Music] him let me see and then I want NS NS I just want to do I need that app map M and and I just want to do and comma over so then this is a list of neighbors and their distances from the current node to the current distances right okay so tentative distance for current consider all of its unvisited neighbors okay so I also have to do so I'll to read SD ref un visited un visited ref okay so and visit it is like this and then we have neighbors and we say filter um not do uh set. member flip set. member visited right maybe not [Music] flip nice okay and I just need to do like this so these are the unvisited neighbors and then I read the distances to those consider all of its unvisited neighbors and calculate their tentative distances through the current node okay so the tentative distances so the distance of the current Noe is going to be curist uh ma. read array uh uh next um this next okay and then the the tentative [Music] distance so so read array this next and then I read all the compare the newly calculated T distance of the one currently neighbor and assign it um if not a is Mark distance of six and the edge connecting with B is a link to then distance B A will be 6 + 2 okay so then I want to say um all right so that's okay so the C this is a so this is the distance of next so DS uh tentative DS Cur is going to be it's going to be but here don't read the this we read the um uh we read the X okay and here we don't just do and Prime we actually do um Plus cist okay now we have the DS sentative and we have the DS [Music] Cur we can actually we don't need to sip this let me do it like this just removing some craft I think I need to do F map do okay uh DS C there's a list of ANS and this is list of DS tentative and then [Music] oh and we also want to write the parents okay let's see and parent and we have the same pounds but here the max [Music] bound let's just have this um nothing the parent of every note is nothing so I want to say here map M um on sip DS tentative um DS Cur that's actually have the node here as [Music] well okay um let F equal so we're going to say here F and this is going to take in the the neighbor and the T dist and the C disc equals so if the distance curv dist is less than T [Music] dist then we do um right array uh parent uh the we write to the parent array and we write parent of n is going to be uh next let changes next to Cur okay Cur or M uh and then these all changed okay right I need parent parent and just curve okay so and then I write the array parent just and I write array H discs uh um curst so that is like if it's the case else why return I don't do anything there right array return yeah I shouldn't return anything right h [Music] m okay f um this type takes in the in comma int the neighbor and then the this and then the current this to SS [Music] um ah and it doesn't have the oops okay so then I map the [Music] esur and now I've also discovered the new neighbors so I want I'm going to add those to the [Music] queue will be checked again okay that's Mark visited m okay go is C KC is equal to [Music] Target then I just read the distance to the Target because I have found it okay otherwise we update the parent we update the dists and then we go go and now we just add the neighbors and is to in front of the rest I think this will work uh let's [Music] see uh but I never did go so I'm going to say uh T this is go in it mhm ah but I didn't I also have to I have to write s ref uh unvisited ref H set. insert Cur and we it [Music] it okay it's saying the distance to the Target is [Music] 79 let's just consider this for a [Music] moment of course this is the PA I want to so I want to actually say here I want to return a list of um so path that's your so path is going to be reconstruct path reconstruct pass a cur is equal to uh curve so we do uh read array parent curve so case red parent curve of nothing empty list it just P to curve um reconstruct path and then we just Ur over Rec construct path P now reconstruct path uh readay is going to be uh in comma int to SD s um in uh we need to turn here and uh this one is supposed to be comma in and reconstruct path so P case read array okay just P why is it maybe maybe [Music] apparent okay read array [Music] parent read [Music] array it should not be this okay so parent is a maybe in in okay now so we take in the Mr array a [Music] n why is it just just P that is where very strange uh return Rec construct pass [Music] and no instance for m s maybe maybe me yeah because it's not just [Music] just okay okay so [Music] here so Target is intent okay Cur so do uh PS [Music] why uh okay two see read array parent curve uh okay just because I don't do it KC of there we go so this is the shortest path but it probably yeah so it takes right A lot of times which is not good but um m [Music] I think this is actually um you want to have the actual path okay so how does it go we go um 01 02 03 04 0 five 07 08 09 01 11 12 and then it just goes [Music] down okay that's [Music] funny okay [Music] um anyway we have a pretty good D TR now uh with the distances and paths and stuff like [Music] that and then if it's within bounds um [Music] then we're okay otherwise let's see this is the heat loss of [Music] 102 so what I think is a trick that we have to do [Music] here let's also just let's just um let's see if this Dy stra works on the [Music] input I don't have the input yet but it's going to be huge uh we already have input what okay save it I just want to see like if the trivial path okay so it takes us doesn't take us that long [Music] um [Music] so what I can also do is I can make this into and we can add a heris stic right by sort [Music] by import data L sort by and then um htic so then we add theistic here array in um that basically makes this an a star uh let me see uh we go sort on is probably better [Music] actually int int to int and then let's make this sort on sort by sort on here we're going to call [Music] it here and r d stra and then this is just going to be first first [Music] uh yeah [Music] first [Music] so actually it's better to have I think a [Music] b like int comma int to in comma int to ordering and then we actually do do sort bu by then let's have it take theistic fear first just to make it smoother okay um [Music] so dyra is just saying they're all equal so then basically nothing should happen but it takes a lot longer but here actually if I then make this um X comma Y and then let's see FX comma a comma B let here equals f a uh here uh a comma b c comma D is equal to so then we're just going to take the we're going to compare them on the distance to the Target that's like a star right so so uh and for us that's actually just going to be um compare a * A + B * B with C * C + D * D ah but this is actually wrong so we want the opposite order because we wanted to so that the uh bigger one is [Music] first okay it just doesn't it doesn't really help the uh sort by theistic here so then let's just go and uh we always so I think it's also because here also always putting the biggest one first okay uh so let's not bother with a star or anything like that now let's focus on making the path like [Music] um making the path [Music] proper what if I um so you might not always have this on a grid right [Music] so this is dtra with [Music] rays let me just [Music] uh [Music] okay maybe I can do it like this Trace show M if I want to just see the path so the shortest path is 892 uh if I ignore this takes X3 distance rule so let's [Music] see [Music] I think this D TR works but it's this is dyra on a 2d grid right um [Music] dtra let's rename it 2D um so what we really want is we want to we want to make sure that so that I think we can kind of Do It um so instead of giving it just like the ones that are one step away we want to give it the ones that are um two steps away and then then three steps away and then just do the [Music] some [Music] it would be nice if this was just a d stra cuz then we could also test our D St right I feel like also this would be like a nice nice part two but what do I know uh let's see okay so let's actually let's just convert it into a map okay so t let's do this all over again then call it D extra map okay so now what I am going to do okay I have um [Music] cuz I don't know need to know the so then okay so [Music] neighbors so map may be FP left right up down so the f is just uh let's change that to be inbounds inbounds okay [Music] um in let's see this is such a stupid name actually uh cuz we're not actually doing anything with the so let's write inbounds p d [Music] uh true false filter okay and then map will be can we just filter them first first and then we do map M okay so neighbors so this is uh the onestep [Music] neighbors so let's let's make a list of the neighbors okay uh these are going to be pths okay so we have nay so for every path we have we can take [Music] um we can take a left we can take a right we can take up and [Music] down uh [Music] um we can [Music] take we can take uh left left we can take um left left I think I'm doing this in a weird [Music] way so the idea is to just [Music] okay maybe I can filter out the legal [Music] neighbors uh okay so I have TR so I have these are the ones in bounds okay let's see this [Music] is Curtis um [Music] okay so first we will say okay [Music] do so IB let IB equals [Music] okay so then I want to see what is the path to the current one uh parent okay but this won't so we seeing an array again it's not good but it's okay uh no this is the one path we can't got to the current one okay so let's just say um so just p is going to be so let's do a read array P current [Music] okay and reader a curve uh CP and then um CPP is going to be case CP of nothing then so if it's nothing it's just [Music] um nothing um just P read array p uh parent P okay rate P rate parent the N Okay so nce okay this is curb let's see um [Music] so I want to see here um so CP is read array parent curve so if there is no parent k cpf nothing then the main neers are just move uh Cur Cur IB it's map move curve IP so if a CP is something if it we have a CP just uh [Music] Cy then I want to see how did we get there [Music] um so from is going to be y comma X uh and then so y1 X1 Y 2 X2 case a x is = to X2 uh so if it's the same um let's Y is equal to y1 so it's the same line a is equal to if X1 less than X2 so to get uh then so to get from uh y y y1.1 to0 2 you had to go right lse left otherwise so then X1 is equal to X2 if uh y1 is less than Y2 so then to get from there you had to go then down else up okay so to get from uh Cur parent then [Music] um [Music] so we want to do here actually case just so if we have a parent then we want to get the parent of that one CPP to okay CPP I know I can just like do some uh map so maybe won't add stuff here but cor parent parent yeah but I don't feel like it h it's uh I don't exactly remember how to do it but it would be very nice um let's just uh cuz I cuz I also need to do the reading of the array [Music] right let let me just see what maybe I can just do it um [Music] pH okay so do just read just curve parent read array parents curve okay and then just Cur parent parent read array parent Cur [Music] parent return [Music] maybe does it work like this oh okay I guess so um rate parent curve rate Cur parent [Music] parent and now let's see if um so let h d Cur is equal to from so to get from y1 to Y2 right uh so to get from yeah from curve parent from uh curve parent to curve and the the parent Cur and then D parent parent equals from a cur parent parent Cur parent and let's [Music] see mhm then if and if the parent curve is equal to D parent [Music] then filter is equal to so not equal to De parent curve so I just remove the direction that would cause it to be the third time [Music] okay um return and then this is just Cas res of let's just say here Rob maybe IB res [Music] and this I need to import from data maybe and then I want to do map move map move curve from maybe uh IB so Ras here [Music] oh [Music] okay [Music] yeah and there's no moad fail right because this isn't [Music] um cuz it it's not in the map mode at right and I have to lift and something like that ah okay let's then just do it different friendly okay [Music] um okay MB Cur parent do mb2 Cur parent case h MB Cur parent of nothing return IB okay um just Cur [Music] parent [Music] two MB C parent read a parent case and be Cur parent parent parent of nothing return IB just Cur parent parent [Music] no do and then we're going to go let we're going to go let and then we're going to say if then else okay now we don't need any Monet fail instance now it's not finishing that's not good um [Music] m [Music] uh it's just not finding any route to the Target I think or is it because I forgot to filter by the unvisited no ands Prime NS Prime [Music] ah yes okay but it's saying uh 1 533 instead of instead of uh 102 so it's something wrong in the example at [Music] least okay so it goes [Music] and and I think it's doing something correct okay so it goes uh 01 then it goes down one one okay and it goes one two okay then it goes this is so it goes 010 it goes 01 okay this is 01 then it goes um ah then it goes one one then it goes one two one two and then it goes 2 one or 2 two yeah goes down again and then it goes two two two three 3 4 4 four so it's not it's not getting the right path does get to the end though which is nice did I maybe flip the [Music] from let's see let's actually make this a lot not less [Music] indented oh right so I filtered out the same direction so it went okay it went okay so it went um let me now actually do um okay let's just look at it okay so it went H 01 02 okay and then one two okay and then I want 2 two um right let's see so 0 one here 0 1 02 1 2 2 2 two 2 three 2 4 2 3 2 4 3 4 4 4 four five 4 six 5 six oh no 56 66 67 six 67 68 7 8 88 8 9 8 10 9 10 uh 911 okay I I got the got something wrong for sure let's [Music] see all maybe we maybe we can't do it this way so we're getting the shortest path to a no and then we're just making sure that if we have two [Music] parents maybe I should always update no we get the [Music] same oh we got to get a different P path though [Music] oops [Music] so this is Neighbors [Music] Cur let's call it valid neighbors okay left right up [Music] down [Music] and then yeah cuz they're not valid neighbors right cuz you we so now so we're looking at the neighbors and we're saying that if the way you got here is left and the way you got there is if the way you got here is right and the way you got there is right um then you should not take the right neighbor right [Music] we I got this one wrong valed n let me see [Music] okay this one is just doing nothing okay maybe C parent of nothing Cur parent parent so how did you get from Cur parent to curb so if if the lines are the same um if the lines are the same so if so then get from X1 to X2 if it's right it's right otherwise it's left yeah okay so otherwise so let's just see X X1 = X2 so if you're in the same column then to get from y1 to Y 2 ah this one should be up if y1 is less than y 2 then I get from y1 to Y2 you go no it's down actually uh yeah it's down [Music] wait H let me just check [Music] uh a search that move the parent curve uh [Music] move a curve parent the parent curve is equal to curve import control. exception [Music] search and I want to I want to make sure that move Cur parent parent the D [Music] parent parent is equal to C parent valid n is apparent to too few arguments mhm [Music] mhm map why R is map move C res turn our oh they should be a list [Music] actually okay let's write it down valid n int comma int SS in comma in valid non exhaustive patterns in function from otherwise equals error from and then show P1 P2 P1 P2 okay and why is it calling that [Music] so there's no way to get from 01 to one 2 right okay uh so it must have written at some point why is it writing that it can [Music] go so all of them are really generated by this NS function right so I'm going to say let NS [Music] Prime over valid nice Cur and we just do this in [Music] thing D ding D what's the type of uh assert um I search okay um two TR show m c her parent ratio M Cur CB [Music] PE okay and then so I do Cur and Cur parent ah they should be Cur parents okay then these were the right directions okay so it's not so the direction thing is correct it's just that it's not good enough I think [Music] so the FR function is correct [Music] also and now [Music] if yeah so if you took the right you took the [Music] right I think I need to do one more layer maybe I just think it's the yeah I think it's one more layer okay let's do it again uh do [Music] MB let's call this one C PPP is read read array parent Cur parent parent do uh case MB CBP [Music] of nothing turn IB just CPP CPP is going to P PPP actually TPP and do and then we're going to do this whole thing let the parent the parent parent D PPP is equal to from [Music] Cur from um C PPP to curve parent and if the [Music] parent and CPP p p is equal to the the parent parent [Music] what's wrong with this whole thing I think it's just indentation right and the parent Cur is equal to DPP so they're all the same then we can't go right anymore DP [Music] H we're still getting 117 uh so if it is then we have to turn 90° we're not allowed to go back I think that might be the thing so let's see um then if D PPP is equal to [Music] um remember ITB is equal to left or D PPP is equal to right then filter inbounds or right up down [Music] else and then uh left right no I still [Music] get let me see okay it's not enough to just go and say like the list hey L Lenny it's going okay I guess and we got the breath for search implemented but we are still we got the dyra implemented but we're still working [Music] on we're still working on the the extra thing so see if I just return I be always so all the neighbors is valid then I get 79 right if I try and filter so that um let's see okay but it seems like I'm closer now so now it goes from goes to 01 first right and then 02 and then it goes to [Music] 03 okay and then it goes a 1 three 14 ooh some Indian candy super good it's called kajuk [Music] catly he's like cashew [Music] flow and ghee and sugar it's quite [Music] good [Music] let me printcess p on [Music] the that's to good sugar ghee cardamom and U cashew [Music] flour so the anim takes care of the um filter something is wrong here also so here it goes one step two steps three steps to the right so it was doing the right thing before cuz now it's just taking two step four steps in right wrong wrong yeah in the same direction so we have to remove this step the parent [Music] girl so there go 2 three 4 and then we change Direction four five 4 six so here we don't have any three more than three in one direction okay so here we go you know we went uh we go okay so we go down down so down and then right right down down right right down down right right m [Music] down down [Music] right [Music] if I make this a largest larger then I can oh yeah [Music] now a bit stuck actually again left right up down still right uh down left up let's just make it in that order and then it gives it a different response which is like okay that's not good and it goes um goes right it goes right we go right right down down [Music] oh wait sry we go uh right right down right right I I do think it's actually the other [Music] one cuz we're allowed to have uh right right [Music] right H MB CP read [Music] Ray array um parent parent parent case MB C PPP [Music] of nothing return I there the PPP of to the PPP from C PPP C uh sorry C [Music] PPP PPP um to curve parent parent parent parent the parent curve is equal to [Music] PPP then you have to turn okay we get 115 then it goes uh right right right okay it goes um right right right let's have this actually be m i [Music] it let me just change the bounds here so that it is um from one one to so just that it matches the uh lines here cuz there's no reason to have zero index rates okay so we go um one two a 1 3 14 and then it goes down to 2 4 and then 2 five No 2 four 2 five right 2 six to s and then it goes to 17 [Music] 18 18 um it went to 17 18 1 n 110 210 10 2 11 2 [Music] 12 now this is oh we went 110 so 210 okay then 21 [Music] 22 213 313 413 513 [Music] 52 so we we're we're having we're getting a similar kind of shape of path but [Music] not [Music] but we really shouldn't be getting a different okay yeah because it's uh it's not breath for searchy [Music] m [Music] okay if we don't have a parent then we can go anywhere if we do have a parent then we need to check if that one has a parent if that one has a parent then it's current parent parent and parent and none of them have say okay so then okay and they all the same direction then we have to turn and then we turn and if we were coming to the left or right then we have to take a 90° turn which means we have to go either up or [Music] down otherwise we're coming from up and down and we have to take a left or right right let's make this uh down up and this right [Music] left then it also changes the path again which is very [Music] annoying well that I that's what I don't understand why does it change the path I me obviously it selects a different path but it should be still they should still be equally [Music] short [Music] so if I got that's the shortest path to getting there right [Music] maybe I should [Music] um return in here return just and otherwise return nothing and let's say this is in comma in so I'll only return the ones that I found the shortest path to [Music] maybe so this is map maybe M no let's just map map MF MB NS May NS Prime and this is then cat maybe mbns Prime import data that maybe can't Maybe okay it doesn't change that [Music] one to just add the ones that we just [Music] saw [Music] maybe we're seeing nodes um twice that could also be it filter not do flip that. member and visit [Music] it uh but we [Music] already no we already take care of that by and whenever we look at the neighbors we filter if they're in the visited set um and they're never going to be they might maybe they're added [Music] twice but they're never like looked at if they see them [Music] again [Music] all right [Music] I think we always need to explore all of them and this is and the distance to the Target so do DT and then it is actually DT plus uh plus [Music] um so it's we read the distance to the Target and then we also want to read [Music] the Cur this the fre yeah okay [Music] so it is this so ma. read array [Music] X [Music] Plus uh ma read array but we need [Music] the are are bang Target so because we need to get to the Target and then we need to get a then we get out of the target [Music] mhm [Music] but so um maybe not so we we get the the target is in the path right okay and then this target go in it so then I'm just going to say uh reverse reconstruct path and let's see what happens if I just add together all the ones in the path a map r r do mang as let a links a race show M path TR show m p lengths mhm okay so we're getting the right pass length as well that's like that's not the case um [Music] so 4 one and then why does it choose the three and not the one let choose this as three and [Music] five and then four three and five and then four but why doesn't it choose one and five and four that doesn't make sense so it sees [Music] the H this is c d ahuh I think so this should not be curist I think this should be um h no okay it is uh so we read the array of X yeah okay this is the this is the length if we get there [Music] let me see uh what if I just reduce the example a bit let's see example me m okay oh this is not this is the [Music] wrong so here let me see I want to go um let's just do it like [Music] this and now let's print the example men here example M okay then it will goes um it goes 4 1 1 3 so it goes 4 1 3 5 and it should go 4 1 15 can we even delete this it goes 4 One Go 4 1 three 35 and it should go 41 one5 okay and that's just uh let's just see here Trace show M Cur ratio m n s okay then it looks at so the current one is 1 one the neighbors are one two one one neighbors are one two and 2 one and let's actually do Trace but let's just do um I show um just I can't do that because I can't show the discs um read array get ass Haw ma do okay I think I have to do do like this okay so okay uh so it's 1 one so we have 2 one and so one two two one and after I found it okay so then this one is zero that's true the distance to distance to one two is uh [Music] four okay then this is to 2 one is three yes okay that's correct so then I go to one two and its neighbors are uh his neers are 2 two and 2 1 three okay yes and then I get that the distance to 22 is six that's 2 + 4 plus yes and the distance to uh to uh 21 21 is uh let me see 2 one is three yes two on is three still okay from the distance to 2 two should be six and the distance to 13 is five so 4 + 1 okay then 1 three so there 1 4 and 2 three then 1 4 becomes 8 which is 5 plus okay and H two and and 2 3 is six okay so it goes 41 um okay so now it's it's correct right it's six okay so now it goes [Music] to it goes to 14 and that it's only is 24 and it finds out that the distance 24 is [Music] 13 okay 24 is 13 ah I think it's maybe just because I I finished the search too [Music] early then it goes 4115 okay I think maybe what does it say for the example now [Music] still says one two one maybe I need a um I probably need a priority Cube [Music] maybe I can uh so when I do Neighbors here I'm not going to so this is going to be list of income in and this Cas going to be like this so always want to select in the right order I think okay and the rest cat maybe mbns so this one is actually going to be it's just going to be it's not going to be map Maybe anything okay we're just going to have in Comm my int but we have also going to have the new distances oh my God so then this we write the parade parent and then we write the new distance let me say cist otherwise a otherwise we return and comma T dist and then we might see noes multiple times but with a different parent so then we just say NS Prime we add NS Prime here and we so we go the in it and it's going to have distance zero and now we are going to do sort on second we going to say sort on here [Music] we actually don't need to trace this [Music] much [Music] U maybe the maybe it's if it's so then now we can throw out the visit if it's visited um let's sort on second filter not do first not set me member [Music] visited do a oh this is actually visited it's not unvisited [Music] um [Music] so then we visited then we're getting there at the shortest path we don't want to go backwards okay let me just fix this so we don't want to have a visib we also want to remove all the we want to remove also the curve right think it might not be going twice into curve filter a not equal first curve not equal to curve [Music] I think we need to actually print out the um the lines cuz now it seems to be going 3 2 1 5 3 2 5 we not supposed to be going 4 1 [Music] 5 let's have this left down right up okay so now at least it doesn't change the out town okay so now at least it doesn't keep changing depending on what I write so four 115 has a path length of 11 3 215 also has a path length of 11 so those two are fine so it goes um three uh 3 2 1 so we should be getting 102 here but we are getting one we are getting 13 let me just make sure paste this again deep [Music] let's see uh 21 22 it would be very nice if I could actually let me see um so let's give me the PA and [Music] um [Music] weint the path what I want to do is I want to do the pars again except this time I'm not going to return Ray I'm just going to return I'm just going to return a list of list of int comma int comma int firsts two and I think it's just the r now let's say P2 is read file example return. pars to do lines now let's uh say here uh let P set equals set. from list path and then we're going to say uh map M map M um put s ln. f on P2 so let F equal so we're going to say here this is f coordinate value equals KC member set. member pet so let's just say if C is member of P set then we print X else we print a show [Music] V uh this is going to be completely messed up and cuz we don't want to put string Len put string and then we want to say [Music] lenis [Music] I think they should work okay so here we do get the path that we took 3 2 1 ah but then it goes okay it goes up and then it goes right four times let me see we're allowed to do that right so we go up and then we go right three times and go down and then we go right and we go one two three and then left down right one two three it seems to be a valid path at least but it's just not the shortest one [Music] so DB file equal do so this debug file f file [Music] file DB example [Music] m [Music] and then we want to debug okay what if I try and what if I just return IB here so I say return res I get a different shorter path right yeah so then I just go to the right and then [Music] down [Music] okay but I do want to return resz [Music] here [Music] I do less than equal to this it does do give something else uh Trace show [Music] um okay [Music] um but it turns one earlier so go right down right right right and it's 535 and it's instead it goes [Music] for after it may only turn left continue straight maybe there some other rule that I'm not [Music] m [Music] it's also just hard to kind of spot a wrong choice here let's [Music] see it should go so it goes uh 353 but could go 633 yeah let me see but here it goes um he plation stra for very long it can move most three blocks in single Direction before must 90° left or right can't end after em left continue straight or turn right and that's all taken care of with his visited right so you were never going back what does it say for the [Music] input and it certainly seems to be doing something for the input I'm going to just check this probably too high yeah I it's not like oh this one looks super silly right weint do the debug thing again um [Music] let's see so we have the path I am going to add 1.1 to the path full path okay and then I'm going to say um get de and I'm going to say X XY press is equal to um how to get how did I get from y to x x comma from YX um get d y as and then H get there um let P we D equals uh get the on reverse full path okay and [Music] um now I'm just going to write here so we're not going to derive show we're going to say instance show dear Weare show up is ital to the up Arrow this one show down is equal to V show left is equal to show right is equal [Music] to okay and then so here I'm going to say case a c map. bang uh um map. from list PV D of DSD we're going to say show D show V [Music] right so this is actually PV D and this is C right and get te ah okay and then get te we just keep the first [Music] element okay then we go down left it's not as nice actually let me see this is a different letter is it maybe it's just uh [Music] okay we certainly have the we got an nice debugging thing going on that's [Music] something I still wondering what to [Music] so we go right right down right right and then we go up a instead of going right and up we go up and right let's see down right right right so in instead of going [Music] uh so here we go up and right so we go it c three and two and instead we go three no we go up one earlier so instead of getting uh four and three so we get four and three [Music] whereas this path let me see so it gets 4 One okay one yeah and then it goes 5 4 five three but we go 5 4 43 we go uh [Music] um we go uh [Music] five so here here they're the same again right but maybe that's because now they can do three times here uh okay and we can't do that because we chose to go up earlier right and the problem here is that yeah there is a shorter path that um that still allows this so it's just this valid neighbors thing it's just uh it's not doing it's not what we [Music] want okay so it's it's a complication right we did we did dyra [Music] correctly but uh we're getting wrong path because there are shorter [Music] paths [Music] H I still want to see this on the input it's going to be nice with the updated [Music] version [Music] so we are too greedy in [Music] selecting in selecting The [Music] Neighbors [Music] maybe I can do something like um that the possible neighbors are always just so not just the ones that are right away but also the ones that are farther away so let's see um [Music] do do do do do do do Oscar Allen was yesterday like oh this is so easy uh but I'm not getting the complication right here let me see so um let's just uh start again okay uh let me get so so I'm going to just take more steps every time okay a valid neighbors so I'm going to take like three steps at a time we just uh get commit get add day 17 get commit um day 17 par day 17 not working just so that we have we have this code so now I'm going to make it so instead of giving the immediate instead of giving the immediate neighbors I'm going to say so the let me see take [Music] path let me see okay so um all paths so it's going to be um up down left right and we're going to make a combination of the [Music] these um so I think what we can do is we can do x y z and do um X colon Y colon Z colon like this and then we just do like this like up down left right up down left right oh and this needs to be a dollar [Music] now let me do here so this is these are this is all Paths of length three [Music] okay and now I'm going to do something different here I'm going to say um I'm going to say uh do okay okay I'm going to [Music] say and be Cur parent of something if we have a parent now we're going to say case and be current parent of nothing all pass okay [Music] so so we're going to say here map so moves is going to take a list of int in an in int and a list there I'm going to do int and moves it's just fold L uh [Music] Prime move [Music] oh I think okay [Music] maybe why not fold l a flip move so fold L has type oh [Music] could match type there okay it's again I am forgetting fold [Music] L yes H okay fold L and [Music] then do we have the list okay was just the fact [Music] that so we do uh moves for All path stret [Music] return moves H oh map moves [Music] curve let X um P NS equals uh no it's actually not like it's just map moves yeah so it's the final neighbor that [Music] we just CP let D CP equals from cp2 curve in so we just want to filter um so we if the current previous [Music] parent m [Music] I feel like I'm trying to do it [Music] again I'll just see let's just see what happens if I just [Music] to I just return like [Music] this okay so first I want to let me see do let so let me see we do um we have all paths so let me see F Cur nothing is equal to Cur F or D DS is equal [Music] to [Music] is equal to uh Cur applied to fds um but we are going to say f move move Cur d [Music] and this is going to be map uh [Music] F map a PS is equal to like [Music] this [Music] in filter inbound let just say inbounds p a [Music] p filter inbound do last filter all [Music] inbound [Music] PS ah this should not be in of [Music] course okay so I will have here not [Music] any so we don't want any of them visited okay so now let's figure out the path cost path cost int so we have a list of ins and uh we're going to give s the as ah thank you path cost XIs is equal to so we're going to do a map r r [Music] bang CS some [Music] okay um so we have all [Music] paths that are valid and let's just actually we want all of them to be in bounds and let's just say um case so let's just say MVP is read array parent curve case and we DP of just P then let dpals H from P curve a in R is equal [Music] to so we have to do this before [Music] actually so if there is nothing then we just do give all Paths of nothing map F curve all paths in a otherwise we we return map F Cur and then filter we're just going to say not DOT first equal D B so we're just going to remove all of the ones that take the same I think otherwise it would have shown up earlier okay now we have the all of the paths that are not and um now we have the so we look up the tentative of the last of all of these and the current is going to be um let DS curve is equal to map plus curve dist um okay so right so here we are not going to say read array X we are going to say we're going to say um yeah we does not let s Cur equals map and plus Cur dist as cost okay so now I have a cost of taking all these paths okay and now we are We Sip the NS here so let's make this actually an list and then we're going to map okay so here if if we find a shorter [Music] path [Music] so we do white array dists and then this is just going to be last [Music] of and we are going to say last event here and last event here but so here we took a [Music] path so then we are going to say [Music] um so F XY rest is equal [Music] to right array um so I'm going to reverse it actually parent and we're going to say y just and don't just just X cuz H okay yeah so an F [Music] of and if we're at the [Music] end no right so this is actually going to be X parent and Y and WR X is equal to right [Music] array okay so I'm going to write rep parent and then I'm going to f y [Music] rest uh but here and then here I'm just going to say right aray arent X just [Music] curve so now we are jumping three at a time error in Array [Music] index [Music] um ah and I have to do here filter all inbounds over this thing okay it didn't crash but it certainly did not do anything let see Trace show NS M NS just crashes right away [Music] mhm oh it's because I didn't actually write any parents down here um f [Music] and [Music] and I forgot to reverse [Music] here [Music] so they should all be in bounds and you cannot let me see uh filter ddop so we don't want like repeats that's messing things up here and let me see set that from list P length p is equal to set out size uh set up from l [Music] p doesn't [Music] work so these are all the combinations of all the paths of length three okay yes all paths [Music] three uh all paths to all paths one that's actually just like [Music] this all paths is equal to all paths one all paths two all paths three okay I'm going to I'm just going to cancel this okay return map F curve have Cur all [Music] paths [Music] so the parent of Y no I reversed it yeah [Music] okay it's strange right cuz it's it's looping infinitely but then it's not um let's [Music] see [Music] but then it just adds the empty list [Music] right traal M length rest M what is it looping on [Music] m [Music] ah this is not supposed to be curest I think no so it is supposed to be C so the one at the end of the past is in okay so it has to not so then this will just be empty right and this will just be empty uh maybe it's trying to reconstruct the paths Trace show M TD this target let's getting 99 which is exactly um this one plus the okay so no okay yeah so the um path to the Target is wrong I think there's like a loop in a path somewhere um so 99 is um it's exactly the length of the P so the so minus the last one [Music] right um tra show m [Music] p [Music] PR show MP okay uh so right array parent so somehow 113 became its own parent right and I think it's okay so we root to visit it and let's see uh this should maybe not be [Music] okay [Music] let me see so here we all the have all the possible [Music] paths so here we just return nothing okay and here we're just going to say um right array so the parent of Y is just X and we are going to [Music] say and I'm going to say um parent right array parent head and just C the first one should be hey um okay now at least I don't get [Music] the ah because I don't do recursion anymore f y all right okay I still get the we don't need we don't need these parents just not construct the past I think it's actually supposed to be this target um and plus the [Music] target [Music] so now I want to just say that it's extra 2D I want to say it's a this target plus r r bang Target [Music] so then we get the flight answer but this yeah this plus Target thing is just something I just made up right but let's see what we [Music] get [Music] don't want to Brint so much out [Music] actually okay it's not finishing for the [Music] input the one we did before was at least correct it was just it was just uh not doing the right number of paths like the right paths like like there were other options for [Music] paths okay let's just do get reset I want to grab this at least uh CU one was cool maybe get reset uh get check out day 17. HS can we back to this point where we got the wrong paths and it's because we're too greedy here right we always just say okay just [Music] okay it's been super long uh where we have dyra correct uh but we don't have we don't have the we don't we don't we're not doing the path correctly we don't have the right way the right um it's it's annoying right cuz we're doing part one and I think probably part two is not too hard or maybe yeah maybe it's just exactly the [Music] same m [Music] so I could also generate just all possible paths right um no that's crazy would make sense to generate all possible paths filter out legal valid pths and then um [Music] m that would at least get us part part one right if we just generate all paths but that's so stupid right and especially for the for the input it's not going to work hey a Felix we have the breath first search CED up we just uh you're too greedy with the paths so it doesn't work what if I um just go the other way [Music] around [Music] um [Music] and then we get an error in from and this one should be actually 13 13 so it doesn't crash let me see p length uh Trace show M uh [Music] some so here we get [Music] 106 so we're going to say um let is PL equal to to SPL is this and then we're just going to say um Trace show M SPL minus r r dot so we don't enter the m in it but our R do if we do enter the [Music] target [Music] 107 then we at least get this initial part part right now no because we go we go here no it's not we're still too greedy do you update the path if you find another way to a node following path can be chosen better or longer because A New Path does not have to reach the limit of three I I do update it right so it says here if the current this is less than a tentative this or equal to um then I update the [Music] path [Music] so it does do that but it's still [Music] uh still gives the wrong [Music] path maybe I should not filter visited here let me also not filter visited here I think they have will Loop yeah okay and yeah no we definitely don't want to visit yet visited here and is oh r and then filter not do set. member so you're only into visit it if we're like do you research the path after it or only update [Music] so I don't look at anyone I've found cuz the argument is that if I get somewhere that is the shortest valid path to get there right do you re search the path after it or only update the path to that no no I don't I don't research right cuz it's okay so what you're yeah so what you're saying is if I found a better path to a note then I should research that Noe NBN is let's try that um so I will not filter [Music] visited and let's see so now I found let's see um if and set that member visit it then Trace show m n I'll read turn let me see I mean so it's never the case that I [Music] hit that I found a new valid neighbor that I had not seen before right [Music] because you could come from a second direction to that node that with what allows you to choose a better path [Music] afterwards yeah [Music] but it's never the case right it's I like I I I never see a node [Music] again let me see why don't I ever see a note [Music] again I should be seeing them again right ding ding visited curst rerat [Music] curve so I get the distance to the current one let's do this here also [Music] yeah so it's often the case that I'm seeing again something that has a larger tentative distance m you just do it this way [Music] so there and if Cur mhm h [Music] m [Music] but I think the thing is that it uh cuz it uses the parent arrays and when it's checking this one [Music] right what is this 11339 I don't get it [Music] m [Music] make the three a four or five so which which three four and five [Music] H okay so you want me to okay let me copy this [Music] in [Music] so what is the answer supposed to be [Music] here [Music] sh so this one here is not included as an option because that would mean I would have to have come up [Music] here okay now I'm sorry I'm talking about my example the one in the Adent of code we're quite close [Music] though [Music] yeah I mean so I mean I know I know what the solution should be right so the problem is that the one here is not offered as a valid neighbor because we're coming from the left to it right but the problem is that we wouldn't be coming from the left to it if we had got gone right here and up right so that's the [Music] problem so we can I need just yeah so it's path dependent what the shortest shortest route there [Music] is [Music] m that's the thing right it's not like I'm suddenly going to come up to a point from some different route because I'm I'm not taking any different routes right I'm just going the shortest route always but so I but route I've chosen shortest routes to this point here is uh this path right this is the shortest valid one of the shortest valid PS okay so I guess I um let me see okay if it's like this uh C this is equal to T [Music] just two and then T show MN return and C just okay so these are the notes where there are two possible [Music] paths so then let me write change this parent list here [Music] empty let me see so right right away let me say um modify array parent and then and maybe that's St maybe I just have to do um [Music] here we had modify array and the array the index all [Music] right so now we're just going to reconstruct a [Music] pass uh now let me see PS so then we're going to say um [Music] okay um this is to to say that there are two multiple paths two paths to the parent um let me see so these [Music] are car [Music] parents okay um so the valid name so the possible paths here let me see and then we're going to say map M read array parent car [Music] parents C parent parent okay and this is going to be [Music] a list of list of inss so they so they have the possible [Music] parents okay and um for each of those parents we have the list of possible parents and [Music] then okay so this is just C parents so um let's see so the the the possible paths to curve is a c parent a P2 curve we're going to have here um so there's going to be reversed okay and a curve curve uh no sorry the curve parents is like this so here I'm going to have a zp with M no I'm just going to have map M and then a CP and I'm going to have reiterate the parent of that one [Music] so now this is the this is the list of paths um C parent parents this is the list of paths to [Music] curve me see okay so CP [Music] is uh I think I think I get it now okay so these are the possible paths to [Music] to curve and now curve parents parents I what I want to do is I want to take a c parent parents so all of the [Music] paths and this is a p okay what I want to do is I want to say here so read array of the last p and then we are going to do p concatenated to that [Music] right um so we take the last of the path no okay [Music] let see grace show her [Music] parents okay [Music] and let's see let's map cp2 uh curve [Music] CP [Music] oh so we're going to say um over this map so one of the parents we're going to say curve [Music] CP so now these are the paths to curve and now okay we want to do the same here so Cur parent parents so we're going to say [Music] um so map M so we have the a path here and we're going to read array apparent last p over um Cur parents [Music] um okay let me [Music] see so we we added the for each of the parents we found the last yeah and then we just [Music] um map to that I [Music] think okay [Music] wait so this is a path we find the rest of the path this is going to be the same as this one okay and [Music] then why can't I map like [Music] this what is this ah okay so for yeah so I'm going to add that to the this going to be the head and this is going to be [Music] T and then again no now it's too many car parents okay so we and [Music] then we conat map like this and then we do it again so these are all the possible paths to curve pass to curve care parents [Music] parents okay and then this is maybe has it's just going to be an empty [Music] list try show um let's you see what it is for [Music] the example okay then it's just an empty list good so now these are the paths to Cur so the uh these are the IBS okay and I'm just going to say h [Music] move uh map move [Music] curve okay so we have the ibas here so now I'm going to say uh all PA n is equal to um so path and new neighbor and we're going to do dollar and we're going to say h paths to Cur and we're going to do IB okay and this is going to be paths to Cur so we reversed it actually no yeah so car was at the end here and then this is just so this is going to be P and H poate paths okay and then I want to [Music] say filter is valid I'll pause n pads where um is valid uh what is valid is going to [Music] do it's first of all it's going to find the the the directions it took okay uh that's the similar that we did here is this gets [Music] function so is valid so an empty path empty path is [Music] valid so now let's see what the actual path is [Music] right um like left here left right left right so uh turns XY this is going to be XY X is is equal to um from how to get to X to Y uh turns y [Music] AIS [Music] okay so if I end up with something this is going to be you know from so the first one to the SE one yeah okay so this is fine so is valid p is equal to [Music] um is equal to case turns P of return um map last case turns P of um and then let's just say [Music] um x y s uh w x isal to Y is equal to set now let's just say turns P of a yeah okay XY s so they all have to be equal x y and x X = set and x [Music] = = w false [Music] and let me see I think and they should all be of length this link I think true error is valid uh I think I I I know I I know what is wrong right uh the problem is more how to implement that a ex okay [Music] um 110 [Music] m [Music] so if pass the Cur is [Music] empty if no pass to go then I be return I [Music] else [Music] we see and and C parents [Music] m okay and [Music] let see if any then return IB m H if not her parents or [Music] so these are all the paths 2 One X is case length x is less than four 1 3 2 3 2 4 [Music] h let just see if I just put contr here H but then it's saying that there like there is a valid path but we didn't take it [Music] m let me just see equals a group map links um well [Music] so it says 2333 1 3 2 3 3 3 and then um okay let me see [Music] from pressure curve trao Cur parents Trace [Music] show so I have 2 three and 3 [Music] three and then we have um so for 3 three we had two possible gr we have I think something is wrong TR M okay read okay and then read array parent [Music] C trce show why does it okay so it has two valid parents two parents okay so I should not make it here I should have this [Music] as nope something wrong with a conat map [Music] here [Music] okay I think I just need to conat [Music] here I was conting at the wrong level I think [Music] you want to one one parent C Okay traa C parents parents okay this is C and then parent C her [Music] parents if null C parents or any null C parents parents or n no par care or no Cur parents parents so 4 three and so 43 we could have either come [Music] from we could have either come from 33 or 42 okay so that's three three or 42 43 okay and then it's either uh then it's 23 33 43 that's valid um I think I did it again here concat and again it's if null pass the car turn IB then else do let me see 4 43 something interesting right so for 2 two so now we're looking at um 2 three so the parents of two three are either it's either 1 three or 2 two cuz it would have been four + [Music] 1 uh I think if it's [Music] less uh okay if it's less then it's just [Music] C and then it's just um right array curve okay [Music] if I find another path then I do the n [Music] curve so for 11 to 125 this parents 115 and 124 and I could have come from [Music] 115 or 124 so apparently I could have come from 114 then 115 or 114 12 4 or 12 3 [Music] 124 oh [Music] okay [Music] mhm less than [Music] three okay I guess maybe I'm not I need to try show again here I [Music] think tra show [Music] M path to curve and then TR show um All Pause na path and then this should be okay this is lesson L to four okay cuz they should not all be the [Music] same this me nu. [Music] sort import that from dat [Music] list okay so these are the possible paths let see if I say less than three here then [Music] there's then should never be more than two right yeah maybe because there is a possible path that [Music] ding dinging ding [Music] d [Music] oh my God there is uh there is an [Music] eruption uh in Iceland not bad [Music] hey [Music] wow and it is uh Not underneath the town which is great means that the town should be fine for a bit well meanwhile I'm doing adid of code okay so what I think is happening here is I now I'm riding all the possible [Music] paths um but I should like fix5 said I should um I [Music] should let me [Music] see C parents C parents par R yes [Music] good [Music] so that when I do um when I do make a [Music] choice I think I should just return here [Music] um I do return map [Music] last let me just remove this all these tracing if now no okay then there's [Music] nothing let me rewrite this valid [Music] pads they can int comma int s s in Comm in and then we here we return maybe with the [Music] paths may we will do this let I be a valid paths equals do and valid nay so here we [Music] turn nothing here we return nothing and here we return just okay uh but we do so we will just recalculate this and say valid BPS is a a valid paths Cur case VPS of just PS uh then we return map last PS nothing return [Music] IB then turn nothing then turn nothing okay so basically what I have to do here and is [Music] um I have to if I if I got there by A New Path I have to say um what does it say now but we're still getting 110 and it's still not selecting that one [Music] there [Music] so the thing is basically that if I if I chose one of the paths to get there [Music] um so let me see here this is NS so okay so here I'm basically saying Okay found a shorter path then I'm going to do [Music] um uh VPS is um valid paths curve and I'm going to say um a VPS up nothing then we just write this parent if I I have some paths then I have to say uh let RPS equals filter uh is equal to n blast of PS and then we have the New Path and then we want to say um f XY XIs equal to right array parent X parent X the parent of Y is just going to be X and then FY AIS and then finally F of Y is equal to so this will be n right array parent [Music] why right array parent [Music] yes and then F RPS [Music] map and [Music] um why am I [Music] getting so I'm doing the valid neighbors and then I filter all is [Music] valid and then I can just do [Music] map just [Music] empty right array parent inur otherwise it's [Music] RPS it's going to be one right in F RPS so how can I have a I have the valid [Music] paths and I add the end to the end of [Music] it and then I [Music] filter okay and [Music] then [Music] tutu [Music] re uh okay the pass [Music] what so you have valid neighbors curve and it was a [Music] just [Music] this should be G [Music] really [Music] 1 one one 2 1 3 [Music] 2322 [Music] mhm so here there are two valid paths are through one one or one [Music] two 233 okay which is to be expected right right but I found right but if they are the same length uh then I really should not I should not change them right [Music] okay but [Music] um [Music] because it might have changed the set of valid paths [Music] right [Music] I see okay so I have to just do here um RPS and then here I write I don't write a r parent so first first I actually so let me see so clear um clear uh X XIs right is equal to right R parent X empty clear axis and then I want to fil them again I do um I do this not dot sort sort dot [Music] x lab. sort. x so we are going to say here do clear map and clear RPS so first clear all of them and then we up the all [Music] and this is going to be Cur but it doesn't like this because it should be modified [Music] array and 113 [Music] and if there are no valy passes just because I'm in that in that uh easy [Music] case okay I clear all of them and now I'm writing a parent ah no the parent why [Music] tra show M um I shouldn't clear the map [Music] clear [Music] tail okay I did the clear but now it's still giving me same wrong [Music] path [Music] valid paths let me see ra show M BS [Music] maybe we should um [Music] ch [Music] m [Music] okay tra show M and then have links F I have it here uh P length let me see ra show m RPS come on [Music] map [Music] okay so there are shorter paths the two of them might be valid but uh there are shorter [Music] paths um [Music] let me see here reconstruct P [Music] um [Music] pause okay and then I'm going to setad of reconstructing this I'm going to say [Music] um I should really just be keeping the the last one [Music] right so after I've seen all of [Music] them what does it say at the dist the target is as it's the same actually ding [Music] ding [Music] I still feel that we should be getting closer here so we whenever we find A New Path right we clear the Old Paths we just write the New Paths so for some of them there are two valid pads [Music] let me see um what if I reverse [Music] these still get the [Music] same [Music] okay now I finally selected the right one and I'm getting a length of 95 which is the S minus the Target right so now let's see if I want to reconstruct the path okay it seems like clear then I clear too much right clear dot tail of head [Music] all I have seen so but once I I think I once I visit a note then I need to finalize the path to which okay and so then I [Music] do let me see um finalizer let's [Music] do uh but the paths the pass I take next depend on the current path [Music] to Cur right up the RPS let me just see what happens okay um this target minus r r bang [Music] Target then I get the right answer here and let me just do it for the [Music] input and I get preload Mt list what does it mean for valid paths so there's no valid next ones [Music] what does that mean then okay so I'm having I'm looking at 15 comma 2 ah yeah okay now this is sorry this is the input so 15 comm2 is perfectly valid um now if I [Music] have tro and then n and NS what is the NS [Music] then [Music] so CU V valid pads Cur and I map last PS [Music] right do Trace show [Music] um [Music] he [Music] what I don't understand how can this be how can I have a neighbors and I I'm getting so the valid neighbors is the valley path of C okay and then I do it again and I'm getting different results uh [Music] okay so because in the meantime the paths have been filtered out because I updated them so like the [Music] two two are interfering t I'm going to try this guess but yeah okay I had an even a better guess before [Music] let's just remove [Music] this 1035 one left guess to wait five more seconds we guess 1036 we're still too high and it's also giving the wrong on the [Music] example given the wrong and it's because it doesn't pick this path even though now it like has the option to do that right let me see and uh get assw um parent tra show [Music] M so one six this is 110 reach 110 is 1 n it's the one wa reach 34 there are two ways h you come from 2 4 or 33 so if you get the pause let me see we do um map reconstruct [Music] path [Music] pause map and reconstruct construct [Music] path these are going to be many path reconstruct path uh taking in comma int and STS in comma int so two ends let's see um so this is going to be a list of list of things and we're going to say map we're going to be doing the same thing as here I [Music] think let's see [Music] um so Con cat map m p map T [Music] DP over reconstruct path [Music] um [Music] me see I think I what I do is so I do um I do map and reconstruct path [Music] pause so PR [Music] Prime it's going to be a list of list of lists Okay so so for all of these lists I'm going to do map there going to be list of lists map [Music] curve [Music] um okay find still paths but they are both the [Music] same [Music] paths so and then F here is um path we're just going to make it to all the work plus PVD there is this is actually going to be taking the path as [Music] uh and now we are going to say um [Music] and now we see that there are multiple [Music] paths and they [Music] differ but they just go slightly differently here but it's not allowing the other [Music] one [Music] put [Music] what maybe I should just always modify the [Music] parent [Music] unless I find a shorter path I modify [Music] so here I'm just always adding parents [Music] we see Trace show M Cur is it just looping uh maybe train is show um this target I get [Music] 78 okay n of this clearing business I do get um so then I get so then I always get all the valid paths to a node [Music] let me see so this is the same as when I had the when I didn't do any of the [Music] filtering [Music] let me see these are the valid paths for all of them okay so one one can be reach by one two and two [Music] one [Music] m [Music] this could actually be the stupid um stupid way to do it right so here we get all the paths [Music] and then we can just um show the minimum path [Music] length [Music] like it's not even working for the example right [Music] and it's going to give us the shortest path which is the distance the problem is that [Music] um this one here 1 n it says it can only be reached by 29 [Music] but should also be able to be reached by 18 [Music] right and why is it doing that wrong it's because so one two can be R by one one one [Music] okay me just [Music] see [Music] um okay so the problem is that we go to this three four so this three here um can be reached by going up like this this three should be reachable from so 17 should be reachable from 16 16 and 27 so [Music] 16 six hey Chris I've been coding now for too long 6 hours but I'm not making it's not happening so 16 should be reachable from so it's saying 16 is reachable from 15 but 16 should also be reachable from 2 six what is it saying about 2 six 26 is reible by 25 [Music] wow follow what I am [Music] so now we get a one six is reachable by 15 17 and 2 six okay [Music] um filter not do flip set. member visited. [Music] last [Music] now I seeing 102 96 it's saying if I add the parents and I filter the [Music] visited the paths are all [Music] wrong [Music] m [Music] okay it generates a lot of path at least some of them have [Music] the right [Music] length [Music] just going to show the shortest [Music] path it's almost there but it does allow this um uh multi- group thing [Music] right [Music] feelings I went to a university of Iceland and then I went to Charmers which is good tra uh let me see we're not interested in this let me see um sorted is equal to uh sort on P length paths so we do head sort it and then we do [Music] um Trace show M map healing sorted okay so here we are getting the right [Music] PA Trace show MP p length head sort [Music] it okay at least it finishes for the example it's currently going to be crazy slow for the input but let's let it run [Music] to [Music] yeah it's missing one put string at the end and to show the bottom [Music] one now it's basically just creating all the paths and [Music] um [Music] let me try make it a bit faster [Music] a we can say here pass two [Music] and I'm going to say here um filter is valid [Music] paths I need to do it a bit later then I can kind of throw out um invalid pass right away let me see did this make make things slower actually [Music] let's see [Music] h [Music] de ah let's [Music] see [Music] m okay this is not going to finish anytime soon so I mean at least we're getting the right answer now for the example um we are doing it super slowly um we could probably do it in a better way H we have D just algorithm coded up but we just not able to kind of make it take all the valid paths in a nice way so I'm going to call it a day for now I've been streaming for like 6 hours or something H I'm going to let this finish call it a day and uh yeah keep trying tomorrow but o this is a difficult one I I don't know why everyone's saying like oh it was so easy I something I'm not some way I'm recording it is that I'm not I'm not able to make it work all right but uh thanks for tuning in sorry for how extremely long this was and uh see you tomorrow where we can hopefully finish this all right bye-bye [Music]