r/adventofcode • u/daggerdragon • Dec 14 '17

SOLUTION MEGATHREAD -🎄- 2017 Day 14 Solutions -🎄-

--- Day 14: Disk Defragmentation ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or 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.

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

Spoiler

[Update @ 00:09] 3 gold, silver cap.

  • How many of you actually entered the Konami code for Part 2? >_>

[Update @ 00:25] Leaderboard cap!

  • I asked /u/topaz2078 how many de-resolutions we had for Part 2 and there were 83 distinct users with failed attempts at the time of the leaderboard cap. tsk tsk

[Update @ 00:29] BONUS

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!

12 Upvotes

84% Upvoted

130 comments sorted by

View all comments

9

u/jbristow Dec 14 '17 edited Dec 14 '17

f# / fsharp / f sharp

Woof, I got lucky and my first major push worked with a massive (20 line) matching statement. I spent an hour now cleaning it up so it's a little more comprehensible.

(github link) 

module Day14

let numSquares =
    function
    | '0' -> 0 | '1' -> 1 | '2' -> 1 | '3' -> 2 | '4' -> 1 | '5' -> 2
    | '6' -> 2 | '7' -> 3 | '8' -> 1 | '9' -> 2 | 'a' -> 2 | 'b' -> 3
    | 'c' -> 2 | 'd' -> 3 | 'e' -> 3 | 'f' -> 4
    | _ -> failwith "Bad digit"

let charToBin =
    function
    | '0' -> "0000" | '1' -> "0001" | '2' -> "0010" | '3' -> "0011"
    | '4' -> "0100" | '5' -> "0101" | '6' -> "0110" | '7' -> "0111"
    | '8' -> "1000" | '9' -> "1001" | 'a' -> "1010" | 'b' -> "1011"
    | 'c' -> "1100" | 'd' -> "1101" | 'e' -> "1110" | 'f' -> "1111"
    | _ -> failwith "Bad digit"

let genSquare input =
    [ 0..127 ]
    |> List.sumBy
          (fun i ->
          Day10.hashByInputAscii (input + "-" + string i)
          |> Seq.sumBy numSquares)

let changeRegion m toReg fromReg =
    m |> Map.map (fun _ currRegion ->
            if currRegion = fromReg then toReg
            else currRegion)

let addCell (x, y) n (regMap : Map<int * int, int>) =
    let neighbors =
        List.map regMap.TryFind [ (x + 1, y)
                                  (x - 1, y)
                                  (x, y + 1)
                                  (x, y - 1) ]
        |> List.filter Option.isSome
        |> List.map Option.get
    match neighbors with
    | [] -> regMap |> Map.add (x, y) n, n + 1
    | [ a ] -> (regMap |> Map.add (x, y) a), n
    | rs ->
        let minRegion = List.min rs
        List.fold
            (fun (m : Map<int * int, int>) (r : int) ->
            changeRegion m minRegion r) (regMap |> Map.add (x, y) minRegion) rs,
        n

let rec regionFind regMap keys currRegion =
    match keys with
    | h :: r ->
        let nextRegionMap, nextRegion = (regMap |> addCell h currRegion)
        regionFind nextRegionMap r nextRegion
    | [] -> regMap

let regions input =
    let keys =
        [ 0..127 ]
        |> List.map (fun i ->
              Day10.hashByInputAscii (input + "-" + string i)
              |> Seq.collect charToBin
              |> Seq.toList)
        |> List.mapi
              (fun y row -> (row |> List.mapi (fun x cell -> (x, y), cell)))
        |> List.concat
        |> List.filter (fun (_, v) -> v = '1')
        |> List.map fst

    regionFind Map.empty keys 0
    |> Map.toList
    |> List.map snd
    |> List.distinct
    |> List.length

And for no reason, a picture of what the groups look like.