The problem statement from the Ole Miss Problems of the Week page is:

You begin at the top point in the figure to the left. You are trying to get to the bottom point. You can move only in a downward direction along the line segments. How many different paths can you take that will get you from the top point to the bottom point?

Well, the generally accepted way to discover how many of something there are is to count them. So a way we can discover how many paths there are from the top point to the bottom point is therefore to enumerate the paths and count them. So, since we happen to have a wonderful counting device — a CFX-9850G or FX-7400G programmable calculator — handy, let us use that. (“When will he ever not want to do a program first?” you ask. “Never,” I say.)

First, we need a way to tell the points apart. The easiest way to do that is to number them. The diagram to right repeats the design of the problem, but with the points numbered 1 through 16. The top point — where the paths start — is point 1, and the bottom point — where the paths end — is point 16. A path through the diagram can be labelled using the series of point labels through which the path travels. For example, the path (1, 2, 5, 9, 13, 15, 16) is a path from the top point to the bottom point. However, the first point is always 1, and the last point is always 16, so we can omit these. The point numbers have at most two digits, so we can simply use two digits for point number and concatenate the digits to make a single number. We could denote the path (1, 2, 5, 9, 13, 15, 16) by the single number 205091315.

Our program needs to know the connections between the points.
We could simply program them in somehow, but as Dijkstra (a Very OK
Name in computer science) says, make your data structures do most of
your work.
So instead we build a table of what points can be reached from each
point.
The CFX-9850G has a convenient data structure — the list —
that we can use for this.
We will use List 1 to describe the connections between the points.
The *k*-th element of List 1 will say what points can be
reached in one step from point *k*.
We could use a two digit representation as we are doing above for
the path names, but (with an eye towards the future and bigger
problems) we will instead use a radix 256 rather than a radix 100
representation.
Since a CFX-9850G list can have up to 255 elements, this will let
us use the same program for problems of this type of up to 255
points.
So the value of List 1[*k*] will be 256*i* + *j*,
where *i* is the point reachable from point *k* by
going left, and *j* is the point reachable from point *k*
by going right.
For example, the List 1 value for point 5 will be 256×8 + 9,
or 2057.
If there is no point that can be reached by going in a direction,
the point number will be 0.
For example, from point 15 one can go only left, to point 16, so the
List 1 value for point 15 will be 256×16 + 0, or 4096.
Similarly, from point 7 one can go only right, to point 11, so the
List 1 value for point 7 will be 0×256 + 11, or 11.
From point 16 (the bottommost point), one can go neither left nor
right, so the List 1 value for point 16 is zero.
We can use this to recognize that we are at the end of a path.

Finally, the program needs to know where it is in its path, and what
path it took, and how to get the “next” path from a path
it has, so it can enumerate the paths.
We will therefore keep a list — List 2 — that has this
information.
Each element in List 2 will describe a single step in the current
path.
Since “here” (the number of a point) can be up to 255,
we will use a List 2 value of 256*i* + *j* to describe
that at point *j* the path includes step *i*.
We will use an *i* value of 0 to denote a step to the right,
and an *i* value of 1 to denote a step to the left.

We are finally ready to write our program, which we will call P073001 in honor of this being the problem for 30 July 2001. We want to structure the program as a general path finding engine, with “hooks” for initializing the description of the network, for handling a path (display it, count it, or whatever else is wanted), and for reporting at the end. These subroutines we will call P073001A, P073001B, and P073001C, respectively. We also remember the lesson of Multiple of 12, and do not use recursion — the calculator has a subroutine nesting depth of 10 calls. While that would be enough for this program, it would put a limit on the maximum path length the general path finding engine could handle — and we would like to avoid that. So we will get down and dirty with labels, gotos, and conditional jumps.

The programs, available here or as a text file with .CAT file contents, are as shown below. Semicolons (“;”) start comments which are not to be entered into the calculator.

Program P073001 (247 bytes):

; Variables: ; A is the length of the path being processed ; Other variables are as noted in the code ; Symbols: ; -> is the assignment arrow ; / is the division operator ; ^ is the exponentiation operator ; => is the conditional jump operator Prog "P073001A" ; Initialize the map in List 1, and put the ; starting point number in B Seq(0,A,1,255,1)->List 2 ; Initialize the path; leave lots of room 0->A ; Initialize the path length to none ; ; Label 0 ; Enter the point whose point number is in B ; Lbl 0 A+1->A ; The path grows one point longer B->List 2[A] ; That point is B; start with the 0-th direction ; from that point ; ; Label 1 ; Try the point/direction at the end of the path ; Lbl 1 List 2[A]->B ; Retrieve the point/direction description into B 256Frac (B/256)->C ; Extract the point number into C List 1[C]->D ; Get the point description into D D=0=>Goto 2 ; If we are at a goal point, handle it Int (B/256)->B ; Retrieve the direction number into B Int (D/256^B)->D ; Retrieve the B'th and following directions into D D=0=>Goto 3 ; If all directions from this point have been ; exhausted, back off to previous point 256Frac (D/256)->E ; Get the B'th direction into E E=0=>Goto 4 ; If there is no B'th way to go, try another way E->B ; Get the next point number into B Goto 0 ; And go there ; ; Label 2 ; Handle being at a goal point ; Lbl 2 Prog "P073001B" ; Call the "handle goal point" subroutine ; Fall through into backing off one point ; ; Label 3 ; We have completely handled all directions from the current point. ; Back off one point and try the next direction from the previous ; point. ; Lbl 3 A-1->A ; Decrement path length A=0=>Goto 5 ; If path length is now 0, we have done all paths ; Fall through into increment direction number ; ; Label 4 ; Try the next direction from the current point. ; Lbl 4 List 2[A]+256->List 2[A] ; Add one to the step's direction index Goto 1 ; Try it ; ; Label 5 ; All paths have been enumerated. Summarize. ; Lbl 5 Prog "P073001C" ; Call summarization routine "Done" ; Say we are done

Note that the above program does *not* handle the possibility of
cycles.
It is assumed to be impossible to return to a point already visited.
This is true of this problem, but not necessarily of other problems.

Program P073001A (141 bytes):

; Variables: ; List 1 is the pathways that can be followed ; B is the starting point number ; K is the number of paths enumerated (zero) ; Symbols: ; -> is assignment arrow ; The following is all one line; it is broken ; across multiple lines here just to get it to fit {2*256+3,4*256+5,5*256+6,7*256+8,8*256+9,9*256+10,11,11*256+12, 12*256+13,13*256,14,14*256+15,15*256,16,16*256,0}->List 1 ; End of all one line ; Initialize the map 1->B ; Start at point 1 0->K ; No paths have been found

Program P073001B (76 bytes):

; Variables: ; A is the current path length ; B is the path step index ; C is the point number ; D is the summary number ; K is the path count ; List 2 is the path description ; Symbols: ; -> is assignment arrow ; / is division operator ; _ is display triangle 0->D ; Initialize the path summary For 2->B To A-1 ; Loop through all steps but first and last List 2[B]->C ; Pull out the step description C-256Int (C/256)->C; Pull out the point number 100D+C->D ; Put the point number at the end of the summary Next ; [End of loop through steps] D_ ; Display the path summary K+1->K ; Add 1 to the path count

Program P073001C (37 bytes):

; Variables: ; K is the number of paths found ; Symbols: ; _ is the display triangle "Number of paths" K_

Now, we run the program, and it happily enumerates the various paths through the map, here given in columns to save space:

306101315 305091215 205091314 205081114 306091315 305091214 205091215 204081215 306091215 305081215 205091214 204081214 306091214 305081214 205081212 204081114 305091315 305081114 205081214 204071114

Remember the paths are given as the interior point numbers, with two digits used for each point. The number 306101315, for example, indicates the path (1, 3, 6, 10, 13, 15, 16).

Then the program produces:

Number of paths 20 Done

So we know there are 20 ways to get from the top point to the bottom point. Further, we even know what those ways are.

Wonderful. But suppose someone wanted to know the paths through a 200-point network. The program would handle it — well, we would need to change the path reporting to handle the presumably longer paths — but how would we ever convince someone the program actually found all the paths? This problem is small enough that you can trace out the paths and convince yourself the program got them all, but perhaps there is some sort of cross-check you could do. The program finds all paths from the first point to the last point. This is like going forward into the problem. Would it be possible work it backward? Why, yes.

Consider being at the bottommost point.
From there, there is one way to get to the bottommost point: stay
where you are.
Now consider being at some point, any point, in the diagram.
The number of ways you can get to the bottommost point is
the number of ways you can get there by going left, plus the
number of ways you can get there by going right.
So if each point has a characteristic number *k*
that is the number of ways to get to the bottommost point
from that point, then every point’s *k* value
is the sum of the *k* values of the points to which it
connects.

The diagram to the right shows these characteristic numbers
*k* for all the points.
We start at the bottom with 1, then go up from there, making each
point’s number the sum of the numbers of the points to which
it leads.
The topmost point has a characteristic number 20 — there
are 20 ways to get from the top point to the bottom point.

Suddenly we realize that in this particular case, the problem is even simpler. We need to take six steps to get from the top point to the bottom point. We will take three steps to the left, and three to the right. Any three steps can be to the left; the other three are to the right. So the number of paths is the same as the number of ways to choose three left steps out of six total steps, or 6 choose 3, or 20.

Oh well. At least we have a nice depth-first search path program. Maybe it will come in useful someday.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.