As I work through these projecteuler problems, it’s become apparent that my brain tends towards a particular style of solution. When I know one way to solve a problem, I tend to just implement it, as I want to get to the next one. In the future, I’m going to start trying to find multiple solutions right off the bat, before I check to see if I’ve answered the problem correctly. Here’s an example; problem 4 requested the largest number that is a product of two 3 digit numbers as well as being a palindrome.<\/p>\n
It’s obvious the answer will be <= 999 x 999 and >= 100 x 100. I came up with this solution relatively quickly:<\/p>\n
\r\ndef findLargestPalindrome():\r\n factorA = 999\r\n factorB = factorA\r\n maxToCheck = 100\r\n maxPalindrome = 0\r\n\r\n while factorA > maxToCheck:\r\n factorB = factorA\r\n while factorB > maxToCheck:\r\n temp = factorA * factorB\r\n if temp < maxPalindrome:\r\n maxToCheck = factorB\r\n break\r\n else:\r\n tempStr = str(temp)\r\n if tempStr == tempStr[::-1]:\r\n maxToCheck = factorB\r\n maxPalindrome = temp\r\n break\r\n factorB -= 1\r\n factorA -= 1\r\n return maxPalindrome\r\n<\/pre>\nAnswer: 906609. 100 iterations took 2.677 seconds<\/p>\n
I want to call out that the syntax for reversing a string, string[::-1] is pretty odd looking. It asks for the representation of the string from the beginning to the end in -1 steps\/strides. So position -1 from the start is the end, and then position -1 from the end is the second to last character, etc.<\/p>\n
When I was playing with Erlang, one of the fundamental aspects of the language is the notion of single assignment i.e. a variable can only be assigned to once, and then never changes. Obviously the code above reassigns numerous variables over and over again during execution. As an exercise I decided to re-write the answer recursively and pretend I was constrained by the single assignment rule.<\/p>\n
\r\ndef findLargestPalindrome2(factorA, factorB, maxToCheck, maxPalindrome):\r\n if factorA < maxToCheck:\r\n return maxPalindrome\r\n elif factorB < maxToCheck:\r\n newFactor = factorA - 1\r\n return findLargestPalindrome2(newFactor, newFactor, maxToCheck, maxPalindrome)\r\n else:\r\n candidate = factorA * factorB\r\n if candidate < maxPalindrome:\r\n newFactor = factorA - 1\r\n return findLargestPalindrome2(newFactor, newFactor, factorB, maxPalindrome)\r\n else:\r\n tempStr = str(candidate)\r\n if tempStr == tempStr[::-1]:\r\n newFactor = factorA - 1\r\n return findLargestPalindrome2(newFactor, newFactor, factorB, candidate)\r\n else:\r\n return findLargestPalindrome2(factorA, factorB - 1, maxToCheck, maxPalindrome)\r\n<\/pre>\nThis function has a very different look to it as state must be passed to each recursive call. I also apparently exceeded the default recursion limit and had to: sys.setrecursionlimit(7000). The recursive solution is also almost twice as slow.<\/p>\n
Answer: 906609. 100 iterations took 4.350 seconds<\/p>\n
This is also another example of a problem that can be optimized further, and even solved with pen and paper...<\/p>\n","protected":false},"excerpt":{"rendered":"
As I work through these projecteuler problems, it’s become apparent that my brain tends towards a particular style of solution. When I know one way to solve a problem, I tend to just implement it, as I want to get to the next one. In the future, I’m going to start trying to find multiple […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[18,11,19,17],"_links":{"self":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/138"}],"collection":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/comments?post=138"}],"version-history":[{"count":4,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/138\/revisions"}],"predecessor-version":[{"id":142,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/138\/revisions\/142"}],"wp:attachment":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/media?parent=138"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/categories?post=138"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/tags?post=138"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}