Treebeard's Stumper Answer

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 sixdigit counter that measures total miles, and a fourdigit 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 (preGEO) 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 worstcase 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,931 too small, less than 132,456 132598  0467 = 131,131 too small, less than 132,456 132698  0457 = 131,241 too small, less than 132,456 132798  0456 = 132,342 too small, less than 132,456 132897  0456 = 132,441 too small, less than 132,456 132987  0456 = 132,531 ok! 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,341 too small, less than 132,456 132948  0567 = 132,381 too small, less than 132,456 132958  0467 = 132,491 ok! 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,272 too small, less than 132,456 132954  0678 = 132,276 too small, less than 132,456 132956  0478 = 132,478 ok! 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 nonobvious 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 nontrivial 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:
 When will my two odometers next show all different digits if I don't press reset? Is there always a solution? This was another POTM problem. Is the best answer that in 3,234 miles my odometers will read 135,690 and 8,724?
 My real trip odometer only counts to 999.9 miles, but it measures tenths of a mile. So when should I next reset to capture a photo with all different digits? Graybear managed to find time with his new daughtor Evelyn Maria to figure that:
If you reset the trip odometer at 132,467.1, then when it reaches 132,546, the trip odometer will read 078.9
 I vaguely remember a movie where a crooked used car dealer runs the odometer backwards with a power drill. In my car, driving backwards still adds miles! How do real odometers work?
Back to Stumper
Last modified .