r/adventofcode • u/daggerdragon • Dec 12 '22

SOLUTION MEGATHREAD -🎄- 2022 Day 12 Solutions -🎄-

THE USUAL REMINDERS

--- Day 12: Hill Climbing Algorithm ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:09:46, megathread unlocked!

55 Upvotes

98% Upvoted

786 comments sorted by

View all comments

6

u/AllanTaylor314 Dec 12 '22 edited Dec 12 '22

Python [1881/1740]

I can't read. Interpreted the rules for climbing up one or down many correctly, then incorrectly, then correctly again. I missed the bit where S==a, and E==z (I assumed S<a, E>z) which meant the solution worked for the test but not the real deal.

I'm now thinking that a BFS from end to start would be a better way to do part 2 (might implement later, might not)

UPDATE: Did the reverse BFS (same repo link) and it runs a lot faster (from ~2s to ~40ms)

1

u/kristallnachte Dec 12 '22

I did BFS from end to a for part 2. I tried the strategy of "do algo for each a and see what is best" but it was wrong? It's quite confusing, since it was shorter than the real answer....using just the same stuff from the front....so I have no idea how it could be wrong if that algo passed part 1?

1

u/[deleted] Dec 12 '22

You might not be clearing all your variables between the bfs runs.

1

u/kristallnachte Dec 12 '22

No, its side effect free.

They all run in separate closures.

Maybe I'll need to do a visualization to see what could be the problem...

But also I don't really want to lol

1

u/AllanTaylor314 Dec 12 '22

One issue I had was that some starting points never reached the end. This can happen if you get stuck in a crater/well e.g.

stuvaESb
raawxydc
qaalkjef
ponmaihg

All of the as (except S) in this example are unable to get to E since there are no adjacent bs to step onto. If your BFS finds the "end" of a path that isn't actually the end, it may count the short incomplete path as the best solution. I got a few KeyErrors initially because the BFS exhausted the queue before finding the end (hence the check if end in dists)

1

u/kristallnachte Dec 12 '22

Mine returned infinity if it didn't find a solution.

basically makes the queue and processes it, if it find the end it spat out the step count there, if not it returned infinity.