-
Notifications
You must be signed in to change notification settings - Fork 3
/
day21.ml
116 lines (97 loc) · 2.62 KB
/
day21.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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
module Grid = struct
open CCFun
type t = bool array array
let of_string: (string -> t) =
let to_bool =
CCString.to_array %> Array.map (Char.equal '#') in
String.split_on_char '/' %> CCArray.of_list %> Array.map to_bool
let make size : t =
Array.make_matrix size size false
let flip (g: t) =
let gc = Array.copy g in
let last = Array.length gc - 1 in
CCArray.swap gc 0 last;
gc
let transpose (g: t) =
let l = Array.length g in
let gc = make l in
for i = 0 to pred l do
for j = i to pred l do
gc.(j).(i) <- g.(i).(j);
gc.(i).(j) <- g.(j).(i);
done
done;
gc
let all_variants (g: t) =
let t = transpose in
let f = flip in
[ g;
g |> t;
g |> t |> f;
g |> t |> f |> t;
g |> t |> f |> t |> f;
g |> t |> f |> t |> f |> t;
g |> t |> f |> t |> f |> t |> f;
g |> t |> f |> t |> f |> t |> f |> t;
]
let pixels_on g =
let result = ref 0 in
g |> Array.iter (fun row ->
row |> Array.iter (fun x -> if x then incr result));
!result
end
let rules = Hashtbl.create (8 * 108)
let parse_line line =
match CCString.split ~by:" => " line with
| [ i; o ] ->
let inputs = Grid.all_variants (Grid.of_string i) in
let output = Grid.of_string o in
inputs |> List.iter (fun input ->
Hashtbl.add rules input output)
| _ -> failwith "invalid input"
let parse filename =
CCIO.(with_in filename read_lines_l)
|> List.iter parse_line
let () = parse "inputs/21.txt"
let starting_grid = Grid.of_string ".#./..#/###"
let grid_2x2 = Grid.make 2
let grid_3x3 = Grid.make 3
let get_square g i j by =
let result = if by = 2 then grid_2x2 else grid_3x3 in
for x = 0 to pred by do
for y = 0 to pred by do
result.(x).(y) <- g.(i+x).(j+y)
done
done;
result
let find_next g =
let size = Array.length g in
let by = if size mod 2 = 0 then 2 else 3 in
let new_size = size * (by+1) / by in
let square_size = size / by - 1 in
let result = Grid.make new_size
in
for i = 0 to square_size do
for j = 0 to square_size do
let square = get_square g (i*by) (j*by) by in
let enhanced = Hashtbl.find rules square in
let h = Array.length enhanced - 1 in
for x = 0 to h do
for y = 0 to h do
result.(i*(by+1) + x).(j*(by+1) + y) <- enhanced.(x).(y)
done
done
done
done;
result
let repeat f n g =
let rec aux n g =
match n with
| 0 -> g
| n -> aux (n-1) (f g)
in
aux n g
|> Grid.pixels_on |> Printf.printf "%d\n"
let () =
starting_grid |> repeat find_next 5;
starting_grid |> repeat find_next 18