/* * SAWs on trihedral lattice from the vertex. * Naive unoptimized counting * * USAGE: nodejs triwalk.js * * We use the square lattice * and fuse the south-west quadrant axes. * 1, 3, 9, 27, 75, 213, 585, 1623, 4425, 12123, 32883, 89415, 241557, 653649, 1760427, 4747005, 12754593, 34301463 * * Francois Alcover 01/12/2019 * */ const maxn = process.argv[2] //print a(n) for n in 0..maxn const s = [] for (let n=0; n<=maxn; n++) s.push(seq(n)) console.log(s.join(", ")) function seq(n) { let stack = [[0,0]] return walk(stack, n) } //count n-walks from last point function walk (stack, n) { if (n==0) return 1 let result = 0 let last = stack[stack.length-1] let reach = get_reach(last) for (let point of reach) { if (!visited(stack, point)) { stack.push(point) result += walk(stack, n-1) stack.pop() } } return result } // Any potential step reaching the south axis // gets tranposed to the west axis function get_reach ([x,y]) { if (x==0 && y==0) return [[1,0],[0,1],[-1,0]] if (x==1 && y<0) return [[x+1,y],[x,y+1],[y,0],[x,y-1]] if (x<0 && y==0) return [[x+1,y],[x,y+1],[x-1,y],[1,x]] return [[x+1,y],[x,y+1],[x-1,y],[x,y-1]] } function visited (list, [x,y]) { for (let [i,j] of list) if (i==x && j==y) return true return false }