{"id":200,"date":"2004-06-09T22:31:51","date_gmt":"2004-06-09T20:31:51","guid":{"rendered":"http:\/\/blogs.bl0rg.net\/neingeist-neu\/2004\/06\/09\/the-nine-nines\/"},"modified":"2006-10-10T03:44:33","modified_gmt":"2006-10-10T01:44:33","slug":"the-nine-nines","status":"publish","type":"post","link":"https:\/\/blogs.bl0rg.net\/neingeist\/2004\/06\/09\/the-nine-nines\/","title":{"rendered":"The Nine Nines"},"content":{"rendered":"

Another nice toy problem I found on
\n
\nthe career page of ITA Software<\/a> (which has some more problems for breakfast \ud83d\ude09 is the “Nine Nines” problem:<\/p>\n


\nCombining nine 9s with any number of the operators +, -, *, \/, (, ) , what is the smallest positive integer that cannot be expressed?
\n<\/em><\/p>\n

I already had a look on
\nthe Lisp solution by Luke Gorrie<\/a> by way of the Small-cl-src<\/a>
\nmailing list, a mailing list intended for small Common Lisp source snippets, so my solution might look a little like his. But I tried not to copy his code, maybe that’s the reason why mine is quite a bit slower (actually, it’s a lot slower…). I guess
\nit’s because of my excessive use of lists and the pushnew statement instead of
\na hash table, as he uses one. Maybe the Lisp wizards in the neighbourhood will enlighten me sometime, and I’ll post a new faster version.<\/p>\n

(defun<\/a> nines (n)\r\n\"Gives the solution to the n-nines problem.\"\r\n(let<\/a> ((solutions (make-array (1+ n) :initial-element nil)))\r\n(setf<\/a> (aref<\/a> solutions 1) '(9))\r\n(do<\/a> ((k 2 (1+<\/a> k)))\r\n((><\/a> k n))\r\n(format<\/a> t \"solve for ~G ~%\" k)\r\n(solve solutions k))\r\n(find-first-missing-integer solutions n)))\r\n\r\n(defun<\/a> solve (solutions n)\r\n\"Find all possible combinations for n nines, using the already\r\ncalculated combinations of 1 to n-1 nines\"\r\n\r\n(do<\/a> ((k 1 (1+<\/a> k)))\r\n((><\/a> k (\/<\/a> n 2)))\r\n(format<\/a> t \"inner loop ~G ~G ~%\" n k)\r\n(dolist<\/a> (solution (combine (aref<\/a> solutions k) (aref<\/a> solutions (-<\/a> n k))))\r\n(pushnew<\/a> solution (aref<\/a> solutions n)))))\r\n\r\n(defun<\/a> find-first-missing-integer (solutions n)\r\n\"Find the first missing integer, our solution.\"\r\n\r\n(do<\/a> ((k 1 (1+<\/a> k)))\r\n((not<\/a> (member<\/a> k (aref<\/a> solutions n))) k)))\r\n\r\n(defun<\/a> combine (a b)\r\n\"Gives arithmetic combinations of the members of a and b\"\r\n\r\n(let<\/a> ((foo nil))\r\n(dolist<\/a> (x a)\r\n(dolist<\/a> (y b)\r\n(pushnew<\/a> (+<\/a> x y) foo)\r\n(pushnew<\/a> (abs<\/a> (-<\/a> x y)) foo)\r\n(pushnew<\/a> (*<\/a> x y) foo)\r\n(unless<\/a> (zerop<\/a> y) (pushnew<\/a> (\/<\/a> x y) foo))\r\n(unless<\/a> (zerop<\/a> x) (pushnew<\/a> (\/<\/a> y x) foo))))\r\nfoo))<\/pre>\n
Other solutions which I found on the web: Luke’s Haskell <\/a>version, Karl Zilles’ port to ML<\/a> and Nicolas Minutillo’s solution in Java (22 pages!)<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Another nice toy problem I found on the career page of ITA Software (which has some more problems for breakfast \ud83d\ude09 is the “Nine Nines” problem: Combining nine 9s with any number of the operators +, -, *, \/, (, ) , what is the smallest positive integer that cannot be expressed? I already had […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[14],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/posts\/200"}],"collection":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/comments?post=200"}],"version-history":[{"count":0,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/posts\/200\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/media?parent=200"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/categories?post=200"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.bl0rg.net\/neingeist\/wp-json\/wp\/v2\/tags?post=200"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}