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))))

• Peilonrayz: Can you add the correct tags, as I requested in one of your previous questions. You may want to reduce the amount of questions you're posting.
• user203258: there is a problem with the tags, I usually tag something such as 'python3.x' or whatever and I end up getting less tags. Anyway the 'python3.x' is checked what's wrong?
• Peilonrayz: codereview.stackexchange.com/questions/224598/…

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.

• user203258: And what do you suggest for improving my programming skills other than project Euler given that 2 months ago i didn't know what programming is?
• vnp: @emadboctor It is a huge question you ask. An obvious - and very vague - answer is to sign up to some class, pick a teacher, and study. Just as you'd study for an artist, a doctor, or a lawyer. Studying solo is a recipe to failure. Consider asking at CS educators