Zadanie z dnia 21 mocno przycisnęło mnie do muru, wrzucam rozwiązanie z opóźnieniem, gdyż zajęło mi ono więcej czasu niż chciałbym przyznać.

Zadanie

Treść zadania jest dosyć skomplikowana, mamy keypad zawierający cyrfy od 0 do 9 oraz przycisk A do akceptowania danej cyfry. Wygląda to tak:

+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
    | 0 | A |
    +---+---+

Nie możemy jednak bezpośrednio wpisywać nic na tym keypadzie, musi to wykonać robot, którym sterujemy za pomocą takiego keypada:

    +---+---+
    | ^ | A |
+---+---+---+
| < | v | > |
+---+---+---+

Każde wciśnięcie przycisku przycisku przesuwa ramie robota w odpowiednią stronę na keypadzie, żeby zaakceptować ruch wciskamy A.

Jednak zadanie się tu nie kończy, okazuje się że do sterowania keypadem z kierunkami musimy użyć jeszcze innego robota z takim samem keypadem (ze strzałkami i A), z kolei tym robotem także steruje kolejny robot z takim samym keypadem, do którego mamy już dostęp.

W skrócie możemy naciskać przyciski keypada który steruje ramieniem robota nr 1 po keypadzie służącym do tego by sterować robotem 2, który steruje po keypadzie robota nr 3, który naciska przyciski na keypadzie z cyframi…

Naszym zadaniem jest policzyć ile razy musimy nacisnąć przyciski na keypadzie pierwszym by wpisać podane hasła na keypadzie z cyframi.

Jako że rozwiązanie opisuję już po rozwiązaniu obu części mogę wyjątkowow zaspojlerować o co będzie chodzić w drugiej części zadania. Wtedy trzeba będzie rozważać sytuację w której pomiędzy naszym keypadem a keypadem z cyframi znajduje się 25 innych keypadów ze strzałkami sterowanych przez roboty.

Napiszę więc od razu kod który generalizuje się do drugiego rozwiązania.

Rozwiązanie

Możemy spróbować wymodelować zadanie jako funkcję rekurencyjną, pozwoli nam to łatwiej rozumować na temat tego co się tam dzieje:

def cost(start, end, level=25):
    i1, j1 = start
    i2, j2 = end
    if level == 0:
        return abs(i1 - i2) + abs(j1 - j2) + 1

    # BFS by znaleźć wszystkie najkrótsze ścieżki od `start` do `end`
    queue = [(i1, j1, [])]
    visited = set()
    paths = []
    while queue:
        i1, j1, moves = queue.pop(0)
        visited.add((i1, j1))
        if (i1, j1) == (i2, j2):
            paths.append(moves)  # dodajemy gotową ścieżkę do listy

        for move, i, j in neighbors(i1, j1, level):
            if (i, j) in visited:
                continue
            queue.append((i, j, moves.copy() + [move]))

    # Dla każdej ścieżki liczymy ile kliknięć będzie kosztować wyklikanie
    # jej przez robota na niższym poziomie
    costs = []
    for path in paths:
        length = 0
        # robot niższego poziomu zawsze zaczyna i kończy na A
        for a, b in pairwise(["A"] + path + ["A"]):
            length += cost(ARROW_PAD[a], ARROW_PAD[b], level - 1)
        costs.append(length)
    return min(costs)

Kod wystarczy by rozwiązać część pierwszą, druga wymaga jeszcze dodanie dekoratora functools.cache, poniżej załączam cały kod rozwiązujący część drugą:

import sys
from functools import cache
from itertools import pairwise

ARROW_KEYPAD = [" ^A", "<v>"]
NUMBER_KEYPAD = ["789", "456", "123", " 0A"]
ARROW_PAD = {"<": (1, 0), "v": (1, 1), ">": (1, 2), "^": (0, 1), "A": (0, 2)}
NUM_PAD = {
    "7": (0, 0),
    "8": (0, 1),
    "9": (0, 2),
    "4": (1, 0),
    "5": (1, 1),
    "6": (1, 2),
    "1": (2, 0),
    "2": (2, 1),
    "3": (2, 2),
    "0": (3, 1),
    "A": (3, 2),
}

pads = [ARROW_KEYPAD] * 25 + [NUMBER_KEYPAD]

MOVES = {
    "^": (-1, 0),
    "<": (0, -1),
    "v": (1, 0),
    ">": (0, 1),
}


def neighbors(i, j, r):
    p = pads[r]
    for move, (di, dj) in MOVES.items():
        ni, nj = i + di, j + dj
        if ni < 0 or nj < 0 or ni >= len(p) or nj >= len(p[0]) or p[ni][nj] == " ":
            continue
        yield move, ni, nj


@cache
def cost(start, end, level):
    i1, j1 = start
    i2, j2 = end
    if level == 0:
        return abs(i1 - i2) + abs(j1 - j2) + 1

    queue = [(i1, j1, [])]
    visited = set()
    paths = []
    while queue:
        i1, j1, moves = queue.pop(0)
        visited.add((i1, j1))
        if (i1, j1) == (i2, j2):
            paths.append(moves)

        for move, i, j in neighbors(i1, j1, level):
            if (i, j) in visited:
                continue
            queue.append((i, j, moves.copy() + [move]))

    costs = []
    for path in paths:
        length = 0
        for a, b in pairwise(["A"] + path + ["A"]):
            length += cost(ARROW_PAD[a], ARROW_PAD[b], level - 1)
        costs.append(length)
    return min(costs)


if __name__ == "__main__":
    part2 = 0
    for line in sys.stdin.readlines():
        code = line.strip()
        res = 0
        for a, b in pairwise("A" + code):
            num_moves = cost(NUM_PAD[a], NUM_PAD[b], 25)
            res += num_moves
        part2 += res * int(code[:-1])
    print(part2)

Dla pierwszej części jedyne zmiany jakie musimy zrobić to ilość arrow padów w zmiennej pads oraz zmiana wartości level w wywołaniu funkcji cost na 2.

Podsumowanie

Zadanie dało w kość ale było bardzo ciekawe, praktycznie niemożliwe jest rozwiązać go nie rozpisując sobie tego na kartce, a nawet wtedy trzeba się mocno skupić by nie popełnić błędów lub skrótów myślowych, jednak ostatecznie rozwiązanie wyszło całkiem eleganckie.