{"id":649,"date":"2012-08-17T02:52:06","date_gmt":"2012-08-17T06:52:06","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=649"},"modified":"2015-11-18T01:06:38","modified_gmt":"2015-11-18T06:06:38","slug":"project-euler-problem-61","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/17\/project-euler-problem-61\/","title":{"rendered":"Project Euler &#8211; Problem 61"},"content":{"rendered":"<p>Problem 61:<br \/>\nTriangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:<\/p>\n<pre>Triangle\t \tP3,n=n(n+1)\/2\t \t1, 3, 6, 10, 15, ...\r\nSquare\t \t\tP4,n=n2\t \t\t1, 4, 9, 16, 25, ...\r\nPentagonal\t \tP5,n=n(3n-1)\/2\t \t1, 5, 12, 22, 35, ...\r\nHexagonal\t \tP6,n=n(2n-1)\t \t1, 6, 15, 28, 45, ...\r\nHeptagonal\t \tP7,n=n(5n-3)\/2\t \t1, 7, 18, 34, 55, ...\r\nOctagonal\t \tP8,n=n(3n-2)\t \t1, 8, 21, 40, 65, ...<\/pre>\n<p>The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.<\/p>\n<p>The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).<br \/>\n<!--more--><br \/>\nEach polygonal type: triangle (P3,127=8128), square (P4,91=8281), and pentagonal (P5,44=2882), is represented by a different number in the set.<br \/>\nThis is the only set of 4-digit numbers with this property.<\/p>\n<p>Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.<\/p>\n<p><code><\/p>\n<pre lang='java'>\r\npublic class Mapping {\r\n\tpublic char[] number;\r\n\tpublic int p;\r\n\tpublic Mapping(int p, char[] array){\r\n\t\tthis.p = p;\r\n\t\tthis.number = array;\r\n\t}\r\n\tpublic String toString(){\r\n\t\treturn p+\" \"+String.valueOf(number);\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><\/p>\n<p><code><\/p>\n<pre lang='java'>\r\nimport java.util.Arrays;\r\nimport java.util.HashMap;\r\nimport java.util.HashSet;\r\nimport java.util.Map.Entry;\r\nimport java.util.Vector;\r\n\r\n\r\nclass runner2\r\n{\t\r\n\tprivate static int triangle(int n){\r\n\t\treturn (n+1)*n\/2;\r\n\t}\r\n\tprivate static int square(int n){\r\n\t\treturn n*n;\r\n\t}\r\n\tprivate static int pentagonal(int n){\r\n\t\treturn (3*n-1)*n\/2;\r\n\t}\r\n\tprivate static int hexagonal(int n){\r\n\t\treturn (2*n-1)*n;\r\n\t}\r\n\tprivate static int heptagonal(int n){\r\n\t\treturn (5*n-3)*n\/2;\r\n\t}\r\n\tprivate static int octagonal(int n){\r\n\t\treturn n*(3*n-2);\r\n\t}\r\n\tprivate static void setup(HashMap<Integer, Vector<char[]>> store){\r\n\t\tfor(int i=3;i<9;i++){\r\n\t\t\tstore.put(i, new Vector<char[]>(50));\r\n\t\t}\r\n\t\tfor(int i=2; i<300; i++){\r\n\t\t\tint cur; \r\n\t\t\tcur = triangle(i); if(1000 <= cur &#038;&#038; cur <= 9999) store.get(3).add((\"\"+cur).toCharArray());\r\n\t\t\tcur = square(i); if(1000 <= cur &#038;&#038; cur <= 9999) store.get(4).add((\"\"+cur).toCharArray());\r\n\t\t\tcur = pentagonal(i); if(1000 <= cur &#038;&#038; cur <= 9999) store.get(5).add((\"\"+cur).toCharArray());\r\n\t\t\tcur = hexagonal(i); if(1000 <= cur &#038;&#038; cur <= 9999) store.get(6).add((\"\"+cur).toCharArray());\r\n\t\t\tcur = heptagonal(i); if(1000 <= cur &#038;&#038; cur <= 9999) store.get(7).add((\"\"+cur).toCharArray());\r\n\t\t\tcur = octagonal(i); if(1000 <= cur &#038;&#038; cur <= 9999) store.get(8).add((\"\"+cur).toCharArray());\r\n\t\t}\r\n\t}\r\n\tprivate static HashSet<Mapping> generateMapping(HashMap<String, HashSet<Mapping>> maps, HashMap<Integer, Vector<char[]>> original_Store, String endsWith) {\r\n\t\tif(maps.containsKey(endsWith)) return maps.get(endsWith);\r\n\t\tHashSet<Mapping> result = new HashSet<Mapping>(25);\r\n\t\tchar y1 = endsWith.charAt(0), y2 = endsWith.charAt(1);\r\n\t\t\r\n\t\tfor(Entry<Integer, Vector<char[]>> entry : original_Store.entrySet()){\r\n\t\t\tint key = entry.getKey();\r\n\t\t\tVector<char[]> arr = entry.getValue();\r\n\t\t\tfor(char[] curStr : arr){\r\n\t\t\t\tif(curStr[0] == y1 && curStr[1] == y2){\r\n\t\t\t\t\tresult.add(new Mapping(key, curStr));\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\tmaps.put(endsWith, result);\r\n\t\t\r\n\t\treturn result;\r\n\t}\r\n\t\r\n\tprivate static boolean isCyclical(boolean[] done, String original_startsWith, String curEnd, HashMap<String, HashSet<Mapping>> maps){\r\n\t\tboolean exitRecur = true;\r\n\t\tfor(boolean x:done){if(!x){exitRecur = false; break;}}\r\n\t\tif(exitRecur){return curEnd.equals(original_startsWith);}\r\n\t\t\r\n\t\tHashSet<Mapping> mapSet = generateMapping(maps, original_Store, curEnd);\r\n\t\tfor(Mapping curMapping: mapSet){\r\n\t\t\tif(done[curMapping.p]) continue;\/\/we already used from that bucket.\r\n\t\t\tboolean[] doneclone = Arrays.copyOf(done, done.length);\r\n\t\t\tdoneclone[curMapping.p] = true;\r\n\t\t\t\r\n\t\t\tif(isCyclical(doneclone, original_startsWith, curMapping.number[2]+\"\"+curMapping.number[3], maps)){\r\n\t\t\t\tSystem.out.println(curMapping.toString());\r\n\t\t\t\treturn true;\r\n\t\t\t}\r\n\t\t}\r\n\t\treturn false;\r\n\t}\r\n\t\r\n\tstatic HashMap<Integer, Vector<char[]>> original_Store = new HashMap<Integer, Vector<char[]>>(6);\r\n\tpublic static void main (String[] args) throws java.lang.Exception\r\n\t{\r\n\t\tlong time = System.currentTimeMillis();\r\n\r\n\t\tHashMap<String, HashSet<Mapping>> maps = new HashMap<String, HashSet<Mapping>>(500);\r\n\t\tsetup(original_Store);\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t\t\r\n\t\tVector<char[]> currentV = original_Store.get(3);\r\n\t\tboolean[] done = {true, true, true, true, false, false, false, false, false};\r\n\t\tfor(int i=0;i<currentV.size(); i++){\r\n\t\t\tchar[] cur = currentV.get(i);\r\n\t\t\tif(isCyclical(done, cur[0]+\"\"+cur[1], cur[2]+\"\"+cur[3], maps)){\r\n\t\t\t\tSystem.out.println(\"3 \"+String.valueOf(cur));\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\t\t}\r\n\t\t\r\n\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><br \/>\nNote: Runs in 15ms on my PC... \ud83d\ude00<br \/>\nNote2: My original code included a lexicographic-ordered permutation for isCyclical in combination with an ugly nested (6 layers) of for-loop.<br \/>\nExecution time was less than desired ... to say the least.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 61:<br \/>\nTriangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:<\/p>\n<pre>Triangle\t \tP3,n=n(n+1)\/2\t \t1, 3, 6, 10, 15, ...\r\nSquare\t \t\tP4,n=n2\t \t\t1, 4, 9, 16, 25, ...\r\nPentagonal\t \tP5,n=n(3n-1)\/2\t \t1, 5, 12, 22, 35, ...\r\nHexagonal\t \tP6,n=n(2n-1)\t \t1, 6, 15, 28, 45, ...\r\nHeptagonal\t \tP7,n=n(5n-3)\/2\t \t1, 7, 18, 34, 55, ...\r\nOctagonal\t \tP8,n=n(3n-2)\t \t1, 8, 21, 40, 65, ...<\/pre>\n<p>The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.<\/p>\n<p>The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[56],"tags":[],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/649"}],"collection":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/comments?post=649"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/649\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=649"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=649"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=649"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}