{"id":1689,"date":"2021-10-10T16:38:00","date_gmt":"2021-10-10T23:38:00","guid":{"rendered":"https:\/\/www.coastalvectors.com\/blog\/?p=1689"},"modified":"2021-09-10T22:44:53","modified_gmt":"2021-09-11T05:44:53","slug":"project-euler-43","status":"publish","type":"post","link":"https:\/\/www.coastalvectors.com\/blog\/2021\/10\/project-euler-43\/","title":{"rendered":"Project Euler 43"},"content":{"rendered":"<p><a href=\"https:\/\/www.coastalvectors.com\/blog\/2015\/06\/project-euler-357\/check\/\" rel=\"attachment wp-att-1184\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-1184\" src=\"https:\/\/www.coastalvectors.com\/blog\/wp-content\/uploads\/2015\/06\/check.jpg\" alt=\"\" width=\"150\" height=\"150\" \/><\/a><\/p>\n<p>I like to go back and re-solve Project Euler problems in different languages. Lately, I&#8217;ve been solving them in Javascript for fun. When I do this, I don&#8217;t look at previous solutions and try to do it from scratch. When I was finished, I was surprised by the performance of my solution to 43 compared to my previous attempts in other languages.<\/p>\n<p><a href=\"https:\/\/projecteuler.net\/problem=43\">Problem 43<\/a> is as follows:<\/p>\n<div class=\"problem_content\" role=\"problem\">\n<blockquote><p>The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.<\/p>\n<p>Let <i>d<\/i><sub>1<\/sub> be the 1<sup>st<\/sup> digit, <i>d<\/i><sub>2<\/sub> be the 2<sup>nd<\/sup> digit, and so on. In this way, we note the following:<\/p>\n<ul>\n<li><i>d<\/i><sub>2<\/sub><i>d<\/i><sub>3<\/sub><i>d<\/i><sub>4<\/sub>=406 is divisible by 2<\/li>\n<li><i>d<\/i><sub>3<\/sub><i>d<\/i><sub>4<\/sub><i>d<\/i><sub>5<\/sub>=063 is divisible by 3<\/li>\n<li><i>d<\/i><sub>4<\/sub><i>d<\/i><sub>5<\/sub><i>d<\/i><sub>6<\/sub>=635 is divisible by 5<\/li>\n<li><i>d<\/i><sub>5<\/sub><i>d<\/i><sub>6<\/sub><i>d<\/i><sub>7<\/sub>=357 is divisible by 7<\/li>\n<li><i>d<\/i><sub>6<\/sub><i>d<\/i><sub>7<\/sub><i>d<\/i><sub>8<\/sub>=572 is divisible by 11<\/li>\n<li><i>d<\/i><sub>7<\/sub><i>d<\/i><sub>8<\/sub><i>d<\/i><sub>9<\/sub>=728 is divisible by 13<\/li>\n<li><i>d<\/i><sub>8<\/sub><i>d<\/i><sub>9<\/sub><i>d<\/i><sub>10<\/sub>=289 is divisible by 17<\/li>\n<\/ul>\n<p>Find the sum of all 0 to 9 pandigital numbers with this property.<\/p><\/blockquote>\n<p>When I first solved this problem, I solved it in C. This was in 2014, and I was still fairly green. My solution at the time was to iterate through every 10-digit number and see if it was pandigital and then if it was, check if it met the sub-divisibility requirement.<\/p>\n<p>This solution is what you would call &#8220;brute-force&#8221;. It&#8217;s inelegant, and slow. However, it does work. It took 33.948 seconds to compute.<\/p>\n<p>A few years later I was doing more with Rust and Python. Both of these solutions I created used the same method. This probably happened because I wrote both solutions close together. At any case, this time I thought myself more clever and took a pandigital number, 1234567890, and discovered every permutation, and then checked for the sub-divisibility requirement of each.<\/p>\n<p>This is better than brute force, but still time consuming. Python can accomplish this in 18.724 seconds and Rust in 4.621. Better, but still not great.<\/p>\n<p>The general rule of thumb with Project Euler is that if a solution takes more than a second, you haven&#8217;t found the intended method of solving it.<\/p>\n<p>Looking at it this time around, it seemed like a very straightforward problem with an obvious path for a solution. Instead of finding pandigital numbers and checking if they meet the sub-string divisibility requirement, this time I would build up the pandigital numbers using the sub-strings.<\/p>\n<p>First I created arrays for the multiples of the first 7 primes with 2 and 3 digits. I then used a recursive function to build up a number using valid combinations of these sub-strings (since each one overlaps the next with 2 digits). This creates a much smaller group of numbers to check.<\/p>\n<p>Once I have all my potential pandigital numbers, I check to make sure they are in fact pandigital. <em>(Note that at this stage, they should be missing the first digit)<\/em>. When checking for pandigitality, I&#8217;m actually looking for 9 different digits, and if so, I prepend the missing 10th digit and voila, it&#8217;s a valid pandigital number!<\/p>\n<p>This solution is much, much faster at .237 seconds.<\/p>\n<p>I&#8217;m very pleased with that result, but a little shocked I didn&#8217;t see this method when I have solved it previously. It&#8217;s nice to know that since I first started solving these problems years ago, I can see measurable improvement in my ability to find and create solutions to these fun little puzzles.<\/p>\n<p><a href=\"https:\/\/github.com\/mryingster\/ProjectEuler\/blob\/master\/problem_043.js\">Source on GitHub<\/a><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>I like to go back and re-solve Project Euler problems in different languages. Lately, I&#8217;ve been solving them in Javascript for fun. When I do this, I don&#8217;t look at previous solutions and try to do it from scratch. When I was finished, I was surprised by the performance of my solution to 43 compared &hellip; <a href=\"https:\/\/www.coastalvectors.com\/blog\/2021\/10\/project-euler-43\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Project Euler 43<\/span><\/a><\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,1],"tags":[],"class_list":["post-1689","post","type-post","status-publish","format-standard","hentry","category-programming","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts\/1689","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/comments?post=1689"}],"version-history":[{"count":2,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts\/1689\/revisions"}],"predecessor-version":[{"id":1694,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/posts\/1689\/revisions\/1694"}],"wp:attachment":[{"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/media?parent=1689"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/categories?post=1689"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.coastalvectors.com\/blog\/wp-json\/wp\/v2\/tags?post=1689"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}