eternal pulsar
https://adventofcode.com/2021/day/23
has anyone else done this problem
my solution takes about a minute to run and literally just checks every possible move (which is a manageable amount)
I was wondering if anyone had some insight on this problem and how they'd approach problems similar to these (i.e. optimal moves when you have very little freedom)
hazy fox
usually when you have optimizations like these its just dynamic programming
this one looks complicated tho
i mean, you could frame it as a cheapest path problem where nodes are room states and edges are transitions w/ total energy cost and do a heuristic search
what do you think @eternal pulsar
eternal pulsar
yeah that's a pretty good idea
you just eliminate visiting a ton of useless states
I googled this problem a while ago and that was generally thought to be the best solution
hazy fox
oh pog i had a good idea
eternal pulsar
also there's only 4^8 possible starting states so you can just find the optimal path for all of them and have an O(1) solution ezclap
hazy fox
well actually you only need https://en.wikipedia.org/wiki/Bellman–Ford_algorithm
since its just the one state
wait all the costs are positive so you might as well just dijkstra's it
hazy fox
bellman ford is if the edges can be negative
johnson's is for when you want all pairs of shortest paths
hazy fox
neat
hazy fox
maybe you can try A*
eternal pulsar
yeah reddit says a* performs even better
hazy fox
i learned all this in my (classical) AI CS course btw 
eternal pulsar
dijkstras doesn't work as well cause you want to move the D's out of the way first but that ends up being the last thing dijkstras checks
an adding a heuristic to it corrects that
eternal pulsar
i gave up
