misc/mhmt.py at master · vsego/misc · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#!/usr/bin/env python3

"""
A crude solver for [Move Here Move There]
(https://www.newgrounds.com/portal/view/718498).
"""

board = {
    (0, 0): "X",
    (3, 0): "X",
    (4, 0): [(-3, 3)],
    (6, 0): "X",
    (0, 1): "X",
    (4, 2): "X",
    (0, 4): [(4, 0)],
    (3, 4): [(3, -3)],
    (4, 4): [(1, 0), (-1, 1)],
    (1, 5): "X",
    (3, 5): [(-1, -1)],
    (5, 5): "X",
}
pieces = [
    [(-1, -1), (0, 4)],
    [(2, -2), (-1, -1)],
    [(4, 0)],
    [(0, -5)],
    [(2, 2)],
    [(0, 3)],
    [(-2, -2)],
    [(-5, 0)],
]
start = (3, 4)
maxes = (6, 5)


def move(pos, piece):
    """
    Return new position after moving by one piece.

    :param pos: A 2-tuple of `int`s, describing the starting position.
    :param piece: A list of 2-tuples of `int`s, describing one piece's moves.
    :raise ValueError: Raised if the move is impossible.
    :return: A 2-tuple of `int`s describing the new position.
    """
    for jmp in piece:
        pos = (pos[0] + jmp[0], pos[1] + jmp[1])
        if not (0 <= pos[0] <= maxes[0] and 0 <= pos[1] <= maxes[1]):
            raise ValueError()
    return pos


def step(pos, pieces, history):
    """
    Execute one step.

    :param pos: A 2-tuple of `int`s, describing the starting position.
    :param pieces: A list of lists of 2-tuples of `int`s, describing still
        unused pieces.
    :param history: A list of lists of 2-tuples of `int`s, describing already
        used pieces.
    """
    if not pieces and all(v == "X" for v in board.values()):
        print(f"{pos}: {history}")
        return
    try:
        nxt = board[pos]
    except KeyError:
        for pidx, piece in enumerate(pieces):
            try:
                pos2 = move(pos, piece)
            except ValueError:
                continue
            else:
                board[pos] = "X"
                step(pos2, pieces[:pidx] + pieces[pidx + 1:], history + [piece])
                del board[pos]
    else:
        if nxt == "X":
            return
        try:
            pos2 = move(pos, nxt)
        except ValueError:
            return
        else:
            board[pos] = "X"
            step(pos2, pieces, history)
            board[pos] = nxt


step(start, pieces, list())