Count all paths from upper left to lower right on NxN lattice graph.

count_lattice_path.py

#!/usr/bin/env python
"""
Count all paths from upper left to lower right on NxN lattice graph.

Build (required SGB and GMP libraries):
% gcc gen_lattice.c -O3 -lgb -o gen_lattice
% wget http://www-cs-faculty.stanford.edu/~uno/programs/simpath.w
% ctangle simpath.w
% gcc simpath.c -O3 -lgb -o simpath
% wget http://www-cs-faculty.stanford.edu/~uno/programs/simpath-reduce.w
% ctangle simpath-reduce.w
% gcc simpath-reduce.c -O3 -lgb -o simpath-reduce
% g++ count_path_mp.cpp -O3 -lgmp -o count_path_mp
"""

import sys, os, subprocess

COMMAND_GEN_LATTICE_GB = "./gen_lattice %d %d %s"
COMMAND_SIMPATH = "./simpath %s %s %s > %s"
COMMAND_SIMPATH_REDUCE = "./simpath-reduce < %s > %s"
COMMAND_COUNT_PATH = "./count_path_mp %s"

def renumber_zdd(infile, outfile):
    data = []
    for l in file(infile):
        l = l.replace(":", " ").replace("(~", "").replace("?", " ").replace(")", "").strip()
        x = map(lambda x: int(x, 16), l.split())
        data.append([x[0], x[2], x[3]])
    data.sort()
    m = {0:0, 1:1}
    cnt = 2
    for d in data:
        m[d[0]] = cnt
        cnt += 1
    for i in range(len(data)):
        for j in range(3):
            data[i][j] = m[data[i][j]]
    outf = file(outfile, "w")
    print >>outf, len(data) + 2
    for d in data:
        print >>outf, "%d %d %d" % tuple(d)

def main(args):
    if len(args) < 2:
        print >>sys.stderr, "Usage: %s N" % os.path.basename(args[0])
        sys.exit()

    N = int(args[1])
    fname = "lattice_%02d" % N

    log = subprocess.Popen(COMMAND_GEN_LATTICE_GB % (N, N, fname + ".gb"), shell=True, stdin=None, stdout=subprocess.PIPE, stderr=subprocess.STDOUT).stdout.read()
    log += subprocess.Popen(COMMAND_SIMPATH % (fname + ".gb", "0.0", "%d.%d" % (N - 1, N - 1), fname + ".out"), shell=True, stdin=None, stdout=subprocess.PIPE, stderr=subprocess.STDOUT).stdout.read()
    log += subprocess.Popen(COMMAND_SIMPATH_REDUCE % (fname + ".out", fname + ".out.r"), shell=True, stdin=None, stdout=subprocess.PIPE, stderr=subprocess.STDOUT).stdout.read()
    renumber_zdd(fname + ".out.r", fname + ".out.rc")
    file(fname + ".log", "w").write(log)

    print "Count all paths from (0, 0) to (%d, %d) in the %dx%d lattice graph:" % (N - 1, N - 1, N, N)
    sys.stdout.flush()
    os.system(COMMAND_COUNT_PATH % fname + ".out.rc")

if __name__ == "__main__": main(sys.argv)