Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
[actually inefficient] Maximize lit area with a priority queue solution in Clear category for Light Up by Phil15
'''
That makes fewer logical deductions than me when I play this game.
A state of the game is represented by three sets: lights, lit cells and
cells where we are sure there is no light.
We put these states in a queue, prioritizing states with
a maximal number of lit cells, thanks to heapq module.
Itertools module is used to compute light crosses and
combinations when there are multiple possibilities to put lights.
'''
from typing import Tuple, Set
from heapq import heappop, heappush
from itertools import combinations, takewhile, count
DARK, *MOVES = ' ', (-1, 0), (1, 0), (0, -1), (0, 1)
def light_up(grid: Tuple[str]) -> Set[Tuple[int]]:
nb_rows, nb_cols = len(grid), len(grid[0])
def is_dark(coords):
i, j = coords
return 0 <= i < nb_rows and 0 <= j < nb_cols and grid[i][j] == DARK
def ray(i, j, di, dj): # First time I use "itertools.takewhile".
return takewhile(is_dark, zip(count(i + di, di), count(j + dj, dj)))
def neighbors(*coords):
for move in MOVES: # at most the beginning of a ray in each direction.
for neighbor in ray(*coords, *move):
yield neighbor
break
def cross(*center): # A cross have a center and a ray in all 4 directions.
yield center
for move in MOVES:
yield from ray(*center, *move)
# Preprocess light crosses and neighbors of the numbers on walls.
crosses, nb_and_neighbors = {}, {}
for i, row in enumerate(grid):
for j, cell in enumerate(row):
if cell == DARK:
crosses[i, j] = set(cross(i, j))
elif cell.isdigit():
nb_and_neighbors[i, j] = int(cell), set(neighbors(i, j))
def check(lights: set, lit_cells: set, no_light: set):
""" Push the state on pqueue when it is not breaking a rule.
And make a few simple deductions. """
taken = lit_cells | no_light
new_lights, new_lit_cells = set(), set() # for simple deductions.
for i, row in enumerate(grid):
for j, cell in enumerate(row):
if cell.isdigit():
nb, neighbors = nb_and_neighbors[i, j]
if len(neighbors & lights) > nb:
return # Already too much lights for this number.
possible_lights = (neighbors & lights) | (neighbors-taken)
if len(possible_lights) < nb:
return # We can't put the required number of lights.
elif cell == DARK and (i, j) not in lit_cells:
free_cells_that_can_lit_ij = crosses[i, j] - taken
if not free_cells_that_can_lit_ij:
return # This dark cell can't be lit.
if len(free_cells_that_can_lit_ij) == 1: # deduction!
# (i, j) can only be lit from one cell, we put a light!
new_light = free_cells_that_can_lit_ij.pop()
if new_light not in new_lights: # only if it is new!
new_cross = crosses[new_light]
if new_cross & new_lights:
return # Two new lights are in conflict.
new_lights.add(new_light)
new_lit_cells |= new_cross
if new_lights:
return check(lights | new_lights,
lit_cells | new_lit_cells, no_light)
# Maximize the number of lit cells.
no_light -= lit_cells # No need to keep informations on lit cells.
heappush(pqueue, (- len(lit_cells), lights, lit_cells, no_light))
# Let's go!
nb_cells_to_lit, pqueue = len(crosses), [(0, set(), set(), set())]
while pqueue:
lit_nb, lights, lit_cells, no_light = heappop(pqueue)
if - lit_nb == nb_cells_to_lit: # All cells are lit, return lights.
return lights
for nb, neighbors in nb_and_neighbors.values():
# Take the first number with (neighboring) free dark cells.
nb_missing_lights = nb - len(neighbors & lights)
free_dark_cells = neighbors - lit_cells - no_light
if free_dark_cells:
break
else:
# Take the first cell where we know there is no light.
# Determine free dark cells that can lit it.
nb_missing_lights = 1
for cell in no_light:
free_dark_cells = crosses[cell] - lit_cells - no_light
break
if not nb_missing_lights:
# No missing light, so all free dark cells don't have light.
check(lights, lit_cells, no_light | free_dark_cells)
else:
# Put the number of missing lights among some free dark cells...
# Look for all combinations of these lights!
for choice in combinations(free_dark_cells, nb_missing_lights):
new_lights = lights | set(choice)
new_lit_cells = lit_cells.union(*map(crosses.get, choice))
check(new_lights, new_lit_cells, no_light)
March 9, 2019
Comments: