61 lines
2.1 KiB
OCaml
61 lines
2.1 KiB
OCaml
(** Module describing a tuple of four integers, used for the map keys later. *)
|
|
module Int4Tuple = struct
|
|
type t = int * int * int * int
|
|
|
|
let compare = Stdlib.compare
|
|
end
|
|
|
|
module Int4Map = Map.Make (Int4Tuple)
|
|
(** Map keyed by a tuple of 4 integers *)
|
|
|
|
(** [next_secret secret] returns the next secret value after [secret]. *)
|
|
let next_secret secret =
|
|
let secret = secret * 64 lxor secret mod 16777216 in
|
|
let secret = secret / 32 lxor secret mod 16777216 in
|
|
let secret = secret * 2048 lxor secret mod 16777216 in
|
|
secret
|
|
|
|
let part1 n nums =
|
|
List.map (Aoc.apply_n n next_secret) nums |> List.fold_left ( + ) 0
|
|
|
|
(** [secret_list n secret] returns a list containing the [n] secrets after
|
|
[secret]. *)
|
|
let secret_list n secret =
|
|
let rec impl s () = Seq.Cons (s, impl (next_secret s)) in
|
|
Seq.drop 1 (impl secret) |> Seq.take n |> List.of_seq
|
|
|
|
(** [find_sequence_values map lst] updates [map] to contain the value of the
|
|
sale for the first occurance in each sequence of 4 differences in [lst]. *)
|
|
let rec find_sequence_values map =
|
|
let update_value amt = function None -> Some amt | x -> x in
|
|
function
|
|
| a :: b :: c :: d :: e :: t ->
|
|
find_sequence_values
|
|
(Int4Map.update (b - a, c - b, d - c, e - d) (update_value e) map)
|
|
(b :: c :: d :: e :: t)
|
|
| _ -> map
|
|
|
|
let part2 n secrets =
|
|
let merge_values _ x y =
|
|
match (x, y) with
|
|
| Some x, Some y -> Some (x + y)
|
|
| Some x, None -> Some x
|
|
| None, Some y -> Some y
|
|
| None, None -> None
|
|
in
|
|
let costs =
|
|
List.map (secret_list n) secrets (* list of lists of secrets *)
|
|
|> List.map (List.map (fun x -> x mod 10)) (* list of lists of values *)
|
|
|> List.map (find_sequence_values Int4Map.empty) (* sequence -> value map *)
|
|
|> List.fold_left (* merge maps - adding values of same key *)
|
|
(fun acc map -> Int4Map.merge merge_values acc map)
|
|
Int4Map.empty
|
|
in
|
|
Int4Map.fold (fun _ v acc -> max acc v) costs 0 (* find max value *)
|
|
|
|
let read_file fname = Aoc.strings_of_file fname |> List.map int_of_string
|
|
|
|
let _ =
|
|
Aoc.main read_file
|
|
[ (string_of_int, part1 2000); (string_of_int, part2 2000) ]
|