Advent of Code - adventofcode.com

You are reading a single comment by @frankenbike and its replies. Click here to read the full conversation.

•

frankenbike
My solutions:
1. Loop over 10×10×21×21 array. I killed it after it hadn't even found the start state after one second as the array is so sparse. Not a good way to go.
2. Hash the state instead: 47s.
3. Hash the state, calculate next states in a function, cache that function: basically the same as above.
4. Recursive calls from a state until all games are won, and caching: 0.18s.
Quite disappointed that my first instinct was so far off optimal.

•

wence in reply to @frankenbike

Nearly caught up (still day 19 to do), but here was my part2 for today (~55ms)

from functools import cache
def part2(inp):
    p1, p2 = inp
    p1 -= 1
    p2 -= 1

    moves = list(Counter(map(sum, product(*repeat(range(1, 4), 3)))).items())

    @cache
    def winners(A, B, s1, s2):
        if s1 >= 21:
            return (1, 0)
        if s2 >= 21:
            return (0, 1)
        winA = 0
        winB = 0
        for move, freq in moves:
            newA = (A + move) % 10
            news1 = s1 + newA + 1
            x, y = winners(B, newA, s2, news1)
            winA += y * freq
            winB += x * freq
        return (winA, winB)

    return max(winners(p1, p2, 0, 0))

Advent of Code - adventofcode.com

About

LFGSS