Puzzles

2001/2002 Puzzles

30 July 2001 (Moving Down)

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 256i + 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 256i + 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.