{"id":27,"date":"2008-05-18T10:32:39","date_gmt":"2008-05-18T09:32:39","guid":{"rendered":"http:\/\/www.hinnerup.net\/?p=27"},"modified":"2008-06-25T15:29:43","modified_gmt":"2008-06-25T14:29:43","slug":"google-treasure-hunt-2008","status":"publish","type":"post","link":"https:\/\/www.hinnerup.net\/en\/permanent\/2008\/05\/18\/google-treasure-hunt-2008\/","title":{"rendered":"Google Treasure Hunt 2008 - Del 1"},"content":{"rendered":"<p>Google har sat gang i en vaske\u00e6gte skattejagt. Hvad kisten indeholder er fornuv\u00e6rende stadig en velbevaret hemmelighed, og det fam\u00f8se X p\u00e5 skattekortet jagtes af mange. Du kan selv deltage <a href=\"http:\/\/treasurehunt.appspot.com\/\">her<\/a> og du kan l\u00e6se mere om konkurrencen p\u00e5 <a href=\"http:\/\/googleblog.blogspot.com\/2008\/05\/google-treasure-hunt-update.html\">denne side<\/a>.<\/p>\n<p>F\u00f8rste etape af udfordringen er at svare p\u00e5 hvor mange unikke stier der er for en robot der kun kan bev\u00e6ge sig henholdsvist ned og mod h\u00f8jre, n\u00e5r denne starter i \u00f8verste venstre hj\u00f8rne af et skakbr\u00e6t af st\u00f8rrelsen W x H. Tallene W og H oplyses naturligvis forskelligt pr. fors\u00f8g man foretager.<\/p>\n<p>Set fra et IT-synspunkt, er det f\u00e6lles for l\u00f8sningerne at det endelige tal overstiger almindelige heltals typer, s\u00e5 man skal benytte bit manipulation eller f.eks. BigInteger klassen fra Java for at kunne rumme det endelige tal.<\/p>\n<p>Hinnerup Net ApS har hastigt strukket denne lille Java sag p\u00e5 <a href=\"http:\/\/en.wikipedia.org\/wiki\/Answer_to_Life,_the_Universe,_and_Everything\">42<\/a> linier sammen, som kan l\u00f8se opgaven uanset W og H (dog givet W og H er positive heltal):<\/p>\n<p style=\"cursor:pointer; text-decoration:underline\" onclick=\"document.getElementById('googleBotSolverCode').style.display='block';document.getElementById('googleBotSolverSpoiler').style.display='none'\" id=\"googleBotSolverSpoiler\">Klik her for at se Java koden &#8211; spoiler advarsel!<\/p>\n<div id=\"googleBotSolverCode\" style=\"display:none\">\n<pre style=\"font-size:7pt\">\r\npackage GoogleTreasureHunt2008;\r\nimport java.math.BigInteger;\r\n\r\npublic class GoogleBotSolver\r\n{\r\n  private BigInteger[][] results;\r\n  public GoogleBotSolver(int w, int h)\r\n  {\r\n    results = new BigInteger[w][h];\r\n    for (int x = 0; x &lt; w; x++)\r\n    {\r\n      for (int y = 0; y &lt; h; y++)\r\n      {\r\n        results[x][y] = null;\r\n      }\r\n    }\r\n    System.out.println(C(w - 1, h - 1).toString());\r\n  }\r\n  private BigInteger C(int x, int y)\r\n  {\r\n    if (results[x][y] != null) return results[x][y];\r\n    BigInteger res;\r\n    if (x == 0 && y == 0)\r\n    {\r\n      res = BigInteger.ZERO;\r\n    }\r\n    else if (x == 0 || y == 0)\r\n    {\r\n      res = BigInteger.ONE;\r\n    }\r\n    else\r\n    {\r\n      res = C(x - 1, y).add(C(x, y - 1));\r\n    }\r\n    results[x][y] = res;\r\n    return res;\r\n  }\r\n  public static void main(String[] args)\r\n  {\r\n    GoogleBotSolver gbs = new GoogleBotSolver(38, 58);\r\n  }\r\n}\r\n<\/pre>\n<p>Svaret for W=38 og H=58 som herover er 194937478788574958222679204. S\u00e5 robotten har rigtigt nok et par muligheder at v\u00e6lge imellem.<\/p>\n<p>Opgaven er i\u00f8vrigt en velkendt afart af <a href=\"http:\/\/en.wikipedia.org\/wiki\/Pascal's_triangle\">Pascal&#8217;s trekant<\/a>.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Google har sat gang i en vaske\u00e6gte skattejagt. Hvad kisten indeholder er fornuv\u00e6rende stadig en velbevaret hemmelighed, og det fam\u00f8se X p\u00e5 skattekortet jagtes af mange. Du kan selv deltage her og du kan l\u00e6se mere om konkurrencen p\u00e5 denne side. F\u00f8rste etape af udfordringen er at svare p\u00e5 hvor mange unikke stier der er [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9,4],"tags":[],"class_list":["post-27","post","type-post","status-publish","format-standard","hentry","category-java","category-programming"],"_links":{"self":[{"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/posts\/27","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/comments?post=27"}],"version-history":[{"count":0,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/posts\/27\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/media?parent=27"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/categories?post=27"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.hinnerup.net\/en\/wp-json\/wp\/v2\/tags?post=27"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}