About five years ago, I was asked to help look at optimizing a bit of code for the SPUs. Fundamental to that particular issue was the problem of 2D self-avoiding walks. It turns out that optimizing self-avoiding walks is a fascinating and deep subject. In this series, I’m going to share with you some of the properties of the problem I’ve observed. And some of the more interesting dead-ends as well.
What is a self-avoiding walk?
Put simply, a path on a grid that does not cross itself.
For more detailed introductions, see also:
- How to Avoid Yourself by Brian Hayes
- Self-Avoiding Walk on Wolfram MathWorld
- Self-Avoiding walk on Wikipedia
Counting walks
From the wikipedia entry:
Calculating the number of self-avoiding walks in any given lattice is a common computational problem. There is currently no known formula for determining the number of self-avoiding walks, although there are rigorous methods for approximating them. Finding the number of such paths is conjectured to be an NP-hard problem.
This is typical academic bullshit.
The problem with declaring (or conjecturing) this problem to be NP-hard is that it’s completely the wrong question being asked. It’s not a question of creating a “formula for determining the number of self-avoiding walks” given no other information. Or at least, it’s not an interesting or relevant question. As a practical matter, it tells us exactly nothing about the real problem: How we can find that number in a reasonable amount of time given any information or method which might be useful.
So that’s where we’ll start this series. We’ll look at different methods for counting paths of arbitrary lengths in a reasonable time (assuming you have a method of adding increasingly huge numbers.) In the first few parts I hope I to convince you that with a little bit of data analysis (because it’s always about the data), that you can calculate the total number of self-avoiding walks exactly for fairly large path lengths in a reasonable time. And then we might look at other interesting properties and related problems.
End points
Let’s start small.
Here are the self-avoiding walks of length 3. (By convention, the center point is not counted as part of the length of the walk.)
Each next step of the walk is denoted by the direction:
- C=Center
- W=West
- E=East
- S=South
- N=North
C,W,W,W C,W,N,W C,S,S,W C,W,W,S C,W,N,E C,S,S,E C,W,W,N C,W,N,N C,S,S,S C,W,S,W C,E,E,E C,N,W,W C,W,S,E C,E,E,S C,N,W,S C,W,S,S C,E,E,N C,N,W,N C,E,S,W C,S,W,W C,N,E,E C,E,S,E C,S,W,S C,N,E,S C,E,S,S C,S,W,N C,N,E,N C,E,N,W C,S,E,E C,N,N,W C,E,N,E C,S,E,S C,N,N,E C,E,N,N C,S,E,N C,N,N,N
Which can also be visualized like this:
Note that some of the paths end at the same point:
We’ll call those points “End Points” and that’s what we’ll concentrate on first. Let’s visualize where those end points end up for these length 3 paths. Here, the center is denoted by “*” and each “X” denotes an end point (where one or more paths end.)
- - - X - - - - - X - X - - - X - X - X - X - X * X - X - X - X - X - - - X - X - - - - - X - - - EndPointCount: 16
This is true for any path length n.
Let’s look at another example. The end points of path length 15:
- - - - - - - - - - - - - - - X - - - - - - - - - - - - - - - - - - - - - - - - - - - - - X - X - - - - - - - - - - - - - - - - - - - - - - - - - - - X - X - X - - - - - - - - - - - - - - - - - - - - - - - - - X - X - X - X - - - - - - - - - - - - - - - - - - - - - - - X - X - X - X - X - - - - - - - - - - - - - - - - - - - - - X - X - X - X - X - X - - - - - - - - - - - - - - - - - - - X - X - X - X - X - X - X - - - - - - - - - - - - - - - - - X - X - X - X - X - X - X - X - - - - - - - - - - - - - - - X - X - X - X - X - X - X - X - X - - - - - - - - - - - - - X - X - X - X - X - X - X - X - X - X - - - - - - - - - - - X - X - X - X - X - X - X - X - X - X - X - - - - - - - - - X - X - X - X - X - X - X - X - X - X - X - X - - - - - - - X - X - X - X - X - X - X - X - X - X - X - X - X - - - - - X - X - X - X - X - X - X - X - X - X - X - X - X - X - - - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X * X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - X - - - X - X - X - X - X - X - X - X - X - X - X - X - X - X - - - - - X - X - X - X - X - X - X - X - X - X - X - X - X - - - - - - - X - X - X - X - X - X - X - X - X - X - X - X - - - - - - - - - X - X - X - X - X - X - X - X - X - X - X - - - - - - - - - - - X - X - X - X - X - X - X - X - X - X - - - - - - - - - - - - - X - X - X - X - X - X - X - X - X - - - - - - - - - - - - - - - X - X - X - X - X - X - X - X - - - - - - - - - - - - - - - - - X - X - X - X - X - X - X - - - - - - - - - - - - - - - - - - - X - X - X - X - X - X - - - - - - - - - - - - - - - - - - - - - X - X - X - X - X - - - - - - - - - - - - - - - - - - - - - - - X - X - X - X - - - - - - - - - - - - - - - - - - - - - - - - - X - X - X - - - - - - - - - - - - - - - - - - - - - - - - - - - X - X - - - - - - - - - - - - - - - - - - - - - - - - - - - - - X - - - - - - - - - - - - - - - EndPointCount: 256
Let’s look again at the end points of path length 3:
- - - X - - - - - X - X - - - X - X - X - X - X * X - X - X - X - X - - - X - X - - - - - X - - - EndPointCount: 16
And at the end points of path length 4:
- - - - X - - - - - - - X - X - - - - - X - X - X - - - X - X - X - X - X - X - * - X - X - X - X - X - X - - - X - X - X - - - - - X - X - - - - - - - X - - - - EndPointCount: 24
Notice that in the odd numbered path the center point is excluded from the area defined by the end points (n+1)*(n+1); in the even numbered path, the center point is included in the area but can obviously not itself be an end point.
Here’s some simple javascript to help you validate the pattern: jsdb to run this javascript, you may need to slightly modify for a different environment.) This script brute force calculates all paths for a given length n, then prints out the end points in the form above. Since it’s brute forcing all paths, it’s only usable for small n.
Now just with Observation-1 and Observation-2, you can already significantly reduce the amount of time enumerating self-avoiding walks. By knowing where paths must end and where paths cannot end, you can reduce the search space significantly. i.e. Traditional brute-force walk enumeration (as in the javascript example above), begin at the center point and simply work out every path one-by-one. However, if you know all the end points, you can iterate through each end point and find the paths that connect the two points instead (end point and center point).
However, we’ll put that aside for now so that we can look at some additional data.
Let’s look at the number of paths found at each end point of a length 3 walk:
----- ----- ----- 00001 ----- ----- ----- ----- ----- 00003 ----- 00003 ----- ----- ----- 00003 ----- 00002 ----- 00003 ----- 00001 ----- 00002 ***** 00002 ----- 00001 ----- 00003 ----- 00002 ----- 00003 ----- ----- ----- 00003 ----- 00003 ----- ----- ----- ----- ----- 00001 ----- ----- ----- EndPointCount: 16 TotalWalkCount: 36
This is obvious. If we know all the points at which paths can end and we know how many paths end at each point we can simply add them all up to get the total number of walks (in this case, 36.)
Another example. End point path counts for path length 8:
----- ----- ----- ----- ----- ----- ----- ----- 00001 ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- 00008 ----- 00008 ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- 00028 ----- 00042 ----- 00028 ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- 00056 ----- 00092 ----- 00092 ----- 00056 ----- ----- ----- ----- ----- ----- ----- ----- ----- 00070 ----- 00118 ----- 00126 ----- 00118 ----- 00070 ----- ----- ----- ----- ----- ----- ----- 00056 ----- 00120 ----- 00118 ----- 00118 ----- 00120 ----- 00056 ----- ----- ----- ----- ----- 00028 ----- 00118 ----- 00112 ----- 00092 ----- 00112 ----- 00118 ----- 00028 ----- ----- ----- 00008 ----- 00092 ----- 00118 ----- 00076 ----- 00076 ----- 00118 ----- 00092 ----- 00008 ----- 00001 ----- 00042 ----- 00126 ----- 00092 ----- ***** ----- 00092 ----- 00126 ----- 00042 ----- 00001 ----- 00008 ----- 00092 ----- 00118 ----- 00076 ----- 00076 ----- 00118 ----- 00092 ----- 00008 ----- ----- ----- 00028 ----- 00118 ----- 00112 ----- 00092 ----- 00112 ----- 00118 ----- 00028 ----- ----- ----- ----- ----- 00056 ----- 00120 ----- 00118 ----- 00118 ----- 00120 ----- 00056 ----- ----- ----- ----- ----- ----- ----- 00070 ----- 00118 ----- 00126 ----- 00118 ----- 00070 ----- ----- ----- ----- ----- ----- ----- ----- ----- 00056 ----- 00092 ----- 00092 ----- 00056 ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- 00028 ----- 00042 ----- 00028 ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- 00008 ----- 00008 ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- 00001 ----- ----- ----- ----- ----- ----- ----- ----- EndPointCount: 80 TotalWalkCount: 5916
For validation, here’s another javascript which will brute force through all paths, add up the number of paths at each end point and output in the format above: walk_12.js
This is where we will concern ourselves. If we can predict the number of self avoiding walks for each end point, we can eliminate the work in walking those paths and simply add up the results. The tricky bit is of course determining what those patterns are exactly. But rest assured, they exist.
First let’s rearrange the format of the data. End points are an (n+1) by (n+1) diamond shape, which if rotated 45 degrees, can be made into a square matrix. Here’s the same data from above for path length 8 in that form:
00001 00008 00028 00056 00070 00056 00028 00008 00001 00008 00042 00092 00118 00120 00118 00092 00042 00008 00028 00092 00126 00118 00112 00118 00126 00092 00028 00056 00118 00118 00092 00076 00092 00118 00118 00056 00070 00120 00112 00076 ***** 00076 00112 00120 00070 00056 00118 00118 00092 00076 00092 00118 00118 00056 00028 00092 00126 00118 00112 00118 00126 00092 00028 00008 00042 00092 00118 00120 00118 00092 00042 00008 00001 00008 00028 00056 00070 00056 00028 00008 00001 EndPointCount: 80 TotalWalkCount: 5916
Let’s start with the easy stuff.
Notice that the walk counts are rotated and mirrored about the center. That makes intuitive sense: Any walk that begins in one direction has an equivalent walk that begins in the other three directions.
This observation is well known and is the basis for most high-level optimizations of the brute force algorithm. And it’s easy to see why. By simply starting the path in one known direction, the total count is simply multiplied by four to account for the other quadrants.
Here the end points paths which are simply mirrors or rotations of one direction for path length 8 are marked in red.
00001 00008 00028 00056 00070 00056 00028 00008 00001 00008 00042 00092 00118 00120 00118 00092 00042 00008 00028 00092 00126 00118 00112 00118 00126 00092 00028 00056 00118 00118 00092 00076 00092 00118 00118 00056 00070 00120 00112 00076 ***** 00076 00112 00120 00070 00056 00118 00118 00092 00076 00092 00118 00118 00056 00028 00092 00126 00118 00112 00118 00126 00092 00028 00008 00042 00092 00118 00120 00118 00092 00042 00008 00001 00008 00028 00056 00070 00056 00028 00008 00001 EndPointCount: 80 TotalWalkCount: 5916
But there is still more duplication here.
In other words, all the paths which are found after you first turn right have equivalent paths if you had turned left instead. You can see how the end point path counts are mirrored along the diagonal of that quadrant.
Which leaves us with just the following green end points for paths of length 8.
00001 00008 00028 00056 00070 00056 00028 00008 00001 00008 00042 00092 00118 00120 00118 00092 00042 00008 00028 00092 00126 00118 00112 00118 00126 00092 00028 00056 00118 00118 00092 00076 00092 00118 00118 00056 00070 00120 00112 00076 ***** 00076 00112 00120 00070 00056 00118 00118 00092 00076 00092 00118 00118 00056 00028 00092 00126 00118 00112 00118 00126 00092 00028 00008 00042 00092 00118 00120 00118 00092 00042 00008 00001 00008 00028 00056 00070 00056 00028 00008 00001 EndPointCount: 80 TotalWalkCount: 5916
This is true for paths of any length n. Here is another example with paths of length 13.
00001 00013 00078 00286 00715 01287 01716 01716 01287 00715 00286 00078 00013 00001 00013 00132 00607 01683 03190 04521 05214 05214 04521 03190 01683 00607 00132 00013 00078 00607 02106 04398 06467 07656 08128 08128 07656 06467 04398 02106 00607 00078 00286 01683 04398 07072 08506 08923 08956 08956 08923 08506 07072 04398 01683 00286 00715 03190 06467 08506 08924 08518 08080 08080 08518 08924 08506 06467 03190 00715 01287 04521 07656 08923 08518 07366 06387 06387 07366 08518 08923 07656 04521 01287 01716 05214 08128 08956 08080 06387 04116 04116 06387 08080 08956 08128 05214 01716 01716 05214 08128 08956 08080 06387 04116 04116 06387 08080 08956 08128 05214 01716 01287 04521 07656 08923 08518 07366 06387 06387 07366 08518 08923 07656 04521 01287 00715 03190 06467 08506 08924 08518 08080 08080 08518 08924 08506 06467 03190 00715 00286 01683 04398 07072 08506 08923 08956 08956 08923 08506 07072 04398 01683 00286 00078 00607 02106 04398 06467 07656 08128 08128 07656 06467 04398 02106 00607 00078 00013 00132 00607 01683 03190 04521 05214 05214 04521 03190 01683 00607 00132 00013 00001 00013 00078 00286 00715 01287 01716 01716 01287 00715 00286 00078 00013 00001 EndPointCount: 196 TotalWalkCount: 881500
At this point, using Observation-5 and Observation-6, you could reduce the work of enumerating self avoiding walks significantly again. It’s hopefully clear that if you can just find those walks which end in the end points in green, you can derive all the remaining walks.
However, again we’ll put this aside for now to concentrate on digging into the data still further.
Here’s where we take a step away from the view of the problem in isolation and use more available data.
For example, if we want to get the end point path counts for paths of length 15, it helps to know the counts for all the paths of lengths less than 15. Or rather, if we want to calculate end point counts for paths of length 15, we can assume we’ve already done that for all the paths of length 14, 13, 12, 11, 10, 9, etc. previously and we can use that data to help.
Let’s have a look at all the end point counts of path lengths between 1 and 15:
n 1 v 1 1 v 1 1 n 2 v 1 2 1 v 2 0 2 v 1 2 1 n 3 v 1 3 3 1 v 3 2 2 3 v 3 2 2 3 v 1 3 3 1 n 4 v 1 4 6 4 1 v 4 6 4 6 4 v 6 4 0 4 6 v 4 6 4 6 4 v 1 4 6 4 1 n 5 v 1 5 10 10 5 1 v 5 12 11 11 12 5 v 10 11 6 6 11 10 v 10 11 6 6 11 10 v 5 12 11 11 12 5 v 1 5 10 10 5 1 n 6 v 1 6 15 20 15 6 1 v 6 20 26 24 26 20 6 v 15 26 20 16 20 26 15 v 20 24 16 0 16 24 20 v 15 26 20 16 20 26 15 v 6 20 26 24 26 20 6 v 1 6 15 20 15 6 1 n 7 v 1 7 21 35 35 21 7 1 v 7 30 52 55 55 52 30 7 v 21 52 54 45 45 54 52 21 v 35 55 45 28 28 45 55 35 v 35 55 45 28 28 45 55 35 v 21 52 54 45 45 54 52 21 v 7 30 52 55 55 52 30 7 v 1 7 21 35 35 21 7 1 n 8 v 1 8 28 56 70 56 28 8 1 v 8 42 92 118 120 118 92 42 8 v 28 92 126 118 112 118 126 92 28 v 56 118 118 92 76 92 118 118 56 v 70 120 112 76 0 76 112 120 70 v 56 118 118 92 76 92 118 118 56 v 28 92 126 118 112 118 126 92 28 v 8 42 92 118 120 118 92 42 8 v 1 8 28 56 70 56 28 8 1 n 9 v 1 9 36 84 126 126 84 36 9 1 v 9 56 149 231 259 259 231 149 56 9 v 36 149 260 286 277 277 286 260 149 36 v 84 231 286 256 220 220 256 286 231 84 v 126 259 277 220 140 140 220 277 259 126 v 126 259 277 220 140 140 220 277 259 126 v 84 231 286 256 220 220 256 286 231 84 v 36 149 260 286 277 277 286 260 149 36 v 9 56 149 231 259 259 231 149 56 9 v 1 9 36 84 126 126 84 36 9 1 n 10 v 1 10 45 120 210 252 210 120 45 10 1 v 10 72 226 416 532 560 532 416 226 72 10 v 45 226 486 636 661 660 661 636 486 226 45 v 120 416 636 654 598 568 598 654 636 416 120 v 210 532 661 598 468 396 468 598 661 532 210 v 252 560 660 568 396 0 396 568 660 560 252 v 210 532 661 598 468 396 468 598 661 532 210 v 120 416 636 654 598 568 598 654 636 416 120 v 45 226 486 636 661 660 661 636 486 226 45 v 10 72 226 416 532 560 532 416 226 72 10 v 1 10 45 120 210 252 210 120 45 10 1 n 11 v 1 11 55 165 330 462 462 330 165 55 11 1 v 11 90 326 699 1026 1176 1176 1026 699 326 90 11 v 55 326 840 1301 1500 1546 1546 1500 1301 840 326 55 v 165 699 1301 1552 1532 1467 1467 1532 1552 1301 699 165 v 330 1026 1500 1532 1340 1157 1157 1340 1532 1500 1026 330 v 462 1176 1546 1467 1157 744 744 1157 1467 1546 1176 462 v 462 1176 1546 1467 1157 744 744 1157 1467 1546 1176 462 v 330 1026 1500 1532 1340 1157 1157 1340 1532 1500 1026 330 v 165 699 1301 1552 1532 1467 1467 1532 1552 1301 699 165 v 55 326 840 1301 1500 1546 1546 1500 1301 840 326 55 v 11 90 326 699 1026 1176 1176 1026 699 326 90 11 v 1 11 55 165 330 462 462 330 165 55 11 1 n 12 v 1 12 66 220 495 792 924 792 495 220 66 12 1 v 12 110 452 1110 1860 2364 2520 2364 1860 1110 452 110 12 v 66 452 1364 2470 3210 3510 3584 3510 3210 2470 1364 452 66 v 220 1110 2470 3428 3712 3686 3644 3686 3712 3428 2470 1110 220 v 495 1860 3210 3712 3558 3216 3054 3216 3558 3712 3210 1860 495 v 792 2364 3510 3686 3216 2532 2164 2532 3216 3686 3510 2364 792 v 924 2520 3584 3644 3054 2164 0 2164 3054 3644 3584 2520 924 v 792 2364 3510 3686 3216 2532 2164 2532 3216 3686 3510 2364 792 v 495 1860 3210 3712 3558 3216 3054 3216 3558 3712 3210 1860 495 v 220 1110 2470 3428 3712 3686 3644 3686 3712 3428 2470 1110 220 v 66 452 1364 2470 3210 3510 3584 3510 3210 2470 1364 452 66 v 12 110 452 1110 1860 2364 2520 2364 1860 1110 452 110 12 v 1 12 66 220 495 792 924 792 495 220 66 12 1 n 13 v 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 v 13 132 607 1683 3190 4521 5214 5214 4521 3190 1683 607 132 13 v 78 607 2106 4398 6467 7656 8128 8128 7656 6467 4398 2106 607 78 v 286 1683 4398 7072 8506 8923 8956 8956 8923 8506 7072 4398 1683 286 v 715 3190 6467 8506 8924 8518 8080 8080 8518 8924 8506 6467 3190 715 v 1287 4521 7656 8923 8518 7366 6387 6387 7366 8518 8923 7656 4521 1287 v 1716 5214 8128 8956 8080 6387 4116 4116 6387 8080 8956 8128 5214 1716 v 1716 5214 8128 8956 8080 6387 4116 4116 6387 8080 8956 8128 5214 1716 v 1287 4521 7656 8923 8518 7366 6387 6387 7366 8518 8923 7656 4521 1287 v 715 3190 6467 8506 8924 8518 8080 8080 8518 8924 8506 6467 3190 715 v 286 1683 4398 7072 8506 8923 8956 8956 8923 8506 7072 4398 1683 286 v 78 607 2106 4398 6467 7656 8128 8128 7656 6467 4398 2106 607 78 v 13 132 607 1683 3190 4521 5214 5214 4521 3190 1683 607 132 13 v 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 n 14 v 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 v 14 156 794 2456 5214 8228 10362 11088 10362 8228 5214 2456 794 156 14 v 91 794 3120 7416 12302 15958 17895 18480 17895 15958 12302 7416 3120 794 91 v 364 2456 7416 13706 18430 20724 21502 21652 21502 20724 18430 13706 7416 2456 364 v 1001 5214 12302 18430 21260 21568 20941 20584 20941 21568 21260 18430 12302 5214 1001 v 2002 8228 15958 20724 21568 20030 18006 17100 18006 20030 21568 20724 15958 8228 2002 v 3003 10362 17895 21502 20941 18006 14220 12240 14220 18006 20941 21502 17895 10362 3003 v 3432 11088 18480 21652 20584 17100 12240 0 12240 17100 20584 21652 18480 11088 3432 v 3003 10362 17895 21502 20941 18006 14220 12240 14220 18006 20941 21502 17895 10362 3003 v 2002 8228 15958 20724 21568 20030 18006 17100 18006 20030 21568 20724 15958 8228 2002 v 1001 5214 12302 18430 21260 21568 20941 20584 20941 21568 21260 18430 12302 5214 1001 v 364 2456 7416 13706 18430 20724 21502 21652 21502 20724 18430 13706 7416 2456 364 v 91 794 3120 7416 12302 15958 17895 18480 17895 15958 12302 7416 3120 794 91 v 14 156 794 2456 5214 8228 10362 11088 10362 8228 5214 2456 794 156 14 v 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 n 15 v 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 v 15 182 1016 3471 8177 14300 19734 22737 22737 19734 14300 8177 3471 1016 182 15 v 105 1016 4466 11941 22211 31730 38052 41007 41007 38052 31730 22211 11941 4466 1016 105 v 455 3471 11941 25124 37813 46068 50084 51540 51540 50084 46068 37813 25124 11941 3471 455 v 1365 8177 22211 37813 48188 52301 52705 52104 52104 52705 52301 48188 37813 22211 8177 1365 v 3003 14300 31730 46068 52301 51932 48665 45958 45958 48665 51932 52301 46068 31730 14300 3003 v 5005 19734 38052 50084 52705 48665 41872 36443 36443 41872 48665 52705 50084 38052 19734 5005 v 6435 22737 41007 51540 52104 45958 36443 23504 23504 36443 45958 52104 51540 41007 22737 6435 v 6435 22737 41007 51540 52104 45958 36443 23504 23504 36443 45958 52104 51540 41007 22737 6435 v 5005 19734 38052 50084 52705 48665 41872 36443 36443 41872 48665 52705 50084 38052 19734 5005 v 3003 14300 31730 46068 52301 51932 48665 45958 45958 48665 51932 52301 46068 31730 14300 3003 v 1365 8177 22211 37813 48188 52301 52705 52104 52104 52705 52301 48188 37813 22211 8177 1365 v 455 3471 11941 25124 37813 46068 50084 51540 51540 50084 46068 37813 25124 11941 3471 455 v 105 1016 4466 11941 22211 31730 38052 41007 41007 38052 31730 22211 11941 4466 1016 105 v 15 182 1016 3471 8177 14300 19734 22737 22737 19734 14300 8177 3471 1016 182 15 v 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
Relationships between different path lengths may not be apparent in this form. So let’s transpose this data. Instead of looking at each path length independently, let’s look at each column together:
c 0 ------------------------------------------------------------------------------------------------------ n 0 | 1 n 1 | 1 1 n 2 | 1 2 1 n 3 | 1 3 3 1 n 4 | 1 4 6 4 1 n 5 | 1 5 10 10 5 1 n 6 | 1 6 15 20 15 6 1 n 7 | 1 7 21 35 35 21 7 1 n 8 | 1 8 28 56 70 56 28 8 1 n 9 | 1 9 36 84 126 126 84 36 9 1 n 10 | 1 10 45 120 210 252 210 120 45 10 1 n 11 | 1 11 55 165 330 462 462 330 165 55 11 1 n 12 | 1 12 66 220 495 792 924 792 495 220 66 12 1 n 13 | 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 n 14 | 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 n 15 | 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 c 1 ------------------------------------------------------------------------------------------------------ n 1 | 1 1 n 2 | 2 0 2 n 3 | 3 2 2 3 n 4 | 4 6 4 6 4 n 5 | 5 12 11 11 12 5 n 6 | 6 20 26 24 26 20 6 n 7 | 7 30 52 55 55 52 30 7 n 8 | 8 42 92 118 120 118 92 42 8 n 9 | 9 56 149 231 259 259 231 149 56 9 n 10 | 10 72 226 416 532 560 532 416 226 72 10 n 11 | 11 90 326 699 1026 1176 1176 1026 699 326 90 11 n 12 | 12 110 452 1110 1860 2364 2520 2364 1860 1110 452 110 12 n 13 | 13 132 607 1683 3190 4521 5214 5214 4521 3190 1683 607 132 13 n 14 | 14 156 794 2456 5214 8228 10362 11088 10362 8228 5214 2456 794 156 14 n 15 | 15 182 1016 3471 8177 14300 19734 22737 22737 19734 14300 8177 3471 1016 182 15 c 2 ------------------------------------------------------------------------------------------------------ n 2 | 1 2 1 n 3 | 3 2 2 3 n 4 | 6 4 0 4 6 n 5 | 10 11 6 6 11 10 n 6 | 15 26 20 16 20 26 15 n 7 | 21 52 54 45 45 54 52 21 n 8 | 28 92 126 118 112 118 126 92 28 n 9 | 36 149 260 286 277 277 286 260 149 36 n 10 | 45 226 486 636 661 660 661 636 486 226 45 n 11 | 55 326 840 1301 1500 1546 1546 1500 1301 840 326 55 n 12 | 66 452 1364 2470 3210 3510 3584 3510 3210 2470 1364 452 66 n 13 | 78 607 2106 4398 6467 7656 8128 8128 7656 6467 4398 2106 607 78 n 14 | 91 794 3120 7416 12302 15958 17895 18480 17895 15958 12302 7416 3120 794 91 n 15 | 105 1016 4466 11941 22211 31730 38052 41007 41007 38052 31730 22211 11941 4466 1016 105 c 3 ------------------------------------------------------------------------------------------------------ n 3 | 1 3 3 1 n 4 | 4 6 4 6 4 n 5 | 10 11 6 6 11 10 n 6 | 20 24 16 0 16 24 20 n 7 | 35 55 45 28 28 45 55 35 n 8 | 56 118 118 92 76 92 118 118 56 n 9 | 84 231 286 256 220 220 256 286 231 84 n 10 | 120 416 636 654 598 568 598 654 636 416 120 n 11 | 165 699 1301 1552 1532 1467 1467 1532 1552 1301 699 165 n 12 | 220 1110 2470 3428 3712 3686 3644 3686 3712 3428 2470 1110 220 n 13 | 286 1683 4398 7072 8506 8923 8956 8956 8923 8506 7072 4398 1683 286 n 14 | 364 2456 7416 13706 18430 20724 21502 21652 21502 20724 18430 13706 7416 2456 364 n 15 | 455 3471 11941 25124 37813 46068 50084 51540 51540 50084 46068 37813 25124 11941 3471 455 c 4 ------------------------------------------------------------------------------------------------------ n 4 | 1 4 6 4 1 n 5 | 5 12 11 11 12 5 n 6 | 15 26 20 16 20 26 15 n 7 | 35 55 45 28 28 45 55 35 n 8 | 70 120 112 76 0 76 112 120 70 n 9 | 126 259 277 220 140 140 220 277 259 126 n 10 | 210 532 661 598 468 396 468 598 661 532 210 n 11 | 330 1026 1500 1532 1340 1157 1157 1340 1532 1500 1026 330 n 12 | 495 1860 3210 3712 3558 3216 3054 3216 3558 3712 3210 1860 495 n 13 | 715 3190 6467 8506 8924 8518 8080 8080 8518 8924 8506 6467 3190 715 n 14 | 1001 5214 12302 18430 21260 21568 20941 20584 20941 21568 21260 18430 12302 5214 1001 n 15 | 1365 8177 22211 37813 48188 52301 52705 52104 52104 52705 52301 48188 37813 22211 8177 1365 c 5 ------------------------------------------------------------------------------------------------------ n 5 | 1 5 10 10 5 1 n 6 | 6 20 26 24 26 20 6 n 7 | 21 52 54 45 45 54 52 21 n 8 | 56 118 118 92 76 92 118 118 56 n 9 | 126 259 277 220 140 140 220 277 259 126 n 10 | 252 560 660 568 396 0 396 568 660 560 252 n 11 | 462 1176 1546 1467 1157 744 744 1157 1467 1546 1176 462 n 12 | 792 2364 3510 3686 3216 2532 2164 2532 3216 3686 3510 2364 792 n 13 | 1287 4521 7656 8923 8518 7366 6387 6387 7366 8518 8923 7656 4521 1287 n 14 | 2002 8228 15958 20724 21568 20030 18006 17100 18006 20030 21568 20724 15958 8228 2002 n 15 | 3003 14300 31730 46068 52301 51932 48665 45958 45958 48665 51932 52301 46068 31730 14300 3003 c 6 ------------------------------------------------------------------------------------------------------ n 6 | 1 6 15 20 15 6 1 n 7 | 7 30 52 55 55 52 30 7 n 8 | 28 92 126 118 112 118 126 92 28 n 9 | 84 231 286 256 220 220 256 286 231 84 n 10 | 210 532 661 598 468 396 468 598 661 532 210 n 11 | 462 1176 1546 1467 1157 744 744 1157 1467 1546 1176 462 n 12 | 924 2520 3584 3644 3054 2164 0 2164 3054 3644 3584 2520 924 n 13 | 1716 5214 8128 8956 8080 6387 4116 4116 6387 8080 8956 8128 5214 1716 n 14 | 3003 10362 17895 21502 20941 18006 14220 12240 14220 18006 20941 21502 17895 10362 3003 n 15 | 5005 19734 38052 50084 52705 48665 41872 36443 36443 41872 48665 52705 50084 38052 19734 5005 c 7 ------------------------------------------------------------------------------------------------------ n 7 | 1 7 21 35 35 21 7 1 n 8 | 8 42 92 118 120 118 92 42 8 n 9 | 36 149 260 286 277 277 286 260 149 36 n 10 | 120 416 636 654 598 568 598 654 636 416 120 n 11 | 330 1026 1500 1532 1340 1157 1157 1340 1532 1500 1026 330 n 12 | 792 2364 3510 3686 3216 2532 2164 2532 3216 3686 3510 2364 792 n 13 | 1716 5214 8128 8956 8080 6387 4116 4116 6387 8080 8956 8128 5214 1716 n 14 | 3432 11088 18480 21652 20584 17100 12240 0 12240 17100 20584 21652 18480 11088 3432 n 15 | 6435 22737 41007 51540 52104 45958 36443 23504 23504 36443 45958 52104 51540 41007 22737 6435 c 8 ------------------------------------------------------------------------------------------------------ n 8 | 1 8 28 56 70 56 28 8 1 n 9 | 9 56 149 231 259 259 231 149 56 9 n 10 | 45 226 486 636 661 660 661 636 486 226 45 n 11 | 165 699 1301 1552 1532 1467 1467 1532 1552 1301 699 165 n 12 | 495 1860 3210 3712 3558 3216 3054 3216 3558 3712 3210 1860 495 n 13 | 1287 4521 7656 8923 8518 7366 6387 6387 7366 8518 8923 7656 4521 1287 n 14 | 3003 10362 17895 21502 20941 18006 14220 12240 14220 18006 20941 21502 17895 10362 3003 n 15 | 6435 22737 41007 51540 52104 45958 36443 23504 23504 36443 45958 52104 51540 41007 22737 6435 c 9 ------------------------------------------------------------------------------------------------------ n 9 | 1 9 36 84 126 126 84 36 9 1 n 10 | 10 72 226 416 532 560 532 416 226 72 10 n 11 | 55 326 840 1301 1500 1546 1546 1500 1301 840 326 55 n 12 | 220 1110 2470 3428 3712 3686 3644 3686 3712 3428 2470 1110 220 n 13 | 715 3190 6467 8506 8924 8518 8080 8080 8518 8924 8506 6467 3190 715 n 14 | 2002 8228 15958 20724 21568 20030 18006 17100 18006 20030 21568 20724 15958 8228 2002 n 15 | 5005 19734 38052 50084 52705 48665 41872 36443 36443 41872 48665 52705 50084 38052 19734 5005 c 10 ------------------------------------------------------------------------------------------------------ n 10 | 1 10 45 120 210 252 210 120 45 10 1 n 11 | 11 90 326 699 1026 1176 1176 1026 699 326 90 11 n 12 | 66 452 1364 2470 3210 3510 3584 3510 3210 2470 1364 452 66 n 13 | 286 1683 4398 7072 8506 8923 8956 8956 8923 8506 7072 4398 1683 286 n 14 | 1001 5214 12302 18430 21260 21568 20941 20584 20941 21568 21260 18430 12302 5214 1001 n 15 | 3003 14300 31730 46068 52301 51932 48665 45958 45958 48665 51932 52301 46068 31730 14300 3003 c 11 ------------------------------------------------------------------------------------------------------ n 11 | 1 11 55 165 330 462 462 330 165 55 11 1 n 12 | 12 110 452 1110 1860 2364 2520 2364 1860 1110 452 110 12 n 13 | 78 607 2106 4398 6467 7656 8128 8128 7656 6467 4398 2106 607 78 n 14 | 364 2456 7416 13706 18430 20724 21502 21652 21502 20724 18430 13706 7416 2456 364 n 15 | 1365 8177 22211 37813 48188 52301 52705 52104 52104 52705 52301 48188 37813 22211 8177 1365 c 12 ------------------------------------------------------------------------------------------------------ n 12 | 1 12 66 220 495 792 924 792 495 220 66 12 1 n 13 | 13 132 607 1683 3190 4521 5214 5214 4521 3190 1683 607 132 13 n 14 | 91 794 3120 7416 12302 15958 17895 18480 17895 15958 12302 7416 3120 794 91 n 15 | 455 3471 11941 25124 37813 46068 50084 51540 51540 50084 46068 37813 25124 11941 3471 455 c 13 ------------------------------------------------------------------------------------------------------ n 13 | 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 n 14 | 14 156 794 2456 5214 8228 10362 11088 10362 8228 5214 2456 794 156 14 n 15 | 105 1016 4466 11941 22211 31730 38052 41007 41007 38052 31730 22211 11941 4466 1016 105 c 14 ------------------------------------------------------------------------------------------------------ n 14 | 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 n 15 | 15 182 1016 3471 8177 14300 19734 22737 22737 19734 14300 8177 3471 1016 182 15 c 15 ------------------------------------------------------------------------------------------------------ n 15 | 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
Now looking at these counts, it should be much more apparent there is a relationship between end point path counts of different path lengths.
Let’s start by looking at column 0. When you take into account mirroring and rotation of the quadrants, column 0 represents the “outer edge” of the square matrix of end point counts.
For example, of path length 8, these counts:
c 0
------------------------------------------------------------------------------------------------------
n 0 | 1
n 1 | 1 1
n 2 | 1 2 1
n 3 | 1 3 3 1
n 4 | 1 4 6 4 1
n 5 | 1 5 10 10 5 1
n 6 | 1 6 15 20 15 6 1
n 7 | 1 7 21 35 35 21 7 1
n 8 | 1 8 28 56 70 56 28 8 1
n 9 | 1 9 36 84 126 126 84 36 9 1
n 10 | 1 10 45 120 210 252 210 120 45 10 1
n 11 | 1 11 55 165 330 462 462 330 165 55 11 1
n 12 | 1 12 66 220 495 792 924 792 495 220 66 12 1
n 13 | 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
n 14 | 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
n 15 | 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
Are found here:
00001 00008 00028 00056 00070 00056 00028 00008 00001 00008 00042 00092 00118 00120 00118 00092 00042 00008 00028 00092 00126 00118 00112 00118 00126 00092 00028 00056 00118 00118 00092 00076 00092 00118 00118 00056 00070 00120 00112 00076 ***** 00076 00112 00120 00070 00056 00118 00118 00092 00076 00092 00118 00118 00056 00028 00092 00126 00118 00112 00118 00126 00092 00028 00008 00042 00092 00118 00120 00118 00092 00042 00008 00001 00008 00028 00056 00070 00056 00028 00008 00001 EndPointCount: 80 TotalWalkCount: 5916
If the pattern of values in column 0 seem familiar, that’s because:
In other words, the outer edge of end point counts for path length n are the values in the nth row in Pascal’s Triangle.
At the very least it should be apparent why the first column of column 0 is always 1. That value represents the outermost tip of the end points. Which always only be reached by exactly one path. Or, for any paths of length n, there are four paths (NSEW) that are straight line paths that reach the four furthest corners permissible by a path of length n.
To generate column 0, we can define it (Pascal’s Triangle) as a recursive function (recurrence relation):
Let’s call the function that generates column 0, f0. And n is the path length (down) and i is the column in this form (across)
f0(n,i) = f0(n-1,i) + f0(n-1,i-1)
Here is an awk script which generates the values in this form. fcol0.awk
c 0 | f0(n,i) = f0(n-1,i) + f0(n-1,i-1) ------------------------------------------------------------------------------------------------------ n 0 | 1 n 1 | 1 1 n 2 | 1 2 1 n 3 | 1 3 3 1 n 4 | 1 4 6 4 1 n 5 | 1 5 10 10 5 1 n 6 | 1 6 15 20 15 6 1 n 7 | 1 7 21 35 35 21 7 1 n 8 | 1 8 28 56 70 56 28 8 1 n 9 | 1 9 36 84 126 126 84 36 9 1 n 10 | 1 10 45 120 210 252 210 120 45 10 1 n 11 | 1 11 55 165 330 462 462 330 165 55 11 1 n 12 | 1 12 66 220 495 792 924 792 495 220 66 12 1 n 13 | 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 n 14 | 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 n 15 | 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
So if we now go back to path length 8, we can also predict the first column and only the following end points in green remain to be calculated:
00001 00008 00028 00056 00070 00056 00028 00008 00001 00008 00042 00092 00118 00120 00118 00092 00042 00008 00028 00092 00126 00118 00112 00118 00126 00092 00028 00056 00118 00118 00092 00076 00092 00118 00118 00056 00070 00120 00112 00076 ***** 00076 00112 00120 00070 00056 00118 00118 00092 00076 00092 00118 00118 00056 00028 00092 00126 00118 00112 00118 00126 00092 00028 00008 00042 00092 00118 00120 00118 00092 00042 00008 00001 00008 00028 00056 00070 00056 00028 00008 00001 EndPointCount: 80 TotalWalkCount: 5916
In the next part, we’ll look at the patterns of the other columns and how to predict the patterns for “future” columns for paths of greater lengths. Lots more to come!
But I’ll give you a hint if you want to start working the patterns out on your own:
Mike.