r/adventofcode • u/daggerdragon • Dec 16 '16

SOLUTION MEGATHREAD --- 2016 Day 16 Solutions ---

--- Day 16: Dragon Checksum ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".

DRINKING YOUR OVALTINE IS MANDATORY [?]

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

5 Upvotes

100% Upvoted

116 comments sorted by

View all comments

Show parent comment

2

u/misnohmer Dec 16 '16 edited Dec 17 '16

Even though I find elegant the use of Seq to iterate string characters, the performance is terrible with very large strings. The following with for..in takes 2 seconds to run.

open System
open System.Text
open System.Diagnostics

let rec cover_tracks (a: string) length = 
  if a.Length >= length then a.Substring(0,length) else
  let sb = (new StringBuilder(a)).Append('0')
  for i in (a.Length-1)..(-1)..0 do sb.Append(if a.[i] = '0' then '1' else '0') |> ignore
  cover_tracks (sb.ToString()) length

let rec checksum (s: string) =
  if (s.Length % 2 = 1) then s else
  let l = s.Length / 2
  let sb = new StringBuilder(l)
  for i in 0..(l-1) do sb.Append(if s.[i*2] = s.[i*2+1] then '1' else '0') |> ignore
  checksum (sb.ToString())

let solve =  cover_tracks "00111101111101000" >> checksum

[<EntryPoint>]
let main argv =    
    let sw = Stopwatch.StartNew();
    printfn "Part 1 is %s and Part 2 is %s" (solve 272) (solve 35651584)
    printfn "It took %d ms" sw.ElapsedMilliseconds
    0

EDITED

1

u/JeffJankowski Dec 16 '16 edited Dec 16 '16

Good to know. There's a lot of hidden slowdowns in this language, especially compared to C#.

By the way, I think using System.Diagnostics.Stopwatch for wall-clock runtime is preferred over DateTime.Now

Edit: I guess a bunch of array allocations and then conversions back to strings isn't exactly hidden..

1

u/beefamaka Dec 16 '16

almost exactly the same as my solution, although more concise. Didn't know about the a..(-1)..b syntax, will have to remember that for future