Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
breadth-first search solution in Clear category for Supply Line by David_Jones
from collections import deque
def neighbors(cell):
(x,y) = map(ord, cell)
k = 1 - 2 * (x % 2)
for (dx,dy) in ((0,-1), (0,1), (1,0), (-1,0), (-1,k), (1,k)):
if 64 < x+dx < 77 and 47 < y+dy < 58:
yield chr(x+dx) + chr(y+dy)
def supply_line(you, depots, enemies):
forbidden_cells = set(enemies)
for enemy in enemies:
forbidden_cells |= set(neighbors(enemy))
queue = deque([(you, 0)])
while queue:
current_cell, d = queue.popleft()
if current_cell in depots:
return d
forbidden_cells.add(current_cell)
for neighbor in neighbors(current_cell):
if neighbor not in forbidden_cells:
queue.append((neighbor, d+1))
June 24, 2019
