Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
move cube to colored cell and collect with bfs nearby colored cells solution in Clear category for Roll the cube by kdim
import time
from collections import deque
from typing import Set, Tuple
def roll_cube(dimensions: Tuple[int, int], start: Tuple[int, int], colored: Set[Tuple[int, int]], ) -> str:
"""
Cube as array of faces - DOWN, UP, LEFT, RIGHT, BACK, FRONT
Cube index of faces (1 - colored 0 - doesnt) - (0,1,1,0,1,0)
Cell identify as tuple of coordinates, cube and set of colored
( (1, 2), (1, 1, 1, 1, 0, 0), frozenset{(1, 2), (2, 3)} )
-coord- -------cube------- ----------colored--------
Algorithm:
1 - go to the cell nearby the random painted,
go with steps - two forward, one backward, one forward,
such steps do not change the state of the cube and colored cells
2 - with the BFS collect all the painted cells around
BFS in my case is slow. While I limited the depth of the path,
by sampling came to a length of 10, it works acceptably.
The slowest search occurs when there is only one unpainted up side on the cube
and it itself is on the colored cell.
What other algorithms can be used and how can performance be improved, help me?
"""
def directions(cell, mini, maxi, minj, maxj):
(i, j) = cell[0]
dir = {(0, -1): 'W', (0, 1): 'E', (-1, 0): 'N', (1, 0): 'S'}
for di, dj in ((0, -1), (0, 1), (-1, 0), (1, 0)):
if mini <= i + di <= maxi and minj <= j + dj <= maxj:
yield dir[(di, dj)]
def move(cell, dir):
(i, j), cube, color = cell
MOVE = {'W': ((i, j - 1), cube[2:4] + cube[0:2][::-1] + cube[4:6]),
'E': ((i, j + 1), cube[2:4][::-1] + cube[0:2] + cube[4:6]),
'N': ((i - 1, j), cube[4:6][::-1] + cube[2:4] + cube[0:2]),
'S': ((i + 1, j), cube[4:6] + cube[2:4] + cube[0:2][::-1])}
(i, j), cube = MOVE[dir]
if cube[0] and (i, j) not in color:
color = color.union({(i, j)})
cube = (0,) + cube[1:]
elif not cube[0] and (i, j) in color:
color = color.difference({(i, j)})
cube = (1,) + cube[1:]
return (i, j), cube, color
def bfs(start):
(si, sj), (mi, mj) = start[0], dimensions
mini, maxi = si - (0 < si), si + (si + 1 < mi)
minj, maxj = sj - (0 < sj), sj + (sj + 1 < mj)
around_colored = sum(start[1]) + sum(abs(si - ci) < 2 and abs(sj - cj) < 2 for ci, cj in start[2])
queue = deque([start])
visited = deque([])
path = {start: ''}
while queue:
cell = queue.popleft()
if sum(cell[1]) == around_colored:
return cell, path[cell]
visited.append(cell)
if len(path[cell]) > 10:
continue
for dir in directions(cell, mini, maxi, minj, maxj):
next = move(cell, dir)
if next not in visited and next not in queue:
queue.append(next)
path[next] = path[cell] + dir
return cell, path[cell]
def movetocolor(cell):
if not cell[2]:
return cell, ''
(si, sj) = cell[0]
(ci, cj), *_ = cell[2]
n, m, path = ci - si, cj - sj, ''
pi = 'NNSN' * (-n // 2) if n < 0 else 'SSNS' * (n // 2)
pj = 'WWEW' * (-m // 2) if m < 0 else 'EEWE' * (m // 2)
for dir in pi + pj:
cell = move(cell, dir)
path += dir
if not cell[2]:
break
return cell, path
fullpath, cell = '', (start, (0, 0, 0, 0, 0, 0), frozenset(colored))
while cell[2]:
cell, path = movetocolor(cell)
fullpath += path
cell, path = bfs(cell)
fullpath += path
return fullpath
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 = [
((10, 10), (0, 0), {(0, 1), (0, 2), (1, 0), (1, 1), (2, 0), (9, 9)}),
((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)}),
((20, 20), (1, 1), {(1, 0), (0, 1), (1, 2), (2, 1), (15, 19), (19, 15)}),
((15, 2), (0, 0), {(1, 0), (2, 1), (3, 0), (4, 1), (5, 0), (14, 1)}),
((4, 4), (2, 2), {(0, 0), (0, 3), (1, 2), (2, 1), (3, 0), (3, 3)}),
((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)}),
((100, 100), (3, 9), {(25, 4), (25, 5), (25, 8), (4, 25), (99, 99), (0, 0)}),
]
stime = time.time()
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.')
print('You did it in %.1f seconds.' % (time.time() - stime))
Feb. 25, 2021
