/
problem_94.ml
102 lines (102 loc) · 2.89 KB
/
problem_94.ml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
exception Solution_Found
exception No_Solution
(*Constraint
* combis is list of arithmetic operations
* 0 is =
* 1 is +
* 2 is -
* 3 is *
* 4 is /
* *)
let arithmetic_puzzle l =
let next_combination combis =
List.fold_right (fun ele (b, acc) ->
if ele = 0 then
(b, ele::acc)
else
if b = true then
if ele = 4 then
(true, 1::acc)
else
(false, ele+1::acc)
else
(false, ele::acc)
)
combis (true, [])
in
let next_equal_pos combis =
List.fold_right (fun ele (b, acc) ->
if b=true then
(false, 0::acc)
else if ele=0 then
(true, 1::acc)
else
(false, ele::acc)
) combis (false , [])
in
let operator x = if x = 1 then (+)
else if x = 2 then (-)
else if x = 3 then ( * )
else if x = 4 then (fun a b -> if a mod b != 0 then raise Division_by_zero else a/b )
else failwith "no operator to this number "
in
let rec eval c l = match (c,l) with
|([], [x]) -> x
| (hdc::tlc, hdl::tll) -> (operator hdc) (eval tlc tll) hdl
| _ -> raise No_Solution
in
let split c l =
let rec aux c l b =
match (c,l) with
| ([], [x]) -> ([],[],[], [x])
| (hdc::tlc, hdl::tll) ->
let acc_f_c, acc_f_l, acc_s_c, acc_s_l = aux tlc tll (if hdc= 0 then true else b)
in
if hdc=0
then acc_f_c, hdl::acc_f_l, acc_s_c, acc_s_l
else
if b then acc_f_c, acc_f_l, hdc::acc_s_c, hdl::acc_s_l
else hdc::acc_f_c, hdl::acc_f_l, acc_s_c, acc_s_l
| _ -> failwith "Error in split"
in
aux c l false
in
let eval_equation c l =
let firstc, firstl, secondc, secondl = split c l
in
try
(if (eval (List.rev firstc) (List.rev firstl)) = (eval (List.rev secondc) (List.rev secondl)) then true
else false) with Division_by_zero -> false
in
let rec solve c =
if eval_equation c l = false then
let b,c = next_combination c
in
if b then
let b2, c = next_equal_pos c
in
if b2=true then raise No_Solution
else
solve c
else solve c
else c
in
let operator_string x = if x=0 then "="
else if x=1 then "+"
else if x=2 then "-"
else if x=3 then "*"
else if x=4 then "/"
else failwith "failure in operator string"
in
let rec to_string c l acc b = match (c,l) with
| ([], [x]) -> acc^(string_of_int x)
| (hdc::tlc, hdl::tll) ->
if hdc = 0 then
acc^(string_of_int hdl)^"="^(to_string tlc tll "" false)
else
to_string tlc tll ((if b then "(" else "")^acc^(string_of_int hdl)^(if b then ")" else "")^operator_string hdc) true
| _ -> failwith "Failure in to_string"
in
let str = to_string (solve (List.rev_append (List.rev_map (fun _ -> 1 ) (List.tl (List.tl l))) [0])) l "" false
in
str