Project Euler

As mentioned in the previous post, I've started working on Project Euler. I've just completed the first 50 puzzles, so I thought I'd share my solutions here.

My language of choice was Python, for a couple of reasons. First, I'm still trying to teach it to myself, so implementing several small programs is a good way to do that. Second, Python natively supports arbitrary-precision integers, which is necessary for some of the programs in Project Euler. Lastly, since it is a scripting language it allows a rapid development cycle.

So far, I've been able to stick to the additional constraint of keeping the runtime of my programs under a minute. Many of these programs have an obvious brute-force solution, but the more elegant, faster solution (that takes under a minute) is a bit more elusive.

Since Blogger apparently doesn't allow attachments in blog posts, here is the URL for my solutions:
http://cseweb.ucsd.edu/~mstepp/euler/projecteuler.1-50.zip

There are currently over 300 programs in Project Euler, and I hope to eventually finish them all, but a man can only procrastinate so much in a given week.

Permutations

I've recently begun working my way through ProjectEuler, and so I've had to write some code to generate permutations of lists. One way to do this is to generate all the permutations up front, in a list of lists. Below is the Python code:

def perms(l):
    if len(l) == 0: return [[]]
    result = []
    for i in range(len(l)):
        first = l[i]
        rest = l[:i] + l[i+1:]
        rperms = perms(rest)
        rperms = [[first]+p for p in rperms]
        result.append(rperms)
    return result

So, for example, a call to perms([0,1,2]) yields [[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]].

This works fine when your original list is small. Keep in mind, however, that the number of permutations is N! for a list of length N, so your result list will get large quickly.

When your list is too large to store all the permutations in memory at once, a slightly altered version of same algorithm can give them to you one by one via a callback function:

def perms(l,sofar,func):
    if len(l) == 0: 
        func(sofar)
        return
    for i in range(len(l)):
        first = l[i]
        sofar.append(first)
        rest = l[:i] + l[i+1:]
        perms(rest,sofar,func)
        sofar.pop()

This version takes 3 parameters: the first is the original list, the second is a partial result list (initially []), and the third is a function that will be called on each permutation as it is generated.

So a call to perms([0,1,2],[],func) will end up calling
func([0,1,2])
func([0,2,1])
func([1,0,2])
func([1,2,0])
func([2,0,1])
func([2,1,0])

The memory overhead for this version is O(N), since it only generates one permutation at a time.

One remaining problem with this version is that there is no way to stop early. If you are searching through all the permutations of [1,...,25] looking for one particular value, then once you find it you probably don't want to generate the other ~25! permutations. So, by changing the callback function so that it returns a boolean, we can make a version that has an early termination condition:

def perms(l,sofar,func):
    if len(l) == 0: 
        return func(sofar)
    for i in range(len(l)):
        first = l[i]
        sofar.append(first)
        rest = l[:i] + l[i+1:]
        if not(perms(rest,sofar,func)):
            return False
        sofar.pop()
    return True

Even with the one-at-a-time version, and even with the early-out ability, one should keep in mind that a modern computer can't handle an N! computation for N bigger than around 12.

Graph equality 3: toString

Last post about rooted, directed graphs, I swear.

It may be useful to find a canonical string representation for a given graph. In Java terms, how would one write the toString() method that would make all equivalent graphs look equal?

Here's the code:

String toString(graph g) {
   return toString(root(g), [])
}
String toString(node n, linkedlist path) {
   // check to see if I'm in the path already
   for each index i of path:
      if equiv(n, path[i])
         return "\" + (length(path)-i)   // return the Debruijn index

   result = label(n) + "("
   addLast(path, n)
   for each index i of children(n):
      if i>0: result += ","
      result += toString(children(n)[i], path)
   removeLast(path)
   result += ")"

   return result
}

If you had a structure like theta(0,+(1,theta(0,+(1,\2)))) then it would print out as theta(0,+(1,\2)), as would theta(0,+(1,theta(0,+(1,\4)))) and every other variant.

Note that this relies on the equiv test from the first post, but also once you have written toString it can serve as an equivalence test itself since it canonicalizes the graphs.

Graph equality 2: hash codes

In the last post I described an algorithm for detecting when two rooted, directed graphs are equivalent. Now I will describe how to compute a hashcode for such graphs.

This problem is again interesting in the setting of PEGs and recursive types. Computing a hashcode on a recursive structure can be a pain. Doing so in a way that gives all equivalent structures the same hashcode is even trickier. However, it turns out that there is a simple way to do this. The main trick is: give up some accuracy.

You hashcode function doesn't have to be as accurate as your equality function. (Note: in the back of my mind, I'm thinking of the Java way of doing things, where your 'equals' method and your 'hashCode' method should always agree). The only invariant you must maintain is

 A.equals(B)  =>  A.hashCode() == B.hashCode()

So, the solution is to not even compute a hashcode for the entire structure. You can simply compute a hashcode for all nodes that have distance less than N away from the root node. Any rooted directed graph can be thought of as a tree. If it has cycles, then it becomes an infinite tree. We simply take the tree (infinite or not) and chop it at the N-th level down. Then we compute the hashcode for just the remaining tree. For instance, say you have the structure: theta(0,+(1,\2)).
If you set your N-value at 4, you will actually compute the hashcode of the following tree:

        theta
        /   \
       0     +
            / \
           1  theta 
              /   \
             0     +
                  / \
                 1  theta

You essentially completely unfold all recursive structures, but only up to a certain depth. If the two structures are indeed equivalent, then they will produce the same tree. If they are not, then they may or may not produce the same tree. The N value you pick controls how closely your hash function agrees with your equality function.

The time complexity of this algorithm is O(N*B*H) where B is the maximum arity of any node in the graph, and H is the time spent hashing a single node.

Graph equality

Here's a piece of code I figured out for testing when two rooted directed graphs are equivalent.

boolean equiv(Graph g1, Graph g2) {
   seen = empty set        // set of ordered pairs of nodes
   worklist = empty queue  // queue of pairs of nodes
   enqueue(worklist, (root(g1), root(g2)))

   while (worklist not empty) {
      (lhs,rhs) = dequeue(worklist)
      if ((lhs,rhs) is in seen)
         continue
      seen = union(seen, {(lhs,rhs)})

      if label(lhs) != label(rhs)
         return false
      if arity(lhs) != arity(rhs)
         return false
      for i in 1...arity(lhs)
         enqueue(worklist, (child(lhs,i),child(rhs,i)))
   }
   return true
}

This algorithm will check every unique pair that is encountered and return false if any of them are incompatible. If there are no incompatibilities, then the two graphs are equivalent. Notice that this allows the two different graphs to have different numbers of nodes. This comes in handy in two situations that are relevant to my research: PEGs and recursive types.

If you don't know what a PEG is, read this paper: http://cseweb.ucsd.edu/~rtate/publications/eqsat/. The algorithm above will tell you when two PEGs are syntactically equal, even if someone has unrolled the thetas any number of times. For example, it will tell you that the expressions theta(0,+(1,\2)) and theta(0,+(1,theta(0,+(1,\2)))) are equivalent (this syntax uses Debruijn indexes, I hope it's clear).

This also comes in handy when trying to represent recursive types. Say you have a simple linked list as follows:

struct list {
   int data;
   struct list *next;
}

You could represent this type in a compiler as the following rooted directed graph: struct(int, ptr(\2)). Using structural typing can be difficult when you have recursive types. For instance, the above struct should be structurally equivalent to this one:

struct list {
   int data;
   struct list2 {
      int data;
      struct list2* next;
   } *next;
}

...whose graph would look like struct(int,ptr(struct(int,ptr(\2)))). The algorithm described above would mark these two graphs as equivalent, as desired.

Both the time and space complexity are clearly O(N1*N2), but the actual complexity is proportional to the number of equivalent pairs of nodes in the two graphs. For most graphs this will be small, so the complexity can be as low as O(max(N1,N2)).