Solving the 'Vietnamese school maths problem'

Question

Having read Can you do the maths puzzle for Vietnamese eight-year-olds that has stumped parents and teachers?, which presented the problem of filling in numbers 1 to 9 to satisfy

$$ a + 13 \frac{b}{c} + d + 12 e - f - 11 + \frac{g \cdot h}{i} - 10 = 66 $$

… I thought I'd try a Common Lisp implementation as a learning exercise.

(defun solve-puzzle (permutation)
  (destructuring-bind (a b c d e f g h i) permutation
    (let ((result (infpre:!! a + 13 * b / c + d + 12 * e - f - 11 + g * h / i - 10)))
      (when (= result 66) (print permutation)))))

(alexandria:map-permutations #'solve-puzzle '(1 2 3 4 5 6 7 8 9) :length 9)

This works; when executed, it produces a list of 136 valid combinations in around 300ms on my laptop. I have a couple of questions regarding the code though:

• How's my idiom? My background is C, C#, Ruby so I'm probably carrying over habits from those languages.
• Are there any obvious performance gotchas in the code - obvious to experienced Lispers, that is?

Answer 1

I'm not familiar with either the alexandria or infpre packages; I wrote my solution in Common Lisp as well, but using only language primitives. Assuming that the infpre evaluator follows standard arithmetic order-of-evaluation rules, your code looks perfectly fine (and more compact and readable than mine) but of course requires having those packages available. More importantly, your code should produce the same answers as my (different) approach.

I used my approach to make sure that the variables were local and that the compiled code manipulated them efficiently. (I ran mine in Clozure Common Lisp which compiles all expressions to machine code before running them).

;; Transcription of expression from puzzle picture
(defvar *expression* '(+ a (/ (* 13 b) c) d (* 12 e) (* -1 f) -11 (/ (* g h) i) -10))

;; Macro to generate nested loops trying all combinations
(defmacro nested-loops (variables variable-initializer body)
  (let ((internal-variable (gensym)))
    `(let ((answers))
       ,(nested-loops-helper t variables variable-initializer body internal-variable)
       answers)))

;; Helper function for macro to generate loop guts for each level
(defun nested-loops-helper (first-time variables variable-initializer body internal-variable)
  (cond ;; no more variables, generate body
    ((null variables)
     `(,@body))
    ;; otherwise generate a loop setting this variable to all possible values except ones already used
    (t (let* ((this-var (pop variables))
              (extra (when first-time `(for ,internal-variable = nil))))
         `(loop for ,this-var ,@variable-initializer ,@extra 
            unless (member ,this-var ,internal-variable)
            do (push ,this-var ,internal-variable)
            (,@(nested-loops-helper nil variables variable-initializer body internal-variable))
            (pop ,internal-variable))))))

;; Invocation of macro to solve puzzle (prints all answers and saves them in solutions variable)
(length (setq solutions
          (nested-loops (a b c d e f g h i) (from 1 to 9) 
                (let ((value #.*expression*))
                  (when (eql value 66)
                (print (list a b c d e f g h i))
                (push (list a b c d e f g h i) answers))))))

(format t "~&There are ~d solution~:p saved in the variable solutions.~%" (length solutions))