Previous page Next page Navigation bar

Puzzles

2001/2002 Puzzles

15 April 2002 (Eulerville to Newtonville)

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

Seven small towns are located on a straight highway. When heading north, the first town on the road is Eulerville and the last town is Newtonville. Between each of these towns are five others: Gaussville, Somerville, Fibonaciville, Riemannville, and Einsteinville. Each town is an integral number of miles from each other. The distances between the towns are such that if you know the number of miles traveled between two particular towns, the names of the towns can be determined uniquely. What is the minimum distance between Eulerville and Newtonville?

(Before we get into this problem, let me make an observation. This problem has the smallest number of solvers of any problem of the week. There is a reason for this: it cannot be done analytically, it is far too large to be done by hand, the solution properties are deceptive, there are a number of subtleties about constructing an algorithm to solve it, and it is at the edge of computational feasibility for something like a calculator. Other than that, it is really a quite pleasing little puzzle.)

Why, this puzzle sounds remarkably like a search problem. Unfortunately, it is a little unclear exactly what we are searching. Let us think about this.

There are seven towns, and so six distances between adjacent towns. Let us call these six distances d1 through d6. Now, the distance between any two towns has to uniquely identify the two towns. The distance between the i-th town and the j-th town is di + di+1 + ... + dj-1. Call this distance between the i-th town and the j-th town di,j. So:

d sub i,j equals the sum from k=i to k=j-1 of d sub k

Note di,i+1 is just di. In order for the distances between two towns to uniquely identify the two towns, all these distances must be distinct. And we want the overall distance, d1,7, to be the minimum possible value.

So we can rephrase the problem as follows:

Find six positive integers, {di : i = 1, ..., 6} where all values of di,j as defined above for i = 1, ..., 6, j = i + 1, ..., 7, are distinct, and where d1,7 = d1 + ... d6 is the minimum possible value.

Well, that is simple enough. We just have six variables representing d1 through d6, and we check all combinations of values from 1 through ... err, infinity. Perhaps we need to think just a little bit more.

Suppose we already have a set of distances d1 through dk identified that satisfy the rule about distinct di,j values. Then a new distance, dk+1, is a possible addition only if the new di,j values continue to be distinct. So, given d1 through dk, we have a rule that enables us to tell whether dk+1 is allowable. We can therefore consider candidate values for dk+1, which will be 1 through dk+1’s maximum possible value; and we can do this repeatedly, for all values of k. So once we have a partial candidate set of distances, we know how to add distances to it such that the final set retains the distinct di,j values.

We need to know the maximum possible dk+1 value, so we can tell when to quit searching possible dk+1 values. The overall distance d1,7 is just the sum of the distances di. Therefore, if we know a maximum possible value for d1,7, and the sum d1 through the candidate dk+1 exceeds that sum, we know that value of dk+1 is too large for it to be involved the solution. Thus, any larger value of dk+1 is also too large, and we need not test them. We therefore have a way to tell when dk+1 has reached a maximum value that needs to be tested.

Our program is starting to take shape. It will maintain a “smallest overall distance yet found” value, along with the distances making up that smallest overall distance yet found (so it can report them). The program will try to add all possible values of dk+1 to the working candidate solution until the partial distance d1 + ... + dk+1 is larger than the smallest overall distance yet found.

Incidentally, this approach of taking a partial potential solution and extending it to a family of more complete potential solutions is a fundamental technique of solution space search. The technique of discarding partial potential solutions when it can be determined that its family of extensions cannot hold an actual solution is called branch and bound. The potential solutions are organized into families deriving from one another (as branches of a tree grow from one another), and are bounded by results of the search already discovered. A related technique, usually found in artificial intelligence, is alpha-beta pruning. The alpha refers to a known lower bound, the beta refers to a known upper bound, on a function being optimized. Potential solutions are discarded as they become known to have values less than alpha, or greater than beta.

Now we have our overall iteration structure defined. If we try to extend a partial solution d1 through dk to d1 through d6 before modifying the value dk, then we initially find at least one set of distances (such as 1, 2, 4, 8, 16, ...) that has distinct di,j values, and so we will have a finite smallest overall distance yet found. The process outlined will therefore terminate. By construction, it will produce the desired minimum.

There is still a somewhat interesting problem before we sit down to code the solution. How can we tell whether all the distances di,j generated from a set of distances {dk} are distinct? We can get a maximum inter-town distance by adding up all the dks — and any intermediate distance will be less than that maximum. We can therefore create a vector of distances, and use the elements of this vector to indicate whether the distance has already been “used” by some intermediate distance. If, as we generate all possible intermediate distances, we discover a duplicate, then the set of distances violates the distinctness rule. If we do not discover a duplicate, then the set of distances follows the distinctness rule.

We immediately recognize the computation of all inter-town distances as an O(n2) operation, that is, one requiring a number of operations proportional to the square of the number of items being manipulated. With n towns, there are n(n-1)/2 = ½(n2-n) pairs of towns for which we need to compute and mark the distance. While an O(n2) operation is frequently acceptable, we will be performing this distance computation many, many times. If at all possible, we would prefer to use have an algorithm with an exponent of 1 — a linear algorithm, rather than a quadratic algorithm. As n may be as much as 6, such a change would speed up the program as a whole by as much as a factor of 6.

Initially, such a desire may appear unreasonable. After all, there are as many pairs of cities as there are pairs of cities, and that number is O(n2). However, the context of this computation is testing whether adding a distance to an existing “acceptable” set of distances retains the “acceptability” of the set. We have already computed most of the inter-town distances.

Suppose, as an example, that we have already figured an acceptable set of distances between the first four towns. When adding a new town, we must figure the distances di,j for all pairs. However, only the distances involving the last town are new. The following graphic shows this situation.

Image indicating d sub 4 affects only distances d sub i,j with j=5

This diagram shows the distances previously figured in the text color, while it shows the distances new to the additional candidate distance in a lighter color. Note that relatively few of these distances are new. Further, the new distances are the only ones that are going to change with different candidate values of the distance to the new town.

We can therefore expect that somehow saving the distinct distances already “used” by the set of towns, and using this is the computation of the new set of “used” distances, will substantially increase the performance of our program.

This imposes a new constraint on how we store the set of “used” distances. Previously, we needed only a vector of indicators. Now, we need a vector of indicators that we can (i) easily save and (ii) easily use as an initial value to a new vector of indicators. Each element of the “distance used” vector needs to store only two states: the distance has not been used, or the distance has been used. The two states suggests a Boolean vector, which in turn suggests using a bit vector. A bit vector could fit conveniently into a small number of variable values, depending on the length of the bit vector. The maximum bit number for which we need to worry is the minimum distance yet found. The overall program will compute an initial minimum distance yet found, then compute distances less than or equal to that distance. It therefore behooves us to figure out what the maximum value of the minimum distance yet found will be — or, given the way our program works, the first value of the minimum distance yet found.

As this computation need only be done once, we may as well do it by hand. The first distance will be 1, consuming only distance 1. The second distance will be 2, consuming both 2 and 3. The third distance must therefore be 4, also consuming 6 (4+2) and 7 (4+2+1). The fourth distance will be 5, also consuming 9 (5+4), 11 (5+4+2), and 12 (5+4+2+1). The next distance must be 8, the first unused distance, also consuming distances 13 (8+5), 17 (8+5+4), 19 (8+5+4+2), and 20 (8+5+4+2+1). The next distance must be 10, consuming also 18 (10+8), 23 (10+8+5), 27 (10+8+5+4), 29 (10+8+5+4+2), and 30 (10+8+5+4+2+1). That is a set of six distances with unique pairwise distances, and will be the first set of six distances accepted by the algorithm we have outlined. All other sets of distances found by the algorithm will have a smaller overall distance.

So we need only to be able to maintain 30 values, corresponding to distances 1 through 30. This is conveniently smaller than 32, and we can use the techniques of Bitwise Operations for the Calculator to store all 30 values in a single calculator variable.

So, we can now get down to work. First, we need to arbitrarily pick some variables. It will be easier to check the program’s logic if it has a smaller problem to work with, so we put the problem size — the number of distances — in A. We will pick distances one after the other, so we put the index of the distance we are currently figuring into B. Similarly, we want to terminate the search when the distance is at least as large as the best distance currently found, so we put this best distance into C.

We assume the existence of a “scoring” subroutine that will tell us whether a candidate distance is good, whether it conflicts with distances already in use, or whether it is too large. We will put the result of this subroutine into D. We will arbitrarily assign 0 as meaning the distance is good, 1 as meaning the distance conflicts with a distance already in use, and 2 as meaning the distance is too large. This subroutine will have to compute the total distance, to see if it is too large. For convenience, we have the subroutine also return the total distance in E.

The question of whether a distance is “too large” brings up an interesting point: what should happen if a distance is the same as the current best distance? This can occur when we find a second set of distances that has the same overall set of distances as a set we already found; and this might, but need not, occur when we have found the actual minimum distance. Should we replace the current best distance (and its set of inter-town distances) with the new set, or should we ignore the new set? We choose to ignore the new set: we will require that a new distance actually be smaller than the current best distance before we give it attention. Therefore, the “scoring” subroutine must report total distances exactly equal to the best distance currently found as “too large.” And we should remember that what we find as “the” minimum distance set of distances is actually a minimum distance set.

We also assume the existence of a reporting subroutine that displays the answer.

We use List 1 to hold the candidate distances: List 1[n] is the distance dn. We use List 2 to hold the bit arrays indicating distances used: List 2[n] includes the value 2k if distances d1 through dn “use” the distance k. Finally we will use List 3 to hold the best set of distances found so far.

The main program is straightforward. It has to perform three major functions. These functions are to start working on a new distance assuming previous distances have been accepted; to try another new distance assuming a previous try at a new distance was unsuccessful; and to advance past a newly discovered minimum overall distance. We therefore write the program as follows. As always, the programs are available in a text file with .CAS file contents, or may be entered as shown here.

; Program P041502
;
; Description:
;   Find a number of individual values such that the sums of all
;   contiguous sets of values are distinct.
;
; Variables:
;   A is the number of individual values required
;   B is the index of the value being examined
;   C is the minimum overall sum yet found
;   D is the coded return from the P041502A routine indicating whether
;     the value being examined is okay (0), conficts with other values
;     aready in use (1), or is too large (2).
;   E is the sum of the distances given to the P041502 routine
;   List 1[n] is the vector of distances
;   List 2[n] is state for the P041502A routine
;   List 3[n] is the best set of distances yet found
;
; Calling sequence:
;   None; main program.
;
; Implicit inputs:
;   None.
;
; Implicit outputs:
;   None.
;
; Side effects:
;   None.
;
; Symbols used:
;   -> is assignment arrow
;   <= is less than or equal to relational
;   => is conditional jump
;   <> is not equal to relational
;
 
6->A               ; Set the problem size into A
Seq(0,B,1,A,1)->List 1
                   ; Get space for the distances in List 1
List 1->List 2     ; Get space for the distance used vectors in List 2
1->B               ; Initially looking for first distance
31->C              ; We know 30 is the maximum distance
 
;
;   Label 0
;
;   Start looking for a B'th distance
;
 
Lbl 0
B<=A=>Goto 1       ; If all distances have been found, new best found
List 1->List 3     ; Save the distances into the "best yet" distances
E->C               ; Save the overall distance into the "best yet"
B-1->B             ; Retry the last distance (which will fail with
                   ;  'too large', forcing a new next to last
                   ;  distance value)
Goto 2             ; Retry the last distance
Lbl 1              ; [Else branch of label 0 test]
0->List 1[B]       ; Initialize B'th distance to 0
 
;
;   Label 2
;
;   Try the next greater value of the B'th distance
;
 
Lbl 2
List 1[B]+1->List 1[B]
                   ; Increment the B'th distance
Prog "P041502A"    ; Call the scoring routine
D=1=>Goto 2        ; If just a conflict, try next distance
D=2=>Goto 3        ; If too large, abandon this sequence
B+1->B             ; Set up to try next distance
Goto 0             ; Try the next distance
 
;
;   Label 3
;
;   The B'th distance is too large, and the sequence giving rise to it
;   is begin abandoned. Back off and modify the B-1'th distance and
;   restart the search.
;
 
Lbl 3
B-1->B             ; Decrement the distance index
B<>0=>Goto 2       ; Unless we are done, continue
 
;
;   Report the solution
;
 
"SOLUTION"
Prog "P041502B"
"DONE"

This is a simple program. It is simple largely because it delegates discovering the result of adding in a distance to a set of already used distances to a subroutine. The subroutine, however, is similarly straightforward:

; Program P041502A
;
; Description:
;   Figures the status of distances for the P041502 program.
;
; Variables:
;   D is the return value: 0 indicates the distance is neither too
;     large nor conflicts with existing distances; 1 indicates the
;     distance conflicts with existing distances; and 2 indicates the
;     distance is too large.
;   E is the overall distance
;   List 1[n] is the vector of distances
;   List 2[n] is vector of distance in use flags
;
; Calling sequence:
;   {Number of distances}->A
;   {Distance index}->B
;   {Shortest distance yet}->C
;   {Vector of distances}->List 1
;   Prog "P041502A"
;   D->{flag as described above}
;   E->{total distance}
;
; Implicit inputs:
;   List 2: the vector of distance in use flags. Construction of this
;     list, and correctness of this routine, depends on List 2 being
;     undisturbed since the last call with the same value of A and a
;     B value of either its value this call, or one less than its
;     value this call.
;
; Implicit outputs:
;   List 2: the vector of distance in use flags. Updated to reflect
;     the distance examined in this call.
;
; Side effects:
;   None.
;
; Symbols used:
;   -> is assignment arrow
;   <> is not equal to relational
;   => is conditional jump
;   ^ is the exponentiation operator
;   / is the division operator
;   >= is the greater than or equal to relational
 
0->D               ; Initially assume distance is okay
0->F               ; Get vector of distances
B<>1=>List 2[B-1]->F ; already in use
B->G               ; Get index of last (added) distance
0->E               ; Zero distance total
While G>0          ; Loop through all distances in reverse order
List 1[G]+E->E     ;   Add this distance into the total
2^E->H             ;   Get the bit corresponding to this distance
If Frac (Int (F/H)/2)=0
                   ;   Test if this distance is allowable
Then H+F->F        ;     If so, mark the distance as in use
Else 1->D          ;     If not, indicate the distance conflicts
IfEnd              ;   [End of test if the distance is allowable]
G-1->G             ;   Continue with the previous distance
WhileEnd           ; [End of loop through all distances]
If E>=C            ; Test if the distance is too large
Then 2->D          ;   If so, indicate that
Else F->List 2[B]  ;   Otherwise, save this distance in use vector
IfEnd              ; [End of test if the distance is too large]

Finally, we have the straightforward reporting routine:

; Program P041502B
;
; Description:
;   Displays the distances in List 1. The distances are displayed five
;   to a line, with two digits each.
;
; Variables:
;   A is the number of distances
;   F is the distance index
;   G is the number of items in the display accumulator
;   H is the display accumulator
;   List 3[n] is the vector of distances
;
; Calling sequence:
;   {Number of distances}->A
;   {Vector of distances}->List 3
;   Prog "P041502B"
;
; Implicit inputs:
;   None.
;
; Implicit outputs:
;   None.
;
; Side effects:
;   Displays values on the display.
;
; Symbols used:
;   -> is assignment arrow
;   >= is greater than or equal to relational operator
;   _ is the display triangle
;   <> is the not equal to relational operator
 
0->G               ; Zero the number of distances reported this line
0->H               ; Zero the accumulator for the line
For 1->F To A      ; Loop through the distances
100H+List 3[F]->H  ;   Add the distance to the line
1+G->G             ;   Note one more distance in the line
If G>=5            ;   If we have 5 distances (10 digits) this line,
Then H_            ;     Display the line
0->G               ;     Zero the count of distances this line
0->H               ;     Zero the accumulator for the line
IfEnd              ;   [End of test if we have 5 distances this line]
Next               ; [End of loop through distances]
G<>0=>H_           ; If there are distances in the buffer, display

We can simply enter all of these into the calculator, select P041502, and press “EXE.” But first we test the program. The program was written with the number of distances a variable, A. If we change the first line of the program P041502 from

6->A

to

1->A

the program should happily find the minimum distinct distance between two towns. We make this change, and the program quickly reports 1 as the set of distances. That seems entirely reasonable. Changing the line to

2->A

and running the program gets the results 1, 2, which similarly seems reasonable. Changing the number of distances to 3 and running the program a third time gets the result 1, 3, 2. This result is not only reasonable, it is more than reasonable: we had anticipated (well, I had anticipated) 1, 2, 4, but the program did what it was supposed to do, optimize. Trying 4 as the number of distances gives the result 1, 3, 5, 2. But it is taking a bit more time to get each of these answers. We instrument the program a wee bit: we add the line

0->W

at the start of the main program P041502, and the line

W+1->W

to the start of program P041502A. This gives us a count of the number of times the P041502A program is run. Going through the sequence again, and this time also solving for 5 distances (which takes about half an hour), we find the following results:

Number of Distances

Distances

P041502A Executions

1

1

2

2

1, 2

7

3

1, 3, 2

38

4

1, 3, 5, 2

325

5

1, 3, 6, 2, 5

2722

The number of times program P041502A is executed seems like an exponential. (In fact, the formula 0.226e1.827n fits the data remarkably well.) So while it was a nice thought to make the P041502A operation O(n) instead of O(n2), it was wasted effort: it appears the overall approach requires O(en) operations. Once you have an exponential term in there, the polynomial factors become largely irrelevant. We succeeded in reducing an O(n2en) algorithm to an O(nen) one — each takes roughly forever to compute. Problems such as this, which require an exponential amount of computation based on the problem size, are regarded as computationally infeasible.

However, our formula indicates a problem of size 6 should require only about 7 times as much computation as a problem of size 5, and the problem of size 5 took about half an hour to compute. So we plug in 6 as the problem size, start the calculator program, and go to bed. The answer will be waiting for us in the morning.

And in the morning, indeed, we find the calculator has finished the computation and has turned itself off. Not all is lost: we cleverly put the best distances into List 3, and memory survives a power off. The saved best distance list in List 3 is 1, 3, 6, 8, 5, 2. Variable W has the count of P041502A executions: 29451.

Our formula substantially underestimated the number of P041502A executions: .226e1.827×6 = 13027, less than half the actual number of 29451. Running the regression again, adding the new data point, gives a formula of .172e1.943x — the scaling multiplier has dropped and the exponential factor has increased. This indicates the actual complexity formula actually rises faster than does an exponential. It is, of course, absolutely senseless to estimate asymptotic complexity with observations of complexities at problem sizes 1 through 6. Nontheless, the counts indicate the complexity rises faster than n! but not as fast as nn. At any rate, the stated problem is only barely feasibile using the calculator. A problem of size 7 would very likely require more computation than the calculator could provide on a single set of batteries.

The answer to the puzzle as posed — what is the minimum distance between the outermost two towns — is therefore 1+3+6+8+5+2, or 25.

[ Previous page | Top of page | Next page ]

Previous page Top of page Next page Navigation bar

Copyright © 2002 Brian Hetrick
Page last updated 26 May 2002.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Index

15 April 2002

11 February 2002

1 October 2001

24 September 2001

13 August 2001

30 July 2001

18 June 2001

4 June 2001

21 May 2001

7 May 2001

30 April 2001

23 April 2001

9 April 2001

18 February 2001

4 February 2001

29 January 2001

Previous years

In memoriam: Dijkstra

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data