113 lines
2.9 KiB
OCaml
113 lines
2.9 KiB
OCaml
type half = L | H
|
|
type bounds = {lo: int; hi: int}
|
|
type result = Exact of int | Between of bounds
|
|
|
|
let avg lo hi = (lo + hi) / 2
|
|
|
|
let rec find' ?(lo=0) ~hi = function
|
|
| [] -> if lo = hi then Exact hi else Between {lo; hi}
|
|
| L::hs -> find' ~lo ~hi:(avg lo hi) hs
|
|
| H::hs -> find' ~lo:(avg (lo+1) hi) ~hi hs
|
|
|
|
exception Inexact of bounds [@warn_on_literal_pattern]
|
|
|
|
let find ?lo ~hi halves =
|
|
match find' ?lo ~hi halves with
|
|
| Exact x -> x
|
|
| Between p -> raise (Inexact p)
|
|
|
|
|
|
type path = {rows: half list; cols: half list}
|
|
|
|
exception Unknown_char of char [@warn_on_literal_pattern]
|
|
|
|
let path_of_string str =
|
|
let revs {rows; cols} = List.{rows = rev rows; cols = rev cols} in
|
|
let put acc = function
|
|
| 'F' -> {acc with rows = L :: acc.rows}
|
|
| 'B' -> {acc with rows = H :: acc.rows}
|
|
| 'L' -> {acc with cols = L :: acc.cols}
|
|
| 'R' -> {acc with cols = H :: acc.cols}
|
|
| c -> raise (Unknown_char c) in
|
|
String.to_seq str |> Seq.fold_left put {rows = []; cols = []} |> revs
|
|
|
|
|
|
type seat = {row: int; col: int}
|
|
|
|
let seat_of_path {rows; cols} =
|
|
{row = find ~hi:127 rows;
|
|
col = find ~hi:7 cols}
|
|
|
|
let seat_id {row; col} = (row * 8) + col
|
|
|
|
let seat_id_of_string str =
|
|
path_of_string str |> seat_of_path |> seat_id
|
|
|
|
|
|
let%test_module _ = (module struct
|
|
let str = "FBFBBFFRLR"
|
|
let rows = [L;H;L;H;H;L;L]
|
|
let row = 44
|
|
let cols = [H;L;H]
|
|
let col = 5
|
|
let path = {rows; cols}
|
|
let seat = {row; col}
|
|
let id = 357
|
|
|
|
let%test _ = find' ~hi:1 [L] = Exact 0
|
|
let%test _ = find' ~hi:1 [H] = Exact 1
|
|
let%test _ = find' ~hi:127 [] = Between {lo = 0; hi = 127}
|
|
let%test _ = find' ~hi:127 rows = Exact row
|
|
let%test _ = find' ~hi:7 cols = Exact col
|
|
|
|
let%test _ = find ~hi:127 rows = row
|
|
let%test _ = find ~hi:7 cols = col
|
|
let%test_unit _ =
|
|
try ignore (find ~hi:127 []); failwith "didn't raise"
|
|
with Inexact _ -> ()
|
|
let%test _ = path_of_string str = path
|
|
|
|
let%test _ = seat_of_path path = seat
|
|
|
|
let%test _ = seat_id seat = id
|
|
end)
|
|
|
|
|
|
let infile_seats ~of_seq input =
|
|
Bracket.infile_lines input ~line:seat_id_of_string ~of_seq
|
|
|
|
let main1 input =
|
|
infile_seats input ~of_seq:(Seq.fold_left max 0)
|
|
|> Format.printf "max id: %d\n"
|
|
|
|
let%expect_test _ =
|
|
main1 "../../data/day5";
|
|
[%expect{| max id: 855 |}]
|
|
|
|
|
|
let make_list cmp seq = List.(fast_sort cmp (of_seq seq))
|
|
|
|
let rec find_pair f = function
|
|
| [] | [_] -> None
|
|
| x::y::zs ->
|
|
match f x y with
|
|
| Some z -> Some z
|
|
| None -> find_pair f (y::zs)
|
|
|
|
let find_gap lst =
|
|
let find_gap1 x y = if x + 1 <> y then Some (x + 1) else None in
|
|
find_pair find_gap1 lst
|
|
|
|
let main2 input =
|
|
match find_gap (infile_seats input ~of_seq:(make_list Int.compare)) with
|
|
| Some x -> Format.printf "seat id: %d\n" x
|
|
| None -> raise Not_found
|
|
|
|
let%expect_test _ =
|
|
main2 "../../data/day5";
|
|
[%expect{| seat id: 552 |}]
|
|
|
|
|
|
|
|
let main = Misc.main 5 [|main1; main2|]
|