Recursive uniform cost search that needs to be optimized

Question

I have this uniform cost search that I created to solve Project Euler Questions 18 and 67. It takes the numbers in the txt file, places them into a two dimensional list, and then traverses them in a uniform cost search (that I hoped was a kind of implementation of an a* search). It looks like this:

f = open('triangle.txt', 'r')
actualRows = [[n for n in p.split(" ")] for p in f.read().split('\n')]
actualRows.pop()
actualRows = [[int(n) for n in p] for p in actualRows]
rows = [[100 - n for n in p] for p in actualRows]

def astar(pq):
    m = min(pq,key=lambda w: w[3])
    if len(m[2]) + 1 is len(actualRows):
        return m
    pq.remove(m)
    toAdd = list(m[2])
    toAdd.append(m[0])
    pq.append((actualRows[m[4]+1][m[5]], rows[m[4]+1][m[5]], toAdd, m[3] + m[1], m[4]+1, m[5]))
    pq.append((actualRows[m[4]+1][m[5]+1], rows[m[4]+1][m[5]+1], toAdd, m[3] + m[1], m[4]+1, m[5]+1))
    return astar(pq)

# Each tuple is: (actualScore, minScore, previous, totalScore, y, x)
priorityQueue = [(actualRows[0][0], rows[0][0], [], 0, 0, 0)]
a = astar(priorityQueue)
print a
print str(sum(a[2]) + a[0])

I'm not asking for you to tell me how to solve the Problem, I just want to optimize this search so that it doesn't crash going past the 17th row of numbers. How would I optimize this? Or how would I write a proper uniform cost search?

Answer 1

You mentioned in the comments that the size of the triangle is hard-coded into the code. The very first thing you should do is make this a variable which you declare at the start of your code. (In many other languages, this would be a constant). You also use the number 100 in line 5. If this is supposed to be one more than the number of lines, it should be defined in terms of the same constant, so that the two can be changed in the same place. (Edit: I see from the problem that 99 and 100 are not related. If you had had two variables, NUM_ROWS and MAX_VALUE defined at the top, the meaning of each of the numbers would have been clear to me immediately.)

A level of sophistication above, but still very easy, would be to give some reasonable error to a user like @JanneKarila who has used the wrong number of lines. This might be overkill for code that you and only you are ever going to run, but a one-line check with an error message might help you if you debug using the wrong file (it's easy to spend hours taking your program to pieces and forget to check which input you are using), and it makes life much easier for anyone else who wants to try it.

Another stylistic thing which can be very important - for me the hardest part of your code to read is the lines that start pq.append. For each expression on these lines, I have to glance several times back to the definition of priorityQueue and the comment with it to find out exactly what each element of your tuple represents. If you defined a very simple class, then rather than m[3] + m[1] I would see m.totalScore + m.currentValue. Just doing this by itself would make the code easier to read (these two lines are going to be among the most important to debug). It might be the case that your class could also have methods or 'smart' constructors which could do some of the trickier work and make your inner loop more readable.

Ultimately, I don't think it is realistic to 'optimize' this program to be able to solve a problem of the same size as Euler problem 67. If you try and store the lists inside your tuples more efficiently you might get to 18, 19 or 20 levels before crashing. However, the fundamental flaw of the algorithm is that you are going to store almost every path in your list in priorityQueue, with probably up to half of them present at any one time. This is unworkable from a memory perspective (the number of paths grows very rapidly as you increase the size of the triangle) and also from a run time perspective (if you try and measure the time taken for levels up to 17 you should be able to see this). Using the a* algo has made it a little bit less obvious to see that you are doing exactly what the Project Euler page recommends against - trying all paths. (EDIT: I didn't run the code. Turns out a stack overflow and not running out of memory is the reason for your crash. If you get rid of the recursion as suggested in @JanneKarila's answer, you will probably make it to quite a few more levels before running out of memory, but still nowhere near 100. The comments below still apply.)

You need to go back to the drawing board and think of another way to solve the problem. A good starting point is to try and solve a few small triangles by hand, and see what methods you come across. Don't worry though - writing this program has given you a chance to learn both about an interesting algo and some things about programming, which I'm sure have made it worthwhile.

Answer 2

• Unpack your tuple to improve readability. There's already a comment

  # Each tuple is: (actualScore, minScore, previous, totalScore, y, x)
  

  Put those names in code like this so you can use eg. actualScore instead of m[0]:

  (actualScore, minScore, previous, totalScore, y, x) = m
  

• You are using recursion to implement a simple loop. I get RuntimeError: maximum recursion depth exceeded even from problem 18. That's because you recurse from every node on every path until you find a solution. Just use a while loop instead.

• Use the heapq module to implement a priority queue to avoid the linear search done by min.
• Compare numbers using ==. Only use is for object identity.

---

• To learn about the A* algorithm, see the highly readable tutorial at Amit’s A* Pages.
• You'll notice that your approach is different. In particular, you don't compute a heuristic. On the other hand I'm not sure if a useful heuristic exists for this problem, but in any case your approach is more like Dijkstra'a algorithm.
• You should keep track of already visited nodes to avoid exploring the same multiple times.
• When you add nodes to the priority queue, you should already compute their scores. Now you add both children with the score of the parent. When you eventually pop these nodes from the queue, you get the left child even though you need the better one first. Try the small example at the top of the problem 18 page: program answers 19 instead of 23, because at the bottom row the 5 pops from the queue before the 9.