Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Supply Line by alterGNU
# MATRICE/GRID:
# - [a, b, c] : a:type(-1:enemy,0:empty,1:depots) ; b:state (0:not visited, 1:visited); c:step (distance from start)
# Ex:
# - [0, 0, x] : empty case never visited with a distance of x step from the start case
# - [0, 1, x] : empty case already visited with a distance of x step from the start case
# - [-1, 0, x] : ennemy case (can't be visited, you fool) (x step distance)
# - [1, 0, x] : depots case (can't be visited:this is the end!) (with x step distance)
# -[ UTILITAIRES ]----------------------------------------------------------------------------------
# Is x even???
even = lambda x: True if (x%2 == 0) else False
# Convert case"LetterNumber" to (line & row) tuple
convertuple = lambda s: (int(s[1])-1,ord(s[0])-ord("A"))
# Convert (line & row) to case"LetterNumber" tuple
convertstr = lambda pt: chr(pt[1]+ord("A"))+str(int(pt[0])+1)
# -[ HEXA GRID MOVEMENTS ]--------------------------------------------------------------------------
# Y-AXIS movements: always the same
N = lambda pt: (pt[0]-1,pt[1]) if (pt[0]>0) else None
S = lambda pt: (pt[0]+1,pt[1]) if (pt[0]<8) else None
# X-AXIS movements: change if columns is even or not:
right = lambda pt: (pt[0],pt[1]+1) if (pt[1]<11) else None
left = lambda pt: (pt[0],pt[1]-1) if (pt[1]>0) else None
even_NE = lambda pt: right(N(pt)) if (N(pt)!=None)and(N(pt)!=None) else None
even_SE = lambda pt: right(pt)
even_NW = lambda pt: left(N(pt)) if (N(pt)!=None)and(N(pt)!=None) else None
even_SW = lambda pt: left(pt)
odd_NE = lambda pt: right(pt)
odd_NW = lambda pt: left(pt)
odd_SE = lambda pt: right(S(pt)) if (S(pt)!=None)and(S(pt)!=None) else None
odd_SW = lambda pt: left(S(pt)) if (S(pt)!=None)and(S(pt)!=None) else None
NE = lambda pt: even_NE(pt) if even(pt[1]) else odd_NE(pt)
NW = lambda pt: even_NW(pt) if even(pt[1]) else odd_NW(pt)
SE = lambda pt: even_SE(pt) if even(pt[1]) else odd_SE(pt)
SW = lambda pt: even_SW(pt) if even(pt[1]) else odd_SW(pt)
# -[ NEIGHBOURS CASES ]-------------------------------------------------------------------------------------------------
adjacent = lambda c: [ N(c), NE(c), NW(c), S(c), SW(c), SE(c) ]
def create_grid(depots, enemies):
# init the 9*12 grid with [0, 0, 0]
(l, c)=(9,12)
grid = []
for i in range(l):
row = []
for j in range(c):
row.append([0,0,0])
grid.append(row)
# Add depots : in this order, depots can be replaced by enemy zoc => depots in enemy-zoc are not depots anymore!
for d in depots:
(l, c)=convertuple(d)
grid[l][c]=[1,0,0]
# Add enemies : state always 1 as they can't be visited
for e in enemies:
x = convertuple(e)
grid[x[0]][x[1]]=[-1,1,0]
zoc = [ z for z in adjacent(x) if z!=None]
for (l,c) in zoc:
grid[l][c]=[-1,1,0]
return grid
def shortest_path(grid, you):
# Variables
start = convertuple(you)
queue = []
# Functions
enqueue = lambda c: queue.append(c)
dequeue = lambda : queue.pop(0)
visitable = lambda c: (c!=None)and(grid[c[0]][c[1]][0] >= 0)
def visited(c):
grid[c[0]][c[1]][1]=1
def update_step(a, n):
oldValue=grid[n[0]][n[1]][2]
newValue=grid[a[0]][a[1]][2]+1
if (oldValue==0)or((oldValue!=0)and(newValue 0:
elem = dequeue()
visited(elem)
neighbours = [n for n in adjacent(elem) if visitable(n) ]
for n in neighbours:
update_step(elem,n)
if grid[n[0]][n[1]][0] == 1:
return grid[elem[0]][elem[1]][2]+1
if grid[n[0]][n[1]][1] == 0:
queue.append(n)
return None
supply_line = lambda you, depots, enemies: shortest_path(create_grid(depots, enemies),you)
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"?')
May 28, 2021
