Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Supply Line by PanchOkamoto
from collections import deque
from string import ascii_uppercase
def supply_line(you, depots, enemies):
zoc_map = ZocHexMap(12, 9)
zoc_map.you = you
zoc_map.depots = depots
zoc_map.set_enemies(enemies)
return count_shortest_line(zoc_map)
def count_shortest_line(zoc_map):
lines = {zoc_map.you: [zoc_map.you]}
queue = deque([zoc_map.you])
while queue:
cell = queue.popleft()
adjacent = zoc_map.adjacent(cell)
for a in adjacent:
if a not in lines and a not in zoc_map.enemy_area:
queue.append(a)
lines[a] = lines[cell] + [a]
to_depots = [lines[d] for d in zoc_map.depots if lines.get(d)]
return min(len(td) for td in to_depots)-1 if to_depots else None
class ZocHexMap:
def __init__(self, width, height):
self.width = width
self.height = height
self.you = None
self.depots = None
self.enemy_area = set()
def set_enemies(self, enemies):
for e in enemies:
self.enemy_area |= self.adjacent(e) | {e}
def adjacent(self, cell):
col, row = ascii_uppercase.index(cell[0]), int(cell[1])-1
result = {(col, row-1), (col, row+1), (col-1, row), (col+1, row)}
if col % 2 == 0:
result |= {(col-1, row-1), (col+1, row-1)}
else:
result |= {(col-1, row+1), (col+1, row+1)}
result = {r for r in result
if 0 <= r[0] < self.width
and 0 <= r[1] < self.height}
return {'{}{}'.format(str(ascii_uppercase[i]), str(j+1))
for i, j in result}
if __name__ == '__main__':
assert supply_line("B4", {"F4"}, {"D4"}) == 6, 'simple'
assert supply_line("A3", {"A9", "F5", "G8"}, {"B3", "G6"}) == 11, 'multiple'
assert supply_line("C2", {"B9", "F6"}, {"B7", "E8", "E5", "H6"}) is None, 'None'
assert supply_line("E5", {"C2", "B7", "F8"}, set()) == 4, 'no enemies'
assert supply_line("A5", {"A2", "B9"}, {"B3", "B7", "E3", "E7"}) == 13, '2 depots'
print('"Run" is good. How is "Check"?')
Jan. 10, 2019
