Day 10 (learned to use ctypes :))

9 files changed, 197 insertions, 1 deletions

diff --git a/bin/main.ml b/bin/main.ml
index 3d957d5..993c926 100644
--- a/bin/main.ml
+++ b/bin/main.ml
@@ -44,6 +44,8 @@ let day_part_fn day part =
   | 8, 2 -> Day08.part2
   | 9, 1 -> Day09.part1
   | 9, 2 -> Day09.part2
+  | 10, 1 -> Day10.part1
+  | 10, 2 -> Day10.part2
   | _ ->
       failwith
         (Format.sprintf "Day %d, part %d, has not yet been implemented\n" day
diff --git a/data b/data
-Subproject e479718840bd0124b170271196b2f60f7fdb3c5
+Subproject f99f49db22b486fa001c2994c77259378f60c90
diff --git a/dune-project b/dune-project
index 03339da..a9ccffc 100644
--- a/dune-project
+++ b/dune-project
@@ -4,6 +4,8 @@
 ;
 ; SPDX-License-Identifier: CC0-1.0
 
+(using ctypes 0.3)
+
 (name aoc2025)
 
 (generate_opam_files false)
diff --git a/external/glpk/dune b/external/glpk/dune
new file mode 100644
index 0000000..5d75615
--- /dev/null
+++ b/external/glpk/dune
@@ -0,0 +1,17 @@
+; SPDX-FileCopyrightText: Copyright 2025 Alexandre Jesus <https://adbjesus.com>
+;
+; SPDX-License-Identifier: CC0-1.0
+
+(library
+ (name glpk)
+ (ctypes
+  (external_library_name glpk)
+  (headers (include "glpk.h"))
+  (type_description
+   (instance Types)
+   (functor Type_description))
+  (function_description
+   (instance Functions)
+   (functor Function_description))
+  (generated_types Types_generated)
+  (generated_entry_point C)))
\ No newline at end of file
diff --git a/external/glpk/function_description.ml b/external/glpk/function_description.ml
new file mode 100644
index 0000000..3dd469a
--- /dev/null
+++ b/external/glpk/function_description.ml
@@ -0,0 +1,37 @@
+open Ctypes
+
+module Types = Types_generated
+
+module Functions (F : Ctypes.FOREIGN) = struct
+  open F
+
+  let glp_create_prob = foreign "glp_create_prob" (void @-> returning Types.glp_prob)
+
+  let glp_delete_prob = foreign "glp_delete_prob" (Types.glp_prob @-> returning void)
+
+  let glp_add_rows = foreign "glp_add_rows" (Types.glp_prob @-> int @-> returning void)
+
+  let glp_add_cols = foreign "glp_add_cols" (Types.glp_prob @-> int @-> returning void)
+
+  let glp_set_row_bnds = foreign "glp_set_row_bnds" (Types.glp_prob @-> int @-> int @-> double @-> double @-> returning void)
+
+  let glp_set_col_bnds = foreign "glp_set_col_bnds" (Types.glp_prob @-> int @-> int @-> double @-> double @-> returning void)
+
+  let glp_set_col_kind = foreign "glp_set_col_kind" (Types.glp_prob @-> int @-> int @-> returning void)
+  
+  let glp_set_obj_coef = foreign "glp_set_obj_coef" (Types.glp_prob @-> int @-> double @-> returning void)
+
+  let glp_set_obj_dir = foreign "glp_set_obj_dir" (Types.glp_prob @-> int @-> returning void)
+
+  let glp_set_mat_col = foreign "glp_set_mat_col" (Types.glp_prob @-> int @-> int @-> ptr int @-> ptr double @-> returning void)
+
+  let glp_simplex = foreign "glp_simplex" (Types.glp_prob @-> Types.glp_smcp_ptr @-> returning void)
+
+  let glp_intopt = foreign "glp_intopt" (Types.glp_prob @-> Types.glp_iocp_ptr @-> returning void)
+
+  let glp_mip_status = foreign "glp_mip_status" (Types.glp_prob @-> returning int)
+
+  let glp_mip_obj_val = foreign "glp_mip_obj_val" (Types.glp_prob @-> returning double)
+
+  let glp_term_out = foreign "glp_term_out" (int @-> returning int)
+end
diff --git a/external/glpk/type_description.ml b/external/glpk/type_description.ml
new file mode 100644
index 0000000..620b82b
--- /dev/null
+++ b/external/glpk/type_description.ml
@@ -0,0 +1,24 @@
+open Ctypes
+
+module Types (F: Ctypes.TYPE) = struct
+  open F
+
+  type glp_prob = unit ptr
+  let glp_prob : glp_prob typ = ptr void
+
+  type glp_iocp_ptr = unit ptr
+  let glp_iocp_ptr : glp_iocp_ptr typ = ptr void
+
+  type glp_smcp
+  let glp_smcp : glp_smcp structure typ = structure "glp_smcp"
+
+  type glp_smcp_ptr = unit ptr
+  let glp_smcp_ptr : glp_smcp_ptr typ = ptr void
+
+  let glp_min = constant "GLP_MIN" int
+  let glp_fx = constant "GLP_FX" int
+  let glp_lo = constant "GLP_LO" int
+  let glp_opt = constant "GLP_OPT" int
+  let glp_iv = constant "GLP_IV" int
+  let glp_off = constant "GLP_OFF" int
+end
diff --git a/flake.nix b/flake.nix
index 8146942..0d32b82 100644
--- a/flake.nix
+++ b/flake.nix
@@ -20,10 +20,13 @@
         nativeBuildInputs = with pkgs; [
           dune_3
           reuse
+          glpk
         ] ++ (with ocamlPackages; [
           ocaml
           ocaml-lsp
           ocamlformat
+          findlib
+          ctypes
         ]);
       };
     };
diff --git a/lib/day10.ml b/lib/day10.ml
new file mode 100644
index 0000000..06be150
--- /dev/null
+++ b/lib/day10.ml
@@ -0,0 +1,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"
diff --git a/lib/dune b/lib/dune
index 8453ca7..308979f 100644
--- a/lib/dune
+++ b/lib/dune
@@ -3,4 +3,5 @@
 ; SPDX-License-Identifier: CC0-1.0
 
 (library
- (name aoc2025))
+ (name aoc2025)
+ (libraries glpk))