Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Speedy category for Roll the cube by _Chico_
from typing import Set, Tuple
from collections import deque
MOVES = {'N': (-1, 0), 'S': (1, 0), 'W': (0, -1), 'E': (0, 1)}
ROLL = {
'N': dict(zip('DUNSWE', 'SNDUWE')),
'S': dict(zip('DUNSWE', 'NSUDWE')),
'W': dict(zip('DUNSWE', 'EWNSDU')),
'E': dict(zip('DUNSWE', 'WENSUD')),
}
def trim(*data):
(height, width), pos, colored = data
if (height, width) in {(2, 4), (4, 2), (3, 3)}:
return data
top, left, bottom, right = height - 1, width - 1, 0, 0
for i, j in colored | {pos}:
top, left = min(top, i), min(left, j)
bottom, right = max(bottom, i), max(right, j)
height, width = bottom - top + 1, right - left + 1
if min(height, width) == 1:
return data
pos = pos[0] - top, pos[1] - left
colored = frozenset((i - top, j - left) for i, j in colored)
return (height, width), pos, colored
def roll_cube(
dimensions: Tuple[int, int],
start: Tuple[int, int],
colored: Set[Tuple[int, int]],
) -> str:
height, width = dimensions
used = set()
que = deque([(height, width, start, frozenset(), frozenset(colored), tuple())])
while que:
height, width, (i, j), faces, colored, path = que.popleft()
if ((i, j), faces, colored) in used:
continue
used.add(((i, j), faces, colored))
data = ((height, width), (i, j), colored)
trim_data = trim(*data)
if trim_data != data:
(height, width), (i, j), colored = trim_data
que.clear()
used.clear()
if len(faces) == 6:
res = "".join(path)
return res
hop_step_jump = False
if path and "D" not in faces and min(height, width) > 3:
for ci, cj in colored:
if path[-1] in "NS" and ci == i:
break
if path[-1] in "WE" and cj == j:
break
else:
hop_step_jump = True
for move, (di, dj) in MOVES.items():
if hop_step_jump and move != path[-1]:
continue
next_pos = ni, nj = i + di, j + dj
if not (0 <= ni < height and 0 <= nj < width):
continue
next_faces = frozenset(map(ROLL[move].get, faces))
b1 = next_pos in colored and 'D' not in next_faces
b2 = next_pos not in colored and 'D' in next_faces
if b1:
next_faces |= {"D"}
next_colored = colored - {next_pos}
elif b2:
next_faces -= {"D"}
next_colored = colored | {next_pos}
else:
next_colored = colored
next_path = path + (move,)
que.append((height, width, next_pos, next_faces, next_colored, next_path))
if __name__ == '__main__':
def checker(data, user_result):
(nrows, ncols), pos, colored = data
assert isinstance(user_result, str), 'You must return a string.'
assert user_result, 'You must return some directions to roll the cube.'
forbidden_chars = ''.join(sorted(set(user_result) - set('NSWE')))
assert not forbidden_chars, \
'You must return NSWE directions, not %r.' % forbidden_chars
MOVES = {'N': (-1, 0), 'S': (1, 0), 'W': (0, -1), 'E': (0, 1)}
ROLL = {
'N': dict(zip('DUNSWE', 'SNDUWE')),
'S': dict(zip('DUNSWE', 'NSUDWE')),
'W': dict(zip('DUNSWE', 'EWNSDU')),
'E': dict(zip('DUNSWE', 'WENSUD')),
}
faces = set()
for nsteps, move in enumerate(user_result, 1):
(r, c), (dr, dc) = pos, MOVES[move]
r, c = pos = r + dr, c + dc
assert 0 <= r < nrows and 0 <= c < ncols, \
'Step %d: you are outside the grid at %s.' % (nsteps, pos)
faces = set(map(ROLL[move].get, faces))
b1 = pos in colored and 'D' not in faces
b2 = pos not in colored and 'D' in faces
if b1:
faces.add('D')
colored.remove(pos)
if len(faces) == 6:
break
if b2:
faces.remove('D')
colored.add(pos)
else:
message = 'After %d steps, there are %d face(s) still uncolored.'
raise AssertionError(message % (nsteps, 6 - len(faces)))
assert len(user_result) == nsteps, "It's colorful, stop rolling."
return nsteps
TESTS = [
((4, 2), (2, 1), {(0, 0), (0, 1), (1, 0), (2, 0), (3, 0), (3, 1)}),
((3, 3), (2, 1), {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0)}),
((4, 4), (1, 3), {(0, 0), (1, 2), (2, 1), (3, 0), (3, 2), (3, 3)}),
((4, 4), (2, 2), {(0, 0), (0, 3), (1, 2), (2, 1), (3, 0), (3, 3)}),
((10, 10), (3, 9), {(0, 4), (2, 9), (3, 8), (4, 0), (4, 9), (7, 7)}),
]
for dimensions, start, colored in TESTS:
try:
user_result = roll_cube(dimensions, start, colored.copy())
print('Your result:', user_result)
nsteps = checker((dimensions, start, colored.copy()), user_result)
print('You did it in %d steps.' % nsteps)
except AssertionError as error:
print('Test dimensions=%s, start=%s failed:' % (dimensions, start))
print(error.args[0])
break
print()
else:
print('Well done! Click on "Check" for more tests.')
May 10, 2021
