Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in 3rd party category for Visibilities by Sillte
from typing import List, Iterable, Tuple
from itertools import product
from functools import reduce
from copy import deepcopy
class Contradiction(Exception):
pass
class Setting:
def __init__(self, grid):
self.n_row = len(grid)
self.n_column = len(grid[0])
self.number_dict = dict()
for r, c in product(range(self.n_row), range(self.n_column)):
if grid[r][c] != 0:
self.number_dict[(r, c)] = grid[r][c]
def print(self):
print("number_dict", self.number_dict)
def _is_within(self, pos):
return 0 <= pos[0] < self.n_row and 0 <= pos[1] < self.n_column
def proximities(self, pos):
dps = [(0, +1), (0, -1), (+1, 0), (-1, 0)]
cands = [(pos[0] + dp[0], pos[1] + dp[1]) for dp in dps]
return list(filter(self._is_within, cands))
class State:
def __init__(self, setting):
number_dict = setting.number_dict
self.white = set(number_dict.keys())
self.black = set()
self.uncertain = {(r, c) for r, c in product(range(setting.n_row), range(setting.n_column))} - self.white
self.setting = setting
self.ok_constraints = set()
def print(self):
print("white", self.white)
print("black", self.black)
print("uncertain", self.uncertain)
print("ok_constraints", self.ok_constraints)
def claim_white(self, pos):
if pos in self.white:
return False
if pos in self.black:
raise Contradiction()
self.uncertain.remove(pos);
self.white.add(pos)
return True
def claim_black(self, pos):
if pos in self.black:
return False
if pos in self.white:
raise Contradiction()
self.uncertain.remove(pos);
self.black.add(pos)
""" A kind of Constraint:
* Proximities of ``black`` must be white.
"""
for p in self.setting.proximities(pos):
self.claim_white(p)
return True
def _divide4(number, limits):
def _inner(remain, values, index=0):
if index == 3:
assert 0 <= remain
if remain <= limits[index]:
yield values + (remain, )
else:
pass
else:
for i in range(limits[index] + 1):
n_values = values + (i, )
n_remain = remain - i
if n_remain < 0:
break
yield from _inner(n_remain, n_values, index + 1)
return list(_inner(number, (), index=0))
def _make_cands(pos, value, setting):
fixed_whites = set(setting.number_dict.keys())
dps = [(+1, 0), (-1, 0), (0, +1), (0, -1)]
limits = [None] * 4
limits[0] = setting.n_row - (pos[0] + 1)
limits[1] = pos[0]
limits[2] = setting.n_column - (pos[1] + 1)
limits[3] = pos[1]
partitions = _divide4(value - 1, limits)
cands = list()
for partition in partitions:
# print("partition", partition, "pos", pos, "limits", limits)
white = set()
black = set()
is_valid = True
for dp, limit in zip(dps, partition):
for step in range(1, limit + 1):
p = pos[0] + dp[0] * step, pos[1] + dp[1] * step
white.add(p)
# print("p", p, step)
assert 0 <= p[0] < setting.n_row and 0 <= p[1] < setting.n_column
p = pos[0] + dp[0] * (limit + 1), pos[1] + dp[1] * (limit + 1)
if not (0 <= p[0] < setting.n_row and 0 <= p[1] < setting.n_column):
pass
elif p in fixed_whites:
is_valid = False
else:
black.add(p)
if is_valid:
cands.append((white, black))
return cands
class NumberConstraint:
def __init__(self, pos, value, setting):
self.cands = [] # ``list`` of ``pair``, whites, blacks
self.cands = _make_cands(pos, value, setting)
def _calc_possible_cands(self, s):
def _inner(cand):
w, b = cand
if w & s.black:
return False
if b & s.white:
return False
return True
return [cand for cand in self.cands
if _inner(cand)]
def is_satisfied(self, s):
possible_cands = self._calc_possible_cands(s)
if not possible_cands:
raise Contradiction
for cand in possible_cands:
w, b = cand
if w.issubset(s.white) and b.issubset(s.black):
return True
return False
def deduce(self, s):
possible_cands = self._calc_possible_cands(s)
if not possible_cands:
raise Contradiction
common_w = reduce(lambda a, b: a & b,
(cand[0] for cand in possible_cands))
for cw in common_w:
s.claim_white(cw)
common_b = reduce(lambda a, b: a & b,
(cand[1] for cand in possible_cands))
for cb in common_b:
s.claim_black(cb)
def complete(state, constraints):
target_constraints = [constraint for c_index, constraint in enumerate(constraints)
if c_index not in state.ok_constraints]
is_updated = False
while True:
for constraint in target_constraints:
if constraint.deduce(state):
is_updated = True
if not is_updated:
break
for c_index, constraint in enumerate(constraints):
if c_index in state.ok_constraints:
continue
if constraint.is_satisfied(state):
state.ok_constraints.add(c_index)
if len(state.ok_constraints) == len(constraints):
uncertain = deepcopy(state.uncertain)
for c in uncertain:
state.claim_white(c)
if not state.uncertain:
import numpy as np
from scipy.ndimage import label
setting = state.setting
array = np.zeros(shape=(setting.n_row, setting.n_column))
for pos in state.white:
array[pos[0]][pos[1]] = True
num_pieces = label(array)[1]
if 1 < num_pieces :
raise Contradiction()
return state
def selector(state, constraints):
target_constraints = [constraint for c_index, constraint in enumerate(constraints)
if c_index not in state.ok_constraints]
return min(target_constraints, key=lambda c: len(c._calc_possible_cands(state)))
def search(state, constraints):
state = complete(state, constraints)
if not state.uncertain:
return state
pivot_const = selector(state, constraints)
possible_cands = pivot_const._calc_possible_cands(state)
for cand in possible_cands:
n_state = deepcopy(state)
for w in cand[0]:
n_state.claim_white(w)
for b in cand[1]:
n_state.claim_black(b)
try:
return search(n_state, constraints)
except Contradiction:
pass
raise Contradiction()
def visibilities(grid: List[List[int]]) -> Iterable[Tuple[int]]:
setting = Setting(grid)
#setting.print()
constraints = [NumberConstraint(pos, value, setting) for pos, value in setting.number_dict.items()]
print("#constraints", len(constraints))
state = State(setting)
#state.print()
state = search(state, constraints)
return state.black
def checker(func, grid):
result = func([row[:] for row in grid])
BLACK, MOVES = -1, ((-1, 0), (1, 0), (0, -1), (0, 1))
in_grid = lambda i, j: 0 <= i < len(grid) and 0 <= j < len(grid[0])
for item in result:
if not (isinstance(item, (tuple, list)) and len(item) == 2 and
all(isinstance(n, int) for n in item)):
print(f"You should give tuples/lists of 2 ints, not {item}.")
return False
i, j = item
if not in_grid(i, j):
print(f"{(i, j)} is outside the grid.")
return False
if grid[i][j] > 0:
print("You can't put a black box on the "
f"number {grid[i][j]} at {(i, j)}.")
return False
if grid[i][j] == BLACK:
print(f"You can't put a black box twice at {(i, j)}.")
return False
for x, y in ((i + di, j + dj) for di, dj in MOVES):
if in_grid(x, y) and grid[x][y] == BLACK: # RULE 1
print(f"You can't put a black box at {(x, y)} because "
f"there is a box at {(i, j)}, it's too close.")
return False
grid[i][j] = BLACK
from numpy import array
from scipy.ndimage import label # Powerful tool.
bool_array = array([[n != BLACK for n in row] for row in grid])
num_pieces = label(bool_array)[1]
if num_pieces > 1: # RULE 2
print("White boxes in the grid should not be separated "
f"into {num_pieces} pieces by black boxes.")
return False
numbers = ((i, j, n) for i, row in enumerate(grid)
for j, n in enumerate(row) if n > 0)
for i, j, n in numbers:
visibility_from_n = 1
for di, dj in MOVES:
x, y = i + di, j + dj
while in_grid(x, y) and grid[x][y] != BLACK:
visibility_from_n += 1
x, y = x + di, y + dj
if visibility_from_n != n: # RULE 3
print(f"The box at {(i, j)} should see "
f"{n} boxes, not {visibility_from_n}.")
return False
return True
if __name__ == "__main__":
GRIDS = (('5x5', [[0, 0, 4, 0, 6],
[0, 6, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 5, 0],
[6, 0, 7, 0, 0]]),
('5x8', [[0, 0, 0, 0, 0, 0, 4, 7],
[0, 0, 0, 0, 4, 0, 3, 0],
[0, 0, 8, 0, 0, 7, 0, 0],
[0, 4, 0, 6, 0, 0, 0, 0],
[6, 5, 0, 0, 0, 0, 0, 0]]),
('6x9', [[6, 0, 0, 8, 0, 0, 4, 0, 0],
[0, 0, 0, 9, 0, 0, 0, 0, 0],
[7, 3, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 7, 8],
[0, 0, 0, 0, 0, 2, 0, 0, 0],
[0, 0, 9, 0, 0, 8, 0, 0, 12]]),
('8x12', [[0, 0, 0, 2, 0, 0, 6, 0, 0, 0, 0, 0],
[0, 5, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0],
[0, 6, 0, 0, 0, 13, 0, 0, 0, 10, 0, 0],
[0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 8, 6],
[8, 3, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0],
[0, 0, 9, 0, 0, 0, 5, 0, 0, 0, 7, 0],
[0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 10, 0],
[0, 0, 0, 0, 0, 13, 0, 0, 7, 0, 0, 0]]))
for dim, grid in GRIDS:
assert checker(visibilities, grid), f"You failed on the grid {dim}."
April 4, 2019
Comments:
