Solving the "magnet" puzzle from Machinarium

magnet.py

"""Solving Machinarium's magnet puzzle with graph traversal."""

import re


def status_check(status: str) -> bool:
    """Check if the status is valid or not

    The status of the board has items of 'D' for down pointing
    arrow, 'U' for up pointing arrow, and 0 for the gap. There
    are exactly 3 'D's, 3 'U's, and 1 '0' in the status.

    Return True if the status is valid, False otherwise.
    """
    return (
        len(status) == 7
        and status.count("D") == 3
        and status.count("U") == 3
        and status.count("0") == 1
    )


def valid_moves(status: str) -> list[str]:
    """Find all the valid moves for the puzzle's status

    The status of the board has items of 'D' for down pointing
    arrow, 'U' for up pointing arrow, and 0 for the gap. There
    are exactly 3 'D's, 3 'U's, and 1 '0' in the status.

    Return all the valid new moves from the current status.
    """

    if not (status_check(status)):
        raise ValueError("Invalid status: " + status)

    valid_moves: set[str] = set()

    # The patterns of what transforms into what:
    patterns: dict[str, str] = {"0U": "U0", "D0": "0D", "0DU": "UD0", "DU0": "0UD"}

    for pattern in patterns:
        matches = [pos.start() for pos in re.finditer(pattern, status)]
        valid_moves.update(
            [
                status[:i] + patterns[pattern] + status[i + len(pattern) :]
                for i in matches
            ]
        )

    return list(valid_moves)


def find_path(
    graph: dict[str, list[str]], start: str, end: str, path: list[str]
) -> list[str]:
    path = path + [start]

    if start == end:
        # We've found our goal
        return path

    # Populate the graph
    if start not in graph:
        graph[start] = valid_moves(start)

    for node in graph[start]:
        if node not in path:
            newpath = find_path(graph, node, end, path)
            if newpath:
                return newpath

    # We've reached a dead end: haven't got to the "end", there are no more un-checked nodes
    return []


def icon_remap(status: str, map: dict[str, str]) -> str:
    """Remap the default symbols to more readable ones."""
    for key in map:
        status = status.replace(key, map[key])
    return status


def basic_remap(status: str) -> str:
    """A default remap for the status."""
    return icon_remap(status, {"D": "↓", "U": "↑", "0": "◯"})


# Find the relevant path
path = find_path(dict(), "DDD0UUU", "UUU0DDD", [])
if  not path:
    print("No path found")
    exit()
print("The path of stages is:")
print(" -> ".join(path))

# Let's display tye path in a pivoted way, side by side
pivoted = "\n".join(
    [" ".join([basic_remap(step[i]) for step in path]) for i in range(len(path[0]))]
)
print()
print("The path as a vertical series is:")
print(pivoted)

Definite spoiler alert for Machinarium, you should try (and try and try) yourself, before resorting to using any external hints like this sequence:

The path of stages is:
DDD0UUU -> DDDU0UU -> DD0UDUU -> D0DUDUU -> DUD0DUU -> DUDUD0U -> DUDUDU0 -> DUDU0UD -> DU0UDUD -> 0UDUDUD -> U0DUDUD -> UUD0DUD -> UUDUD0D -> UUDU0DD -> UU0UDDD -> UUU0DDD

The path as a vertical series is:
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ◯ ↑ ↑ ↑ ↑ ↑ ↑
↓ ↓ ↓ ◯ ↑ ↑ ↑ ↑ ↑ ↑ ◯ ↑ ↑ ↑ ↑ ↑
↓ ↓ ◯ ↓ ↓ ↓ ↓ ↓ ◯ ↓ ↓ ↓ ↓ ↓ ◯ ↑
◯ ↑ ↑ ↑ ◯ ↑ ↑ ↑ ↑ ↑ ↑ ◯ ↑ ↑ ↑ ◯
↑ ◯ ↓ ↓ ↓ ↓ ↓ ◯ ↓ ↓ ↓ ↓ ↓ ◯ ↓ ↓
↑ ↑ ↑ ↑ ↑ ◯ ↑ ↑ ↑ ↑ ↑ ↑ ◯ ↓ ↓ ↓
↑ ↑ ↑ ↑ ↑ ↑ ◯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓