{"id":445,"date":"2012-07-29T03:26:49","date_gmt":"2012-07-29T07:26:49","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=445"},"modified":"2012-09-07T16:17:00","modified_gmt":"2012-09-07T20:17:00","slug":"project-euler-problem-14","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/07\/29\/project-euler-problem-14\/","title":{"rendered":"Project Euler &#8211; Problem 14"},"content":{"rendered":"<p>Problem 14: Find the longest sequence using a starting number under one million. (via Collatz conjecture)<br \/>\n<!--more--><\/p>\n<p>I used a cache to improve my execution time&#8230; my PC takes about 5seconds.<\/p>\n<p><code><\/p>\n<pre lang=\"java\">import java.util.HashMap;\r\nimport java.util.Map;\r\n\r\nclass runner\r\n{\r\n\tstatic HashMap<Long, Integer> cache = new HashMap<Long, Integer>();\r\n\tpublic static void mergeCache(HashMap<Long, Integer> minicache){\r\n\t\tcache.putAll(minicache);\r\n\t}\r\n\tpublic static long calc(long n){\r\n\t\tif(n%2 == 0)\r\n\t\t\treturn n\/2;\r\n\t\telse\r\n\t\t\treturn 3*n+1;\r\n\t}\r\n\tpublic static void main (String[] args) throws java.lang.Exception\r\n\t{\r\n\t\tlong time = System.currentTimeMillis();\r\n\t\tlong lrgLen = 0, lrgNum = 0; \r\n\t\tfor(int i=1; i<1000000; i++){\r\n\t\t\tHashMap<Long, Integer> minicache = new HashMap<Long, Integer>();\r\n\t\t\t\r\n\t\t\tlong val = i, counter = 1;\r\n\t\t\twhile(val != 1){\r\n\t\t\t\t\/\/Check cache\r\n\t\t\t\tif(cache.containsKey(val)){\r\n\t\t\t\t\tInteger cachedVal = cache.get(val);\r\n\t\t\t\t\t\/\/update all values in minicache\r\n\t\t\t\t\tfor (Map.Entry<Long, Integer> entry : minicache.entrySet()){\r\n\t\t\t\t\t\tentry.setValue(entry.getValue()+cachedVal);\r\n\t\t\t\t\t}\r\n\t\t\t\t\tcounter += cachedVal;\r\n\t\t\t\t\tbreak;\r\n\t\t\t\t}\r\n\t\t\t\tval = calc(val);\r\n\t\t\t\t\r\n\t\t\t\t\/\/update all values in minicache\r\n\t\t\t\tfor (Map.Entry<Long, Integer> entry : minicache.entrySet()){\r\n\t\t\t\t\tentry.setValue(entry.getValue()+1);\r\n\t\t\t\t}\r\n\t\t\t\tminicache.put(val, 1);\r\n\t\t\t\tcounter ++;\r\n\t\t\t}\r\n\t\t\t\r\n\t\t\tmergeCache(minicache);\r\n\t\t\t\r\n\t\t\tif(counter > lrgLen){\r\n\t\t\t\tlrgLen = counter; lrgNum = i;\r\n\t\t\t}\r\n\t\t\t\r\n\t\t\t\/\/System.out.println(\"cachesize: \"+cache.size());\r\n\t\t}\r\n\t\tSystem.out.println(\"i: \"+lrgNum+\" len: \"+lrgLen+\" time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}<\/pre>\n<p><\/code><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 14: Find the longest sequence using a starting number under one million. (via Collatz conjecture)<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[56],"tags":[],"class_list":["post-445","post","type-post","status-publish","format-standard","hentry","category-project-euler"],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/445","targetHints":{"allow":["GET"]}}],"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=445"}],"version-history":[{"count":2,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/445\/revisions"}],"predecessor-version":[{"id":790,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/445\/revisions\/790"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=445"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=445"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=445"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}