Discussion on: AoC Day 5: Alchemical Reduction

View post

...welp, that was a solid "d'oh" moment, opening this thread. Hindsight is 20/20.

Here's the brute force way in F#. I'll have to come back to it after work to implement the smart way.

module util =
  let getInput inputFile =
    System.IO.File.ReadAllText(inputFile)

  let doesReact first second =
    (System.Char.ToUpper first = System.Char.ToUpper second) && first <> second

  let rec reactString altered result input =
    match input with
    | [] -> if altered then reactString false "" (string result |> List.ofSeq) else result
    | [a] -> if altered then reactString false "" (string result + string a |> List.ofSeq) else result + string a
    | head::next::tail ->
      if doesReact head next then
        reactString true result tail
      else
        reactString altered (result + string head) ([next] @ tail)

module part1 =
  open util

  let execute inputFile =
    getInput inputFile
    |> List.ofSeq
    |> reactString false ""
    |> String.length

module part2 =
  open util
  let cleanInput targetPair input =
    List.filter (fun el -> el <> System.Char.ToUpper targetPair && el <> System.Char.ToLower targetPair) input
  let execute inputFile =
     let input = getInput inputFile |> List.ofSeq
     let allPairs = [ for l in 'a' .. 'z' do yield l ]
     let res = List.map (fun el -> (el, reactString false "" (cleanInput el input))) allPairs
     List.sortBy (fun el -> String.length (snd el)) res
     |> List.head
     |> snd
     |> String.length

Ben Lovy • Dec 5 '18 • Edited

Yep, stack-based trick worked just fine:

  let reactQuickly input =
    Seq.fold (fun s c ->
      let last = if Array.length s > 0 then Some (Array.last s) else None
      match last with
      | Some x ->
        if c <> x && (x = System.Char.ToUpper c || x = System.Char.ToLower c) then
          Array.sub s 0 (Array.length s - 1)
        else Array.append s [| c |]
      | None -> Array.append s [| c |]) [| |] input
        |> Array.length

Replacing reactString with reactQuickly was enough to bring the total runtime from several (many) minutes to around 3 seconds.

Using the tip from @choroba and reducing everything first would probably speed it up even more.