{"id":187,"date":"2021-03-14T17:04:55","date_gmt":"2021-03-14T17:04:55","guid":{"rendered":"http:\/\/aslak.nu\/?page_id=187"},"modified":"2021-03-17T19:44:21","modified_gmt":"2021-03-17T19:44:21","slug":"project-euler","status":"publish","type":"page","link":"http:\/\/aslak.nu\/index.php\/portfolio\/project-euler\/","title":{"rendered":"project euler"},"content":{"rendered":"\n<div style=\"height:100px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h4 class=\"alignwide wp-block-heading\"><span class=\"has-inline-color has-accent-color\">Introduction<\/span><\/h4>\n\n\n\n<div class=\"wp-block-columns alignwide is-layout-flex wp-container-core-columns-is-layout-8f761849 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<p class=\"wp-block-paragraph\">Project Euler is a websites dedicated to problem solving. The site is is similar but much older than the usually more known website called HackerRank. Problems at Project Euler always require a number as an answer. The problems increase in difficulty. Most problems can not be brute forced (at least not in the early 2000s) and therefore often requires a mathematical trick to quickly find the answer. Below are a couple of selected problems which sparked my interest, as they are easy to understand and have an elegant solution.    <\/p>\n<\/div>\n<\/div>\n\n\n\n<h4 class=\"alignwide wp-block-heading\"><span class=\"has-inline-color has-accent-color\">Problem 15<\/span><\/h4>\n\n\n\n<figure class=\"wp-block-image alignwide size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"988\" height=\"312\" src=\"http:\/\/aslak.nu\/wp-content\/uploads\/2021\/03\/project-euler-problem15.png\" alt=\"\" class=\"wp-image-196\" srcset=\"http:\/\/aslak.nu\/wp-content\/uploads\/2021\/03\/project-euler-problem15.png 988w, http:\/\/aslak.nu\/wp-content\/uploads\/2021\/03\/project-euler-problem15-300x95.png 300w, http:\/\/aslak.nu\/wp-content\/uploads\/2021\/03\/project-euler-problem15-768x243.png 768w\" sizes=\"auto, (max-width: 988px) 100vw, 988px\" \/><\/figure>\n\n\n\n<div class=\"wp-block-columns alignwide is-layout-flex wp-container-core-columns-is-layout-8f761849 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-vertically-aligned-center is-layout-flow wp-block-column-is-layout-flow\">\n<p class=\"wp-block-paragraph\">Answer is: 137846528820<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Converting the original problem statement to finding all sequences of Downs (D) &amp; Rights (R), makes the problem easier to solve. In the given example, one has 2 Downs and 2 Rights. Arranging them in all possible permutations as in the figures gives the following 6 sequences<\/p>\n\n\n\n<p class=\"has-text-align-left wp-block-paragraph\">R1 R2 D1 D2<br>R1 D1 R2 D2<br>R1 D1 D2 R2<br>D1 R1 R2 D2<br>D1 R1 D1 R2<br>D1 D2 R1 R1<br><br>Now the trick is to spot how this relates to factorials. In the example above, there is a total of 4 moves for all permutations. All possible arrangements of these 4 moves results in 4! or 24 possible moves. However, the key insight is noticing, that is does not matter which Down of the 2 Downs we pick, neither which Right of the 2 Rights we pick. This means that we must remove all duplicate arrangements such as <strong>D1 D2<\/strong> R1 R2 and <strong>D2 D1<\/strong> R1 R2, as they are equal based on the problem statement. We can therefore divide the total number of arrangements, first with the number of Down arrangements and then again with the number of Right arrangements.<br><\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\"><br><strong> ( (Downs + Rights)! \/ Downs!) \/ Rights!<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Putting this into play with the 2&#215;2 example from the beginning<br>(4! \/ 2!) \/ 2! = (24 \/ 2) \/ 2 = 6 <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">And for a 20&#215;20 grid the answer becomes<br>137846528820<\/p>\n<\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator alignwide is-style-default\"\/>\n","protected":false},"excerpt":{"rendered":"<p>Introduction Project Euler is a websites dedicated to problem solving. The site is is similar but much older than the usually more known website called HackerRank. Problems at Project Euler always require a number as an answer. The problems increase in difficulty. Most problems can not be brute forced (at least not in the early [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":104,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-187","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"http:\/\/aslak.nu\/index.php\/wp-json\/wp\/v2\/pages\/187","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/aslak.nu\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/aslak.nu\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/aslak.nu\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/aslak.nu\/index.php\/wp-json\/wp\/v2\/comments?post=187"}],"version-history":[{"count":3,"href":"http:\/\/aslak.nu\/index.php\/wp-json\/wp\/v2\/pages\/187\/revisions"}],"predecessor-version":[{"id":197,"href":"http:\/\/aslak.nu\/index.php\/wp-json\/wp\/v2\/pages\/187\/revisions\/197"}],"up":[{"embeddable":true,"href":"http:\/\/aslak.nu\/index.php\/wp-json\/wp\/v2\/pages\/104"}],"wp:attachment":[{"href":"http:\/\/aslak.nu\/index.php\/wp-json\/wp\/v2\/media?parent=187"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}