kleemans.ch

Project Euler is not only a great place for solving problems, but I often find myself rewriting my code over and over again, until I get a really short piece of code. Most of the time I'll stop if it gets really ugly and unreadable, but at that point I'm kinda satisfied with the amount of LOC (lines of code). (Actually, most of the time the code gets better and faster until a certain level of reduction.)

Today I solved Problem 36. My first attempt was just to loop through the numbers from 1 to a million and use bin(), pythons int->binary function and str() to check for palindromes.

I always try to build a top-down model of the code at the beginning of what I'm going to do, and in this case it was something like this:

for i < 1 million
    if i is palindrome and bin(i) is palindrome
        add i to sum
print sum

After breaking down tasks to simple functions it's easy to implement them. So the palindrome-check became pal(n), in which the first and the last character are compared, then the second and the second-last and so on. If one pair is not the same the function returns False.

I did a check wether the middle of the string was reached: so if c is bigger than half of the length (len(n)/2), it stops and concludes, that the two strings have to be the same. I didn't really overthink this, I just had the feeling to stop after half the string.

If len(n) is even, both halves are compared, if len(n) is uneven, the middle character is left out. So the program was:

from __future__ import division
def pal(n):
    for c in range(0, len(n)):
        if n[c] != n[-c-1]:
            return False
        if c > len(n)/2:
            return True
    return True
s = 0
for i in xrange(1, 1000000):
    if pal(str(i)) and pal(bin(i)[2:]):
        s += i
print s
#V1, runtime: 1.77s,  lines of code: 13

which gave the correct result, 872187.

I then rethought the pal(n)-method and saw that it doesn't matter if the length of the string is even or uneven - we could just loop through the whole string. This way, the effort would be a bit higher, because we process the whole string (if it's a palindrome - in most of the cases we won't reach the middle) but we can leave away the extra condition.

def pal(n):
    for c in range(0, len(n)):
        if n[c] != n[-c-1]:
            return False
    return True
s = 0
for i in xrange(1, 1000000):
    if pal(str(i)) and pal(bin(i)[2:]):
        s += i
print s
#V2, runtime: 1.77s, LOC: 10

Still correct, same runtime, but not very pretty. I once again tried to optimize the the palindrome thing, and then grasped that a comparison of a string with its inverse would do the job. This got me rid of the whole palindrome function:

s = 0
for i in xrange(1, 1000000):
    if str(i) == str(i)[::-1] and bin(i)[2:] == bin(i)[2:][::-1]:
        s += i
print s
#V3, runtime: 1.10s, LOC: 5

The code got even a bit faster, which is almost always the case when using built-in functions. Since there was only a loop and two conditions left which lead to counting variables, it was quite obvious to put that together in one generator expression, ending up in a one-liner:

print sum([i for i in xrange(1, 1000000) if str(i) == str(i)[::-1] and bin(i)[2:] == bin(i)[2:][::-1]])
#V4, runtime: 1.10s, LOC: 1

Runtime stays the same, but the code melts down to just one line. I wonder how many Project Euler Problems could be solved with (Python) one-liners...? :)