So, it turns out that my ISP blocked Project Euler, so instead of
working on my next problem, I polished Problem 4 a bit:
>A palindromic number reads the same both ways. The largest palindrome made
>from the product of two 2-digit numbers is 9009 = 91 × 99.
>Find the largest palindrome made from the product of two 3-digit numbers.
Those who don't want spoilers should look away.
While it's perfectly fine to brute-force this (what I initially did)
with two for-loops, I wanted to make a better version. Here's the
code:
First something to check whether a number is a palindrome:
def is_palindrome(number):
number = str(number)
return number == number[::-1]
Then the crunching part:
def biggest():
big_x, big_y, max_seen = 0, 0, 0
for x in range(999, 99, -1):
for y in range(x, 99, -1): #so we don't double count
if x*y < max_seen: continue #since we're decreasing
if is_palindrome(x*y):
big_x, big_y, max_seen = x, y, x*y
return big_x, big_y, max_seen
However, I got to thinking... If we assume that the palindrome starts
with 9, it must end with 9 (I think that's a fair assumption, really
-- but it could come back and bite me I suppose). That means that the
only values for the third digit in each of the two factors would have
to be 1, 3, 7 or 9 (1 * 9, 3 * 3, 7 * 7 or 9 * 1). If we check for
this condition before checking whether a number is palindromic, we
ought to cut down on the numbers checked by, oh, I don't know... half,
at least? (it turns out that it's more: 405450 values, only 64980 have
1, 3, 7 or 9 in the end), so in order to avoid checking some 340,000
numbers, I wrote a third function:
def check_value(number1, number2):
number1, number2 = str(number1), str(number2)
return number1[-1] in "1379" and number2[-1] in "1379"
Putting this one inside the biggest() function, the final biggest()
function looks like this:
def biggest():
big_x, big_y, max_seen = 0, 0, 0
for x in range(999, 99, -1):
for y in range(x, 99, -1): #so we don't double count
if check_value(x, y): #we ignore all numbers that
doesn't end in 1379
if x*y < max_seen: continue #since we're decreasing
if is_palindrome(x*y):
big_x, big_y, max_seen = x, y, x*y
return big_x, big_y, max_seen
My biggest problem now is that I don't know how to measure any changes
in efficiency. I know that the functions are working perfectly fine
as-is, and I shouldn't really optimize without a need to, but I'm
mostly curious as to whether the check_value() function is worth it or
not. To this I thought I'd use timeit(), but I can't for the life of
me work out how it works. At all. I've tried using it from the command
prompt, from the interpreter and in the code itself and it just
doesn't work. Or, it might very well work but it doesn't actually time
anything for me. It's very frustrating, but I feel like I'm too stupid
to read the official documentation for it (that is, I might understand
the words in the documentation, but I can't get it to work). Please
help?
--
best regards,
Robert S.
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
