Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment