Advent of Code 2018 Day 1 in OCaml: Find length of cycles when accumulating deltas

Question

I just started Advent of Code 2018. This is exercise 2 of day 1, and I can't understand why my code is so slow (4 minutes 37 seconds, compared to 200ms for a friend who did it in Clojure with the same computer).

Basically, it accumulates integers from a provided list of ints, named input. Whenever the current value of the accumulator is equal to one of its previous values, it is returned. We might have to loop many times over the provided list before we find such an occurrence. Here is the code:

 let main () =
 let rec my_slow_code lst history =
 if lst == [] then my_slow_code input history
 else
 let current = List.hd lst + List.hd history in
 if List.mem current history then current
 else my_slow_code (List.tl lst) (current :: history)
 in
 my_slow_code input [0]

I can't understand what mistake here makes such a slow code, maybe the use of List.mem?

Answer 1

I won't give it all away, since that would take away some of the fun of Advent of Code, but I'll point out:

First, yes, List.mem takes time proportional to the length of your list, which means if you're calling it over and over again it can be quite slow indeed. There might be faster structures you could use if you want to track if a previous value has been seen before, like Sets. Also, you should not be using == for equality here but rather =; I recommend learning the difference between = and ==, you will want to know it.

Second, your code is not very idiomatic OCaml; in general, if you're doing things like nesting lots of ifs and using List.hd instead of pattern matching, you may not be doing things quite right. This won't impact your performance but might impact readability and correctness. (For example, the match l with | [] -> ... pattern will warn you if a pattern match isn't exhaustive, which avoids nasty bugs.)

• laurentmeyer: thanks for the tips! Using = instead of == is indeed more correct - even if it did not improve the efficiency. On the other hand, using Set made it much, much faster (more than 500x)
• Perry: It improves it from O(n) to O(1), which is vastly better than improving by a constant, no matter how large.

Answer 2

As noted, you can refactor your slow code to utilize structural equality (=) rather than physical equality (==) and pattern-matching. It's still slow, but it's more idiomatic.

let main () =
 let rec my_slow_code lst history =
 match lst with
 | [] -> my_slow_code input history
 | x::xs ->
 let y = List.hd history in 
 let current = x + y in
 if List.mem current history then current
 else my_slow_code xs (current :: history) 
 in
 my_slow_code input [0]

If you use a set for history rather than a list, then adding is O(log n) rather than O(1), but lookup is also O(log n) rather than O(n).

let main () =
 let module Int_set = Set.Make (Int) in
 let rec aux lst prev history =
 match lst with
 | [] -> aux input prev history
 | x::xs ->
 let current = x + prev in
 if Int_set.mem current history then current
 else aux xs current (Int_set.add current history) 
 in
 aux input 0 (Int_set.singleton 0)

As Int_set isn't required outside of main it can be locally scoped.

Breaking it down

We know the input list can repeat forever. This suggests we want to convert the list to a sequence and then cycle it.

If we then have something with keeps a rolling accumulation of a sequence, and a function which finds the first repeat in a sequence, we can string it together to get the overall solution.

let main () =
 let first_repeat seq =
 let module Int_set = Set.Make (Int) in 
 let rec aux seq history =
 match seq () with 
 | Seq.Nil -> failwith "Shouldn't be encountered"
 | Seq.Cons (x, _) when Int_set.mem x history -> x 
 | Seq.Cons (x, seq) -> aux seq (Int_set.add x history)
 in
 aux seq Int_set.empty
 in
 let accum_seq seq =
 let rec aux seq sum () =
 match seq () with
 | Seq.Nil as s -> s
 | Seq.Cons (x, seq) -> 
 let sum = sum + x in 
 Seq.Cons (sum, aux seq sum)
 in
 aux seq 0
 in
 input 
 |> List.to_seq 
 |> Seq.cycle 
 |> accum_seq 
 |> first_repeat

While this is longer, we have decomposed the problem into simpler sub-problems, and the part that puts it all together is shorter and more expressive:

 input 
 |> List.to_seq 
 |> Seq.cycle 
 |> accum_seq 
 |> first_repeat

One more thing

We can use first class modules to make find_repeat more generically useful. It's not useful in this case because accum_seq requires an int Seq.t, but if we wanted to use it for other types of sequences it might be.

let main () =
 let first_repeat (type a) (module T : Set.OrderedType with type t = a) seq =
 let module S = Set.Make (T) in
 let rec aux seq history =
 match seq () with 
 | Seq.Nil -> failwith "Shouldn't be encountered"
 | Seq.Cons (x, _) when S.mem x history -> x 
 | Seq.Cons (x, seq) -> aux seq (S.add x history)
 in
 aux seq S.empty
 in
 let accum_seq seq =
 let rec aux seq sum () =
 match seq () with
 | Seq.Nil as s -> s
 | Seq.Cons (x, seq) -> 
 let sum = sum + x in 
 Seq.Cons (sum, aux seq sum)
 in
 aux seq 0
 in
 input 
 |> List.to_seq 
 |> Seq.cycle 
 |> accum_seq 
 |> first_repeat (module Int)

With an additional module signature we could make accum_seq more generically applicable. Also breaking the functions out of main.

module type Addable = sig
 type t
 val zero : t
 val add : t -> t -> t
end
let first_repeat (type a) (module T : Set.OrderedType with type t = a) seq =
 let module S = Set.Make (T) in
 let rec aux seq history =
 match seq () with 
 | Seq.Nil -> failwith "Shouldn't be encountered"
 | Seq.Cons (x, _) when S.mem x history -> x 
 | Seq.Cons (x, seq) -> aux seq (S.add x history)
 in
 aux seq S.empty
let accum_seq (type a) (module T : Addable with type t = a) seq =
 let rec aux seq sum () =
 match seq () with
 | Seq.Nil as s -> s
 | Seq.Cons (x, seq) -> 
 let sum = T.add sum x in 
 Seq.Cons (sum, aux seq sum)
 in
 aux seq T.zero
let main () =
 input 
 |> List.to_seq 
 |> Seq.cycle 
 |> accum_seq (module Int)
 |> first_repeat (module Int)

As a quick demonstration:

# let module S = struct
 type t = string
 let zero = ""
 let add = (^)
 end in
 ["hello"; " "; "world"]
 |> List.to_seq
 |> accum_seq (module S)
 |> List.of_seq;;
- : string list = ["hello"; "hello "; "hello world"]