solutions/day7.fs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

module Solutions.Day7
open System.IO
open System.Text.RegularExpressions

type Listing =
| LS
| CD of target: string
| Dir of name: string
| File of name: string * size: int

let (|RegexMatch|_|) pattern line =
    let matched = Regex.Match(line, pattern)
    if matched.Success then
        let groups =
            matched.Groups |> Seq.map (fun x -> x.Value) |> Seq.tail |> List.ofSeq
        Some groups
    else None

let parseListing = function
| RegexMatch "\$ cd (\/|\S+)" args -> CD args[0]
| RegexMatch "\$ ls" [] -> LS
| RegexMatch "dir (\S+)" name -> Dir name[0]
| RegexMatch "(\d+) (\S+)" data -> File (data[1], int data[0])
| _ -> failwith "shouldn't happen"

let input = File.ReadLines("inputs/day7.txt") |> Seq.map parseListing |> List.ofSeq


let dirSizes listings = 
    let processListing (pwd, tree) listing =
        match listing with 
        | CD ".." -> (List.tail pwd, tree)
        | CD target -> (target::pwd, tree)
        | File (name, size) -> 
            let rec addFileSize rem dirs =
                match rem with
                | [] -> dirs
                | _ :: t ->
                    let addIfExists current = defaultArg current 0 + size
                    let newDirs = Map.change rem (addIfExists >> Some) dirs
                    addFileSize t newDirs
            pwd, addFileSize pwd tree
        | _ -> pwd, tree
    listings |> List.fold processListing ([], Map.empty) |> snd

let part1 () = dirSizes input |> Map.values |> Seq.filter (fun size -> size <= 100000) |> Seq.sum

let part2 () = 
    let sizes = dirSizes input
    let totalSpace = 70000000
    let targetSpace = 30000000
    let usedSpace = sizes[[ "/" ]]
    let needToFree = usedSpace - (totalSpace - targetSpace)
    sizes.Values |> Seq.sort |> Seq.find (fun x -> x >= needToFree)