blob: 7e16cb6f01db4c5fd3ba8dbb7b524a304f0f0fdc (
plain)
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
module Day07
open System.IO
open FParsec
let fileSizeThreshold = 100_000
let totalDiskSpace = 70_000_000
let requiredUnusedSpace = 30_000_000
type Node =
| File of int // file size
| Dir of string // dir name
type Command =
| CD of string // dest
| LS of Node list // nodes in current dir
let parseCommands input =
let pcd = pstring "$ cd " >>. restOfLine true |>> CD
let pfile = pint32 .>> pchar ' ' .>> restOfLine true |>> File
let pdir = pstring "dir " >>. restOfLine true |>> Dir
let pnode = pfile <|> pdir
let pls =
pstring "$ ls" >>. skipNewline >>. many pnode
|>> LS
let pcmd = pcd <|> pls
let pinput = many pcmd
Common.parse pinput input
let combine =
function
| (_, "/") -> []
| (_ :: t, "..") -> t
| ([], "..") -> failwith "Can't go above root directory!"
| (path, dest) -> dest :: path
let buildFilesystem commands =
let rec helper path =
function
| (CD dir) :: t -> helper (combine (path, dir)) t
| (LS list) :: t -> (path, list) :: helper path t
| [] -> []
commands |> helper [] |> Map.ofList
let rec directorySize fileSystem path =
fileSystem
|> Map.find path
|> List.sumBy (function
| Dir dir -> directorySize fileSystem <| combine (path, dir)
| File size -> size)
let part1 = Seq.filter ((>=) fileSizeThreshold) >> Seq.sum
let part2 sizes =
let occupiedSpace = Seq.max sizes // root directory size
let unusedSpace = totalDiskSpace - occupiedSpace
let missingSpace = requiredUnusedSpace - unusedSpace
sizes |> Seq.filter ((<=) missingSpace) |> Seq.min
let solution reduceSizes input =
let fileSystem = input |> parseCommands |> buildFilesystem
fileSystem
|> Map.keys
|> Seq.map (directorySize fileSystem)
|> reduceSizes
let test = File.ReadAllText("test.txt")
assert (solution part1 test = 95437)
assert (solution part2 test = 24933642)
let input = File.ReadAllText("input.txt")
printfn "%d" <| solution part1 input
printfn "%d" <| solution part2 input
|
