{"id":455,"date":"2012-07-30T01:18:26","date_gmt":"2012-07-30T05:18:26","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=455"},"modified":"2012-09-07T16:16:40","modified_gmt":"2012-09-07T20:16:40","slug":"project-euler-problem-17","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/07\/30\/project-euler-problem-17\/","title":{"rendered":"Project Euler &#8211; Problem 17"},"content":{"rendered":"<p>Problem 17:<br \/>\nIf the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.<\/p>\n<p>If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?<br \/>\n<!--more--><br \/>\nNOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of &#8220;and&#8221; when writing out numbers is in compliance with British usage.<\/p>\n<p><code><\/p>\n<pre lang=\"java\">\r\nimport java.util.Vector;\r\n\r\n\r\nclass runner\r\n{\r\n\t@SuppressWarnings(\"serial\")\r\n\tstatic Vector<Integer[]> map = new Vector<Integer[]>(){{\r\n\t\tadd(new Integer[]{1, 3}); add(new Integer[]{2, 3}); add(new Integer[]{3, 5}); add(new Integer[]{4, 4}); add(new Integer[]{5, 4}); add(new Integer[]{6, 3}); add(new Integer[]{7, 5}); add(new Integer[]{8, 5});\tadd(new Integer[]{9, 4});\r\n\t\tadd(new Integer[]{10, 3}); add(new Integer[]{11, 6}); add(new Integer[]{12, 6}); add(new Integer[]{13, 8}); add(new Integer[]{14, 8}); add(new Integer[]{15, 7}); add(new Integer[]{16, 7}); add(new Integer[]{17, 9}); add(new Integer[]{18, 8}); add(new Integer[]{19, 8});\r\n\t\tadd(new Integer[]{20, 6}); add(new Integer[]{30, 6}); add(new Integer[]{40, 5}); add(new Integer[]{50, 5}); add(new Integer[]{60, 5}); add(new Integer[]{70, 7}); add(new Integer[]{80, 6}); add(new Integer[]{90, 6});\r\n\t\tadd(new Integer[]{100, 7}); add(new Integer[]{1000, 8});\r\n\t}\r\n\t};\r\n\r\n\r\n\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\tint sum = 0; int n = 1000;\r\n\t\tfor(int i = 1; i<= n; i++){\r\n\t\t\tboolean BRITISH_AND = false;\r\n\t\t\tint cur = i;\r\n\t\t\tint length = 0;\r\n\r\n\t\t\tfor(int j = map.size()-1; j>-1; j--){\r\n\t\t\t\tif(cur == 0) break;\r\n\r\n\t\t\t\tInteger[] mapcur = map.elementAt(j);\r\n\r\n\t\t\t\tint counter = 0;\r\n\t\t\t\tif(mapcur[0] >= 100){\/\/1000, 100\r\n\t\t\t\t\twhile(cur > 0 && mapcur[0] <= cur){\r\n\t\t\t\t\t\tcounter++;\r\n\t\t\t\t\t\tcur -= mapcur[0];\r\n\t\t\t\t\t}\r\n\t\t\t\t\tif(counter > 0){\r\n\t\t\t\t\t\tlength += mapcur[1];\/\/Add the base number 1000, 100\r\n\r\n\t\t\t\t\t\t\/\/Add the counter value\r\n\t\t\t\t\t\tfor(int z = 0; z<map.size(); z++){\r\n\t\t\t\t\t\t\tif(map.get(z)[0] == counter){\r\n\t\t\t\t\t\t\t\tlength += map.get(z)[1]; \r\n\t\t\t\t\t\t\t\tbreak;\r\n\t\t\t\t\t\t\t}\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t\t\/\/Special case for British compliance... add the word \"and\" for >100\r\n\t\t\t\t\t\tif(cur > 0){\r\n\t\t\t\t\t\t\tBRITISH_AND = true;\r\n\t\t\t\t\t\t}\r\n\r\n\t\t\t\t\t}\r\n\t\t\t\t}else{\/\/Normal Number\r\n\t\t\t\t\tif(mapcur[0] <= cur){\r\n\t\t\t\t\t\tlength += mapcur[1];\r\n\t\t\t\t\t\tcur -= mapcur[0];\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\tif(BRITISH_AND) length += 3;\r\n\r\n\t\t\tsum += length;\r\n\t\t}\r\n\r\n\t\tSystem.out.println(sum);\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 17:<br \/>\nIf the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.<\/p>\n<p>If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?<\/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\/455"}],"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=455"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/455\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=455"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=455"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=455"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}