Ancestors

Toot

Written by Walker Boh🛡 on 2024-12-21 at 16:32

Day 21 #adventofcode in the books.

Part 1 was to figure out the minimum move sequence to input a code on keypad, with the wrinkle being there were three other keypads above it before the movement was applied to the final keypad.

I wrote a BFS pathfinder for the keypads and then used it to derive all of the minimum paths and use that to find the min length on the first keypad.

Except it would have taken 10 hours to complete. By this point it was headed for 2am and I decided to take the slot machine route and write a bogo function (IE choose a random code at each level and just try that to see if you get lucky). Yeah thats when I knew it was time to pack it in for the night.

Epiphanies I had in the shower this morning:

1. Its basically a weird movement factorial. Factorials respond well to being memoized. So I memoized it.

2. BFS pathfinding on the keypad was massive overkill. You could reduce it to simple linear combinations of x and y movements.

After a complete rewrite taking those into account it finished in milliseconds.

Part 2 took it to stupid levels by making it 25 levels deep. But as luck would have it the way I rewrote my code made this an easy extension.

The only wrinkle here was the sheer size of the number it returned needed a bigint.

Don't know that #typescript was the best for this one, would probably have been easier in #python

=> View attached media

=> More informations about this toot | More toots from walkerb@infosec.exchange

Descendants

Written by Sawmurai on 2024-12-21 at 16:42

@walkerb I got lucky and my number into a regular number type. Apart from that my attempt had a similar evolution. Took me way longer than the final code would suggest 😂

=> More informations about this toot | More toots from Sawmurai@fosstodon.org

Written by Walker Boh🛡 on 2024-12-22 at 01:09

@Sawmurai yeah this one was long for me too. Late in the competition I'm always wary of them pushing ints high.

=> More informations about this toot | More toots from walkerb@infosec.exchange