🏡 index : ~doyle/aoc.git

d1188699e5c26918c398a11cc51d1bf8821dbb09 [patch]

4ec463429c760858a30515f7169e417e7db701d5

15a856261b2c5baa25d5ea135aef710aff4bdc5b

d1188699e5c26918c398a11cc51d1bf8821dbb09.tar.gz

Add 2024 day 11

Diff

 README     |  4 ++--
 2024/11.ml | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 51 insertions(+), 2 deletions(-)

diff --git a/README b/README
index 5e855a0..0a04c45 100644
--- a/README
+++ a/README
@@ -24,8 +24,8 @@
|        8 | Rust     | |        8 | Haskell  |
|        9 | OCaml    | |        9 | Haskell  |
|       10 | OCaml    | |       10 | Haskell  |
+---------------------+ |       11 | Haskell  |
                        |       12 | Rust     |
|       11 | OCaml    | |       11 | Haskell  |
+---------------------+ |       12 | Rust     |
                        |       13 | Haskell  |
                        |       14 | Haskell  |
                        |       15 | Haskell  |
diff --git a/2024/11.ml b/2024/11.ml
new file mode 100755
index 0000000..b3779ef 100755
--- /dev/null
+++ a/2024/11.ml
@@ -1,0 +1,49 @@
#!/usr/bin/env nix-shell

(*
#!nix-shell --pure -i ocaml -p ocaml
*)

let input = read_line () |> String.split_on_char ' ' |> List.map int_of_string

let rec pow a = function
  | 0 ->
      1
  | 1 ->
      a
  | n ->
      let b = pow a (n / 2) in
      b * b * if n mod 2 = 0 then 1 else a

let transform = function
  | 0 ->
      [1]
  | n ->
      let log10 = Float.(to_int (log10 (of_int n))) + 1 in
      let exp = pow 10 (log10 / 2) in
      let lhs = n / exp in
      let rhs = n - (lhs * exp) in
      if log10 mod 2 = 0 then [lhs; rhs] else [n * 2024]

let count n x =
  let memo = Hashtbl.create 100 in
  let rec aux n x =
    match (n, Hashtbl.find_opt memo (n, x)) with
    | _, Some v ->
        v
    | 0, _ ->
        1
    | n, _ ->
        let res =
          transform x |> List.map (aux (n - 1)) |> List.fold_left ( + ) 0
        in
        Hashtbl.add memo (n, x) res ;
        res
  in
  aux n x

let iter n = input |> List.map (count n) |> List.fold_left ( + ) 0

let _ = iter 25 |> print_int |> print_newline

let _ = iter 75 |> print_int |> print_newline