puzzle liseuse

puzzle.py

# -*- coding: utf-8 -*-
from copy import deepcopy
from collections import defaultdict, namedtuple, deque
from functools import wraps


class Colors:
    HEADER = '\033[95m'
    OKBLUE = '\033[94m'
    OKGREEN = '\033[92m'
    WARNING = '\033[93m'
    FAIL = '\033[91m'
    ENDC = '\033[0m'
    BOLD = '\033[1m'
    UNDERLINE = '\033[4m'

    @staticmethod
    def green(r):
        return '%s%s%s' % (Colors.OKGREEN, r, Colors.ENDC)


def add_2tuple(t1, t2):
    return (t1[0] + t2[0], t1[1] + t2[1])


def sub_2tuple(t1, t2):
    return (t1[0] - t2[0], t1[1] - t2[1])

Piece = namedtuple('Piece', ['id', 'type', 'length'])


class Result():
    def __init__(self, solution, ancestors, initial):
        self.solution = solution
        self.ancestors = ancestors
        self.initial = initial

    def print_all(self):
        steps = [a for a in self.ancestors] + [self.solution]
        a, b = iter(steps), iter(steps)
        b.next()
        print
        print self.initial
        for w in b:
            print
            print w.str_with_diff(a.next())


class Immutable(object):
    def __setattr__(self, attr, value):
        if getattr(self, 'init_done', None):
            raise ValueError('%s cannot be changed after initialization' %
                self.__class__.__name__)
        else:
            super(Immutable, self).__setattr__(attr, value)

    @staticmethod
    def init(fn):
        @wraps(fn)
        def wrapped(self, *args, **kwargs):
            fn(self, *args, **kwargs)
            self.init_done = True
        return wrapped


class Game(Immutable):
    VERTICAL = 0
    HORIZONTAL = 1

    @Immutable.init
    def __init__(self, r, c, pieces, positions, matrix=None):
        self.r = r
        self.c = c
        self.positions = positions
        self.pieces = pieces

        if matrix is None:
            self.matrix = [[0] * self.c for _ in xrange(self.r)]
            for p_id, (x, y) in self.positions.iteritems():
                p_id, p_type, length = self.pieces[p_id]
                for i in xrange(length):
                    px = x + (i if p_type == Game.VERTICAL else 0)
                    py = y + (i if p_type == Game.HORIZONTAL else 0)
                    self.matrix[px][py] = p_id
        else:
            self.matrix = matrix

        self.cached_str = '\n'.join(' '.join(map(str, row))
            for row in self.matrix)

    @staticmethod
    def get_piece_type(positions):
        x, y = positions[0]
        if positions[1][0] == x:
            return Game.HORIZONTAL
        else:
            return Game.VERTICAL

    @staticmethod
    def parse(game_str):
        lines = [l.split('-') for l in game_str.split('\n') if l != '']
        positions = defaultdict(list)
        for r, row in enumerate(lines):
            for c, piece_id in enumerate(row):
                if piece_id != '0':
                    positions[piece_id].append((r, c))
        pieces = {piece_id: Piece(piece_id, Game.get_piece_type(p), len(p))
            for piece_id, p in positions.iteritems()}
        positions = {piece_id: p[0] for k, p in positions.iteritems()
            for piece_id, p in positions.iteritems()}

        r = len(lines)
        c = len(lines[0])
        return Game(r, c, pieces, positions)

    def is_free(self, i, j):
        return self.matrix[i][j] == 0

    def possible_moves(self, piece_id):
        piece_id, t, length = self.pieces[piece_id]
        position = self.positions[piece_id]
        if t == Game.VERTICAL:
            # up
            x, y = position  # top most position
            i = -1
            while x + i >= 0 and self.is_free(x + i, y):
                yield (i, 0)
                i -= 1
            # down
            x, y = add_2tuple(position, (length - 1, 0))  # bottom most position
            i = 1
            while x + i < self.r and self.is_free(x + i, y):
                yield (i, 0)
                i += 1
        else:
            # left
            x, y = position
            j = -1
            while y + j >= 0 and self.is_free(x, y + j):
                yield (0, j)
                j -= 1
            # right
            x, y = add_2tuple(position, (0, length - 1))
            j = 1
            while y + j < self.r and self.is_free(x, y + j):
                yield (0, j)
                j += 1

    def iter_positions(self, piece_id, position=None):
        x, y = self.positions[piece_id] if position is None else position
        _, t, length = self.pieces[piece_id]
        for l in xrange(length):
            yield (x + (l if t == Game.VERTICAL else 0),
                y + (l if t == Game.HORIZONTAL else 0))

    def print_matrix(self):
        print
        for row in self.matrix:
            for col in row:
                print col,
            print

    def make_move(self, piece_id, move):
        piece_id, t, length = self.pieces[piece_id]
        position = self.positions[piece_id]
        new_position = add_2tuple(position, move)
        new_positions = dict(self.positions, **{piece_id: new_position})
        matrix = deepcopy(self.matrix)
        for x, y in self.iter_positions(piece_id):
            matrix[x][y] = 0
        for x, y in self.iter_positions(piece_id, new_position):
            matrix[x][y] = piece_id
        return Game(self.r, self.c, self.pieces, new_positions, matrix)

    def next_states(self):
        for piece_id in self.pieces.iterkeys():
            for move in self.possible_moves(piece_id):
                yield self.make_move(piece_id, move)

    def is_win(self):
        return self.positions['N'] == (2, 4)

    def __str__(self):
        return self.cached_str

    def diff(self, other):
        diff = {}
        for pid, piece in self.pieces.iteritems():
            if other.pieces[pid].position != piece.position:
                diff[pid] = True
        return diff

    def str_with_diff(self, other):
        diff = self.diff(other)
        str_mat = []
        arrow_yet = False
        for row in self.matrix:
            str_row = []
            for piece_id in row:
                if piece_id not in diff:
                    symbol = piece_id
                else:
                    if not arrow_yet:
                        sub = sub_2tuple(
                            self.pieces[piece_id].position,
                            other.pieces[piece_id].position
                        )
                        if sub[0] > 0:
                            symbol = u'↓'
                        elif sub[0] < 0:
                            symbol = u'↑'
                        elif sub[1] < 0:
                            symbol = u'←'
                        elif sub[1] > 0:
                            symbol = u'→'
                        arrow_yet = True
                    else:
                        symbol = piece_id
                    symbol = Colors.green(symbol)
                str_row.append(unicode(symbol))
            str_mat.append(' '.join(str_row))
        return '\n'.join(str_mat)

    def solve(self):
        q = deque([self])
        parents = {self.cached_str: None}
        already = set()
        while len(q) > 0:
            game = q.popleft()
            for next_state in game.next_states():

                # stop if we've already seen this state
                h = next_state.cached_str
                if h in already:
                    continue
                already.add(next_state.cached_str)

                # save parent
                if h not in parents:
                    parents[h] = game

                if not next_state.is_win():
                    # continue exploration
                    q.append(next_state)
                else:
                    # we have a winner !
                    # build the ancestor chain
                    ancestors = []
                    cur = next_state
                    while parents.get(cur.cached_str):
                        cur = parents[cur.cached_str]
                        ancestors.insert(0, cur)
                    return Result(
                        solution=next_state, ancestors=ancestors, initial=self)

test_puzzle.py

from puzzle import Game
from nose.tools import assert_raises

g1 = """
1-2-2-0-3-0
1-0-4-0-3-0
N-N-4-0-0-5
6-6-6-7-7-5
0-0-8-9-9-9
0-0-8-0-0-0
"""

g2 = """
1-2-2-0-3-5
1-0-4-0-3-5
0-0-4-0-N-N
6-6-6-7-7-0
0-0-8-9-9-9
0-0-8-0-0-0
"""

g3 = """
2-2-4-0-3-0
0-0-4-0-3-5
1-N-N-0-0-5
1-6-6-6-7-7
0-0-8-9-9-9
0-0-8-0-0-0
"""

ghard = """
1-1-0-2-3-4
0-0-0-2-3-4
5-0-N-N-3-6
5-0-0-7-7-6
8-8-9-10-10-6
0-0-9-0-11-11
"""


def test_basic():
    g = Game.parse(g1)
    assert g.r == 6
    assert g.c == 6
    assert g.pieces['1'].type == Game.VERTICAL
    assert g.pieces['N'].type == Game.HORIZONTAL
    assert g.pieces['2'].type == Game.HORIZONTAL

    assert g.positions['1'] == (0, 0)
    assert g.positions['2'] == (0, 1)
    assert g.positions['3'] == (0, 4)

    assert g.is_free(1, 1) is True
    assert g.is_free(1, 0) is False
    assert g.is_free(0, 3) is True
    assert g.is_free(0, 0) is False
    assert g.is_free(2, 0) is False
    assert g.is_free(2, 2) is False

    assert len(list(g.possible_moves('1'))) == 0
    assert len(list(g.possible_moves('2'))) == 1
    assert len(list(g.possible_moves('3'))) == 1
    assert len(list(g.possible_moves('4'))) == 0
    assert len(list(g.possible_moves('5'))) == 2
    assert len(list(g.possible_moves('6'))) == 0
    assert len(list(g.possible_moves('7'))) == 0
    assert len(list(g.possible_moves('8'))) == 0
    assert len(list(g.possible_moves('9'))) == 0


def test_make_move():
    g = Game.parse(g1)
    g2 = g.make_move('2', (0, 1))
    g3 = g2.make_move('3', (1, 0))
    assert g2.is_free(0, 1)
    assert g2.is_free(0, 2) is False
    assert g2.is_free(0, 3) is False
    assert g3.is_free(0, 4)
    assert g3.is_free(1, 4) is False


def test_next_states():
    g = Game.parse(g1)
    next_states = list(g.next_states())
    assert len(next_states) == 4


def test_win():
    g = Game.parse(g2)
    assert g.is_win() is True


def test_next_states():
    g = Game.parse(g3)
    for ns in g.next_states():
        assert str(g) != str(ns)


def test_solve():
    g = Game.parse(g1)
    res = g.solve()
    assert len(res.ancestors) == 14


def test_immutability():
    g = Game.parse(g1)

    def mutate():
        g.pieces = []

    assert_raises(ValueError, mutate)


def test_hard():
    g = Game.parse(ghard)
    res = g.solve()
    assert len(res.ancestors) == 25