Given four integers n1, n2, n3 and n4, one chooses two and uses them to produce a rational number r1 by applying either addition, subtraction, multiplication or division; one mixes r1 with the remaining two numbers and chooses two of them to produce a rational number r2 by applying either addition, subtraction, multiplication or division; one then takes r2 and the last remaining number to produce a rational number r3 by applying addition, subtraction, multiplication, or division; if there exists a way to make r3 equal 24, then (n1, n2, n3, n4) is said to be a good quad. For instance, (10,10,4,4) is a good quad since we have: (10*10-4)/4 = 24; (5,7,7,11) is a good quad since we have: (5-11/7)*7 = 24. Game-of-24 is a game that determines whether four given integers form a good quad or not. For a demo of Game-of-24, please visit this link.
In the following presentation of this chapter, I intend to present an implementation of Game-of-24 in pure functional style, solidifying various functional programming concepts covered so far. Please pay attention to the support for overloading in ATS, which helps make the presented code significantly easier to access.
Instead of making direct use of rational numbers in the implementation, I choose to use doubles (that is, floating point numbers of double precision) to approaximate them. The following declarations introduce int2dbl and dbl2int for casting integers to doubles and vice versa, respectively:
In the case where four given integers are claimed to form a good quad, we may want to see a proof to justify the claim. The following datatype expr is meant for providing such a proof:
// datatype expr = | EXPRnum of double | EXPRbop of (string(*opr*), expr, expr) // typedef exprlst = list0(expr) //
// val myproof = EXPRbop("/", EXPRbop("-", EXPRbop("*", EXPRnum(10), EXPRnum(10)), EXPRnum(4)), EXPRnum(4)) //
Given an expression (that is, an expr-value), the following function eval_expr returns the value of the expression:
// extern fun eval_expr(x0: expr): double // overload eval with eval_expr // implement eval_expr(x0) = ( case+ x0 of | EXPRnum(v0) => v0 | EXPRbop(opr, x1, x2) => let val v1 = eval_expr(x1) val v2 = eval_expr(x2) in case+ opr of | "+" => v1 + v2 | "-" => v1 - v2 | "*" => v1 * v2 | "/" => v1 / v2 | _(*unrecognized*) => let val () = assertloc(false) in 0.0 end end ) (* end of [eval_expr] *) //
The following functions print_expr and fprint_expr are needed for displaying an expression (that is, an expr-value):
// extern fun print_expr : (expr) -> void extern fun fprint_expr : (FILEref, expr) -> void // overload print with print_expr overload fprint with fprint_expr // (* ****** ****** *) // implement print_expr(x0) = fprint_expr(stdout_ref, x0) // implement fprint_expr(out, x0) = ( case x0 of | EXPRnum(v0) => fprint(out, dbl2int(v0)) | EXPRbop(opr, x1, x2) => fprint!(out, "(", x1, opr, x2, ")") ) //
The following functions are introduced for constructing abstract syntax trees to represent the 4 arithmetic operations: addition, subtraction, multiplication, and division:
// extern fun add_expr_expr : (expr, expr) -> expr and sub_expr_expr : (expr, expr) -> expr and mul_expr_expr : (expr, expr) -> expr and div_expr_expr : (expr, expr) -> expr // overload + with add_expr_expr overload - with sub_expr_expr overload * with mul_expr_expr overload / with div_expr_expr // (* ****** ****** *) // implement add_expr_expr(x1, x2) = EXPRbop("+", x1, x2) implement sub_expr_expr(x1, x2) = EXPRbop("-", x1, x2) implement mul_expr_expr(x1, x2) = EXPRbop("*", x1, x2) implement div_expr_expr(x1, x2) = EXPRbop("/", x1, x2) //
When using floating point numbers, one often needs to pay special attention equality test. For testing whether the value of an expression equals a given integer, the following function eq_expr_int checks whether the absolute difference between the value and the integer is less than a tiny fraction EPSILON:
// #define EPSILON 1E-8 // extern fun eq_expr_int(expr, int): bool // overload = with eq_expr_int // implement eq_expr_int(x0, i0) = abs(eval_expr(x0) - i0) < EPSILON //
What is done so far can be thought of as providing basic setup for the task of implementing Game-of-24. It is time for us to switch to the algorithmic part of the task next.
Given two expressions, the function combine_expr_expr returns a list consisting of every expression that can be constructed by applying addition, subtraction, multiplication, or division to the two given ones:
// extern fun combine_expr_expr(expr, expr): exprlst // overload combine with combine_expr_expr // (* ****** ****** *) // implement combine_expr_expr (x1, x2) = res where { // val res = list0_nil() val res = list0_cons(x1+x2, res) val res = list0_cons(x1-x2, res) val res = list0_cons(x2-x1, res) val res = list0_cons(x1*x2, res) val res = if x2 = 0 then res else list0_cons(x1/x2, res) val res = if x1 = 0 then res else list0_cons(x2/x1, res) // val res = list0_reverse(res) // } (* end of [combine_expr_expr] *) //
In practice, the following higher-order function list0_mapjoin is of common use:
// extern fun {a:t@ype} {b:t@ype} list0_mapjoin ( xs: list0(INV(a)) , fopr: cfun(a, list0(b))): list0(b) // implement {a}{b} list0_mapjoin (xs, fopr) = ( list0_concat<b>(list0_map<a><list0(b)>(xs, fopr)) ) //
Let task be an alias for list0(expr). Given a task-value xs of the type task, we can choose two expressions out of xs to form a new expression (by applying addition, subtraction, multiplication or division) and then combine it with the rest to construct a new task-value. By calling do_one on xs, we obtain all of the possible new task-values:
// typedef task = list0(expr) // extern fun do_one(xs: task): list0(task) // implement do_one(xs) = let // val x1x2xss = list0_nchoose_rest<expr>(xs, 2) // in // list0_mapjoin<$tup(exprlst, exprlst)><task> ( x1x2xss , lam ($tup(x1x2, xs)) => list0_map<expr><task> (combine(x1x2[0], x1x2[1]), lam(x) => list0_cons(x, xs)) ) // end // end of [do_one] //
// extern fun do_ones(n: int, xss: list0(task)): list0(task) // implement do_ones(n, xss) = if n >= 2 then do_ones ( n-1 , list0_mapjoin<task><task>(xss, lam(xs) => do_one(xs)) ) (* do_ones *) else xss // (* ****** ****** *) // extern fun play_game ( n1: int , n2: int , n3: int , n4: int): exprlst // implement play_game (n1, n2, n3, n4) = let // val x1 = EXPRnum(int2dbl(n1)) val x2 = EXPRnum(int2dbl(n2)) val x3 = EXPRnum(int2dbl(n3)) val x4 = EXPRnum(int2dbl(n4)) in // list0_mapopt<task><expr> ( do_ones(4, list0_sing(g0ofg1($list{expr}(x1, x2, x3, x4)))) , lam(xss) => if (xss[0] = 24) then Some0(xss[0]) else None0() ) // end // end of [play_game]
The code presented in this chapter targets C. After a bit of adaption, the code can also be compiled into JS for interpretation inside a browser. Please see a demo of Game-of-24 on-line, which is directly based on the presented code.
Please find on-line the entirety of the code used in this chapter. The mentioned URL link(s) can be found as follows: