The Nine Nines
Another nice toy problem I found on
the career page of ITA Software (which has some more problems for breakfast 😉 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 a look on
the Lisp solution by Luke Gorrie by way of the Small-cl-src
mailing 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
it’s because of my excessive use of lists and the pushnew statement instead of
a 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.
(defun nines (n) "Gives the solution to the n-nines problem." (let ((solutions (make-array (1+ n) :initial-element nil))) (setf (aref solutions 1) '(9)) (do ((k 2 (1+ k))) ((> k n)) (format t "solve for ~G ~%" k) (solve solutions k)) (find-first-missing-integer solutions n))) (defun solve (solutions n) "Find all possible combinations for n nines, using the already calculated combinations of 1 to n-1 nines" (do ((k 1 (1+ k))) ((> k (/ n 2))) (format t "inner loop ~G ~G ~%" n k) (dolist (solution (combine (aref solutions k) (aref solutions (- n k)))) (pushnew solution (aref solutions n))))) (defun find-first-missing-integer (solutions n) "Find the first missing integer, our solution." (do ((k 1 (1+ k))) ((not (member k (aref solutions n))) k))) (defun combine (a b) "Gives arithmetic combinations of the members of a and b" (let ((foo nil)) (dolist (x a) (dolist (y b) (pushnew (+ x y) foo) (pushnew (abs (- x y)) foo) (pushnew (* x y) foo) (unless (zerop y) (pushnew (/ x y) foo)) (unless (zerop x) (pushnew (/ y x) foo)))) foo))
Other solutions which I found on the web: Luke’s Haskell version, Karl Zilles’ port to ML and Nicolas Minutillo’s solution in Java (22 pages!).