blob: 06be150364b0ddfe84eddefad005187e67685862 (
plain) (
blame)
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
|
(*
* SPDX-FileCopyrightText: Copyright 2025 Alexandre Jesus <https://adbjesus.com>
*
* SPDX-License-Identifier: GPL-3.0-or-later
*)
open Glpk.C.Functions
open Glpk.C.Types
type machine = { lights : int; buttons : int list list; ibuttons : int list; joltage : int list }
let parse_machine s =
let a = String.split_on_char ' ' s in
let lights =
List.hd a
|> String.fold_left
(fun acc c ->
match c with
| '.' -> acc * 2
| '#' -> (acc * 2) + 1
| '[' | ']' -> acc
| _ -> failwith (Printf.sprintf "Wrong data: %s" s))
0
in
let nlights = String.length (List.hd a) - 2 in
let parse_button s =
if s.[0] = '(' then
let sub = String.sub s 1 (String.length s - 2) in
Some (String.split_on_char ',' sub |> List.map int_of_string)
else None
in
let parse_ibutton b =
b
|> List.map (fun v ->
let v = nlights - v - 1 in
Int.shift_left 1 v)
|> List.fold_left ( + ) 0
in
let buttons = List.filter_map parse_button (List.tl a) in
let ibuttons = List.map parse_ibutton buttons in
let joltage = List.rev a |> List.hd in
let joltage = String.sub joltage 1 (String.length joltage - 2) in
let joltage = String.split_on_char ',' joltage |> List.map int_of_string in
{ lights; buttons; ibuttons; joltage }
let print_machines machines =
List.iter
(fun machine ->
Printf.printf "%d ->" machine.lights;
List.iter (Printf.printf " %d") machine.ibuttons;
Printf.printf " ->";
List.iter (Printf.printf " %d") machine.joltage;
Printf.printf "\n")
machines
let parse ch = ch |> In_channel.input_lines |> List.map parse_machine
let part1 ch =
let machines = parse ch in
let solve machine =
let rec fn v c bs =
if v = machine.lights then c
else
match bs with
| [] -> Int.max_int
| b :: bt -> Int.min (fn (Int.logxor v b) (c + 1) bt) (fn v c bt)
in
fn 0 0 machine.ibuttons
in
List.map solve machines |> List.fold_left ( + ) 0 |> Printf.printf "%d\n"
let part2 ch =
let machines = parse ch in
let solve machine =
let p = glp_create_prob () in
let n = List.length machine.joltage in
let m = List.length machine.buttons in
glp_set_obj_dir p glp_min;
glp_add_rows p n;
machine.joltage
|> List.to_seq
|> Seq.map Float.of_int
|> Seq.iteri (fun i v -> glp_set_row_bnds p (i + 1) glp_fx v v);
glp_add_cols p m;
for i = 1 to m do
glp_set_col_bnds p i glp_lo 0.0 0.0;
glp_set_col_kind p i glp_iv;
glp_set_obj_coef p i 1.0;
done;
(machine.buttons
|> List.iteri
(fun i b ->
let len = List.length b in
let ind = 0 :: (List.map (( + ) 1) b) |> Ctypes.CArray.of_list Ctypes.int in
let vals = Ctypes.CArray.make Ctypes.double ~initial:1.0 (len + 1) in
glp_set_mat_col p (i + 1) len (Ctypes.CArray.start ind) (Ctypes.CArray.start vals)
));
glp_simplex p Ctypes.null;
glp_intopt p Ctypes.null;
(if (glp_mip_status p) <> glp_opt then
failwith "Infeasible ILP");
let ans = glp_mip_obj_val p in
glp_delete_prob p;
Int.of_float (ans +. 0.1)
in
ignore (glp_term_out glp_off);
machines
|> List.map solve
|> List.fold_left ( + ) 0
|> Printf.printf "%d\n"
|
