Project Euler problem 83 – how creeps can help
June 19th, 2009 at 5:10 pmProblems 18, 67, 81, 82 and 83 in Project Euler are quite similar, but increase in level of difficulty.
For all of these except 83 I’ve used a specialized dynamic-programming solution that worked quite well. Being recursive it was a tiny bit slower than the iterative approaches others have used, but I believe recursive solutions are more elegant.
Anyway, project 83 proved too hard for my approach, because it introduces real cycles into the paths. So, this time I had to arm myself with a real path-finding algorithm. Luckily, I’ve coded a pretty generic implementation of the A* algorithm quite recently for my Creeps PyGame demo.
A*, however, requires a heuristic to do its magic, and for problem 83 there’s no real heuristic. However, since a constant heuristic is acceptable and effectively “dumbs down” A* to the original Dijkstra algorithm (the heuristic of A* must be non-decreasing, which a constant satisfies), I was able to make use of the code from the Creeps game to find a solution in 0.3 seconds, with only 30 lines of code.
Related posts:
June 21st, 2009 at 03:52
Oy ye of little faith! A simple A* Heuristic solves this problem in a fraction of a second on my 1GHz laptop. 50 lines of python including comments and vertical whiespace.
Some things to remember about A*:
- the heapq module is your friend
- If you arrive at a node with a cost higher than you’ve seen at this node before you can toss out the current info, that path was a dead end.
- the Heuristic doesn’t need to be complicated (that’s a hint)
Here is the skeleton of my main routine
def main(score_function):
..stack = []
..def push(pos, cost):
….score = score_function(pos, cost)
….heapq.heappush(stack, (score, (pos, cost)))
..def pop():
….score, (pos, cost) = heapq.heappop(stack)
….return pos, cost
..while stack:
….cur_pos, cur_cost = pop() # lowest ’score’ entry to date
….# do stuff
The reason the score function is passed in is so you can try new ones easily.
June 21st, 2009 at 04:08
Ahh, nevermind. You’re saying that A* collapses to Dijkstra.
July 8th, 2009 at 07:07
Hey i tried using A star to solve this problem and I get the correct answer but it is so AWFULLY sloww (500 secs). My program looks at all 6400 cells, what do you think I am doing wrong?
heuristic:
[code]
def h(n, goal):
....return 11 * (abs(n.col - goal.col) + abs(n.row - goal.row))
[/code]
If i change the 11 to a bigger number I get the wrong answer.
Any suggestions
[code]
def astar(start, goal, matrix):....closedset = []
....openset = []
....start.hscore = h(start, goal, matrix)
....start.fscore = start.hscore + start.gscore
....openset.append(start)
....while openset:
........x = None # find node with lowest fscore
........for n in openset:
............if not x or n.fscore < x.fscore:
................x = n
if x.row == goal.row and x.col == goal.col:
return x.gscore
print x.row, x.col, len(closedset), x.fscore
openset.remove(x)
closedset.append(x)
neighbors = []
if x.row != len(matrix)-1:
neighbors.append(matrix[x.row+1][x.col])
if x.row != 0:
neighbors.append(matrix[x.row-1][x.col])
if x.col != len(matrix[0])-1:
neighbors.append(matrix[x.row][x.col+1])
if x.col != 0:
neighbors.append(matrix[x.row][x.col-1])
........for y in neighbors:
............if y in closedset:
................continue
gscore = x.gscore + y.gscore
better = False
if not y in openset:
openset.append(y)
y.hscore = h(y, goal, matrix)
better = True
elif gscore < y.gscore:
better = True
if better:
y.parent = x
y.gscore = gscore
y.fscore = y.gscore + y.hscore
return None
[/code]
Sorry for the long code =/
July 9th, 2009 at 05:46
@Python Coder,
Perhaps you could use a real ’set’ or a dict type for the open and closed sets instead of lists? Removing from a list is O(n).
You can download and compare my A* code from the Creeps game link I provided – it’s quite short and simple, and well commented.
July 9th, 2009 at 22:28
thanks, after changing closedset and openset to sets it runs in a little over 2 seconds, wow!
such a difference it makes