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 *d*_{1} through
*d*_{6}.
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 *d*_{i} + *d*_{i+1}
+ ... + *d*_{j-1}.
Call this distance between the *i*-th town and the *j*-th
town *d*_{i,j}.
So:

Note *d*_{i,i+1} is just
*d*_{i}.
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, *d*_{1,7}, to be the
minimum possible value.

So we can rephrase the problem as follows:

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

Well, that is simple enough.
We just have six variables representing *d*_{1} through
*d*_{6}, 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 *d*_{1} through
*d*_{k} identified that satisfy the rule about
distinct *d*_{i,j} values.
Then a new distance, *d*_{k+1}, is a possible
addition only if the new *d*_{i,j} values
continue to be distinct.
So, given *d*_{1} through *d*_{k},
we have a rule that enables us to tell whether
*d*_{k+1} is allowable.
We can therefore consider candidate values for
*d*_{k+1}, which will be 1 through
*d*_{k+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
*d*_{i,j} values.

We need to know the maximum possible *d*_{k+1}
value, so we can tell when to quit searching possible
*d*_{k+1} values.
The overall distance *d*_{1,7} is just the sum of the
distances *d*_{i}.
Therefore, if we know a maximum possible value for
*d*_{1,7}, and the sum *d*_{1} through
the candidate *d*_{k+1} exceeds that sum, we
know that value of *d*_{k+1} is too large for it
to be involved the solution.
Thus, any larger value of *d*_{k+1} is also too
large, and we need not test them.
We therefore have a way to tell when *d*_{k+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
*d*_{k+1} to the working candidate solution until
the partial distance *d*_{1} + ... +
*d*_{k+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 *d*_{1} through
*d*_{k} to *d*_{1} through
*d*_{6} before modifying the value
*d*_{k}, then we initially find at least one
set of distances (such as 1, 2, 4, 8, 16, ...) that has distinct
*d*_{i,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
*d*_{i,j} generated from a set of
distances {*d*_{k}} are distinct?
We can get a maximum inter-town distance by adding up all the
*d*_{k}s — 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(*n*^{2}) 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 =
½(*n*^{2}-*n*) pairs of towns for which we
need to compute and mark the distance.
While an O(*n*^{2}) 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(*n*^{2}).
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
*d*_{i,j} for all pairs.
However, only the distances involving the last town are new.
The following graphic shows this situation.

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 *d*_{n}.
We use List 2 to hold the bit arrays indicating distances used:
List 2[*n*] includes the value 2^{k} if
distances *d*_{1} through
*d*_{n} “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.226e^{1.827n} fits the data
remarkably well.)
So while it was a nice thought to make the P041502A operation
O(*n*) instead of O(*n*^{2}), it was wasted
effort: it appears the overall approach requires
O(e^{n}) operations.
Once you have an exponential term in there, the polynomial factors
become largely irrelevant.
We succeeded in reducing an
O(*n*^{2}e^{n}) algorithm to an
O(*n*e^{n}) 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: .226e^{1.827×6} = 13027, less than half
the actual number of 29451.
Running the regression again, adding the new data point, gives a
formula of .172e^{1.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 *n*^{n}.
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 ]

Copyright © 2002 Brian Hetrick

Page last updated 26 May 2002.