Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Inertia by mortonfox
from typing import Tuple, Iterable
# Represent each move as a single char for compactness.
MOVE_CODE = {'a': 'NW', 'b': 'N', 'c': 'NE',
'd': 'W', 'e': 'E',
'f': 'SW', 'g': 'S', 'h': 'SE'}
MOVE_TABLE = {'a': (-1, -1), 'b': (-1, 0), 'c': (-1, 1),
'd': ( 0, -1), 'e': ( 0, 1),
'f': ( 1, -1), 'g': ( 1, 0), 'h': ( 1, 1)}
GEM_SYM, ROUGH_SYM, ICE_SYM, ROCK_SYM, MINE_SYM = '$. X*'
# Preprocessing step. Find out which directions we can go from each square
# without hitting mines.
def preprocess(grid):
possible = []
nrows = len(grid)
ncols = len(grid[0])
for row in range(nrows):
possiblerow = []
for col in range(ncols):
possiblecell = []
for move, (drow, dcol) in MOVE_TABLE.items():
thisrow = row
thiscol = col
is_good_move = True
while True:
nextrow = thisrow + drow
nextcol = thiscol + dcol
if nextrow < 0 or nextrow >= nrows or nextcol < 0 or nextcol >= ncols:
break
if grid[nextrow][nextcol] == ROCK_SYM:
break
if grid[nextrow][nextcol] == MINE_SYM:
is_good_move = False
break
thisrow = nextrow
thiscol = nextcol
if grid[thisrow][thiscol] == ROUGH_SYM:
break
if is_good_move and (row != thisrow or col != thiscol):
possiblecell.append(move)
possiblerow.append(possiblecell)
possible.append(possiblerow)
return possible
# Search for possible solutions.
def try_moves(grid, possible, start):
nrows = len(grid)
ncols = len(grid[0])
ngems = sum(c == GEM_SYM for row in grid for c in row)
gemhash_table = {}
visited = {}
startrow, startcol = start
startset = set()
# Special case: We started on a squqre with a gem.
if grid[startrow][startcol] == GEM_SYM:
startset.add((startrow, startcol))
gemset = frozenset(startset)
gemhash = hash(gemset)
gemhash_table[gemhash] = gemset
visited.setdefault((startrow, startcol), set()).add(gemhash)
stack = [(start, '', gemhash)]
while stack:
(row, col), moves, gemhash = stack.pop()
for move in possible[row][col]:
drow, dcol = MOVE_TABLE[move]
thisrow = row
thiscol = col
newgems = []
while True:
nextrow = thisrow + drow
nextcol = thiscol + dcol
if nextrow < 0 or nextrow >= nrows or nextcol < 0 or nextcol >= ncols:
break
if grid[nextrow][nextcol] == ROCK_SYM:
break
thisrow = nextrow
thiscol = nextcol
if grid[thisrow][thiscol] == ROUGH_SYM:
break
if grid[thisrow][thiscol] == GEM_SYM:
newgems.append((thisrow, thiscol))
continue
if newgems:
# New gems were found on this move, so construct and hash a new gem list.
thisgems = gemhash_table[gemhash].union(newgems)
# Check if we have every gem.
if len(thisgems) >= ngems:
return [MOVE_CODE[m] for m in moves + move]
thisgemhash = hash(thisgems)
gemhash_table[thisgemhash] = thisgems
else:
thisgemhash = gemhash
# If we have already been to this square with the same set of gems
# as a prior visit, we can prune this branch of the search tree.
if thisgemhash in visited.get((thisrow, thiscol), set()):
continue
# Record that we have been here with this set of gems.
visited.setdefault((thisrow, thiscol), set()).add(thisgemhash)
# Add this move to the search queue.
stack.append(((thisrow, thiscol), moves + move, thisgemhash))
def inertia(grid: Tuple[str], start: tuple) -> Iterable[str]:
possible = preprocess(grid)
return try_moves(grid, possible, start)
if __name__ == '__main__':
def checker(function, grid, start):
result = function(grid, start)
GEM, ROUGH, ICE, ROCK, MINE = '$. X*'
MOVES = {'NW': (-1, -1), 'N': (-1, 0), 'NE': (-1, 1),
'W': ( 0, -1), 'E': ( 0, 1),
'SW': ( 1, -1), 'S': ( 1, 0), 'SE': ( 1, 1)}
grid, (x, y) = list(map(list, grid)), start
nb_rows, nb_cols = len(grid), len(grid[0])
for nb, move in enumerate(result, 1):
try:
dx, dy = MOVES[move]
except KeyError:
print(f"I don't understand your {nb}-th move: '{move}'.")
return False
while 0 <= x + dx < nb_rows and 0 <= y + dy < nb_cols and \
grid[x + dx][y + dy] != ROCK:
x, y = x + dx, y + dy
if grid[x][y] == ROUGH:
break
elif grid[x][y] == GEM:
grid[x][y] = ICE
elif grid[x][y] == MINE:
print(f"You are dead at {(x, y)}, bye!")
return False
try:
coord = next((i, j) for i, row in enumerate(grid)
for j, cell in enumerate(row) if cell == GEM)
except StopIteration:
print(f"Great, you did it in {nb} moves!")
return True
print(f"You have at least forgot one gem at {coord}.")
return False
GRIDS = (('5x5', (1, 1), ('*X$$.',
' .$*.',
'... X',
' *$* ',
'XXX*$')),
('7x6', (6, 1), ('**$. ',
'$*$.. ',
'X.**.$',
'*XX$ .',
'.X XX',
'X$* X$',
'$.* .')),
('5x10', (3, 8), (' X**$X.$X*',
'*$ X$.X*$.',
'* *X$..$$X',
'*. .* *. ',
'X.$.XX $ .')))
for dim, start, grid in GRIDS:
assert checker(inertia, grid, start), f'You failed with the grid {dim}.'
print('The local tests are done. Click on "Check" for more real tests.')
Dec. 25, 2018
