1
\$\begingroup\$

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))))
\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Peilonrayz Jul 21 at 11:05
  • \$\begingroup\$ 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? \$\endgroup\$ – user203258 Jul 21 at 11:25
  • 1
    \$\begingroup\$ codereview.stackexchange.com/questions/224598/… \$\endgroup\$ – Peilonrayz Jul 21 at 11:26
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – user203258 Jul 21 at 22:41
  • \$\begingroup\$ @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 \$\endgroup\$ – vnp Jul 21 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy