Treebeard's Homepage : Stumpers

Treebeard's Stumper Answer
28 April 2000

Are We There Yet?

We've all been noticing our mileage with recent high gas prices. My car has two odometers that measure mileage. There's a six-digit counter that measures total miles, and a four-digit trip odometer that I can reset with a button. Recently, I noticed my odometer read [1 3 2 4 5 6]. Too bad the bottom was [5 4 9 0] instead of [7 8 9 0] (no tenths), not quite in order, but all the digits different at once! When should I have reset the trip odometer to make that happen? When should I next press reset so they'll all be different again as soon as possible?

My odometer really did reach this setting, and I managed to capture the moment! The trip odometer in my car actually measures tenths of a mile. I ignored that to simplify the stumper. I don't think I've ever pegged my Chevy Spectrum (pre-GEO) at 85 mph, but it still gets 40+ miles/gallon, important on a teacher's salary!


If I had reset my trip odometer 7,890 miles ago, then my odometers would now read [1 3 2 4 5 6] and [7 8 9 0]. That's simple subtraction. To next see all the digits at once I should press reset at 132,478 miles. Then 478 miles later, I will see [1 3 2 9 5 6] and [0 4 7 8]. I like this kind of problem that is so easy to state, but I don't have a clue how to begin! There's no simple calculation that gives the answer. Trial and error works, but there is also a method or algorithm that finds the answer for any mileage. The details are below.

Notes:

I found this great stumper in the Programmer Of The Month (POTM) contest archives. This is a great collection of tricky programming challenges. My car just happened to be close to an interesting mileage, and I got a picture after driving around the neighborhood for a while!

I thought this stumper would be too hard for Dunn Middle School students, but I went with it anyway since the problem is easy to understand, if not the solution. I don't really expect answers to all my stumpers at school, though the questions and answers should always make sense when revealed. Any problem with a solution is trivial, so it's always instructive to find problems we can't solve!

I found my first answer by trial and error. I kept the first 3 digits for the main odometer, and the smallest trip odometer value possible, and the smallest possible remaining number for the main odometer. This gave:

  [1 3 2 7 8 9]
      [0 4 5 6]
But subtracting these numbers to find when I should press reset gives 132,789 - 456 = 132,332 miles, which is less than my current mileage of 132,456. I can't press reset before 132,456 miles. It's not a possible solution.

Then I tried to make the top number bigger with the available digits:

  [1 3 2 8 9 7]
      [0 4 5 6]
But 132,897 - 456 = 132,441 miles, which is still less than 132,456 miles, so that's not a possible solution either.

So I made the top number even bigger:

  [1 3 2 9 8 7]
      [0 4 5 6]
Now 132,987 - 456 = 132,531 miles, which is more than my starting mileage of 132,456 miles, so it works! I should press reset to zero the trip odometer at 132,531 miles Then after 456 miles, my two odometers will read:
  [1 3 2 9 8 7]
      [0 4 5 6]
which uses each digit just once. This works, but it's not the best solution.

Graybear (busy with finals and the birth of daughter Evelyn Maria!) wrote:

Reset the trip odometer at either 132,513 or 132,522 miles. When it reaches 132,978 miles, the trip odometer will be either 0465 or 0456, respectively.
That's better than my first guess, but there's a better solution, and a sure way to find it.

The algorithm to find the best solution works by successively refining an initial worst-case guess. Paradoxically, the way to do this is to guess the largest number for the main odometer and the smallest number for the trip odometer. The method is to make guesses digit by digit from left to right, and refine the guess as you go along.

Let's assume the first 3 digits are ok, so the answer is of the form 132xyz miles. We know x must be 4 or larger, since that's the starting value. Then find the largest digits for y and z, and the smallest remaining value for the 4 digit trip odometer. Subtract them and check whether the result is greater than the starting mileage of 132,456. If not, then bump x to the next available digit and try again. When you find an acceptable value, move on to the next digit to the right and repeat. Here's how it works.

132498 - 0567 = 131,931too small, less than 132,456
132598 - 0467 = 131,131too small, less than 132,456
132698 - 0457 = 131,241too small, less than 132,456
132798 - 0456 = 132,342too small, less than 132,456
132897 - 0456 = 132,441too small, less than 132,456
132987 - 0456 = 132,531ok!

Now we know the answer is of the form 1329yz, so do the same thing with digit y starting with the smallest possible value which is zero. Note we don't have to check digits {1,2,3} since they are already used.

132908 - 4567 = 128,341too small, less than 132,456
132948 - 0567 = 132,381too small, less than 132,456
132958 - 0467 = 132,491ok!

Now we know the answer is of the form 13295z, so do the same thing with digit z starting with the smallest possible value which is still zero. This gets easier since more difgits are in use.

132950 - 4678 = 128,272too small, less than 132,456
132954 - 0678 = 132,276too small, less than 132,456
132956 - 0478 = 132,478ok!

We're out of digits, so that's the answer. I should press reset at 132,478 miles. Then 478 miles later, I will see

  [1 3 2 9 5 6]
      [0 4 7 8]

I can also press reset at 132,469 miles. Then 487 miles later, I will see

  [1 3 2 9 5 6]
      [0 4 8 7]
The reset for this answer is sooner, but the main odometer reading is the same. I don't know if that's a better solution, but at least I get a second chance to capture the moment.

This is a non-obvious algorithm, but it always gets the best answer. I remember having to learn how to find square roots by hand when I was in high school. It involved dividing the number into pairs of digits and doing something that looked like long division, but was even harder. Somehow that method approached the right answer as close as desired! Finding good algorithms for non-trivial problems is what computer programming is all about.

I couldn't resist writing a small DOS Basic program to solve this stumper. It's a quickie, and not at all optimized, but it seems to work. You can download my ODOMETER program with source and executable from Treebeard's Basic Vault.

There are some more stumpers here:

Back to Stumper


Last modified .

Copyright © 2000 by Marc Kummel / mkummel@rain.org