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
55
56

namespace Solutions

module 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)