Discussion on: AoC Day 1: Chronal Calibration

[Ben Lovy]

F# - this is my first brush with F# and .NET in general, so pointers are more'n welcome!

Common code:

let getFrequencies fileName =
  let lines = IO.File.ReadLines(fileName)
  lines
    |> Seq.map Convert.ToInt32
    |> Seq.toList

Part 1:

let rec addFreq acc s =
  match s with
    | [] -> acc
    | freq::freqs -> addFreq (acc + freq) freqs

let day1Part1 fileName =
  getFrequencies fileName |> addFreq 0

part 2:

let rec addFreqWithState acc visited whole remaining =
  match remaining with
    | [] -> addFreqWithState acc visited whole whole
    | head::tail ->
      let newval = acc + head
      if Array.contains newval visited then
        newval
      else
        addFreqWithState newval (Array.append visited [| newval |]) whole tail

let day1Part2 fileName =
  let freqs = getFrequencies fileName
  addFreqWithState 0 [| |] freqs freqs

Entry point:

open System
open Library

[<EntryPoint>]
let main argv =
    day1Part1 argv.[0] |> printfn "Part 1 result: %i"
    day1Part2 argv.[0] |> printfn "Part 2 result: %i"

    0 // return an integer exit code

Part 2 is sloooow. How would you optimize this?

[Ali Spittel]

Nice!! For optimizing part 2, I would use a set! O(1) to check if an item is in it!

[Ben Lovy]

Aha! Thanks so much, it's blazingly fast now:

let rec addFreqWithState acc visited whole remaining =
  match remaining with
    | [] -> addFreqWithState acc visited whole whole
    | head::tail ->
      let newval = acc + head
      if Set.contains newval visited then
        newval
      else
        addFreqWithState newval (Set.add newval visited) whole tail

let day1Part2 fileName =
  let freqs = getFrequencies fileName
  addFreqWithState 0 (new Set<int> (Seq.empty)) freqs freqs

I guess the Tour of F# page shouldn't be my only learning resource :)