Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Digging a Canal by Miaou
import heapq
from itertools import permutations
# I'm back with Dijkstra ! This one's taken from my Snake solution,
# which was inspired from 8Puzzle, wich was inspired from ... so many.
# The 8puzzle solution has a *big* doc.
# A situation represents which cells are dug to reach that cell.
# cost is implicit : it is len(lDug)
class Situation:
def __init__(self,i,j,tDug,prevNode):
"i,j of head, cost, previousNode, absolute direction, is winning."
self.__dict__.update(locals())
def reachableSituations(self,field):
lReach = []
for di,dj in permutations([-1,0,1],2):
if di*dj:
continue
i,j = self.i+di,self.j+dj
if i not in range(len(field)) or j not in range(len(field[0])):
continue
if field[i][j]:
lReach.append(Situation(i,j,self.tDug+((i,j),),self))
else:
lReach.append(Situation(i,j,self.tDug,self))
return lReach
def __eq__(s,o):
return (s.i,s.j) == (o.i,o.j)
def __hash__(s):
return hash((s.i,s.j))
def checkio(data):
# I prepend a row of empty cells north, so that algorithm will choose it's starting point
# I append a row of empty cells south, so that algo will choose ending point
field = [[0]*len(data[0])] + data + [[0]*len(data[0])]
sExplored = set()
initSit = Situation(0,0,(),None)
n = 0
sCandidates = {initSit}
lCandidates = [(len(initSit.tDug),n,initSit)]
# Dijkstra
while sCandidates:
# Pick best candidates
sit = heapq.heappop(lCandidates)[2]
if sit.i == len(field)-1:
break # Win !
sCandidates.remove(sit)
sExplored.add(sit)
for newSit in sit.reachableSituations(field):
if newSit not in sExplored|sCandidates:
n += 1
sCandidates.add(newSit)
heapq.heappush(lCandidates, (len(newSit.tDug),n,newSit))
return len(sit.tDug)
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([[1, 1, 1, 1, 0, 1, 1],
[1, 1, 1, 1, 0, 0, 1],
[1, 1, 1, 1, 1, 0, 1],
[1, 1, 0, 1, 1, 0, 1],
[1, 1, 0, 1, 1, 1, 1],
[1, 0, 0, 1, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 1]]) == 2, "1st example"
assert checkio([[0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 0, 1, 1],
[1, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0]]) == 3, "2nd example"
assert checkio([[1, 1, 1, 1, 1, 0, 1, 1],
[1, 0, 1, 1, 1, 0, 1, 1],
[1, 0, 1, 0, 1, 0, 1, 0],
[1, 0, 1, 1, 1, 0, 1, 1],
[0, 0, 1, 1, 0, 0, 0, 0],
[1, 0, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 1, 1, 1, 1]]) == 2, "3rd example"
June 21, 2013
Comments:
