/* * * allint.m, 5 Apr 12 * * Calculate the list of all values that can be generated * by expressions containing +, -, * and / and any single * digit number other than zero. */ all_0 : [1,2,3,4,5,6,7,8,9]; PLUS : 1; MINUS : 2; TIMES : 3; DIVIDE : 4; EXPON : 5; operators : [PLUS, MINUS, TIMES, DIVIDE]; do_op(op1, op2, operator) := block ( if (operator = PLUS) then return(op1 + op2), if (operator = MINUS) then return(op1 - op2), if (operator = TIMES) then return(op1 * op2), if (operator = DIVIDE) then /* return(sublist(op1 / op2, integerp)) */ return(op1 / op2) ); eval_op(op1, op2, operator) := ( result : [], l_op1 : length(op1), l_op2 : length(op2), /* * Call unique of every iteration to cut down on memory usage. * Loop over shorter list (because it is probably faster???) */ if (l_op1 < l_op2) then for i in op1 do result : unique(append(result, do_op(i, op2, operator))) else for i in op2 do result : unique(append(result, do_op(op1, i, operator))), delete(0, result) ); apply_all_ops(op1, op2) := ( result : [], for i_op in operators do result : unique(append(result, eval_op(op1, op2, i_op))), result ); non_neg(n) := ( n >= 0); list_info(l) := block ( l_i : sublist(l, integerp), /* Add 1 to include 0 in count */ print("Elements ", length(l)+1, ", integer elements ", length(l_i)+1, ", non-negative integer elements ", length(sublist(l_i, non_neg))+1), last_l: last(l_i), for i:1 thru last_l do if (member(i, l_i) = false) then ( print("First missing value ", i), return(1) ) ); all_1 : sort(unique(flatten(append( eval_op(all_0, all_0, TIMES), eval_op(all_0, all_0, DIVIDE), eval_op(all_0, all_0, MINUS), eval_op(all_0, all_0, PLUS))))); list_info(all_1); all_2 : sort(unique(append( apply_all_ops(all_0, all_1), apply_all_ops(all_1, all_0)))); list_info(all_2); all_3 : sort(unique(append( apply_all_ops(all_1, all_1), apply_all_ops(all_0, all_2), apply_all_ops(all_2, all_0)))); all_4 : sort(unique(append( apply_all_ops(all_1, all_2), apply_all_ops(all_2, all_1), apply_all_ops(all_0, all_3), apply_all_ops(all_3, all_0)))); all_5 : sort(unique(append( apply_all_ops(all_2, all_2), apply_all_ops(all_1, all_3), apply_all_ops(all_3, all_1), apply_all_ops(all_0, all_4), apply_all_ops(all_4, all_0)))); /* * If non-integer values are being calculated then * more than 4G of memory is needed for the following * to execute completely. */ all_6 : sort(unique(append( apply_all_ops(all_2, all_3), apply_all_ops(all_3, all_2), apply_all_ops(all_1, all_4), apply_all_ops(all_4, all_1), apply_all_ops(all_0, all_5), apply_all_ops(all_5, all_0)))); all_7 : sort(unique(append( apply_all_ops(all_3, all_3), apply_all_ops(all_2, all_4), apply_all_ops(all_4, all_2), apply_all_ops(all_1, all_5), apply_all_ops(all_5, all_1), apply_all_ops(all_0, all_6), apply_all_ops(all_6, all_0)))); /* * On a machine with 4G maxima runs out of heap space when * executing the following. */ all_8 : sort(unique(append( apply_all_ops(all_3, all_4), apply_all_ops(all_3, all_3), apply_all_ops(all_2, all_5), apply_all_ops(all_5, all_2), apply_all_ops(all_6, all_1), apply_all_ops(all_1, all_6), apply_all_ops(all_0, all_7), apply_all_ops(all_7, all_0)))); all_9 : sort(unique(append( apply_all_ops(all_4, all_4), apply_all_ops(all_3, all_5), apply_all_ops(all_5, all_3), apply_all_ops(all_2, all_6), apply_all_ops(all_6, all_2), apply_all_ops(all_1, all_7), apply_all_ops(all_7, all_1), apply_all_ops(all_0, all_8), apply_all_ops(all_8, all_0))));