5
\$\begingroup\$

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!
\$\endgroup\$

1 Answer 1

7
\$\begingroup\$

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.
    """
    def as_reading(x):
        return format(x % 10**6, "06")

    # 6 digit numbers
    for guess in range(10**6):
        valid = (
            is_palindrome(as_reading(guess + 0)[2:]) and
            is_palindrome(as_reading(guess + 1)[1:]) and
            is_palindrome(as_reading(guess + 2)[1:5]) and
            is_palindrome(as_reading(guess + 3))
        )

        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.

\$\endgroup\$
7
  • \$\begingroup\$ 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 \$\endgroup\$ Aug 4, 2016 at 23:25
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Veedrac
    Aug 4, 2016 at 23:47
  • 1
    \$\begingroup\$ @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! \$\endgroup\$
    – Veedrac
    Aug 4, 2016 at 23:48
  • \$\begingroup\$ 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 \$\endgroup\$ Aug 6, 2016 at 16:50
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Veedrac
    Aug 6, 2016 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.