Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Quantum algorithm with entanglement between hobbits :-) solution in Clear category for Chicken Hunt by martin_b
# Quantum algorithm? Not yet :-)
# Just plain boring dijktra...
EMPTY = "."
ACTIVE_HOBBIT = "I"
OTHER_HOBBIT = "S"
OBSTACLE = "X"
CHICKEN = "C"
DIRS = {
"N": (-1, 0),
"S": (1, 0),
"E": (0, 1),
"W": (0, -1),
"NW": (-1, -1),
"NE": (-1, 1),
"SE": (1, 1),
"SW": (1, -1),
"": (0, 0),
}
MOVES = dict((v, k) for k, v in DIRS.items() if len(k))
def dijkstra(map, f, t, moves, allowed):
from heapq import heappop, heappush
q, seen = [(0, f, ())], set()
while q:
(cost, v1, path) = heappop(q)
if v1 not in seen:
seen.add(v1)
path += (v1,)
if v1 == t:
return cost, path
y, x = v1
for dy, dx in moves:
v2 = ny, nx = y + dy, x + dx
if 0 <= ny < len(map) and 0 <= nx < len(map[ny]) and map[ny][nx] in allowed and v2 not in seen:
heappush(q, (cost + 1, v2, path))
return None, None
def hunt(map):
retval = ""
mapw = len(map[0])
flatmap = "".join(map)
ay, ax = active = divmod(flatmap.index(ACTIVE_HOBBIT), mapw)
oy, ox = other = divmod(flatmap.index(OTHER_HOBBIT), mapw)
target = divmod(flatmap.index(CHICKEN), mapw)
# lower right hobbit must give way to upper left
if ay > oy or (ay == oy and ax > ox):
# find where the other hobbit will go
dist, p = dijkstra(map, other, target, MOVES, {EMPTY, CHICKEN})
if p:
ny, nx = p[1]
map = [list(r) for r in map]
map[oy][ox] = EMPTY
map[ny][nx] = OTHER_HOBBIT
# if the other hobbit goes to the position of the chicken
# move the chicken to some other place
if p[1] == target:
y, x = target
for dy, dx in MOVES:
ny, nx = y + dy, x + dx
if 0 <= ny < len(map) and 0 <= nx < len(map[ny]) and map[ny][nx] == EMPTY:
target = (ny, nx)
break
map = tuple("".join(r) for r in map)
dist, p = dijkstra(map, active, target, MOVES, {EMPTY, CHICKEN})
if p:
retval = MOVES[tuple(a - b for a, b in zip(p[1], p[0]))]
return retval
Oct. 21, 2017
Comments:
