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.

## 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.

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```
Observation-1: The arrangement of end points is a diamond shape square of (n+1) by (n+1), where n is the length of the path.

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```
Observation-2: The number of end points of a path length n is (n+1)^2 for odd numbered path lengths and (n+1)^2-1 for even numbered path lengths.

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```
Observation-3: The total number of self avoiding walks for paths of length n is equal to the sum of all self avoiding walks of length n at each end point.

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

Observation-4: There are predictable patterns to the number of self avoiding walks at the end points of any set of walks of length n.

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```

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.

Observation-5: Any self avoiding path beginning in one direction has equivalent paths 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.

Observation-6: All self avoiding paths after the first turn on a path have equivalent paths in the opposite turn direction.

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.

Observation-7: There is a relationship among end point paths counts of path length n and all end point path counts for path lengths less than n.

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:

Observation-9: Column 0 of the transposed end point counts for all path length n is Pascal’s Triangle.

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:

Observation-10: All columns of the transposed end point counts for all path length n have a relationship to Pascal’s Triangle.

Mike.