24 game/Solve: Difference between revisions
Content added Content deleted
(clarify a descriptive sentence.) |
(added ocaml) |
||
| Line 224: | Line 224: | ||
*<code>Permutations[Array[v, n]]</code> returns <math>n!</math> permutations. |
*<code>Permutations[Array[v, n]]</code> returns <math>n!</math> permutations. |
||
Therefore, the size of the working set is <math>64 \cdot n!\, C_{n-1} = 64 \cdot (n-1)!!!! = 64 \frac{(2n-2)!}{(n-1)!}</math>, where <math>n!!!!</math> is the [[wp:quadruple factorial|quadruple factorial]]. It goes without saying that this number increases very fast. For this game, the total is 7680 elements. For higher numbers of inputs, it is {7 680, 107 520, 1 935 360, 42 577 920, 1 107 025 920, ...}. |
Therefore, the size of the working set is <math>64 \cdot n!\, C_{n-1} = 64 \cdot (n-1)!!!! = 64 \frac{(2n-2)!}{(n-1)!}</math>, where <math>n!!!!</math> is the [[wp:quadruple factorial|quadruple factorial]]. It goes without saying that this number increases very fast. For this game, the total is 7680 elements. For higher numbers of inputs, it is {7 680, 107 520, 1 935 360, 42 577 920, 1 107 025 920, ...}. |
||
=={{header|OCaml}}== |
|||
<lang ocaml>type expression = |
|||
| Const of float |
|||
| Sum of expression * expression (* e1 + e2 *) |
|||
| Diff of expression * expression (* e1 - e2 *) |
|||
| Prod of expression * expression (* e1 * e2 *) |
|||
| Quot of expression * expression (* e1 / e2 *) |
|||
let rec eval = function |
|||
| Const c -> c |
|||
| Sum (f, g) -> eval f +. eval g |
|||
| Diff(f, g) -> eval f -. eval g |
|||
| Prod(f, g) -> eval f *. eval g |
|||
| Quot(f, g) -> eval f /. eval g |
|||
let print_expr expr = |
|||
let open_paren prec op_prec = |
|||
if prec > op_prec then print_string "(" in |
|||
let close_paren prec op_prec = |
|||
if prec > op_prec then print_string ")" in |
|||
let rec print prec expr = (* prec is the current precedence *) |
|||
match expr with |
|||
| Const c -> Printf.printf "%g" c |
|||
| Sum(f, g) -> |
|||
open_paren prec 0; |
|||
print 0 f; print_string " + "; print 0 g; |
|||
close_paren prec 0 |
|||
| Diff(f, g) -> |
|||
open_paren prec 0; |
|||
print 0 f; print_string " - "; print 1 g; |
|||
close_paren prec 0 |
|||
| Prod(f, g) -> |
|||
open_paren prec 2; |
|||
print 2 f; print_string " * "; print 2 g; |
|||
close_paren prec 2 |
|||
| Quot(f, g) -> |
|||
open_paren prec 2; |
|||
print 2 f; print_string " / "; print 3 g; |
|||
close_paren prec 2 |
|||
in |
|||
print 0 expr |
|||
let rec insert v li = match li with |
|||
| [] -> [[v]] |
|||
| x::xs -> (v::li) :: (List.map (fun y -> x::y) (insert v xs)) |
|||
let rec permutations li = match li with |
|||
| x::xs -> List.flatten (List.map (insert x) (permutations xs)) |
|||
| _ -> [li] |
|||
let rec comp expr = function |
|||
| x::xs -> |
|||
comp (Sum (expr, x)) xs; |
|||
comp (Diff(expr, x)) xs; |
|||
comp (Prod(expr, x)) xs; |
|||
comp (Quot(expr, x)) xs; |
|||
| [] -> |
|||
if (eval expr) = 24.0 |
|||
then (print_expr expr; print_newline()) |
|||
;; |
|||
let () = |
|||
Random.self_init(); |
|||
let digits = Array.init 4 (fun _ -> 1 + Random.int 9) in |
|||
Array.iter (Printf.printf " %d") digits; print_newline(); |
|||
let digits = Array.to_list(Array.map float_of_int digits) in |
|||
let digits = List.map (fun v -> Const v) digits in |
|||
let all = permutations digits in |
|||
List.iter (fun this -> |
|||
match this with |
|||
| x::xs -> comp x xs |
|||
| _ -> assert false |
|||
) all</lang> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||