puzzle-solution-1.py

# MIT License
#
# Copyright (c) 2019 Herbert Shin
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

from collections import deque
from itertools import permutations
from tabulate import tabulate

import attr
import numpy
import sys


# static table of adjacent neighbor positions. Delta mapping should be
# calculated based on index of the origin position (0, 0) in 2-D.
NEIGHBOR_DELTA_SQUARE = (
    (-1, 1),  (0, 1),  (1, 1),
    (-1, 0),  (0, 0),  (1, 0),
    (-1, -1), (0, -1), (1, -1),
)


def print_ascii_table(array):
    """ pretty print arrays into ASCII table """
    print(tabulate(array, (), tablefmt="grid"))


@attr.s(slots=True)
class Board(object):

    template = attr.ib(default=[], converter=list)
    _buffer = attr.ib(default=None)  # overwritten

    def __attrs_post_init__(self):
        self._buffer = self.template

    @property
    def data(self):
        return self._buffer

    @property
    def height(self):
        """ table height """
        return self.data.__len__()

    @property
    def width(self):
        """ table width """
        return self.data[-1].__len__()

    def populate(self, pattern=deque()):
        """ populate table template with pattern.
        @pattern<list> -- list of values to to populate vacant ("True") spots.
        """
        self._buffer = [
            [
                pattern.popleft() if self.template[i][j] is not None else None
                for j in range(self.width)
            ]
            for i in range(self.height)
        ]

    def neighbors(self, x=0, y=0):
        """ find adjacent neighbors to a point (x, y) """

        neighbors = [
            [None] * 3,
            [None] * 3,
            [None] * 3,
        ]

        for (dx, dy) in NEIGHBOR_DELTA_SQUARE:
            _x, _y = x + dx, y + dy
            try:
                assert _x >= 0 and _y >= 0 and self.data[_x][_y] is not None
            except AssertionError:
                continue
            except IndexError:
                continue
            neighbors[1 + dx][1 + dy] = self.data[_x][_y]
        return neighbors


def check_solution_sanity(board, threshold=1):
    """ """
    for i in range(board.height):
        for j in range(board.width):
            matrix = board.neighbors(x=i, y=j)
            origin = matrix[1][1]
            if origin is None:
                continue

            # match heat map with difference by `threshold`.
            if threshold in [abs(_ - origin) if _ is not None else None
                     for _ in numpy.array(matrix).flatten()]:
                return False
    return True


def main():

    # modify `town` for different board constructs. `None` means not available,
    # and `True` means available position. For example, below default draws:
    #  +---+---+---+---+
    #  |   | X | X |   |
    #  +---+---+---+---+
    #  | X | X | X | X |
    #  +---+---+---+---+
    #  |   | X | X |   |
    #  +---+---+---+---+
    town = (
        (None, True, True, None),
        (True, True, True, True),
        (None, True, True, None),
    )

    # Note: do not edit below line.
    vacancy = sum((sum([_ is not None for _ in row]) for row in town))

    board = Board(template=town)
    for pattern in permutations(range(1, vacancy + 1)):
        board.populate(pattern=deque(pattern))
        if check_solution_sanity(board):
            print_ascii_table(board.data)  # solution


if __name__ == "__main__":
    try:
        sys.exit(main())
    except KeyboardInterrupt:
        pass