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))))

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!).

Comments are closed.