{"id":210,"date":"2006-02-23T20:40:39","date_gmt":"2006-02-24T04:40:39","guid":{"rendered":"http:\/\/multimedia.cx\/eggs\/?p=210"},"modified":"2006-03-10T21:33:00","modified_gmt":"2006-03-11T05:33:00","slug":"send-more-geese","status":"publish","type":"post","link":"https:\/\/multimedia.cx\/eggs\/send-more-geese\/","title":{"rendered":"Send More Geese"},"content":{"rendered":"

Pickover’s puzzle for the weekend of February 4-5 challenged the reader to find 8 numbers to stand in for the letters D, E, G, M, N, O, R, and S such that the equation SEND + MORE = GEESE would be true. Again, there are multiple solutions. I’m pleased to report that I found 3 orders of magnitude more solutions than the big brain himself.<\/p>\n

<\/p>\n

At first I tried to set up a series of equations. It’s obvious from the right side of each number that D must be 0 (D + E = E; D = E – E; D = 0). But beyond that, anything’s possible. So I eventually went to code. Pickover claims to have worked through 6 unique solutions. I figured that’s all there are. However, when I let my program rip I found precisely 1000 solutions. Caveat: The original problem statement never said anything about each of the 8 digits needing to be unique. Thus, for example, if all 8 variables are 0, that would be a valid solution. If someone wants to haul out the permutation logic and make sure that all the digits being tested are unique, it would be interesting to see if there are more than 6 solutions.<\/p>\n

Here’s my code:<\/p>\n

\/*\r\n * Program to brute-force the solution(s) to Cliff Pickover's\r\n * 2006\/02\/04 puzzle.\r\n *\/<\/i><\/font>\r\n\r\n#include <<\/font>stdio.<\/b><\/font>h><\/font>\r\n\r\nint<\/b><\/font> main(<\/b><\/font>void<\/b><\/font>)<\/b><\/font>\r\n{<\/b><\/font>\r\n    int<\/b><\/font> d,<\/b><\/font> e,<\/b><\/font> g,<\/b><\/font> m,<\/b><\/font> n,<\/b><\/font> o,<\/b><\/font> r,<\/b><\/font> s;<\/b><\/font>\r\n    int<\/b><\/font> send,<\/b><\/font> more,<\/b><\/font> geese;<\/b><\/font>\r\n    int<\/b><\/font> count =<\/font> 0<\/font>;<\/b><\/font>\r\n\r\n    for<\/b><\/font> (<\/b><\/font>d =<\/font> 0<\/font>;<\/b><\/font> d <<\/font> 10<\/font>;<\/b><\/font> d<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n     for<\/b><\/font> (<\/b><\/font>e =<\/font> 0<\/font>;<\/b><\/font> e <<\/font> 10<\/font>;<\/b><\/font> e<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n      for<\/b><\/font> (<\/b><\/font>g =<\/font> 0<\/font>;<\/b><\/font> g <<\/font> 10<\/font>;<\/b><\/font> g<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n       for<\/b><\/font> (<\/b><\/font>m =<\/font> 0<\/font>;<\/b><\/font> m <<\/font> 10<\/font>;<\/b><\/font> m<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n        for<\/b><\/font> (<\/b><\/font>n =<\/font> 0<\/font>;<\/b><\/font> n <<\/font> 10<\/font>;<\/b><\/font> n<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n         for<\/b><\/font> (<\/b><\/font>o =<\/font> 0<\/font>;<\/b><\/font> o <<\/font> 10<\/font>;<\/b><\/font> o<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n          for<\/b><\/font> (<\/b><\/font>r =<\/font> 0<\/font>;<\/b><\/font> r <<\/font> 10<\/font>;<\/b><\/font> r<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n           for<\/b><\/font> (<\/b><\/font>s =<\/font> 0<\/font>;<\/b><\/font> s <<\/font> 10<\/font>;<\/b><\/font> s<\/font>+<\/font>+<\/font>)<\/b><\/font> {<\/b><\/font>\r\n               send =<\/font> s *<\/font> 1000<\/font> +<\/font> e *<\/font> 100<\/font> +<\/font> n *<\/font> 10<\/font> +<\/font> d;<\/b><\/font>\r\n               more =<\/font> m *<\/font> 1000<\/font> +<\/font> o *<\/font> 100<\/font> +<\/font> r *<\/font> 10<\/font> +<\/font> e;<\/b><\/font>\r\n               geese =<\/font> g *<\/font> 10000<\/font> +<\/font> e *<\/font> 1000<\/font> +<\/font> e *<\/font> 100<\/font> +<\/font> s *<\/font> 10<\/font> +<\/font> e;<\/b><\/font>\r\n               if<\/b><\/font> (<\/b><\/font>send +<\/font> more =<\/font>=<\/font> geese)<\/b><\/font>\r\n                   printf(<\/b><\/font>\"solution %d: %d + %d = %d\\n\"<\/font>,<\/b><\/font> <\/font>+<\/font>+<\/font>count,<\/b><\/font> send,<\/b><\/font> more,<\/b><\/font> geese)<\/b><\/font>;<\/b><\/font>\r\n           }<\/b><\/font>\r\n\r\n    return<\/b><\/font> 0<\/font>;<\/b><\/font>\r\n}<\/b><\/font>\r\n<\/pre>\n
It requires ~37.4 seconds to run on my 512 MHz, x86-based CPU. For the optimization-obsessive personalities among our ranks<\/a>,  I replaced all of the multiplications with table lookups. That brings the nominal runtime down to 17.8 seconds.<\/p>\n
\r\n\/*\r\n * Program to brute-force the solution(s) to Cliff Pickover's\r\n * 2006\/02\/04 puzzle.\r\n *\/<\/i><\/font>\r\n\r\n#include <<\/font>stdio.<\/b><\/font>h><\/font>\r\n\r\nint<\/b><\/font> main(<\/b><\/font>void<\/b><\/font>)<\/b><\/font>\r\n{<\/b><\/font>\r\n    int<\/b><\/font> d,<\/b><\/font> e,<\/b><\/font> g,<\/b><\/font> m,<\/b><\/font> n,<\/b><\/font> o,<\/b><\/font> r,<\/b><\/font> s;<\/b><\/font>\r\n    int<\/b><\/font> send,<\/b><\/font> more,<\/b><\/font> geese;<\/b><\/font>\r\n    int<\/b><\/font> count =<\/font> 0<\/font>;<\/b><\/font>\r\n    int<\/b><\/font> tens[<\/b><\/font>10<\/font>]<\/b><\/font>;<\/b><\/font>\r\n    int<\/b><\/font> hundreds[<\/b><\/font>10<\/font>]<\/b><\/font>;<\/b><\/font>\r\n    int<\/b><\/font> thousands[<\/b><\/font>10<\/font>]<\/b><\/font>;<\/b><\/font>\r\n    int<\/b><\/font> tenthousands[<\/b><\/font>10<\/font>]<\/b><\/font>;<\/b><\/font>\r\n\r\n    for<\/b><\/font> (<\/b><\/font>d =<\/font> 0<\/font>;<\/b><\/font> d <<\/font> 10<\/font>;<\/b><\/font> d<\/font>+<\/font>+<\/font>)<\/b><\/font> {<\/b><\/font>\r\n        tens[<\/b><\/font>d]<\/b><\/font> =<\/font> d *<\/font> 10<\/font>;<\/b><\/font>\r\n        hundreds[<\/b><\/font>d]<\/b><\/font> =<\/font> d *<\/font> 100<\/font>;<\/b><\/font>\r\n        thousands[<\/b><\/font>d]<\/b><\/font> =<\/font> d *<\/font> 1000<\/font>;<\/b><\/font>\r\n        tenthousands[<\/b><\/font>d]<\/b><\/font> =<\/font> d *<\/font> 10000<\/font>;<\/b><\/font>\r\n    }<\/b><\/font>\r\n\r\n    for<\/b><\/font> (<\/b><\/font>d =<\/font> 0<\/font>;<\/b><\/font> d <<\/font> 10<\/font>;<\/b><\/font> d<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n     for<\/b><\/font> (<\/b><\/font>e =<\/font> 0<\/font>;<\/b><\/font> e <<\/font> 10<\/font>;<\/b><\/font> e<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n      for<\/b><\/font> (<\/b><\/font>g =<\/font> 0<\/font>;<\/b><\/font> g <<\/font> 10<\/font>;<\/b><\/font> g<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n       for<\/b><\/font> (<\/b><\/font>m =<\/font> 0<\/font>;<\/b><\/font> m <<\/font> 10<\/font>;<\/b><\/font> m<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n        for<\/b><\/font> (<\/b><\/font>n =<\/font> 0<\/font>;<\/b><\/font> n <<\/font> 10<\/font>;<\/b><\/font> n<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n         for<\/b><\/font> (<\/b><\/font>o =<\/font> 0<\/font>;<\/b><\/font> o <<\/font> 10<\/font>;<\/b><\/font> o<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n          for<\/b><\/font> (<\/b><\/font>r =<\/font> 0<\/font>;<\/b><\/font> r <<\/font> 10<\/font>;<\/b><\/font> r<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n           for<\/b><\/font> (<\/b><\/font>s =<\/font> 0<\/font>;<\/b><\/font> s <<\/font> 10<\/font>;<\/b><\/font> s<\/font>+<\/font>+<\/font>)<\/b><\/font> {<\/b><\/font>\r\n               send =<\/font> thousands[<\/b><\/font>s]<\/b><\/font> +<\/font> hundreds[<\/b><\/font>e]<\/b><\/font> +<\/font> tens[<\/b><\/font>n]<\/b><\/font> +<\/font> d;<\/b><\/font>\r\n               more =<\/font> thousands[<\/b><\/font>m]<\/b><\/font> +<\/font> hundreds[<\/b><\/font>o]<\/b><\/font> +<\/font> tens[<\/b><\/font>r]<\/b><\/font> +<\/font> e;<\/b><\/font>\r\n               geese =<\/font> tenthousands[<\/b><\/font>g]<\/b><\/font> +<\/font> thousands[<\/b><\/font>e]<\/b><\/font> +<\/font> hundreds[<\/b><\/font>e]<\/b><\/font> +<\/font> tens[<\/b><\/font>s]<\/b><\/font> +<\/font> e;<\/b><\/font>\r\n               if<\/b><\/font> (<\/b><\/font>send +<\/font> more =<\/font>=<\/font> geese)<\/b><\/font>\r\n                   printf(<\/b><\/font>\"solution %d: %d + %d = %d\\n\"<\/font>,<\/b><\/font> <\/font>+<\/font>+<\/font>count,<\/b><\/font> send,<\/b><\/font> more,<\/b><\/font> geese)<\/b><\/font>;<\/b><\/font>\r\n           }<\/b><\/font>\r\n\r\n    return<\/b><\/font> 0<\/font>;<\/b><\/font>\r\n}<\/b><\/font>\r\n<\/pre>\n
C code colorized by the CodeColorizer<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"
Another brute force puzzle…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[27],"tags":[],"class_list":["post-210","post","type-post","status-publish","format-standard","hentry","category-pickover-puzzles"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts\/210","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/comments?post=210"}],"version-history":[{"count":0,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts\/210\/revisions"}],"wp:attachment":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/media?parent=210"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/categories?post=210"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/tags?post=210"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}