Advent of Code, día 22

Requisitos, requisitos y más requisitos

https://adventofcode.com/2020/day/22

En este puzzle, la mayor dificultad es leer bien todos los requisitos e implementarlos con exactitud, sin olvidarse ninguno. Que no es poco. Parece mentira lo difícil que es leer unas instrucciones detalladas y seguirlas al pie de la letra.

Parte 1

Implementada con ayuda de un par de deques. Una deque es una lista implementada de forma que es igualmente eficiente (O(1)) añadir o quitar elementos de ambos extremos.

def solve(input):
    players = [None]
    for player_cards in input.strip().split('\n\n'):
        cards = deque(
            int(card) 
            for card in player_cards.strip().split('\n')[1:]
        )
        players.append(cards)

    while players[1] and players[2]:
        p1_card = players[1].popleft()
        p2_card = players[2].popleft()
        if p1_card > p2_card:
            players[1].extend([p1_card, p2_card])
        else:
            players[2].extend([p2_card, p1_card])

    return sum(
        (i+1) * card 
        for i, card in enumerate(reversed(players[1] or players[2]))
    )

Parte 2

La parte 2 complica las reglas con combates recursivos. La clave para resolver esta parte ha sido salpicar el código con print()s para reproducir exactamente la secuencia del ejemplo. Usando una herramienta de diff he podido detectar un par de reglas no implementadas correctamente y en unas pocas iteraciones obtener la solución correcta.

El código completo con todos los prints, se puede ver aquí.

Esta es la función recursiva:

def recursive_combat(player1_cards, player2_cards):
    seen_games = set()
    turn = 1
    while player1_cards and player2_cards:
        round = (tuple(player1_cards), tuple(player2_cards))
        if round in seen_games:
            return True  # player 1 wins
        seen_games.add(round)

        p1_card = player1_cards.popleft()
        p2_card = player2_cards.popleft()

        p1_won = None
        if len(player1_cards) >= p1_card and \
           len(player2_cards) >= p2_card:
            p1_won = recursive_combat(
                deque(islice(player1_cards, 0, p1_card)),
                deque(islice(player2_cards, 0, p2_card)),
            )

        if p1_won or p1_won is None and p1_card > p2_card:
            player1_cards.extend([p1_card, p2_card])
        else:
            player2_cards.extend([p2_card, p1_card])

        turn += 1

    p1_won = len(player1_cards) > len(player2_cards)
    return p1_won

Y este es el cuerpo principal que hace la primera llamada recursiva y calcula la respuesta al final:

def solve(input):
    players = [None]
    for player_cards in input.strip().split('\n\n'):
        cards = deque(
            int(card) 
            for card in player_cards.strip().split('\n')[1:]
        )
        players.append(cards)

    recursive_combat(players[1], players[2])

    return sum(
        (i + 1) * card 
        for i, card in enumerate(reversed(players[1] or players[2]))
    )

Un código sin grandes complicaciones algorítmicas pero lleno de trampas y detalles en los que caer.

El código completo aquí: https://github.com/jabadia/adventOfCode2020/tree/main/d22