/*
 * Simple Fril program to play the "countdown" game.
 * Select 6 numbers (typically
 * four numbers which are less than 10 and two from {25, 50, 75, 100} and 
 * a target number in the range 100-999, then use the six numbers at most once each to 
 * create an expression involving +, -, * and / which evaluates to the target value.
 * e.g. target = 643, numbers = {1, 2, 5, 7, 25, 75}
 * expression = (((((5 - 1) * 75) + 25) * 2) - 7)
 * The Fril call to do this is 
 * ?((build 643 (1 2 5 7 25 75) X) (pp X))
 * Backtracking generates alternative expressions (although these may
 * be simple re-writes of the same expression.
 * No error checking, argument checking etc - what you see is what you get.
 *
 * Author T. P. Martin	Oct 2001 - beta release at best
 *
 */
 
 /* seq is the core - it creates a list of expressions and their values.
  * Initally, both are the input numbers.
  * Each recursive step deletes two values and their corresponding expressions,
  * and creates a new expression by combining these  with an operation (+,-,* or /)
  * This is evaluated, and if the value is a new positive integer, this value and
  * the corresponding expression are added to the lists and execution continues.
  * If not a new value, there's no point adding it, so fail and try another pair.
  * Continue until ther target is reached or there are no more possibilities.
  */
((seq TARGET USED (TARGET|REST) (EXPR|_) EXPR))

((seq TARGET USED VALUES EXPRS EXPROUT)
        (delete2 N1 D1 N2 D2 VALUES EXPRS RESTVALUES RESTEXPRS)
        (expr N1 N2 VAL D1 D2 EXPR)
        (negg member VAL USED)
        (negg member VAL VALUES)
        (seq TARGET (N1 N2 |USED) (VAL|RESTVALUES) (EXPR|RESTEXPRS) EXPROUT))

/* 
 * takes inputs N1 N2 E1 E2 where E1 is an expression that evaulates to N1,
 * and similar for E2 and N2; combines expressions E1 and E2 in some way to yield 
 * expression (E1 op E2), with value T
 */
((expr N1 N2 T E1 E2 (E1 + E2)) (sum N1 N2 T))
((expr N1 N2 T E1 E2 (E2 - E1)) (sum N1 T N2) (less 0 T))
((expr N1 N2 T E1 E2 (E1 - E2)) (sum N2 T N1) (less 0 T))
((expr N1 N2 T E1 E2 (E1 * E2))  (times N1 N2 T))
((expr N1 N2 T E1 E2 (E2/E1))  (times N1 T N2) (int T))
((expr N1 N2 T E1 E2 (E1/E2))  (times T N2 N1) (int T))

/* delete, delete2 and member - standard list processing predicates,
 * does what it says on the tin
 */

((delete N E (N|T) (E|ET) T ET))
((delete N E (VH|VT) (EH|ET) (VH|RV) (EH|RE)) (delete N E VT ET RV RE))

((delete2 N1 E1 N2 E2 (N1|VT) (E1|ET) RV RE)
         (delete N2 E2 VT ET RV RE))
((delete2 N1 E1 N2 E2 (N|VT)  (E|ET) (N|RV) (E|RE))
         (delete2 N1 E1 N2 E2 VT ET RV RE))


((member E (E|T)))
((member E (_|T)) (member E T))

/*
 * top level call from Fril
 */
 
((build TOT FROM EXPR) (seq TOT () FROM  FROM EXPR)  )