Discussion on: Advent of Code 2020 Solution Megathread - Day 23: Crab Cups

View post

A bit of linked list action in python. This can be optimized further because the dict only contains continuous numbers (other than 0) so we shouldn't need: a dict whose key is the cup value, and where each entry is a node containing the next cup. Instead we can have a list whose index is the cup value and where each entry contains the next cup. The two are basically equivalent, but the list is faster.

from functools import reduce

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

    def gen(self, count):
        cur = self
        for _ in range(count):
            yield cur
            cur = cur.next

class CupsGame:
    def __init__(self, data):
        self.min_cup = min(data)
        self.max_cup = max(data)
        self.cups = {value: Node(value) for value in data}

        def link(prev, cup):
            prev.next = cup
            return cup

        last_cup = reduce(link, self.cups.values())
        self.current = last_cup.next = self.cups[data[0]]

    def run(self, count):
        for _ in range(count):
            *pickup, self.current.next = self.current.gen(5)

            try_value = self.current.value
            while self.cups[try_value] in pickup:
                try_value -= 1
                if try_value < self.min_cup:
                    try_value = self.max_cup

            destination = self.cups[try_value]
            pickup[-1].next = destination.next
            destination.next = pickup[1]

            self.current = self.current.next

    def output(self, value, count):
        return (cup.value for cup in self.cups[value].next.gen(count))

raw = "872495136"
data = list(map(int, raw))

game = CupsGame(data)
game.run(100)
print("output", "".join(map(str, game.output(1, 8))))

data = list(map(int, raw)) + list(range(10, 1000001))
game = CupsGame(data)
game.run(10000000)
cup_a, cup_b = game.output(1, 2)
print("prod", cup_a*cup_b)