Project Euler # 36 Double-base palindromes in Python

Question

The decimal number, 585 = 1001001001 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

Awaiting feedback.

def is_palindrome(n):
    """returns True if palindrome, False otherwise."""
    to_str = str(n)
    if to_str == to_str[::-1]:
        return True
    return False


def find_palindromes(n):
    """generates all numbers if palindrome in both bases 2, 10 in range n. """
    decimal_binary = {decimal: bin(decimal)[2:] for decimal in range(1, n) if is_palindrome(decimal)}
    for decimal, binary in decimal_binary.items():
        if is_palindrome(binary) and not binary[0] == 0:
            yield decimal


if __name__ == '__main__':
    print(sum(list(find_palindromes(1000000))))

Answer 1

Code review

• The sequence of

      if condition:
          return True
      return False
  

  is a long way to say

      return condition
  

  Consider instead

  def is_palindrome(n):
      return to_str == to_str[::-1]:
  

• Generator vs list.

  A list takes space. The entire point of a generator is to not take space. Your find_palindrome does yield, that is produces one palindrome at a time. Very well suited to sum them as they are produced. Your code collects them all in a list for no reason.

  Even more curious is that your code

  • builds a dictionary
  • then yields each entry
  • to build the list
  • which is sent to sum to traverse it.

  I see at least 4 traversals over the same data. Seems excessive.

---

Efficiency

Thou shalt not brute force.

There are just 1000 decimal palindromes below 1000000: they are all in form abccba. In fact, we are not interested in all of them: if a is even, the binary representation would have a trailing 0, and to be a palindrome it would have a leading 0 as well. We may immediately disqualify such numbers. What remains, is just 500 candidates.

So, we only need to iterate over 500 numbers, instead of 1000000 your code does. A 2000-fold speedup, immediately. In fact, a bit more, because there is no need to test wether a decimal representation is a palindrome anymore, and such test is quite expensive. There is also no need to test for the parity, but it is peanuts.

The fun part is to design test that the binary representation is palindromic. The usually recommended

        binary = bin(n)
        return binary == binary[-1:1:-1]

works well in general. In this particular setting you know a lot about the numbers and their binary representation (at the very least you know how many bits the number takes), and there are few more performant solutions.

---

Rant

Please keep in mind that solving Project Euler problems will not make you a better programmer. Project Euler is designed for programmers striving to be better mathematicians.

And no matter what, do not brute force.