diff options
Diffstat (limited to 'solutions')
| -rw-r--r-- | solutions/day1.fs | 30 | ||||
| -rw-r--r-- | solutions/day10.fs | 66 | ||||
| -rw-r--r-- | solutions/day11.fs | 198 | ||||
| -rw-r--r-- | solutions/day2.fs | 53 | ||||
| -rw-r--r-- | solutions/day3.fs | 48 | ||||
| -rw-r--r-- | solutions/day4.fs | 56 | ||||
| -rw-r--r-- | solutions/day5.fs | 106 | ||||
| -rw-r--r-- | solutions/day6.fs | 28 | ||||
| -rw-r--r-- | solutions/day7.fs | 110 | ||||
| -rw-r--r-- | solutions/day8.fs | 98 | ||||
| -rw-r--r-- | solutions/day9.fs | 62 |
11 files changed, 417 insertions, 438 deletions
diff --git a/solutions/day1.fs b/solutions/day1.fs index 0b2c519..5561601 100644 --- a/solutions/day1.fs +++ b/solutions/day1.fs @@ -1,19 +1,17 @@ -namespace Solutions +module Solutions.Day1 +open System.IO -module Day1 = - open System.IO +let lines = File.ReadLines("inputs/day1.txt") +let totalWeights = seq { + let mutable subseq = 0 - let lines = File.ReadLines("inputs/day1.txt") - let totalWeights = seq { - let mutable subseq = 0 + for line in lines do + if line.Equals("") then + yield subseq + subseq <- 0 + else + subseq <- subseq + int line +} - for line in lines do - if line.Equals("") then - yield subseq - subseq <- 0 - else - subseq <- subseq + int line - } - - let part1 () = totalWeights |> Seq.max - let part2 () = totalWeights |> Seq.sortDescending |> Seq.take 3 |> Seq.sum +let part1 () = totalWeights |> Seq.max +let part2 () = totalWeights |> Seq.sortDescending |> Seq.take 3 |> Seq.sum diff --git a/solutions/day10.fs b/solutions/day10.fs index 799850d..59ede91 100644 --- a/solutions/day10.fs +++ b/solutions/day10.fs @@ -1,34 +1,32 @@ -namespace Solutions - -module Day10 = - open System.IO - open System.Text.RegularExpressions - - let (|InstRegex|_|) pattern line = - let matched = Regex.Match(line, pattern) - if matched.Success then - matched.Groups |> Seq.tail |> Seq.map (fun x -> x.Value) |> List.ofSeq |> Some - else None - - let parseInst line = - match line with - | InstRegex "noop" [] -> [0] - | InstRegex "addx (-?\d+)" x -> [0; (int x[0])] - | _ -> failwith "invalid input" - - let changes = File.ReadLines("inputs/day10.txt") |> Seq.map parseInst |> List.concat - - let executeInsts changes = - List.scan (+) 1 changes - - let getStateSum cycles (states: int list) = - cycles |> List.map (fun x -> x * states[x-1]) |> List.sum - - let part1 () = executeInsts changes |> getStateSum [20; 60; 100; 140; 180; 220] - - let part2 () = executeInsts changes - |> List.mapi (fun pixel signal -> abs (signal - (pixel % 40)) <= 1) - |> List.map (fun x -> if x then "#" else " ") - |> List.chunkBySize 40 - |> List.map (String.concat "") - |> List.iter (printf "%s\n") \ No newline at end of file +module Solutions.Day10 +open System.IO +open System.Text.RegularExpressions + +let (|InstRegex|_|) pattern line = + let matched = Regex.Match(line, pattern) + if matched.Success then + matched.Groups |> Seq.tail |> Seq.map (fun x -> x.Value) |> List.ofSeq |> Some + else None + +let parseInst line = + match line with + | InstRegex "noop" [] -> [0] + | InstRegex "addx (-?\d+)" x -> [0; (int x[0])] + | _ -> failwith "invalid input" + +let changes = File.ReadLines("inputs/day10.txt") |> Seq.map parseInst |> List.concat + +let executeInsts changes = + List.scan (+) 1 changes + +let getStateSum cycles (states: int list) = + cycles |> List.map (fun x -> x * states[x-1]) |> List.sum + +let part1 () = executeInsts changes |> getStateSum [20; 60; 100; 140; 180; 220] + +let part2 () = executeInsts changes + |> List.mapi (fun pixel signal -> abs (signal - (pixel % 40)) <= 1) + |> List.map (fun x -> if x then "#" else " ") + |> List.chunkBySize 40 + |> List.map (String.concat "") + |> List.iter (printf "%s\n") \ No newline at end of file diff --git a/solutions/day11.fs b/solutions/day11.fs index 2b93042..d9a9d17 100644 --- a/solutions/day11.fs +++ b/solutions/day11.fs @@ -1,108 +1,106 @@ -namespace Solutions +module Solutions.Day11 +type Monkey = { + Items: int64 list + Operation: int64 -> int64 + Test: int64 + TrueMonkey: int + FalseMonkey: int + Inspections: int64 +} -module Day11 = - type Monkey = { - Items: int64 list - Operation: int64 -> int64 - Test: int64 - TrueMonkey: int - FalseMonkey: int - Inspections: int64 - } +let monkeys = + [ { Items = [89; 95; 92; 64; 87; 68] + Operation = (*) 11L + Test = 2 + TrueMonkey = 7 + FalseMonkey = 4 + Inspections = 0 } + { Items = [87; 67] + Operation = (+) 1L; + Test = 13; + TrueMonkey = 3 + FalseMonkey = 6 + Inspections = 0 } + { Items = [95; 79; 92; 82; 60] + Operation = (+) 6L + Test = 3 + TrueMonkey = 1 + FalseMonkey = 6 + Inspections = 0 } + { Items = [67; 97; 56] + Operation = fun x -> x * x + Test = 17 + TrueMonkey = 7 + FalseMonkey = 0 + Inspections = 0 } + { Items = [80; 68; 87; 94; 61; 59; 50; 68] + Operation = (*) 7L + Test = 19 + TrueMonkey = 5 + FalseMonkey = 2 + Inspections = 0 } + { Items = [73; 51; 76; 59] + Operation = (+) 8L + Test = 7 + TrueMonkey = 2 + FalseMonkey = 1 + Inspections = 0 } + { Items = [92] + Operation = (+) 5L + Test = 11 + TrueMonkey = 3 + FalseMonkey = 0 + Inspections = 0 } + { Items = [99; 76; 78; 76; 79; 90; 89] + Operation = (+) 7L + Test = 5 + TrueMonkey = 4 + FalseMonkey = 5 + Inspections = 0 } ] - let monkeys = - [ { Items = [89; 95; 92; 64; 87; 68] - Operation = (*) 11L - Test = 2 - TrueMonkey = 7 - FalseMonkey = 4 - Inspections = 0 } - { Items = [87; 67] - Operation = (+) 1L; - Test = 13; - TrueMonkey = 3 - FalseMonkey = 6 - Inspections = 0 } - { Items = [95; 79; 92; 82; 60] - Operation = (+) 6L - Test = 3 - TrueMonkey = 1 - FalseMonkey = 6 - Inspections = 0 } - { Items = [67; 97; 56] - Operation = fun x -> x * x - Test = 17 - TrueMonkey = 7 - FalseMonkey = 0 - Inspections = 0 } - { Items = [80; 68; 87; 94; 61; 59; 50; 68] - Operation = (*) 7L - Test = 19 - TrueMonkey = 5 - FalseMonkey = 2 - Inspections = 0 } - { Items = [73; 51; 76; 59] - Operation = (+) 8L - Test = 7 - TrueMonkey = 2 - FalseMonkey = 1 - Inspections = 0 } - { Items = [92] - Operation = (+) 5L - Test = 11 - TrueMonkey = 3 - FalseMonkey = 0 - Inspections = 0 } - { Items = [99; 76; 78; 76; 79; 90; 89] - Operation = (+) 7L - Test = 5 - TrueMonkey = 4 - FalseMonkey = 5 - Inspections = 0 } ] +let throw item target monkeys = + let monkey = List.item target monkeys - let throw item target monkeys = - let monkey = List.item target monkeys - - List.updateAt target {monkey with Items = (List.append monkey.Items [item])} monkeys + List.updateAt target {monkey with Items = (List.append monkey.Items [item])} monkeys - let doItem operation monkey monkeys item = - let worryLevel = monkey.Operation item - let boredLevel = operation worryLevel - let target = if boredLevel % monkey.Test = 0L then monkey.TrueMonkey else monkey.FalseMonkey - throw boredLevel target monkeys - - let playTurn operation monkeys id = - let monkey = List.item id monkeys +let doItem operation monkey monkeys item = + let worryLevel = monkey.Operation item + let boredLevel = operation worryLevel + let target = if boredLevel % monkey.Test = 0L then monkey.TrueMonkey else monkey.FalseMonkey + throw boredLevel target monkeys - let cleared = monkeys - |> List.updateAt - id - {monkey with Items = [] - Inspections = monkey.Inspections + (int64 monkey.Items.Length)} - - monkey.Items |> List.fold (doItem operation monkey) cleared - - let playRound operation monkeys = - let players = [ 0 .. (List.length monkeys - 1)] - List.fold (playTurn operation) monkeys players +let playTurn operation monkeys id = + let monkey = List.item id monkeys + + let cleared = monkeys + |> List.updateAt + id + {monkey with Items = [] + Inspections = monkey.Inspections + (int64 monkey.Items.Length)} - let rec playRounds operation nb monkeys = - if nb = 0 then monkeys - else - let next = playRound operation monkeys - playRounds operation (nb - 1) next + monkey.Items |> List.fold (doItem operation monkey) cleared - let solve operation count = - monkeys - |> playRounds operation count - |> List.map (fun m -> m.Inspections) - |> List.sortDescending - |> List.take 2 - |> List.reduce (*) +let playRound operation monkeys = + let players = [ 0 .. (List.length monkeys - 1)] + List.fold (playTurn operation) monkeys players - let part1 () = - solve (fun x -> x / 3L) 20 - - let part2 () = - let safeMod = monkeys |> Seq.map (fun m -> m.Test) |> Seq.reduce (*) - solve (fun x -> x % safeMod) 10_000 +let rec playRounds operation nb monkeys = + if nb = 0 then monkeys + else + let next = playRound operation monkeys + playRounds operation (nb - 1) next + +let solve operation count = + monkeys + |> playRounds operation count + |> List.map (fun m -> m.Inspections) + |> List.sortDescending + |> List.take 2 + |> List.reduce (*) + +let part1 () = + solve (fun x -> x / 3L) 20 + +let part2 () = + let safeMod = monkeys |> Seq.map (fun m -> m.Test) |> Seq.reduce (*) + solve (fun x -> x % safeMod) 10_000 diff --git a/solutions/day2.fs b/solutions/day2.fs index 5822d00..5ae5552 100644 --- a/solutions/day2.fs +++ b/solutions/day2.fs @@ -1,31 +1,30 @@ -namespace Solutions +module Solutions.Day2 +open System.IO -module Day2 = - open System.IO - let lines = File.ReadLines("inputs/day2.txt") |> Seq.map (fun x -> x[0], x[2]) +let lines = File.ReadLines("inputs/day2.txt") |> Seq.map (fun x -> x[0], x[2]) - let outcomes1 = Map.empty - .Add(('A', 'X'), 4) // rock: 1 + tie: 3 - .Add(('A', 'Y'), 8) // paper: 2 + rock win: 6 - .Add(('A', 'Z'), 3) // scissors: 3 + rock lose: 0 - .Add(('B', 'X'), 1) // rock: 1 + paper lose: 0 - .Add(('B', 'Y'), 5) // paper: 2 + tie: 3 - .Add(('B', 'Z'), 9) // scissors: 3 + paper win: 6 - .Add(('C', 'X'), 7) // rock: 1 + scissors win: 6 - .Add(('C', 'Y'), 2) // paper: 2 + scissors lose: 0 - .Add(('C', 'Z'), 6) // scissors: 3 + tie: 3 +let outcomes1 = Map.empty + .Add(('A', 'X'), 4) // rock: 1 + tie: 3 + .Add(('A', 'Y'), 8) // paper: 2 + rock win: 6 + .Add(('A', 'Z'), 3) // scissors: 3 + rock lose: 0 + .Add(('B', 'X'), 1) // rock: 1 + paper lose: 0 + .Add(('B', 'Y'), 5) // paper: 2 + tie: 3 + .Add(('B', 'Z'), 9) // scissors: 3 + paper win: 6 + .Add(('C', 'X'), 7) // rock: 1 + scissors win: 6 + .Add(('C', 'Y'), 2) // paper: 2 + scissors lose: 0 + .Add(('C', 'Z'), 6) // scissors: 3 + tie: 3 - let part1 () = lines |> Seq.map outcomes1.TryFind |> Seq.map (function | Some value -> value | None -> 0) |> Seq.sum +let part1 () = lines |> Seq.map outcomes1.TryFind |> Seq.map (function | Some value -> value | None -> 0) |> Seq.sum - let outcomes2 = Map.empty - .Add(('A', 'X'), 3) // lose to rock: 0 pts + 3 for scissors - .Add(('A', 'Y'), 4) // draw to rock: 3 pts + 1 for rock - .Add(('A', 'Z'), 8) // win to rock: 6 pts + 2 for paper - .Add(('B', 'X'), 1) // lose to paper: 0 pts + 1 for rock - .Add(('B', 'Y'), 5) // draw to paper: 3 pts + 2 for paper - .Add(('B', 'Z'), 9) // win to paper: 6 pts + 3 for scissors - .Add(('C', 'X'), 2) // lose to scissors: 0 pts + 2 for paper - .Add(('C', 'Y'), 6) // draw to scissors: 3 pts + 3 for scissors - .Add(('C', 'Z'), 7) // win to scissors: 6 pts + 1 for rock - - let part2 () = lines |> Seq.map outcomes2.TryFind |> Seq.map (function | Some value -> value | None -> 0) |> Seq.sum +let outcomes2 = Map.empty + .Add(('A', 'X'), 3) // lose to rock: 0 pts + 3 for scissors + .Add(('A', 'Y'), 4) // draw to rock: 3 pts + 1 for rock + .Add(('A', 'Z'), 8) // win to rock: 6 pts + 2 for paper + .Add(('B', 'X'), 1) // lose to paper: 0 pts + 1 for rock + .Add(('B', 'Y'), 5) // draw to paper: 3 pts + 2 for paper + .Add(('B', 'Z'), 9) // win to paper: 6 pts + 3 for scissors + .Add(('C', 'X'), 2) // lose to scissors: 0 pts + 2 for paper + .Add(('C', 'Y'), 6) // draw to scissors: 3 pts + 3 for scissors + .Add(('C', 'Z'), 7) // win to scissors: 6 pts + 1 for rock + +let part2 () = lines |> Seq.map outcomes2.TryFind |> Seq.map (function | Some value -> value | None -> 0) |> Seq.sum diff --git a/solutions/day3.fs b/solutions/day3.fs index cebfde5..541a0b4 100644 --- a/solutions/day3.fs +++ b/solutions/day3.fs @@ -1,26 +1,24 @@ -namespace Solutions +module Solutions.Day3 +open System.IO -module Day3 = - open System.IO - - let lines = File.ReadLines("inputs/day3.txt") - let rucksacks = lines - |> Seq.map (fun x -> (Set.ofSeq x[0..x.Length / 2 - 1], Set.ofSeq x[x.Length/2..x.Length])) - let groups = lines - |> Seq.map Set.ofSeq - |> Seq.splitInto (Seq.length lines / 3) - - let prioritize ch = - match ch with - | x when 'a' <= x && x <= 'z' -> int x - int 'a' + 1 - | x when 'A' <= x && x <= 'Z' -> int x - int 'A' + 27 - | _ -> 0 - - // extract the single element from the set with maxElement - let part1 () = rucksacks - |> Seq.map ((fun (x, y) -> Set.intersect x y |> Set.maxElement) >> prioritize) - |> Seq.sum - - let part2 () = groups - |> Seq.map (Set.intersectMany >> Set.maxElement >> prioritize) - |> Seq.sum \ No newline at end of file +let lines = File.ReadLines("inputs/day3.txt") +let rucksacks = lines + |> Seq.map (fun x -> (Set.ofSeq x[0..x.Length / 2 - 1], Set.ofSeq x[x.Length/2..x.Length])) +let groups = lines + |> Seq.map Set.ofSeq + |> Seq.splitInto (Seq.length lines / 3) + +let prioritize ch = + match ch with + | x when 'a' <= x && x <= 'z' -> int x - int 'a' + 1 + | x when 'A' <= x && x <= 'Z' -> int x - int 'A' + 27 + | _ -> 0 + +// extract the single element from the set with maxElement +let part1 () = rucksacks + |> Seq.map ((fun (x, y) -> Set.intersect x y |> Set.maxElement) >> prioritize) + |> Seq.sum + +let part2 () = groups + |> Seq.map (Set.intersectMany >> Set.maxElement >> prioritize) + |> Seq.sum \ No newline at end of file diff --git a/solutions/day4.fs b/solutions/day4.fs index beb0515..82b523c 100644 --- a/solutions/day4.fs +++ b/solutions/day4.fs @@ -1,35 +1,33 @@ -namespace Solutions +module Solutions.Day4 +open System.IO +open System.Text.RegularExpressions -module Day4 = - open System.IO - open System.Text.RegularExpressions +type range = { + startID: int; + endID: int +} - type range = { - startID: int; - endID: int - } +let getRanges input = + let matches = Regex.Matches(input, "(\d+)-(\d+),(\d+)-(\d+)") + |> Seq.head + |> fun x -> x.Groups + |> Seq.map (fun x -> x.Value) + |> List.ofSeq + |> List.tail + assert (Seq.length matches = 4) + {startID = int matches[0]; endID = int matches[1]}, {startID = int matches[2]; endID = int matches[3]} + +let ranges = File.ReadLines("inputs/day4.txt") |> Seq.map getRanges - let getRanges input = - let matches = Regex.Matches(input, "(\d+)-(\d+),(\d+)-(\d+)") - |> Seq.head - |> fun x -> x.Groups - |> Seq.map (fun x -> x.Value) - |> List.ofSeq - |> List.tail - assert (Seq.length matches = 4) - {startID = int matches[0]; endID = int matches[1]}, {startID = int matches[2]; endID = int matches[3]} - - let ranges = File.ReadLines("inputs/day4.txt") |> Seq.map getRanges +let contains (rangeA, rangeB) = + (rangeA.startID <= rangeB.startID && rangeA.endID >= rangeB.endID) || (rangeA.startID >= rangeB.startID && rangeA.endID <= rangeB.endID) - let contains (rangeA, rangeB) = - (rangeA.startID <= rangeB.startID && rangeA.endID >= rangeB.endID) || (rangeA.startID >= rangeB.startID && rangeA.endID <= rangeB.endID) +let part1 () = ranges |> Seq.filter contains |> Seq.length - let part1 () = ranges |> Seq.filter contains |> Seq.length +let overlaps (rangeA, rangeB) = + (rangeA.startID >= rangeB.startID && rangeA.startID <= rangeB.endID) || + (rangeA.endID >= rangeB.startID && rangeA.endID <= rangeB.endID) || + (rangeB.startID >= rangeA.startID && rangeB.startID <= rangeA.endID) || + (rangeB.endID >= rangeA.startID && rangeB.endID <= rangeA.endID) - let overlaps (rangeA, rangeB) = - (rangeA.startID >= rangeB.startID && rangeA.startID <= rangeB.endID) || - (rangeA.endID >= rangeB.startID && rangeA.endID <= rangeB.endID) || - (rangeB.startID >= rangeA.startID && rangeB.startID <= rangeA.endID) || - (rangeB.endID >= rangeA.startID && rangeB.endID <= rangeA.endID) - - let part2 () = ranges |> Seq.filter overlaps |> Seq.length \ No newline at end of file +let part2 () = ranges |> Seq.filter overlaps |> Seq.length \ No newline at end of file diff --git a/solutions/day5.fs b/solutions/day5.fs index 6c8bce3..2355e00 100644 --- a/solutions/day5.fs +++ b/solutions/day5.fs @@ -1,61 +1,59 @@ -namespace Solutions +module Solutions.Day5 +open System.IO +open System.Text.RegularExpressions -module Day5 = - open System.IO - open System.Text.RegularExpressions +// forgive me lord for what i'm about to do +// too lazy to figure out how to parse initial state so hardcoding instead +let initState = [| + ['D'; 'T'; 'W'; 'N'; 'L']; + ['H'; 'P'; 'C']; + ['J'; 'M'; 'G'; 'D'; 'N'; 'H'; 'P'; 'W']; + ['L'; 'Q'; 'T'; 'N'; 'S'; 'W'; 'C']; + ['N'; 'C'; 'H'; 'P']; + ['B'; 'Q'; 'W'; 'M'; 'D'; 'N'; 'H'; 'T']; + ['L'; 'S'; 'G'; 'J'; 'R'; 'B'; 'M']; + ['T'; 'R'; 'B'; 'V'; 'G'; 'W'; 'N'; 'Z']; + ['L'; 'P'; 'N'; 'D'; 'G'; 'W'] + |] - // forgive me lord for what i'm about to do - // too lazy to figure out how to parse initial state so hardcoding instead - let initState = [| - ['D'; 'T'; 'W'; 'N'; 'L']; - ['H'; 'P'; 'C']; - ['J'; 'M'; 'G'; 'D'; 'N'; 'H'; 'P'; 'W']; - ['L'; 'Q'; 'T'; 'N'; 'S'; 'W'; 'C']; - ['N'; 'C'; 'H'; 'P']; - ['B'; 'Q'; 'W'; 'M'; 'D'; 'N'; 'H'; 'T']; - ['L'; 'S'; 'G'; 'J'; 'R'; 'B'; 'M']; - ['T'; 'R'; 'B'; 'V'; 'G'; 'W'; 'N'; 'Z']; - ['L'; 'P'; 'N'; 'D'; 'G'; 'W'] - |] +type instruction = { + amount: int; + source: int; + target: int +} - type instruction = { - amount: int; - source: int; - target: int - } +let getInstruction inst = + let matches = Regex.Matches(inst, "move (\d+) from (\d+) to (\d+)") + |> Seq.head + |> fun x -> x.Groups + |> List.ofSeq |> List.tail + |> List.map (fun x -> int x.Value) + assert (List.length matches = 3) + {amount = matches[0]; source = matches[1] - 1; target = matches[2] - 1} - let getInstruction inst = - let matches = Regex.Matches(inst, "move (\d+) from (\d+) to (\d+)") - |> Seq.head - |> fun x -> x.Groups - |> List.ofSeq |> List.tail - |> List.map (fun x -> int x.Value) - assert (List.length matches = 3) - {amount = matches[0]; source = matches[1] - 1; target = matches[2] - 1} - - let instructions = File.ReadLines("inputs/day5.txt") - |> Array.ofSeq - |> fun x -> Array.splitAt (Array.findIndex ((=) "") x) x - |> snd |> Array.tail |> Array.map getInstruction +let instructions = File.ReadLines("inputs/day5.txt") + |> Array.ofSeq + |> fun x -> Array.splitAt (Array.findIndex ((=) "") x) x + |> snd |> Array.tail |> Array.map getInstruction - let executeInstruction1 (state: list<char>[]) inst = - for _ in 1..inst.amount do - match state[inst.source] with - | top::bottom -> - state[inst.source] <- bottom - state[inst.target] <- top::state[inst.target] - | _ -> failwith "this shouldn't happen" +let executeInstruction1 (state: list<char>[]) inst = + for _ in 1..inst.amount do + match state[inst.source] with + | top::bottom -> + state[inst.source] <- bottom + state[inst.target] <- top::state[inst.target] + | _ -> failwith "this shouldn't happen" - let part1 () = - let mutable currentState = initState - Array.iter (executeInstruction1 currentState) instructions - Array.map (List.head >> string) currentState |> String.concat "" +let part1 () = + let mutable currentState = initState + Array.iter (executeInstruction1 currentState) instructions + Array.map (List.head >> string) currentState |> String.concat "" - let executeInstruction2 (state: char [] []) inst = - state[inst.target] <- Array.append state[inst.source].[..inst.amount-1] state[inst.target] - state[inst.source] <- state[inst.source][inst.amount..] - - let part2 () = - let mutable currentState = initState |> Array.map Array.ofList - Array.iter (executeInstruction2 currentState) instructions - Array.map (Array.head >> string) currentState |> String.concat "" \ No newline at end of file +let executeInstruction2 (state: char [] []) inst = + state[inst.target] <- Array.append state[inst.source].[..inst.amount-1] state[inst.target] + state[inst.source] <- state[inst.source][inst.amount..] + +let part2 () = + let mutable currentState = initState |> Array.map Array.ofList + Array.iter (executeInstruction2 currentState) instructions + Array.map (Array.head >> string) currentState |> String.concat "" \ No newline at end of file diff --git a/solutions/day6.fs b/solutions/day6.fs index bb83388..fb2d451 100644 --- a/solutions/day6.fs +++ b/solutions/day6.fs @@ -1,20 +1,18 @@ -namespace Solutions +module Solutions.Day6 +open System.IO -module Day6 = - open System.IO +let buf = File.ReadAllText("inputs/day6.txt") - let buf = File.ReadAllText("inputs/day6.txt") - - let rec scan size str index = - if String.length str < size then -1 +let rec scan size str index = + if String.length str < size then -1 + else + let current = str[..size - 1] |> Set.ofSeq + if Set.count current = size then index + size else - let current = str[..size - 1] |> Set.ofSeq - if Set.count current = size then index + size - else - scan size str[1..] index + 1 + scan size str[1..] index + 1 - let part1 () = - scan 4 buf 0 +let part1 () = + scan 4 buf 0 - let part2 () = - scan 14 buf 0 \ No newline at end of file +let part2 () = + scan 14 buf 0 \ No newline at end of file diff --git a/solutions/day7.fs b/solutions/day7.fs index 622c54c..5f507c4 100644 --- a/solutions/day7.fs +++ b/solutions/day7.fs @@ -1,56 +1,54 @@ -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) \ No newline at end of file +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) \ No newline at end of file diff --git a/solutions/day8.fs b/solutions/day8.fs index 757cb74..8978700 100644 --- a/solutions/day8.fs +++ b/solutions/day8.fs @@ -1,53 +1,51 @@ -namespace Solutions +module Solutions.Day8 +open System.IO -module Day8 = - open System.IO +let input = File.ReadLines("inputs/day8.txt") |> Array.ofSeq |> Array.map (Array.ofSeq >> Array.map (fun x -> int x - int '0')) |> array2D - let input = File.ReadLines("inputs/day8.txt") |> Array.ofSeq |> Array.map (Array.ofSeq >> Array.map (fun x -> int x - int '0')) |> array2D - - let rec countVisible line index indices max = - if line = [||] then indices +let rec countVisible line index indices max = + if line = [||] then indices + else + let current = Array.head line + if current > max then + countVisible (Array.tail line) (index + 1) (Set.add index indices) current else - let current = Array.head line - if current > max then - countVisible (Array.tail line) (index + 1) (Set.add index indices) current - else - countVisible (Array.tail line) (index + 1) indices max - - let countBidirectional goHorizontal index line = - let dirSet dir = - countVisible (Array.tail dir) 1 (Set.singleton 0) (Array.head dir) - let forwards = dirSet line - let backwards = dirSet (Array.rev line) |> Set.map (fun x -> Array.length line - 1 - x) - Set.union forwards backwards |> Set.map(fun x -> if goHorizontal then (index, x) else (x, index)) - - let countGridVisible grid = - let rows, cols = Array2D.length1 grid, Array2D.length2 grid - let rowSet = seq { for x in 0..rows - 1 -> x } |> Seq.map (fun x -> grid[x, *] |> countBidirectional true x) |> Set.unionMany - let colSet = seq { for y in 0..cols - 1 -> y } |> Seq.map (fun y -> grid[*, y] |> countBidirectional false y) |> Set.unionMany - Set.union rowSet colSet |> Set.count - - let part1 () = countGridVisible input - - let getViewingDistance index (line: int array) = - let before, after = Array.rev line[..index - 1], line[index + 1..] - let getDistance height trees = - try - 1 + Array.findIndex (fun x -> x >= height) trees - with - | :? System.Collections.Generic.KeyNotFoundException -> Array.length trees - | :? System.ArgumentNullException -> failwith "should never happen" - - getDistance line[index] before * getDistance line[index] after - - let getScore (grid: int[,]) (x, y) = - let row, col = grid[x, *], grid[*, y] - let hScore = getViewingDistance y row - let vScore = getViewingDistance x col - hScore * vScore - - let part2 () = - seq {for x in 0..Array2D.length1 input - 1 do - for y in 0..Array2D.length2 input - 1 -> (x, y)} - |> Seq.map (getScore input) - |> Seq.max \ No newline at end of file + countVisible (Array.tail line) (index + 1) indices max + +let countBidirectional goHorizontal index line = + let dirSet dir = + countVisible (Array.tail dir) 1 (Set.singleton 0) (Array.head dir) + let forwards = dirSet line + let backwards = dirSet (Array.rev line) |> Set.map (fun x -> Array.length line - 1 - x) + Set.union forwards backwards |> Set.map(fun x -> if goHorizontal then (index, x) else (x, index)) + +let countGridVisible grid = + let rows, cols = Array2D.length1 grid, Array2D.length2 grid + let rowSet = seq { for x in 0..rows - 1 -> x } |> Seq.map (fun x -> grid[x, *] |> countBidirectional true x) |> Set.unionMany + let colSet = seq { for y in 0..cols - 1 -> y } |> Seq.map (fun y -> grid[*, y] |> countBidirectional false y) |> Set.unionMany + Set.union rowSet colSet |> Set.count + +let part1 () = countGridVisible input + +let getViewingDistance index (line: int array) = + let before, after = Array.rev line[..index - 1], line[index + 1..] + let getDistance height trees = + try + 1 + Array.findIndex (fun x -> x >= height) trees + with + | :? System.Collections.Generic.KeyNotFoundException -> Array.length trees + | :? System.ArgumentNullException -> failwith "should never happen" + + getDistance line[index] before * getDistance line[index] after + +let getScore (grid: int[,]) (x, y) = + let row, col = grid[x, *], grid[*, y] + let hScore = getViewingDistance y row + let vScore = getViewingDistance x col + hScore * vScore + +let part2 () = + seq {for x in 0..Array2D.length1 input - 1 do + for y in 0..Array2D.length2 input - 1 -> (x, y)} + |> Seq.map (getScore input) + |> Seq.max \ No newline at end of file diff --git a/solutions/day9.fs b/solutions/day9.fs index 9c1407f..b681266 100644 --- a/solutions/day9.fs +++ b/solutions/day9.fs @@ -1,39 +1,37 @@ -namespace Solutions +module Solutions.Day9 +open System.IO +open System.Text.RegularExpressions +open FSharpPlus.Operators -module Day9 = - open System.IO - open System.Text.RegularExpressions - open FSharpPlus.Operators +let parseInstruction line = + let groups = Regex.Match(line, "([LRUD]) (\d+)").Groups + |> Seq.map (fun x -> x.Value) + |> Array.ofSeq + match groups[1], groups[2] with + | "L", count -> List.replicate (int count) (-1, 0) + | "R", count -> List.replicate (int count) (1, 0) + | "U", count -> List.replicate (int count) (0, 1) + | "D", count -> List.replicate (int count) (0, -1) + | _ -> failwith "invalid input" - let parseInstruction line = - let groups = Regex.Match(line, "([LRUD]) (\d+)").Groups - |> Seq.map (fun x -> x.Value) - |> Array.ofSeq - match groups[1], groups[2] with - | "L", count -> List.replicate (int count) (-1, 0) - | "R", count -> List.replicate (int count) (1, 0) - | "U", count -> List.replicate (int count) (0, 1) - | "D", count -> List.replicate (int count) (0, -1) - | _ -> failwith "invalid input" +let headPositions steps = List.scan (fun (x1, y1) (x2, y2) -> (x1 + x2, y1 + y2)) (0, 0) steps +let instructions = File.ReadLines("inputs/day9.txt") |> Seq.map parseInstruction |> Seq.concat |> List.ofSeq |> headPositions - let headPositions steps = List.scan (fun (x1, y1) (x2, y2) -> (x1 + x2, y1 + y2)) (0, 0) steps - let instructions = File.ReadLines("inputs/day9.txt") |> Seq.map parseInstruction |> Seq.concat |> List.ofSeq |> headPositions +let rec followPath (rope: list<int * int>) (tailSet: Set<int*int>) (heads: list<int*int>) = + let touches pointA pointB = abs (fst pointA - fst pointB) <= 1 && abs (snd pointA - snd pointB) <= 1 + let moveTowards head tail = (fst tail + signum (fst head - fst tail), snd tail + signum (snd head - snd tail)) - let rec followPath (rope: list<int * int>) (tailSet: Set<int*int>) (heads: list<int*int>) = - let touches pointA pointB = abs (fst pointA - fst pointB) <= 1 && abs (snd pointA - snd pointB) <= 1 - let moveTowards head tail = (fst tail + signum (fst head - fst tail), snd tail + signum (snd head - snd tail)) + if List.length heads = 0 then Set.count tailSet + else + let newHead = List.head heads + let newRope = List.scan (fun head tail -> if touches head tail then tail else moveTowards head tail) newHead (List.tail rope) + followPath newRope (Set.add (List.last newRope) tailSet) (List.tail heads) - if List.length heads = 0 then Set.count tailSet - else - let newHead = List.head heads - let newRope = List.scan (fun head tail -> if touches head tail then tail else moveTowards head tail) newHead (List.tail rope) - followPath newRope (Set.add (List.last newRope) tailSet) (List.tail heads) - - let solution ropeSize = - followPath (List.replicate ropeSize (0, 0)) Set.empty +let solution ropeSize = + followPath (List.replicate ropeSize (0, 0)) Set.empty - let part1 () = instructions - |> solution 2 +let part1 () = instructions + |> solution 2 - let part2 () = instructions - |> solution 10 \ No newline at end of file +let part2 () = instructions + |> solution 10 \ No newline at end of file |