Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for House of Mirrors by Somebody12345678910
import copy,itertools
from typing import Tuple, Dict, List
class Robot:
def __init__(self,R,C,direction="N",steps_taken=0):
self.R,self.C,self.direction,self.steps_taken = R,C,direction,steps_taken
def __repr__(self):
return "({},{}) -> {} <{} steps>".format(self.R,self.C,self.direction,self.steps_taken)
def turn_left(self) -> "Robot":
"""Create a new Robot, 90° anticlockwise from itself,without moving."""
return Robot(self.R,self.C,"NESW"[("NESW".index(self.direction)-1)%4],self.steps_taken)
def move_forward(self) -> "Robot":
"""Create a new Robot, one step forward from itself.."""
if self.direction == "N": return Robot(self.R-1,self.C ,self.direction,self.steps_taken+1)
if self.direction == "E": return Robot(self.R ,self.C+1,self.direction,self.steps_taken+1)
if self.direction == "S": return Robot(self.R+1,self.C ,self.direction,self.steps_taken+1)
if self.direction == "W": return Robot(self.R ,self.C-1,self.direction,self.steps_taken+1)
def turn_right(self) -> "Robot":
"""Create a new Robot, 90° clockwise from itself, without moving."""
return Robot(self.R,self.C,"NESW"[("NESW".index(self.direction)+1)%4],self.steps_taken)
def move_explicit(self,direction) -> "Robot":
"""Create a new Robot, one step in a given direction, without turning."""
if direction in "UN": return Robot(self.R-1,self.C ,self.direction,self.steps_taken+1)
if direction in "RE": return Robot(self.R ,self.C+1,self.direction,self.steps_taken+1)
if direction in "DS": return Robot(self.R+1,self.C ,self.direction,self.steps_taken+1)
if direction in "LW": return Robot(self.R ,self.C-1,self.direction,self.steps_taken+1)
def undead(house_plan: Tuple[str, ...],
monsters: Dict[str, int],
counts: Dict[str, List[int]]) -> Tuple[str, ...]:
# Create full layout of house, with all possible monsters.
A = [row.split() for row in house_plan]
H,W = len(A),len(A[0])
A = [[{"ghost","vampire","zombie"} if A[R][C] == "." else A[R][C] for C in range(W)] for R in range(H)]
# Create a dict of all paths running through the haunted mansion.
paths = {} # (tuple of empty tiles on path, in dict: (R,C,is_after_mirror) -> monsters seen
for direction,monsters_seen_list in counts.items():
for i,monsters_seen in enumerate(monsters_seen_list):
robot = {"N":Robot(0,i,"S"), "E":Robot(i,W-1,"W"), "S":Robot(H-1,i,"N"), "W":Robot(i,0,"E")}[direction]
robot_path = [] # Be brave, little robot. :o
is_after_mirror = False
while 0 <= robot.R < H and 0 <= robot.C < W:
if A[robot.R][robot.C] == "/":
new_direction = {"E":"N", "N":"E", "W":"S", "S":"W"}[robot.direction]
robot = Robot(robot.R,robot.C,new_direction,robot.steps_taken)
is_after_mirror = True
elif A[robot.R][robot.C] == "\\":
new_direction = {"E":"S", "S":"E", "W":"N", "N":"W"}[robot.direction]
robot = Robot(robot.R,robot.C,new_direction,robot.steps_taken)
is_after_mirror = True
else:
robot_path.append((robot.R,robot.C,is_after_mirror))
robot = robot.move_forward()
paths[tuple(robot_path)] = monsters_seen
# Solve the grid.
A = solve(A,monsters,paths)
A = [[max(A[R][C])[0].upper() if type(A[R][C]) == set else A[R][C] for C in range(W)] for R in range(H)]
return [" ".join(row) for row in A]
def solve(A,monsters,paths) -> list:
"""Recursive. Return A, the solved grid. Each recursion attempts to solve as much of A as possible."""
H,W = len(A),len(A[0])
for iteration_i in range(10):
# Strategy 1: Look at each path for if all of the tiles must be seen/unseen
paths_solved = []
for path,monsters_target in paths.items():
# Clean away any tiles which we know which are definitely seen/unseen.
unsolved_tiles = []
for tile in path:
R,C,is_after_mirror = tile
assert A[R][C], "Tile ({},{}) has no monsters left!".format(R,C)
if is_after_mirror:
could_be_seen = "ghost" in A[R][C] or "zombie" in A[R][C]
could_be_unseen = "vampire" in A[R][C]
else:
could_be_seen = "vampire" in A[R][C] or "zombie" in A[R][C]
could_be_unseen = "ghost" in A[R][C]
if could_be_seen and not could_be_unseen: monsters_target -= 1
elif could_be_unseen and not could_be_seen: pass
else: unsolved_tiles.append(tile)
assert monsters_target >= 0, "The path {} is overfilled.".format(path)
assert monsters_target <= len(unsolved_tiles), "The path {} is underfilled.".format(path)
# Strategy 1a: All unknown tiles must be unseen
if monsters_target == 0:
for R,C,is_after_mirror in unsolved_tiles:
if is_after_mirror: A[R][C].discard("ghost"); A[R][C].discard("zombie")
else: A[R][C].discard("vampire"); A[R][C].discard("zombie")
paths_solved.append(path)
# Strategy 1b: All unknown tiles must be seen
elif monsters_target == len(unsolved_tiles):
for R,C,is_after_mirror in unsolved_tiles:
if is_after_mirror: A[R][C].discard("vampire")
else: A[R][C].discard("ghost")
paths_solved.append(path)
### We're not using this strategy.
### This gets super crazy when the mirror lines go back on themselves in the later tests,
### so the recursion will just have to cover it.
## # Strategy 1c: Is a monster living only on this line?
## # Consider all correct permutations of monsters for these unknown tiles.
## # Do they all use up all of the remaining types of a certain monster?
## # If so, that monster can't live off that line.
## else:
## def is_monster_visible(monster,is_after_mirror) -> bool:
## """Is this monster visible?"""
## if is_after_mirror: return monster in ("zombie","ghost")
## else: return monster in ("zombie","vampire")
##
## # Find all valid monster groups
## monsters_on_path = [A[R][C] for R,C,is_after_mirror in unsolved_tiles]
## valid_monster_groups = []
## for q in itertools.product(*monsters_on_path):
## # Don't go over the amount of monsters left
## monster_counts_left = {k:v for k,v in monsters.items()}
## for R in range(H):
## for C in range(W):
## if type(A[R][C]) == set and len(A[R][C]) == 1:
## monster_counts_left[max(A[R][C])] -= 1
## if any(q.count(monster) > monster_counts_left[monster] for monster in monsters): continue
##
## # Hit monsters_target exactly
## monster_count_on_path = 0
## for (R,C,is_after_mirror),monster in zip(unsolved_tiles,q):
## if is_monster_visible(monster,is_after_mirror):
## monster_count_on_path += 1
## if monster_count_on_path != monsters_target: continue
## valid_monster_groups.append(q)
##
## # Do all remaining monsters of this type belong on this path?
## for monster in monsters:
## if monster_counts_left[monster] == 0: continue
## if all(q.count(monster) == monster_counts_left[monster] for q in valid_monster_groups):
## for R in range(H):
## for C in range(W):
## if not any((R,C) == (tile[0],tile[1]) for tile in path):
## if type(A[R][C]) == set and len(A[R][C]) > 1:
## A[R][C].discard(monster)
# Remove any paths which have been solved.
for path in paths_solved: paths.pop(path)
# Strategy 2: For each monster, find which tiles could contain that monster to determine if all/none of them are that monster.
for monster in monsters:
possible_monster_tiles = [(R,C) for R in range(H) for C in range(W) if len(A[R][C]) > 1 and monster in A[R][C]]
definite_monster_tiles = [(R,C) for R in range(H) for C in range(W) if A[R][C] == {monster}]
# All possible tiles must not contain the monster.
if len(definite_monster_tiles) == monsters[monster]:
for R,C in possible_monster_tiles:
A[R][C].discard(monster)
# All possible tiles must contain the monster.
elif len(definite_monster_tiles) + len(possible_monster_tiles) == monsters[monster]:
for R,C in possible_monster_tiles:
A[R][C] = {monster}
# Recursive step. If paths hasn't become empty, choose a tile not solved, and take a guess and recurse downwards.
if paths:
unknown_tiles = [(R,C) for R in range(H) for C in range(W) if len(A[R][C]) > 1]
R,C = min(unknown_tiles,key=lambda x:len(A[x[0]][x[1]]))
for monster_to_guess in A[R][C]:
A_new = copy.deepcopy(A)
A_new[R][C] = {monster_to_guess}
try:
res = solve(A_new,monsters,copy.deepcopy(paths))
return res
except Exception as error:
pass
raise Exception("Dead End")
else:
for R in range(H):
for C in range(W):
assert len(A[R][C]) == 1
for monster in monsters:
assert len([(R,C) for R in range(H) for C in range(W) if A[R][C] == {monster}]) == monsters[monster]
return A
July 17, 2021
