2021 advent of code - day 15 solutions

hello and welcome to another day of advent of code this is day 15. and in day 15 we have a cost graph oops sorry about that uh and oh there's the follow notification and the cost graph looks something like this um the goal of the problem is to make a path from the input which is in the top left to the bottom right and each node represents or each number in this represents a cost for that particular node uh now some tricky things that you know you wouldn't get out of the mirror you would get out of the reading if you read closely the input is not counted or the the top left is not counted so don't add this one or whatever number it is in your input to your cost and then the answer is the cost that it takes to get to whatever path that you take to get down to here and for this there is an algorithm that is optimal for computing this which is called dijkstra's algorithm um i have implemented this at some point did not remember it off the top of my head and independently derived something very similar to it so my solution here is is not exactly dijkstra's but you could just you know implement dijkstra's algorithm um so i guess the important things that i wanted to cover for this at least for part one uh we will cover a little bit more for part two for this grid expansion though it's not that complicated um my parsing is basically the same parsing that i've done for any of the other coordinates problems where i produce coordinates at x y by parsing in this case i keep track of the max values so that i know where i need to end and then i use an interesting module called heap cube so what heap cue is oh actually this code is buggy this is supposed to use heapq.push wait why does this work [Laughter] uh this is not supposed to work as written this is supposed to use heap q dot heap push uh i guess i am getting lucky currently or oh weird anyway so what um what heap cue does is it creates a priority queue here uh and so then you use a priority cue based on the cost of your current path and that will allow you to optimally find the route to the finish wait why does this work that's weird anyway i'll look into that after i finish the recording uh but yeah there's nothing you know terribly complicated about this part two is much of the same you are still doing the routing however it takes all of these grids down here and it expands them out to a 5x5 grid so it's much much larger and the math for that is is each of these numbers will have its same number in the next position but add one for every movement that you make so like the square directly to the right of this will have plus one this will have plus two if you go over one and down one that'll be plus one plus two uh and it has a special wrap around rule in the wrap around here 10 becomes 1 so it's not quite a mod which is why i wrote this special little function that does essentially that wrap around and this is how i plotted each of those so basically same loop for for parsing the input values but i also parse an additional offset by five here and i compute the width and the height beforehand they happen to be squares in all of the given inputs so you could just compute one of them and use that value there and then i use these inner five loops to offset by the height and the width and add how far i've moved and do that weird mod thingy so this is kind of the only difference between part one and part two anyway hopefully you found this useful and i'll see you around for the next day you

Channel: anthonywritescode

Views: 127

Keywords:

Id: 8_9I6fNR7Z8

Length: 4min 22sec (262 seconds)

Published: Wed Dec 15 2021