Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
[typed] Light paths and backtrack on the position of the monsters solution in Clear category for House of Mirrors by Phil15
from typing import Dict, Iterator, List, Tuple
Position = Tuple[int, int]
LightPath = Tuple[List[Position], List[Position]]
MOVES = {'N': (-1, 0), 'S': (1, 0), 'W': (0, -1), 'E': (0, 1)}
OPPOSITE = dict(zip('NSWE', 'SNEW'))
MIRROR_REDIRECTIONS = {
'\\': {'N': 'W', 'S': 'E', 'W': 'N', 'E': 'S'},
'/': {'N': 'E', 'S': 'W', 'W': 'S', 'E': 'N'},
}
MONSTER_VISIBILITIES = {
# monster: (can be seen directly, can be seen via mirror)
'zombie': (True, True),
'ghost': (False, True),
'vampire': (True, False),
} # Order matters a bit because it is a bit faster to put the zombies first.
def undead(
house_plan: Tuple[str, ...],
monsters_counts: Dict[str, int],
outside_counts: Dict[str, List[int]],
) -> Tuple[str, ...]:
"""Complete the plan of the house of mirrors with the monsters."""
grid = list(map(str.split, house_plan))
paths_and_counts = list(light_paths_and_counts(grid, outside_counts))
free_positions = [
(r, c)
for r, row in enumerate(grid)
for c, cell in enumerate(row)
if cell == '.'
]
places = find_monsters(free_positions, paths_and_counts, monsters_counts)
for (r, c), monster in places.items():
grid[r][c] = monster[0].upper() # ghost: G, vampire: V, zombie: Z
return tuple(map(' '.join, grid))
def light_paths_and_counts(
grid: List[List[str]], outside_counts: Dict[str, List[int]]
) -> Iterator[Tuple[LightPath, int]]:
"""Get all light paths, and the number of monsters we see in them."""
nrows, ncols = len(grid), len(grid[0])
def in_grid(r: int, c: int) -> bool:
"""Is the position (r, c) in the grid?"""
return 0 <= r < nrows and 0 <= c < ncols
def go_next(
position: Position, nwse: str, directly: bool
) -> Tuple[Position, str, bool]:
"""Next (directly?) light position/direction."""
(r, c), (dr, dc) = position, MOVES[nwse]
r += dr
c += dc
if in_grid(r, c) and grid[r][c] in MIRROR_REDIRECTIONS:
# Going through a mirror.
nwse = MIRROR_REDIRECTIONS[grid[r][c]][nwse]
directly = False
return (r, c), nwse, directly
def light_path(position: Position, nwse: str) -> LightPath:
"""Light path from starting position, and starting nwse direction."""
path: LightPath = ([], []) # ([directly], [via mirror])
directly = True # No mirror yet.
while True:
position, nwse, directly = go_next(position, nwse, directly)
r, c = position
if not in_grid(r, c):
break
if grid[r][c] == '.':
path[not directly].append(position)
return path
outside = [('N', c, (-1, c)) for c in range(ncols)]
outside += [('S', c, (nrows, c)) for c in range(ncols)]
outside += [('W', r, (r, -1)) for r in range(nrows)]
outside += [('E', r, (r, ncols)) for r in range(nrows)]
for from_, index, start in outside:
path = light_path(start, OPPOSITE[from_])
if any(path): # Otherwise, this would be an useless information.
yield path, outside_counts[from_][index]
def find_monsters(
monsters_positions: List[Position],
paths_and_counts: List[Tuple[LightPath, int]],
max_monsters: Dict[str, int],
) -> Dict[Position, str]:
"""Determine where the monsters are according to constraints."""
solution = dict.fromkeys(monsters_positions, '')
monster_counts = dict.fromkeys(MONSTER_VISIBILITIES, 0)
light_paths = [path for path, _ in paths_and_counts]
full_paths = [part1 + part2 for part1, part2 in light_paths]
path_counts = [count for _, count in paths_and_counts]
def backtracking(index: int = 0) -> bool:
"""Determine the `index`-th monster and go back when necessary."""
if index == len(monsters_positions):
# Path counts and monter counts both satisfied?
return not any(path_counts) and monster_counts == max_monsters
monsters_position = monsters_positions[index]
for monster_type, (
visible_directly,
visible_via_mirror,
) in MONSTER_VISIBILITIES.items():
if monster_counts[monster_type] >= max_monsters[monster_type]:
# Already enough of this type of monster, so skip it.
continue
# Add a monster, see if it is okay with light paths.
monster_counts[monster_type] += 1
solution[monsters_position] = monster_type
count_changes = []
for n, (directly_path, via_mirror_path) in enumerate(light_paths):
count = 0
if visible_directly:
count += directly_path.count(monsters_position)
if visible_via_mirror:
count += via_mirror_path.count(monsters_position)
if path_counts[n] < count:
break # Too many monsters in the path.
if count:
count_changes.append((n, count))
path_counts[n] -= count
# A tricky way to count free places but a bit faster that way:
nb_free_places = [*map(solution.get, full_paths[n])].count('')
if nb_free_places < path_counts[n]:
break # Not enough free places to satisfy the path count.
else:
if backtracking(index + 1):
return True
# Something went wrong: cancel count changes & remove the monster.
for n, count in count_changes:
path_counts[n] += count
solution[monsters_position] = ''
monster_counts[monster_type] -= 1
return False
if backtracking():
return solution
raise Exception('No solution.')
if __name__ == '__main__':
TESTS = [
(
(
'. \\ . /',
'\\ . . .',
'/ \\ . \\',
'. \\ / .',
),
{'ghost': 2, 'vampire': 2, 'zombie': 4},
{
'E': [0, 3, 0, 1],
'N': [3, 0, 3, 0],
'S': [2, 1, 1, 4],
'W': [4, 0, 0, 0],
},
(
'Z \\ V /',
'\\ Z G V',
'/ \\ Z \\',
'G \\ / Z',
),
),
(
(
'\\ . . .',
'. . \\ /',
'/ \\ . \\',
'/ . \\ \\',
'. . . .',
'/ / . /',
),
{'ghost': 3, 'vampire': 5, 'zombie': 4},
{
'E': [1, 0, 0, 3, 4, 0],
'N': [2, 1, 2, 0],
'S': [0, 3, 3, 0],
'W': [0, 3, 0, 0, 4, 2],
},
(
'\\ G V G',
'V G \\ /',
'/ \\ Z \\',
'/ V \\ \\',
'Z V Z Z',
'/ / V /',
),
),
(
(
'. . . / . . /',
'. . \\ / . . .',
'. . . . . . .',
'. \\ . . . / \\',
'. / . \\ . . \\',
),
{'ghost': 6, 'vampire': 10, 'zombie': 9},
{
'E': [0, 4, 6, 0, 1],
'N': [3, 5, 0, 3, 3, 7, 1],
'S': [3, 0, 5, 0, 3, 0, 3],
'W': [2, 4, 6, 0, 2],
},
(
'Z Z G / V V /',
'Z Z \\ / G V V',
'G Z Z V Z Z V',
'G \\ Z V V / \\',
'V / V \\ G G \\',
),
),
(
(
'\\ . . .',
'. / \\ .',
'/ \\ . \\',
'. . \\ /',
),
{'ghost': 5, 'vampire': 1, 'zombie': 2},
{
'E': [0, 1, 2, 0],
'N': [3, 0, 1, 0],
'S': [2, 2, 2, 0],
'W': [0, 2, 0, 2],
},
(
'\\ G G G',
'V / \\ G',
'/ \\ G \\',
'Z Z \\ /',
),
),
(
(
'. / . .',
'. . . .',
'/ . . .',
'. / . /',
'\\ . . /',
),
{'ghost': 7, 'vampire': 3, 'zombie': 4},
{
'E': [3, 0, 3, 4, 0],
'N': [1, 0, 4, 2],
'S': [0, 4, 4, 0],
'W': [1, 0, 1, 5, 0],
},
(
'V / Z G',
'G G G G',
'/ Z Z G',
'V / Z /',
'\\ G V /',
),
),
(
(
'. / . \\',
'/ . / .',
'\\ . \\ /',
'. . \\ /',
'. . . .',
'. / . .',
'. / . /',
),
{'ghost': 2, 'vampire': 9, 'zombie': 5},
{
'E': [0, 5, 1, 0, 4, 2, 0],
'N': [1, 0, 1, 0],
'S': [3, 0, 4, 0],
'W': [1, 0, 3, 2, 4, 5, 2],
},
(
'V / Z \\',
'/ V / Z',
'\\ V \\ /',
'G Z \\ /',
'V V V V',
'Z / G V',
'Z / V /',
),
),
(
(
'. / . . \\',
'\\ . . . .',
'\\ / . . .',
'\\ . / . .',
'. \\ . . .',
),
{'ghost': 6, 'vampire': 5, 'zombie': 6},
{
'E': [0, 3, 5, 3, 4],
'N': [4, 1, 0, 5, 0],
'S': [1, 0, 0, 5, 6],
'W': [1, 5, 3, 0, 1],
},
(
'Z / G Z \\',
'\\ G G Z V',
'\\ / G Z Z',
'\\ V / V V',
'V \\ G Z G',
),
),
(
(
'. . . . /',
'/ . \\ . .',
'. . . \\ \\',
'. . . / \\',
'. . . . .',
'. . / . .',
),
{'ghost': 11, 'vampire': 8, 'zombie': 3},
{
'E': [0, 2, 0, 2, 1, 0],
'N': [1, 4, 2, 0, 3],
'S': [5, 4, 2, 1, 3],
'W': [2, 0, 5, 3, 1, 8],
},
(
'V G Z G /',
'/ V \\ G V',
'Z V Z \\ \\',
'G V G / \\',
'G G G G V',
'V V / G G',
),
),
(
(
'. \\ . \\ . .',
'. . \\ . . .',
'. . / . / \\',
'. . / . / .',
'. . . . . .',
'. . . . \\ \\',
),
{'ghost': 4, 'vampire': 7, 'zombie': 15},
{
'E': [2, 4, 2, 1, 4, 4],
'N': [5, 5, 4, 1, 4, 2],
'S': [5, 4, 4, 5, 4, 1],
'W': [5, 0, 4, 3, 4, 4],
},
(
'Z \\ Z \\ V Z',
'G G \\ Z Z Z',
'V V / V / \\',
'Z Z / Z / Z',
'V G Z G V V',
'Z Z Z Z \\ \\',
),
),
(
(
'. \\ . / . \\ \\',
'. \\ . . . . .',
'. . . . . \\ \\',
'/ . / \\ \\ . .',
'. / / / . . .',
'. \\ \\ / . . .',
),
{'ghost': 9, 'vampire': 10, 'zombie': 6},
{
'E': [0, 2, 0, 4, 0, 3],
'N': [3, 0, 5, 0, 2, 0, 0],
'S': [2, 1, 3, 3, 7, 4, 8],
'W': [4, 2, 7, 0, 0, 1],
},
(
'V \\ V / G \\ \\',
'V \\ V G G G V',
'V V Z G V \\ \\',
'/ V / \\ \\ Z V',
'G / / / G G G',
'Z \\ \\ / Z Z Z',
),
),
(
(
'. \\ . . . \\ .',
'. \\ / / . / .',
'. \\ . \\ / \\ .',
'\\ / / \\ \\ . \\',
'\\ . / \\ . \\ .',
'. \\ . . . \\ .',
'. . \\ . / \\ .',
),
{'ghost': 5, 'vampire': 13, 'zombie': 6},
{
'E': [1, 2, 2, 2, 4, 1, 0],
'N': [3, 0, 2, 2, 2, 0, 3],
'S': [1, 1, 2, 2, 0, 0, 3],
'W': [0, 3, 3, 1, 2, 2, 0],
},
(
'G \\ V V V \\ V',
'V \\ / / V / Z',
'Z \\ V \\ / \\ Z',
'\\ / / \\ \\ V \\',
'\\ V / \\ V \\ Z',
'Z \\ V V V \\ Z',
'G G \\ G / \\ G',
),
),
(
(
'. . \\ . . / .',
'. . . . \\ . /',
'. . \\ \\ / / .',
'. . \\ \\ / . /',
'/ \\ . . . \\ \\',
'\\ . . . . \\ .',
'. . \\ . . . \\',
),
{'ghost': 7, 'vampire': 12, 'zombie': 10},
{
'E': [4, 4, 1, 0, 0, 7, 1],
'N': [4, 6, 0, 6, 1, 0, 1],
'S': [1, 3, 1, 4, 1, 5, 3],
'W': [3, 4, 3, 4, 4, 0, 1],
},
(
'Z Z \\ V V / V',
'Z G Z Z \\ V /',
'Z Z \\ \\ / / Z',
'Z V \\ \\ / V /',
'/ \\ G G G \\ \\',
'\\ Z V V G \\ V',
'V G \\ V G V \\',
),
),
(
(
'. . . . . . .',
'. . . \\ . \\ /',
'. . . . . / \\',
'. . . . / \\ \\',
'. \\ \\ . \\ / .',
'\\ . . . \\ / \\',
'. \\ . . . . /',
),
{'ghost': 13, 'vampire': 16, 'zombie': 2},
{
'E': [4, 0, 0, 0, 1, 0, 0],
'N': [4, 0, 4, 4, 4, 0, 2],
'S': [0, 1, 6, 5, 5, 1, 0],
'W': [4, 3, 4, 5, 1, 1, 0],
},
(
'V G V G Z G V',
'G G V \\ G \\ /',
'G G V V G / \\',
'Z G V G / \\ \\',
'V \\ \\ V \\ / V',
'\\ V V G \\ / \\',
'G \\ V V V V /',
),
),
]
from time import perf_counter
for n, (house_plan, monsters, counts, answer) in enumerate(TESTS, 1):
t = -perf_counter()
result = undead(house_plan, monsters, counts)
t += perf_counter()
print(f'Test #{n: <2} solved in {t:.6f} seconds.')
if result != answer:
print(f'You failed the test #{n}:', *house_plan, monsters, counts,
'Your result:', *result, 'Right result:', *answer, sep='\n')
break
else:
print('Well done!')
Nov. 10, 2020
