{"id":461,"date":"2012-07-30T14:45:54","date_gmt":"2012-07-30T18:45:54","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=461"},"modified":"2012-09-07T16:16:33","modified_gmt":"2012-09-07T20:16:33","slug":"project-euler-problem-18","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/07\/30\/project-euler-problem-18\/","title":{"rendered":"Project Euler &#8211; Problem 18"},"content":{"rendered":"<p>Problem 18: Find the maximum sum travelling from the top of the triangle to the base.<br \/>\n<!--more--><\/p>\n<p><code><\/p>\n<pre lang=\"java\">\r\nimport java.util.Vector;\r\n\r\npublic class test {\r\n\tpublic static void main(String[] args) {\r\n\t\tString triangle = \"75\\n\"+\r\n\t\t\t\"95 64\\n\"+\r\n\t\t\t\"17 47 82\\n\"+\r\n\t\t\t\"18 35 87 10\\n\"+\r\n\t\t\t\"20 04 82 47 65\\n\"+\r\n\t\t\t\"19 01 23 75 03 34\\n\"+\r\n\t\t\t\"88 02 77 73 07 63 67\\n\"+\r\n\t\t\t\"99 65 04 28 06 16 70 92\\n\"+\r\n\t\t\t\"41 41 26 56 83 40 80 70 33\\n\"+\r\n\t\t\t\"41 48 72 33 47 32 37 16 94 29\\n\"+\r\n\t\t\t\"53 71 44 65 25 43 91 52 97 51 14\\n\"+\r\n\t\t\t\"70 11 33 28 77 73 17 78 39 68 17 57\\n\"+\r\n\t\t\t\"91 71 52 38 17 14 91 43 58 50 27 29 48\\n\"+\r\n\t\t\t\"63 66 04 68 89 53 67 30 73 16 69 87 40 31\\n\"+\r\n\t\t\t\"04 62 98 27 23 09 70 98 73 93 38 53 60 04 23\";\t\r\n\r\n\t\tString[] lines = triangle.split(\"\\n\");\r\n\t\tVector<Vector<Integer>> map = new Vector<Vector<Integer>>();\r\n\t\t\/\/populate vector\r\n\t\tfor(int i = 0; i < lines.length; i++){\r\n\t\t\tString[] line = lines[i].split(\" \");\r\n\t\t\tVector<Integer> sub = new Vector<Integer>();\r\n\t\t\tfor(int j=0;j<line.length;j++){\r\n\t\t\t\tsub.add(new Integer((line[j].charAt(0) - 48 )*10 + (line[j].charAt(1) - 48)));\r\n\t\t\t}\r\n\t\t\tmap.add(sub);\r\n\t\t}\r\n\t\t\r\n\t\tfor(int i=map.size()-2;i>-1;i--){\r\n\t\t\tVector<Integer> sub = map.get(i);\r\n\t\t\tVector<Integer> prev = map.get(i+1);\r\n\t\t\tfor(int j=0;j<sub.size();j++){\r\n\t\t\t\tsub.set(j, sub.get(j) + (prev.get(j) > prev.get(j+1) ? prev.get(j) : prev.get(j+1))); \r\n\t\t\t}\r\n\t\t}\r\n\t\t\r\n\t\tSystem.out.println(map.get(0).get(0));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 18: Find the maximum sum travelling from the top of the triangle to the base.<\/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\/461"}],"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=461"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/461\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=461"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=461"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=461"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}