{"id":522,"date":"2012-08-03T16:49:56","date_gmt":"2012-08-03T20:49:56","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=522"},"modified":"2012-09-07T16:13:08","modified_gmt":"2012-09-07T20:13:08","slug":"project-euler-problem-31","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/03\/project-euler-problem-31\/","title":{"rendered":"Project Euler &#8211; Problem 31"},"content":{"rendered":"<p>Problem 31: Given the following coin values: (1p,2p,5p,10p,20p,50p,\u00a31,\u00a32):<br \/>\nWhere (1p = 1\/\u00a31)<br \/>\nHow many different ways can \u00a32 be made using any number of coins?<br \/>\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\nimport java.util.Collections;\r\nimport java.util.Stack;\r\n\r\nclass runner\r\n{\r\n\tstatic final int[] available = new int[] {1,2,5,10,20,50,100,200}; \r\n\r\n\tprivate static int counting(int m){\r\n\t\tStack<Integer> tally = new Stack< Integer>();\r\n\t\t\/\/setup\r\n\t\tsetupTally(m, tally);\r\n\r\n\t\tint count = 1+counting_aux(tally);\r\n\r\n\t\treturn count;\r\n\t}\r\n\tprivate static int counting_aux(Stack<Integer> tally){\r\n\t\tif(tally.size() == 0 || tally.firstElement() == 1) return 0;\r\n\r\n\t\tint count = 0;\r\n\r\n\t\tint prev = tally.lastElement();\r\n\t\tStack<Integer> temporaryTally = new Stack<Integer>();\r\n\t\tfor(int i=tally.size()-1; i>-1; i--){\r\n\t\t\tif(prev < tally.get(i))\r\n\t\t\t\ttemporaryTally = subList(tally, i+1, tally.size());\r\n\t\t\tswitch(tally.get(i)){\r\n\t\t\tcase 200: \ttemporaryTally.push(100);temporaryTally.push(100);\r\n\t\t\tbreak;\r\n\t\t\tcase 100:\ttemporaryTally.push(50);temporaryTally.push(50);   \r\n\t\t\tbreak;\r\n\t\t\tcase 50: \ttemporaryTally.push(20);temporaryTally.push(20);\r\n\t\t\t\t\t\tif(temporaryTally.contains(10)){\r\n\t\t\t\t\t\t\ttemporaryTally.remove(temporaryTally.indexOf(10));\r\n\t\t\t\t\t\t\ttemporaryTally.push(20);\r\n\t\t\t\t\t\t}else \r\n\t\t\t\t\t\t\ttemporaryTally.push(10);\r\n\t\t\tbreak;\r\n\t\t\tcase 20: \ttemporaryTally.push(10);temporaryTally.push(10);\r\n\t\t\t\t\t\tbreak;\r\n\t\t\tcase 10: \ttemporaryTally.push(5);temporaryTally.push(5);\r\n\t\t\tbreak;\r\n\t\t\tcase 5: \ttemporaryTally.push(2);temporaryTally.push(2);\r\n\t\t\t\t\t\tif(temporaryTally.contains(1)){\r\n\t\t\t\t\t\t\ttemporaryTally.remove(temporaryTally.indexOf(1));\r\n\t\t\t\t\t\t\ttemporaryTally.push(2);\r\n\t\t\t\t\t\t}else \r\n\t\t\t\t\t\t\ttemporaryTally.push(1);\r\n\t\t\tbreak;\r\n\t\t\tcase 2: \ttemporaryTally.push(1);temporaryTally.push(1);\r\n\t\t\tbreak;\r\n\t\t\t}\r\n\t\t\treOrder(temporaryTally);\r\n\r\n\t\t\tif(tally.get(i) != 1) count++;\r\n\r\n\t\t\tcount += counting_aux(temporaryTally);\r\n\t\t\tprev = tally.get(i);\r\n\t\t}\r\n\r\n\t\treturn count;\r\n\t}\r\n\r\n\tprivate static Stack<Integer> subList(Stack<Integer> tally, int from, int to){\r\n\t\tStack<Integer> x = new Stack<Integer>();\r\n\t\tif(from > tally.size() || to > tally.size()) return x;\r\n\t\tfor(int i = from; i<to; i++){\r\n\t\t\tx.add(tally.get(i));\r\n\t\t}\r\n\t\treturn x;\r\n\t}\r\n\tprivate static void setupTally(int m, Stack<Integer> tally){\r\n\t\tint i = available.length-1;\r\n\t\twhile(i>=0){\r\n\t\t\tif(m >= available[i]){\r\n\t\t\t\tm -= available[i];\r\n\t\t\t\ttally.push(available[i]);\r\n\t\t\t}else{\r\n\t\t\t\ti--;\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\tprivate static void reOrder(Stack<Integer> tally){\r\n\t\tCollections.sort(tally);\r\n\t\tCollections.reverse(tally);\r\n\t}\r\n\r\n\tprivate static void test(int i, int r){\r\n\t\tint actual = counting(i);\r\n\t\tSystem.out.println((actual == r)+\"\\t:: Testing i:\"+i+\" r:\"+r+\" actual:\"+actual);\r\n\t}\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\r\n\t\ttest(1,1);\/\/1\r\n\t\ttest(2,2);\/\/2, 11\r\n\t\ttest(3,2);\/\/21, 111\r\n\t\ttest(4,3);\/\/22, 211, 1111\r\n\t\ttest(5,4);\/\/5, 221, 2111, 11111\r\n\t\ttest(6,5);\/\/51, 222, 2211, 21111, 111111\r\n\t\ttest(10,11);\/\/A, 55, 5221, 521*3, 51*5, 22222, 222211, 2221*4, 221*6, 21*8, 1*A\r\n\t\ttest(11,12);\/\/A1, 551, 5222, 52211, 521*4, 51*6, 222221, 22221*3, 2221*5, 221*7, 21*9, 1*B\r\n\t\ttest(12,15);\/\/A2, A11, 552, 52221, 522111, 5211111, 51111111, 222222, 2222211, 22221*4, 2221*6, 221*8, 21*A, 1*C\r\n\t\t\r\n\t\tSystem.out.println(counting(200));\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: This piece of code took a few code re-writes.. Finally works though!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 31: Given the following coin values: (1p,2p,5p,10p,20p,50p,\u00a31,\u00a32):<br \/>\nWhere (1p = 1\/\u00a31)<br \/>\nHow many different ways can \u00a32 be made using any number of coins?<\/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-522","post","type-post","status-publish","format-standard","hentry","category-project-euler"],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/522","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=522"}],"version-history":[{"count":4,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/522\/revisions"}],"predecessor-version":[{"id":771,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/522\/revisions\/771"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=522"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=522"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=522"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}