Advent of Code 2020 https://adventofcode.com/
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

78 lines
2.4 KiB

2 years ago
  1. (* Common util. Should probably put this in a module or something.. *)
  2. let get_one_line file =
  3. try Some (input_line file) with
  4. End_of_file -> None
  5. let get_lines file =
  6. let rec input lines =
  7. match get_one_line file with
  8. Some line -> input (line :: lines)
  9. | None -> List.rev lines
  10. in input []
  11. let read_file file =
  12. let channel = open_in(file) in
  13. get_lines channel
  14. let (<<) f g x = f(g(x))
  15. let (>>) f g x = g(f(x))
  16. let rec take n (x :: xs) = (* take the first n elements *)
  17. match n with
  18. | 0 -> []
  19. | n -> x :: (take (n-1) xs)
  20. let rec drop n l = (* drop the first n elemnts *)
  21. match n with
  22. | 0 -> l
  23. | n -> drop (n-1) @@ List.tl l
  24. let sub_list start length = (* sub list from start *)
  25. take length >> drop start
  26. let list_sum = List.fold_left (+) 0
  27. let list_max l = List.fold_left (fun acc x -> if x > acc then x else acc) (List.hd l) l
  28. let list_min l = List.fold_left (fun acc x -> if x < acc then x else acc) (List.hd l) l
  29. let range start len = (* makes a new list from start with length len *)
  30. List.init len (fun x -> x + 0) |> List.map (fun x -> x + start)
  31. let flip f x y = f y x
  32. (* --- *)
  33. let has_adders l target = (* do any 2 elements of l add up to target *)
  34. match List.find_opt (fun x ->
  35. match List.find_opt (fun y -> x != y && x + y = target) l with
  36. | Some _ -> true
  37. | None -> false
  38. ) l with
  39. | Some _ -> true
  40. | None -> false
  41. let rec first_without_adders pre lines =
  42. let x :: xs = lines in (* match out the head and tail *)
  43. let cur = List.nth lines pre in (* grab the first row after the preamble *)
  44. let sub = take pre lines in (* grab the preamble sublist *)
  45. if has_adders sub cur (* chechk for adders *)
  46. then first_without_adders pre xs (* if it has adders, recurse with the tail of the original list *)
  47. else cur (* no adders! return this one *)
  48. let rec all_sub_lists = function (* all combinations of sub-lists *)
  49. | [] -> []
  50. | xs ->
  51. range 0 (List.length xs)
  52. |> List.map (fun len' -> sub_list 0 len' xs)
  53. |> flip List.append (all_sub_lists @@ List.tl xs)
  54. let () =
  55. let lines = read_file "day9.txt" |> List.map int_of_string in
  56. let first = lines |> first_without_adders 25 in
  57. Printf.printf "first without 2 adders %i\n" first;
  58. let all_subs = all_sub_lists lines in
  59. let our_range = List.find (fun l -> list_sum l = first) all_subs in
  60. let our_sum = (list_max our_range) + (list_min our_range) in
  61. Printf.printf "sum %i\n" our_sum;