Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
heap on complex plane solution in Clear category for Roll the cube by ogoro
from heapq import heappop, heappush
NEIGHBOURS = 1j, 1, -1j, -1
DIRECTIONS = 'ESWN'
FACES_COUNT = 6
class Cube:
def __init__(self):
self.equator = [1, 2, 6, 5]
self.meridian = [1, 4, 6, 3]
self.colored = set()
rotate_right = staticmethod(lambda perimeter: perimeter.append(perimeter.pop(0)))
rotate_left = staticmethod(lambda perimeter: perimeter.insert(0, perimeter.pop()))
@staticmethod
def copy_even_elements(a, b):
a[0], a[2] = b[0], b[2]
def turn(self, direction):
if direction == 'E':
self.rotate_right(self.equator)
self.copy_even_elements(self.meridian, self.equator)
elif direction == 'W':
self.rotate_left(self.equator)
self.copy_even_elements(self.meridian, self.equator)
elif direction == 'S':
self.rotate_right(self.meridian)
self.copy_even_elements(self.equator, self.meridian)
elif direction == 'N':
self.rotate_left(self.meridian)
self.copy_even_elements(self.equator, self.meridian)
@property
def current_face(self):
return self.equator[0]
def paint(self, face):
self.colored.add(face)
def copy(self):
new_cube = Cube()
new_cube.equator = self.equator.copy()
new_cube.meridian = self.meridian.copy()
new_cube.colored = self.colored.copy()
return new_cube
def roll_cube(dimensions, start, colored):
height, width = dimensions
map_colored = {complex(re, im) for re, im in colored}
all_cells = {complex(re, im) for im in range(width) for re in range(height)}
tick = 0
history = set()
q = [(0, tick, complex(*start), Cube(), map_colored, '')]
while q:
priority, _, a, cube, map_colored, path = heappop(q)
for b, direction in ((a + neighbour, direction) for neighbour, direction
in zip(NEIGHBOURS, DIRECTIONS)
if a + neighbour in all_cells):
new_map_colored = map_colored.copy()
new_cube = cube.copy()
new_cube.turn(direction)
if new_cube.current_face not in new_cube.colored and b in map_colored:
new_map_colored.remove(b)
new_cube.colored.add(new_cube.current_face)
if new_cube.current_face in new_cube.colored and b not in map_colored:
new_cube.colored.remove(new_cube.current_face)
new_map_colored.add(b)
uncolored_count = FACES_COUNT - len(new_cube.colored)
if uncolored_count == 0:
return path + direction
current_hash = hash((b, tuple(new_cube.colored), tuple(new_map_colored)))
if current_hash in history:
continue
history.add(current_hash)
priority = uncolored_count
tick += 1
new_entry = (priority, tick, b, new_cube, new_map_colored, path + direction)
heappush(q, new_entry)
March 15, 2021
Comments:
