I found the absolute best way to learn the Python programming language, while at the same time, increasing deductive logic capacity and learning mathematics. The way is through Project Euler. Of course, you don't have to use the Python language to complete the problems. You can use any language you like, or use pencil and paper if that suits your needs best.
At any event, I'm going through the problems one by one, and have completed the first 4. The fourth problem took a great deal of thinking to get right, but I nailed it out slowly, and actually came up with a pretty fast solution. The problem is this:
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.
After hacking a bit, I realized that the only way I knew how to solve this problem, was to brute force it. Some things came to mind almost immediately:
- I should start with 999 * 999 and count down, rather than 100 * 100 and count up, seeing as though I'm looking for the largest palindromic number.
- 999 * 999 = 998001 iterations through every number, but I will be testing each one at least twice, so I only need to test half (999 * 999, 999 * 998, 999 * 997, ... 999*100, 998 * 998, 998 * 997, ... 998 * 100, 997 * 997, 997 * 996, ..., etc)
- There should a pattern with palindromic numbers to further increase my algorithm.
Point 3 was the hardest for me to find, but I found it. There is in fact a pattern with 6-digit palindromic numbers (technically speaking, any even-digit palindrome (I know that my result will be 6-digits, or at least I'm fairly confident)). Consider the palindrome "abccba":
Let's look at the numeric column of each letter: a(100,000) + b(10,000) + c(1,000) + c(100) + b(10) + a(1) Adding similar variables (in algebraic notation): 100001a + 10010b + 1100c The common denominator is 11: 11(9091a + 910b + 100c) This means that each palindrome will be a multiple of 11.
This means that I can start with 999 * 990 for my first test, 999 * 979 for my second, 999 * 968 for my third, and so on. This will greatly reduce the number of iterations that I need to step through when finding this palindromic number. It wasn't long, however, that I realized this problem will need to be separated into two functions. One to determine if the number is in fact a palindrome, returning either True or False, and the second function to iterate through all the possible product combinations, filling an array with nothing but palindromic numbers. Here is my solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #!/usr/bin/env python def is_palin(string): """Returns true if a string is a palindrome""" start, end = 0, len(string) - 1 while end > start: if string[start] != string[end]: return False start += 1 end -= 1 return True def palindrome(): """Finds the largest palindrome that is the product of 2 3-digit numbers""" num1 = 999 result_arr = [] while num1 > 100: num2 = 990 if num2 > num1: num2 = num1 - (num1 % 11) while num2 > 109: if is_palin(str(num1 * num2)): result_arr.append(num1 * num2) num2 -= 11 num1 -= 1 result_arr.sort() print result_arr[len(result_arr) - 1] palindrome() |
A couple comments about the code. First, I'm turning the number into a string, then determining if that string is in fact a palindrome. I look at the beginning and ending letter of the string. If they match, I increase the beginning letter by 1 and decrease the ending letter by one, and test again if they match. I continue to do this throughout the string until every letter was tested. If they all passed, return True, otherwise, return False. Second, to keep my algorithm only churning through half of the required iterations, I want to make sure that I start with the square, and work down from there. For example:
View with a monospace font, or this table won't make much sense (see the original post): 999*990 998*990 997*990 ... 990*990 999*979 998*979 997*979 ... 990*979 989*979 988*979 987*979 etc. 999*968 998*968 997*968 ... 990*968 989*968 988*968 987*968 ... ... ... ... ... ... ... ... 999*121 998*121 997*121 ... 990*121 989*121 988*121 987*121 999*110 998*110 997*110 ... 990*110 989*110 988*110 987*110
The only aspect about my algorithm, was that I am not breaking out when I find the largest palindromic number. The reason for this was simple- I got too caught up in churning through every 11 numbers, that I forgot to test when I found the largest. However, after looking at the code, I figured that I was curious about all the palindromes that I have found, so I stored them in an array then sorted it ascending. It is interesting to look through the array at each one, seeing the patterns throughout.
At any rate, on my machine, I benchmarked the code:
aaron@kratos:~$ time python palindrome.py 906609 real 0m0.067s user 0m0.068s sys 0m0.000s
Nice and lean. 0.067 seconds isn't bad for a first attempt, I think. Thoughts? Comments?
{ 13 } Comments