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