August 21, 2024
P93 - An arithmetic puzzle
Given a list of integer numbers, find a correct way of inserting arithmetic signs (operators) such that the result is a correct equation. Example: With the list of numbers (2 3 5 7 11) we can form the equations 2-3+5+7 = 11 or 2 = (3*5+7)/11 (and ten others!).
lisp
;;; Generate and test paradigm
;;; Generates all possible expressions
;;; then chooses one that is valid and returns it
;;; or nil if none exists
(load "p17.lisp") ; for split
(defun valid-expr (lista)
(if (< (length lista) 2)
nil
(one-valid (bool-exprs-up-to (1- (length lista)) lista))
)
)
(defun one-valid (lista)
(if (null lista)
nil
(if (eval (car lista))
(car lista)
(one-valid (cdr lista))
)
)
)
(defun bool-exprs-up-to (k lista)
(if (< k 1)
nil
(append (bool-exprs-up-to (1- k) lista)
(bool-exprs-with k lista)
)
)
)
(defun bool-exprs-with (k lista)
(let* ((pair (split lista k))
(a (first pair))
(b (second pair))
)
(put-one '=
(cartesian (arith-exprs a)
(arith-exprs b)
)
)
)
)
(defun put-one (symb lista)
(mapcar #'(lambda (x) (cons symb x)) lista)
)
(defun cartesian (la lb)
(if (null la)
nil
(append (cart-one (car la) lb)
(cartesian (cdr la) lb)
)
)
)
(defun cart-one (a lb)
(if (null lb)
nil
(cons (list a (car lb))
(cart-one a (cdr lb))
)
)
)
(defun arith-exprs (lista)
(if (null (cdr lista))
(list (car lista) (cons '- lista))
(arith-exprs-up-to (1- (length lista)) lista)
)
)
(defun arith-exprs-up-to (k lista)
(if (< k 1)
nil
(append (arith-exprs-up-to (1- k) lista)
(arith-exprs-with k lista)
)
)
)
(defun arith-exprs-with (k lista)
(let* ((pair (split lista k))
(a (first pair))
(b (second pair))
)
(put '(+ * /)
(cartesian (arith-exprs a)
(arith-exprs b)
)
)
)
)
(defun put (symbs lista)
(if (null symbs)
nil
(append (put-one (car symbs) lista)
(put (cdr symbs) lista)
)
)
)
Be first to comment