# The Palindromic Odometer Puzzler: A Programmatic Solution

That is a programmatic solution to a puzzler from Car Talk, its summary is:

"I noticed that the last 4 digits were palindromic. I drove a mile, and the last 5 were palindromic. I drove another mile and the middle 4 were palindromic, and the ends were not involved. And then one mile later, all 6 digits were palindromic."

def is_palindrome(string):
"""Finds if a string is a plaindrome or not.

string: str

returns: bool
"""
return string == string[::-1]

def find_puzzle_number():
"""Finds the number which was first seen.

prints: int
"""
guess = 100000
# the odometer shows only 6 numbers,
# therefore 999999 is the last number to test.
while guess < 1000000:
if is_palindrome(str(guess)[2:]):  # last 4 numbers.
if is_palindrome(str(guess + 1)[1:]):  # last 5 numbers.
if is_palindrome(str(guess + 2)[1:5]):  # middle 4 numbers.
if is_palindrome(str(guess + 3)):
print(guess)

guess = guess + 1

print('These are the possible odometer readings: ')
find_puzzle_number()


Notes:

• I'm a hobbyist and a beginner.
• I don't only want to optimize the code, but also my skills and style. Therefore any notes, advice and suggestions aren't only welcomed, but also encouraged!

The documentation

   string: str

returns: bool


is pretty obvious. I would skip it. The rest of the documentation can be more idiomatically written as

"""Return whether input sequence is a palindrome."""


(note palindrome, not plaindrome). I removed the term string because many sequence types can be palindromic, like [1, 2, 3, 2, 1].

find_puzzle_number should yield, not print, its values.

I would change the documentation to specify the rules the output satisfy.

def find_puzzle_number():
"""Generates 6-digit integers, x, where all of

* the last 4 digits of x,
* the last 5 digits of x+1,
* the middle 4 digits of x+2, and
* all 6 digits of x+3

are palindromes.
"""
guess = 100000
# the odometer shows only 6 numbers,
# therefore 999999 is the last number to test.
while guess < 1000000:
if is_palindrome(str(guess)[2:]):  # last 4 numbers.
if is_palindrome(str(guess + 1)[1:]):  # last 5 numbers.
if is_palindrome(str(guess + 2)[1:5]):  # middle 4 numbers.
if is_palindrome(str(guess + 3)):
yield guess

guess = guess + 1


The while should become a for

# 6 digit numbers
for guess in range(10**5, 10**6):


Then the if chain of is_palindromes can be simplified:

valid = (
is_palindrome(str(guess + 0)[2:]) and
is_palindrome(str(guess + 1)[1:]) and
is_palindrome(str(guess + 2)[1:5]) and
is_palindrome(str(guess + 3))
)

if valid:
yield guess


Now note something bad: guess + 3, can overflow. Either you want to clamp the code so that guess + 3 < 10**6, or you want to perform modular arithmetic.

Further, you don't know that 10**5 is a valid lower bound: 000000 is a valid reading. You can use format(guess, "06") to pad like this.

If you care about speed, PyPy makes the code run in about a tenth the time.

def is_palindrome(seq):
"""Return whether input sequence is a palindrome."""
return seq == seq[::-1]

def find_puzzle_number():
"""Generates 6-digit integers, x, where all of

* the last 4 digits of x,
* the last 5 digits of x+1,
* the middle 4 digits of x+2, and
* all 6 digits of x+3

are palindromes.
"""
return format(x % 10**6, "06")

# 6 digit numbers
for guess in range(10**6):
valid = (
)

if valid:
yield guess

print('These are the possible odometer readings: ')
for solution in find_puzzle_number():
print(solution)


Note that there are simple optimizations you can apply. For instance, you can easily iterate over only those values for which guess + 3 is a palindrome by construction - this reduces the values to iterate over from $10^6$ to $10^3$.

for guess_digits in range(10**3):
# guess + 3 is a palindrome
# NOTE: relies on correct handling of wrapping
guess = guess_digits + int(format(guess_digits, "06")[::-1]) - 3


This makes the code basically instantaneous, so if optimizations were pointless to apply before they're most certainly pointless to apply now.

• Thank you for this great review! I'd to ask about something. Why I should use "for" instead of "while"? What is the meaning of: "guess + 6 can overflow" (I'm a beginner)? It is said, in the full description of the puzzler, that the odometer shows only whole miles and he was driving. Therefore, is 10 ** 5 a valid lower bound? The puzzler is on: cartalk.com/content/palindromic-odometer Aug 4, 2016 at 23:25
• @MahmudMuhammadNaguib Whoops, I meant "guess + 3 can overflow". IOW, if you guess 999 998, then is_palindrome(str(guess + 3)) will be operating on is_palindrome(str(1000001))! But that's not a valid reading! $10^5$ is a reasonable lower bound, but you could consider 0-1-2-3-2-0 to be a valid odometer reading. Aug 4, 2016 at 23:47
• @MahmudMuhammadNaguib You should use for instead of while because that's what for is designed to do. It looks nicer, and it reduces the chance of errors. There are only upsides! Aug 4, 2016 at 23:48
• I've implemented your suggestions, but I can't understand: for guess_digits in range(10**3): # guess + 3 is a palindrome # NOTE: relies on correct handling of wrapping guess = guess_digits + int(format(guess_digits, "06")[::-1]) - 3 Aug 6, 2016 at 16:50
• @MahmudMuhammadNaguib guess_digits will be the bottom 3 digits of guess + 3. We can make guess + 3 by flipping the bottom digits, as we know guess + 3 is a palindrome. Thus, guess + 3 == guess_digits + int(format(guess_digits, "06")[::-1]). Then we need to get guess, so we subtract the 3 again. Note that this can become negative if guess_digits == 0, so you need to handle that. In my code, as_reading handles it by wrapping negative numbers back around to high numbers. Aug 6, 2016 at 16:51