Project Euler – Problem 93

The problem: Problem 93

Analysis

This problem was straight-forward to solve and only required the use of some standard algorithms. A quick analysis shows that a brute-force method suffices to find the solution. Let be a subset of . There are such subsets. Let be a permutation on . Clearly, there are such permutations. For each we simply compute all possible ways of evaluating the expression using all possible ways of adding parentheses, where . Since, can each be selected in ways and there are exactly ways to add parentheses to the above expression, it follows that we have expressions involving . Overall, we will end up evaluating expressions, which a brute-force algorithm is capable of computing in a reasonable amount of time.

Algorithm

So here’s the algorithm:

largest = 0, ret = {}
for each 4-subset, X, of {0,1,2,3,4,5,6,7,8,9} do
  for each permutation, p, on X do
    for x, y, z in {+,-,*,/} do
      compute all expressions, p[X[0]] x p[X[1]] y p[X[2]] z p[X[3]] using all 5 possible parenthesizations
    end-for
  end-for
  determine n, such that n + 1 was not the result of one of the expressions evaluated in lines 3-7 and 1, 2, 3, ..., n was a result of one of the expressions
  if n > largest then
    largest = n
    ret = X
  end-if
end-for
return ret

To clarify how it works, let’s suppose that , , , and . Then we will have to compute the expressions:

Finally, after computing all expressions involving and , we determine . In this case , since is never computed as a result of one of the expressions and are results of at least one of the expressions.

Implementation Details

I solved this problem in Lisp. The function solve implements the
algorithm.

(defun solve ()
  (do ((largest 0) (ret nil)
       (s (vector 0 1 2 3) (next-subset s)))
      ((null s) (values largest ret))
    (let ((n (perform-evaluations s)))
      (if (> n largest) (setf ret s largest n)))))

The function perform-evaluations implements lines 3-8 of the
algorithm. It returns as described in line 8.

(defun perform-evaluations (s)
  (do ((seen (make-array (1+ max-result)))
       (p s (next-permutation p)))
      ((null p) (largest-consecutive seen)) ; returns n
    (dolist (f ops)
      (dolist (g ops)
        (dolist (h ops)
          (let ((a (svref p 0)) (b (svref p 1)) (c (svref p 2)) (d (svref p 3)))
            (dolist (x (parens a f b g c h d))
              (if (positive-integerp x) (setf (aref seen (1- x)) t)))))))))

parens is a macro that produces a list containing the parenthesizations of the expression it is given.

(defmacro parens (a f b g c h d)
  `(list
    (funcall ,h (funcall ,g (funcall ,f ,a ,b) ,c) ,d)
    (funcall ,g (funcall ,f ,a ,b) (funcall ,h ,c ,d))
    (funcall ,h (funcall ,f ,a (funcall ,g ,b ,c)) ,d)
    (funcall ,f ,a (funcall ,h (funcall ,g ,b ,c) ,d))
    (funcall ,f ,a (funcall ,g ,b (funcall ,h ,c ,d)))))

So, for example,

> (parens 1 '* 2 '- 3 '+ 4)
(3 -5 3 3 -5)

However, notice that parens fails whenever one of the parenthesizations yields a division by zero.

> (parens 1 '+ 2 '+ 3 '/ 0)
error: division by zero

> (parens 4 '/ 3 '- 2 '+ 1)
error: division by zero

To circumvent this problem I decided to implement new functions add,sub, mul and div such that whenever one of their arguments is nil the result is nil. Also, using div to divide by zero yields nil instead of an error. So,

> (parens 1 'add 2 'add 3 'div 0)
(nil nil nil nil nil)

> (parens 4 'div 3 'sub 2 'add 1)
(1/3 -5/3 5 2 nil)

The code for add, sub, mul and div is shown below.

(defun add (a b) (perform '+ a b))
(defun sub (a b) (perform '- a b))
(defun mul (a b) (perform '* a b))
(defun div (a b) (perform '/ a b))

(defun perform (op a b)
  (cond ((or (null a) (null b)) nil)
        ((and (eql op '/) (zerop b)) nil) ; avoid division by zero
        (t (funcall (symbol-function op) a b))))

Finally, the functions next-subset and next-permutation do exactly what their names imply. These are interesting algorithms in their own right and I will try to explain how they can be implemented in another post.

To solve the problem simply call solve and wait in anticipation (about 17 secs) for the answer.

> (time (solve))

Run time: 16.48103 secs.
(the answer has been removed, solve it yourself)

About these ads