8 puzzle game

puzzle8.py

import math
import random
from enum import Enum, auto
from typing import Iterable, Optional, Set, Tuple, List, Dict
from itertools import chain

#CHAR_CUR = '█'
#CHAR_CUR = '□'
#CHAR_CUR = ' '
CHAR_CUR = '▯'
CHAR_UP = '↑'
CHAR_DOWN = '↓'
CHAR_LEFT = '←'
CHAR_RIGHT = '→'


class Move(Enum):
    UP = auto()
    DOWN = auto()
    LEFT = auto()
    RIGHT = auto()

    def __str__(self):
        if self is Move.UP:
            return CHAR_UP
        elif self is Move.DOWN:
            return CHAR_DOWN
        elif self is Move.LEFT:
            return CHAR_LEFT
        elif self is Move.RIGHT:
            return CHAR_RIGHT

    def to_english(self) -> str:
        if self is Move.UP:
            return 'up'
        elif self is Move.DOWN:
            return 'down'
        elif self is Move.LEFT:
            return 'left'
        elif self is Move.RIGHT:
            return 'right'

    @classmethod
    def from_key(cls, key: str) -> Optional['Move']:
        k = key.lower()  
        if k == 'w':
            return cls.UP
        elif k == 'a':
            return cls.LEFT
        elif k == 's':
            return cls.DOWN
        elif k == 'd':
            return cls.RIGHT


class State:
    def __init__(self, tiles: Iterable[Optional[str]]):
        # strip spaces from individual tiles:
        tiles = map(str.strip, tiles)
        # consume iterator and save as tuple (immutable)
        self.state = tuple(tiles)
        # make sure there is exactly one '', that is the empty space
        assert self.state.count('') == 1
        # make sure it forms a square
        assert self.size ** 2 == len(self.state)

    def __key(self):
        return self.state

    def __eq__(self, other):
        return self.__key() == other.__key()

    def __hash__(self):
        return hash(self.__key())

    def __str__(self):
        s, t = self.size, [i and str(i) or CHAR_CUR for i in self.state]
        # separate the tuple t in s by s tuples and join with line breaks
        return '\n'.join(''.join(t[i:i + s]) for i in range(0, len(t), s))

    def shuffled(self, count: int) -> 'State':
        state = State(self.state)
        # XXX: don't use shuffle, there are invalid states
        for _i in range(count):
            state = state.apply(random.choice(list(state.valid_moves())))
        return state

    @property
    def size(self) -> int:
        return int(math.sqrt(len(self.state)))

    @property
    def index(self) -> int:
        return self.state.index('')

    @property
    def pos(self) -> Tuple[int, int]:
        i, s = self.index, self.size
        y, x = divmod(i, s)
        return x, y

    def valid_moves(self) -> Set[Move]:
        s = self.size
        x, y = self.pos
        valid = set(Move)
        if x == 0:
            valid.remove(Move.LEFT)
        elif x == s - 1:
            valid.remove(Move.RIGHT)
        if y == 0:
            valid.remove(Move.UP)
        elif y == s - 1:
            valid.remove(Move.DOWN)
        return valid

    def neighbor(self, move: Move) -> int:
        if move is Move.RIGHT:
            return self.index + 1
        elif move is Move.LEFT:
            return self.index - 1
        elif move is Move.UP:
            return self.index - self.size
        elif move is Move.DOWN:
            return self.index + self.size

    def neighbors(self) -> Dict['State', Move]:
        return {self.apply(m): m for m in self.valid_moves()}

    def apply(self, move: Move) -> 'State':
        assert move in self.valid_moves()
        i = self.index
        n = self.neighbor(move)
        s = list(self.state)  # mutable copy
        s[i], s[n] = s[n], s[i]
        return State(s)

    def applyn(self, moves: Iterable[Move]) -> List['State']:
        states = []
        cur = self
        for move in moves:
            cur = cur.apply(move)
            states.append(cur)
        return states

    def distance(self, other: 'State') -> int:
        return sum(a != b for a, b in zip(self.state, other.state))

    def find(self, goal: 'State') -> List[Move]:
        # ripoff from: https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode
        import heapq
        from collections import defaultdict

        start = self

        def heuristic_cost_estimate(start, goal):
            return start.distance(goal)

        def reconstruct_path(came_from, current):
            total_path = []
            while current in came_from:
                current, move = came_from[current]
                total_path.append(move)
            return list(reversed(total_path))

        # The set of nodes already evaluated
        closed_set = set()

        # The set of currently discovered nodes that are not evaluated yet.
        # Initially, only the start node is known.
        open_set = {start}

        # For each node, which node it can most efficiently be reached from.
        # If a node can be reached from many nodes, cameFrom will eventually contain the
        # most efficient previous step.
        came_from = dict()

        # For each node, the cost of getting from the start node to that node.
        g_score = defaultdict(lambda: math.inf)

        # The cost of going from start to start is zero.
        g_score[start] = 0

        # For each node, the total cost of getting from the start node to the goal
        # by passing by that node. That value is partly known, partly heuristic.
        f_score = defaultdict(lambda: math.inf)

        # For the first node, that value is completely heuristic.
        f_score[start] = heuristic_cost_estimate(start, goal)

        while open_set:
            current, = heapq.nsmallest(1, open_set, lambda i: f_score[i])
            if current == goal:
                return reconstruct_path(came_from, current)

            open_set.remove(current)
            closed_set.add(current)

            for neighbor, move in current.neighbors().items():
                if neighbor in closed_set:
                    continue  # Ignore the neighbor which is already evaluated.

                # The distance from start to a neighbor
                tentative_g_score = g_score[current] + 1

                if neighbor not in open_set:  # Discover a new node
                    open_set.add(neighbor)
                elif tentative_g_score >= g_score[neighbor]:
                    continue  # This is not a better path.

                # This path is the best until now. Record it!
                came_from[neighbor] = (current, move)
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)


def play_game() -> None:
    tiles = '12345678 '
    #tiles = '123456789ABCDEF '
    #tiles = '┏━┓┃ ┃┗━┛'
    initial_state = State(tiles)
    print('>> get to this state:')
    print(initial_state)
    print()
    print('>> use WASD to move. go!')
    state = initial_state.shuffled(100)
    while state != initial_state:
        print(state)
        print('move> ', end='', flush=True)
        inp = input().strip()
        if inp == 'cheat':
            moves = state.find(initial_state)
            print('>> answer:', ''.join(map(str, moves)))
            continue
        elif inp == 'giveup':
            moves = state.find(initial_state)
            for move in moves:
                print(move)
                state = state.apply(move)
                print(state)
            print('>> that is how you should have done')
            break
        move = Move.from_key(inp)
        if move is None:
            print('>> invalid input, not one of: WASD')
            continue
        if move not in state.valid_moves():
            print('>> invalid move, cannot go', move.to_english())
            continue
        print('>> alright')
        state = state.apply(move)
    else:
        print(state)
        print('>> congratulations! you won!')


if __name__ == '__main__':
    try:
        play_game()
    except KeyboardInterrupt:
        print()
    print('>> bye!')