diff options
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Common/Util.fs | 18 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Common/Vec2.fs | 20 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day04/Program.fs | 4 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day05/Program.fs | 4 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day07/Program.fs | 4 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day08/Program.fs | 25 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day09/Program.fs | 13 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day10/Program.fs | 4 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day11/Program.fs | 4 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day12/Day12.fsproj | 22 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day12/Program.fs | 101 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day13/Day13.fsproj | 26 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day13/Program.fs | 73 | ||||
| -rw-r--r-- | aoc-2022-dotnet/README.md | 56 | ||||
| -rw-r--r-- | aoc-2022-dotnet/aoc-2022-dotnet.sln | 14 |
16 files changed, 323 insertions, 67 deletions
@@ -10,7 +10,7 @@ Repository storing my solutions to Advent of Code. See other people's solutions ### [2022](aoc-2022-dotnet)  - + [awesome]: https://github.com/Bogdanp/awesome-advent-of-code [aoc]: https://adventofcode.com diff --git a/aoc-2022-dotnet/Common/Util.fs b/aoc-2022-dotnet/Common/Util.fs index 34bf8ff..8505f58 100644 --- a/aoc-2022-dotnet/Common/Util.fs +++ b/aoc-2022-dotnet/Common/Util.fs @@ -10,7 +10,7 @@ module Util = | Success (result, _, _) -> result | _ -> failwith "Invalid input format!" - let countDistinct seq = seq |> Set |> Set.count + let countDistinct xs = xs |> Set |> Set.count let countWhere pred = Seq.filter pred >> Seq.length @@ -20,16 +20,24 @@ module Util = let half = Seq.length xs / 2 [ Seq.take half xs; Seq.skip half xs ] - let splitStringToTuple sep str = - match Seq.toList <| String.split [ sep ] str with + let splitStringToTuple sep string = + match Seq.toList <| String.split [ sep ] string with | [ x; y ] -> x, y | _ -> failwith "Invalid string format!" - let matrixToString m = - m + let matrixToString matrix = + matrix |> Seq.map (Seq.map string >> String.concat "") |> String.concat "\n" + let mapEachToSeq mapping matrix = + seq { + for row in 0 .. Array2D.length1 matrix - 1 do + for col in 0 .. Array2D.length2 matrix - 1 -> mapping matrix (Vec2(col, row)) matrix[row, col] + } + + let mAt matrix (Vec2 (col, row)) = Array2D.get matrix row col + let composition n f = List.replicate n f |> List.reduce (>>) let topN n xs = diff --git a/aoc-2022-dotnet/Common/Vec2.fs b/aoc-2022-dotnet/Common/Vec2.fs index bbe3ef2..11c94aa 100644 --- a/aoc-2022-dotnet/Common/Vec2.fs +++ b/aoc-2022-dotnet/Common/Vec2.fs @@ -4,6 +4,16 @@ type Vec2 = | Vec2 of int * int static member zero = Vec2(0, 0) + static member up = Vec2(0, 1) + static member right = Vec2(1, 0) + static member down = Vec2(0, -1) + static member left = Vec2(-1, 0) + + static member directions4 = + [ Vec2.up + Vec2.right + Vec2.down + Vec2.left ] static member inline (~-) = Vec2.map (~-) static member inline (+)(Vec2 (x1, y1), Vec2 (x2, y2)) = Vec2(x1 + x2, y1 + y2) @@ -11,9 +21,17 @@ type Vec2 = static member inline (*)(v1, k) = Vec2.map ((*) k) v1 static member inline dot (Vec2 (x1, y1)) (Vec2 (x2, y2)) = x1 * x2 + y1 * y2 static member inline cross (Vec2 (x1, y1)) (Vec2 (x2, y2)) = x1 * y2 - y1 * x2 - static member map f (Vec2 (x, y)) = Vec2(f x, f y) static member inline sign = Vec2.map sign static member inline lengthSquared(Vec2 (x, y)) = x * x + y * y static member mahattanDist (Vec2 (x1, y1)) (Vec2 (x2, y2)) = abs (x2 - x1) + abs (y2 - y1) static member chebyshevDist (Vec2 (x1, y1)) (Vec2 (x2, y2)) = max (abs <| x2 - x1) (abs <| y2 - y1) + static member neighbours4 v = List.map ((+) v) Vec2.directions4 + + static member inMatrix matrix (Vec2 (col, row)) = + col >= 0 + && col < Array2D.length2 matrix + && row >= 0 + && row < Array2D.length1 matrix + + static member toIndexOf matrix (Vec2 (col, row)) = (Array2D.length2 matrix) * row + col diff --git a/aoc-2022-dotnet/Day04/Program.fs b/aoc-2022-dotnet/Day04/Program.fs index 7d37d3e..1f0f78f 100644 --- a/aoc-2022-dotnet/Day04/Program.fs +++ b/aoc-2022-dotnet/Day04/Program.fs @@ -4,10 +4,10 @@ open System.IO open FParsec open Common -let parseLine line = +let parseLine = let prange = pint32 .>> pstring "-" .>>. pint32 let ppair = prange .>> pstring "," .>>. prange .>> eof - Util.parse ppair line + Util.parse ppair let fullyOverlap ((a, b), (c, d)) = (a <= c && d <= b) || (c <= a && b <= d) diff --git a/aoc-2022-dotnet/Day05/Program.fs b/aoc-2022-dotnet/Day05/Program.fs index 7bad269..9d9be48 100644 --- a/aoc-2022-dotnet/Day05/Program.fs +++ b/aoc-2022-dotnet/Day05/Program.fs @@ -8,11 +8,11 @@ open Common type Move = | Move of int * int * int - static member parse str = + static member parse = let dec n = n - 1 let pPart str = pstring str >>. pint32 let pMove = tuple3 (pPart "move ") (pPart " from " |>> dec) (pPart " to " |>> dec) - Util.parse pMove str |> Move + Util.parse pMove >> Move static member execute order stacks (Move (n, fi, ti)) = List.mapi diff --git a/aoc-2022-dotnet/Day07/Program.fs b/aoc-2022-dotnet/Day07/Program.fs index e48bb53..7079a33 100644 --- a/aoc-2022-dotnet/Day07/Program.fs +++ b/aoc-2022-dotnet/Day07/Program.fs @@ -16,7 +16,7 @@ type Command = | CD of string // dest | LS of Node list // nodes in current dir -let parseCommands input = +let parseCommands = let pcd = pstring "$ cd " >>. restOfLine true |>> CD let pfile = pint32 .>> pchar ' ' .>> restOfLine true |>> File let pdir = pstring "dir " >>. restOfLine true |>> Dir @@ -29,7 +29,7 @@ let parseCommands input = let pcmd = pcd <|> pls let pinput = many pcmd - Util.parse pinput input + Util.parse pinput let combine = function diff --git a/aoc-2022-dotnet/Day08/Program.fs b/aoc-2022-dotnet/Day08/Program.fs index 23f93c0..881ac72 100644 --- a/aoc-2022-dotnet/Day08/Program.fs +++ b/aoc-2022-dotnet/Day08/Program.fs @@ -5,37 +5,34 @@ open Common let parseMatrix = array2D >> Array2D.map Util.charToInt -let mapEachToSeq mapping m = - seq { - for r in 0 .. Array2D.length1 m - 1 do - for c in 0 .. Array2D.length2 m - 1 -> mapping m r c - } - -let sideViews (m: 'a [,]) r c = +let sideViews (m: 'a [,]) (Vec2 (c, r)) = [ m[0 .. r - 1, c] |> Array.rev m[r, c + 1 ..] m[r + 1 .., c] m[r, 0 .. c - 1] |> Array.rev ] -let isVisible (m: 'a [,]) r c = +let isVisible (matrix: 'a [,]) pos height = not - <| List.forall (Array.exists ((<=) m[r, c])) (sideViews m r c) + <| List.forall (Array.exists ((<=) height)) (sideViews matrix pos) -let scenicScore (m: 'a [,]) r c = - sideViews m r c +let scenicScore (matrix: 'a [,]) pos height = + sideViews matrix pos |> List.map (fun s -> s - |> Seq.tryFindIndex ((<=) m[r, c]) + |> Seq.tryFindIndex ((<=) height) |> Option.map ((+) 1) |> Option.defaultValue (Array.length s)) |> List.reduce (*) let solution1 = parseMatrix - >> mapEachToSeq isVisible + >> Util.mapEachToSeq isVisible >> Util.countWhere id -let solution2 = parseMatrix >> mapEachToSeq scenicScore >> Seq.max +let solution2 = + parseMatrix + >> Util.mapEachToSeq scenicScore + >> Seq.max let test = File.ReadLines("test.txt") assert (solution1 test = 21) diff --git a/aoc-2022-dotnet/Day09/Program.fs b/aoc-2022-dotnet/Day09/Program.fs index df9f040..83df6fd 100644 --- a/aoc-2022-dotnet/Day09/Program.fs +++ b/aoc-2022-dotnet/Day09/Program.fs @@ -4,13 +4,12 @@ open System.IO open Common let directionToVec = - Vec2 - << function - | 'U' -> (0, 1) - | 'R' -> (1, 0) - | 'D' -> (0, -1) - | 'L' -> (-1, 0) - | char -> failwithf "Invalid direction: %c" char + function + | 'U' -> Vec2.up + | 'R' -> Vec2.right + | 'D' -> Vec2.down + | 'L' -> Vec2.left + | char -> failwithf "Invalid direction: %c" char let parseHeadMoves = Seq.collect (fun (line: string) -> Seq.replicate (int line[2..]) (directionToVec line[0])) diff --git a/aoc-2022-dotnet/Day10/Program.fs b/aoc-2022-dotnet/Day10/Program.fs index 35f602f..9a2f002 100644 --- a/aoc-2022-dotnet/Day10/Program.fs +++ b/aoc-2022-dotnet/Day10/Program.fs @@ -20,11 +20,11 @@ type Instr = | NOOP | ADDX of int - static member parse str = + static member parse = let pnoop = pstring "noop" >>% NOOP let paddx = pstring "addx " >>. pint32 |>> ADDX let pinstr = pnoop <|> paddx - Util.parse pinstr str + Util.parse pinstr let solution actOnCpuStates = Seq.map Instr.parse diff --git a/aoc-2022-dotnet/Day11/Program.fs b/aoc-2022-dotnet/Day11/Program.fs index 640a731..0fca3bf 100644 --- a/aoc-2022-dotnet/Day11/Program.fs +++ b/aoc-2022-dotnet/Day11/Program.fs @@ -41,7 +41,7 @@ type Monkey = Inspections = m.Inspections + int64 (List.length throws) }, throws - static member parseList input = + static member parseList = let pid = pstring "Monkey " >>. pint32 .>> pchar ':' @@ -88,7 +88,7 @@ type Monkey = Inspections = 0 } let pmonkeys = sepBy1 pmonkey newline - Util.parse pmonkeys input + Util.parse pmonkeys let monkeyBusiness = List.map Monkey.inspections diff --git a/aoc-2022-dotnet/Day12/Day12.fsproj b/aoc-2022-dotnet/Day12/Day12.fsproj new file mode 100644 index 0000000..b9a3919 --- /dev/null +++ b/aoc-2022-dotnet/Day12/Day12.fsproj @@ -0,0 +1,22 @@ +ο»Ώ<Project Sdk="Microsoft.NET.Sdk"> + + <PropertyGroup> + <OutputType>Exe</OutputType> + <TargetFramework>net7.0</TargetFramework> + </PropertyGroup> + + <ItemGroup> + <Content Include="test.txt"> + <CopyToOutputDirectory>Always</CopyToOutputDirectory> + </Content> + <Content Include="input.txt"> + <CopyToOutputDirectory>Always</CopyToOutputDirectory> + </Content> + <Compile Include="Program.fs" /> + </ItemGroup> + + <ItemGroup> + <ProjectReference Include="..\Common\Common.fsproj" /> + </ItemGroup> + +</Project> diff --git a/aoc-2022-dotnet/Day12/Program.fs b/aoc-2022-dotnet/Day12/Program.fs new file mode 100644 index 0000000..0ccaab7 --- /dev/null +++ b/aoc-2022-dotnet/Day12/Program.fs @@ -0,0 +1,101 @@ +ο»Ώmodule Day12 + +open System.IO +open Common + +type Square = + | Start + | End + | Height of char + + static member elevation = + function + | Start -> Square.elevation <| Height 'a' + | End -> Square.elevation <| Height 'z' + | Height c -> int c - int 'a' + + static member canTraverse a b = + Square.elevation a + 1 >= Square.elevation b + + static member parse = + function + | 'S' -> Start + | 'E' -> End + | c when 'a' <= c && c <= 'z' -> Height(c) + | c -> failwithf "Invalid square: %c" c + +type Graph<'T> = + | Graph of Map<int, 'T * Set<int>> + + static member edges(Graph nodes: Graph<'T>) = + nodes + |> Seq.collect (fun kv -> Set.map (fun n -> (kv.Key, n)) (snd kv.Value)) + |> List.ofSeq + + static member withNewEdges (Graph nodes: Graph<'T>) edges = + nodes + |> Map.map (fun i (v, _) -> + (v, + edges + |> List.choose (fun (a, b) -> if a = i then Some(b) else None) + |> Set)) + |> Graph + + static member invert(graph: Graph<'T>) = + Graph.edges graph + |> List.map (fun (a, b) -> (b, a)) + |> Graph.withNewEdges graph + + static member distance spred epred (Graph nodes: Graph<'T>) = + let rec bfsExplore queue explored = + match queue with + | [] -> None + | (vi, depth) :: qt -> + (let (v, neighbours) = nodes[vi] + + if epred v then + Some(depth) + else + bfsExplore + (neighbours + |> Seq.choose (fun n -> + match Set.contains n explored with + | true -> None + | false -> Some(n, depth + 1)) + |> Seq.append qt + |> List.ofSeq) + (explored + neighbours)) + + let si = Map.findKey (fun _ (v, _) -> spred v) nodes + bfsExplore [ (si, 0) ] (Set.singleton si) + +let solution distanceCalculation = + array2D + >> Array2D.map Square.parse + >> Util.mapEachToSeq (fun matrix pos square -> + (square, + Vec2.neighbours4 pos + |> Seq.filter (fun np -> + Vec2.inMatrix matrix np + && Square.canTraverse square (Util.mAt matrix np)) + |> Seq.map (Vec2.toIndexOf matrix) + |> Set)) + >> Seq.indexed + >> Map.ofSeq + >> Graph + >> distanceCalculation + >> Option.get + +let part1 = Graph.distance ((=) Start) ((=) End) + +let part2 = + Graph.invert + >> Graph.distance ((=) End) (Square.elevation >> (=) 0) + +let test = File.ReadLines("test.txt") +assert (solution part1 test = 31) +assert (solution part2 test = 29) + +let input = File.ReadLines("input.txt") +printfn "%d" <| solution part1 input +printfn "%d" <| solution part2 input diff --git a/aoc-2022-dotnet/Day13/Day13.fsproj b/aoc-2022-dotnet/Day13/Day13.fsproj new file mode 100644 index 0000000..358ef88 --- /dev/null +++ b/aoc-2022-dotnet/Day13/Day13.fsproj @@ -0,0 +1,26 @@ +ο»Ώ<Project Sdk="Microsoft.NET.Sdk"> + + <PropertyGroup> + <OutputType>Exe</OutputType> + <TargetFramework>net7.0</TargetFramework> + </PropertyGroup> + + <ItemGroup> + <Content Include="test.txt"> + <CopyToOutputDirectory>Always</CopyToOutputDirectory> + </Content> + <Content Include="input.txt"> + <CopyToOutputDirectory>Always</CopyToOutputDirectory> + </Content> + <Compile Include="Program.fs" /> + </ItemGroup> + + <ItemGroup> + <PackageReference Include="FParsec" Version="1.1.1" /> + </ItemGroup> + + <ItemGroup> + <ProjectReference Include="..\Common\Common.fsproj" /> + </ItemGroup> + +</Project> diff --git a/aoc-2022-dotnet/Day13/Program.fs b/aoc-2022-dotnet/Day13/Program.fs new file mode 100644 index 0000000..2ff8b8d --- /dev/null +++ b/aoc-2022-dotnet/Day13/Program.fs @@ -0,0 +1,73 @@ +ο»Ώmodule Day13 + +#nowarn "0342" + +open System +open System.IO +open FParsec +open Common + +[<StructuralEquality; CustomComparison>] +type Packet = + | Integer of int + | List of Packet list + + static member dividers = + [ Packet.parse "[[2]]" + Packet.parse "[[6]]" ] + + interface IComparable with + member this.CompareTo other = + match other with + | :? Packet as p -> (this :> IComparable<_>).CompareTo p + | _ -> failwith "Can only compare packets with other packets!" + + interface IComparable<Packet> with + member this.CompareTo other = + match (this, other) with + | Integer l, Integer r -> compare l r + | List l, List r -> compare l r + | (Integer _ as l), (List _ as r) -> compare (List [ l ]) r + | (List _ as l), (Integer _ as r) -> compare l (List [ r ]) + + static member parse = + let ppacket, ppacketImpl = createParserForwardedToRef () + let pinteger = pint32 |>> Integer + + let plist = + between (pchar '[') (pchar ']') (sepBy ppacket (pchar ',')) + |>> List + + ppacketImpl.Value <- pinteger <|> plist + + Util.parse ppacket + +let solution (transform, predicate, reducer) = + Seq.filter (not << String.IsNullOrWhiteSpace) + >> Seq.map Packet.parse + >> transform + >> Seq.indexed + >> Seq.choose (fun (i, p) -> + match predicate p with + | true -> Some(i + 1) + | false -> None) + >> Seq.reduce reducer + +let part1 = + (Seq.chunkBySize 2 + >> Seq.map (function + | [| l; r |] -> compare l r + | _ -> failwith "Invalid packet groupings!"), + (>=) 0, + (+)) + +let part2 = + (Seq.append Packet.dividers >> Seq.sort, (fun p -> List.contains p Packet.dividers), (*)) + +let test = File.ReadLines("test.txt") +assert (solution part1 test = 13) +assert (solution part2 test = 140) + +let input = File.ReadLines("input.txt") +printfn "%d" <| solution part1 input +printfn "%d" <| solution part2 input diff --git a/aoc-2022-dotnet/README.md b/aoc-2022-dotnet/README.md index 94f057c..dbcb833 100644 --- a/aoc-2022-dotnet/README.md +++ b/aoc-2022-dotnet/README.md @@ -1,32 +1,32 @@ # Advent of Code 2022 in .NET  - + ## Progress -| Day | Part 1 | Part 2 | -| ------------------------------ | :----: | :----: | -| Day 1: Calorie Counting | π | π | -| Day 2: Rock Paper Scissors | π | π | -| Day 3: Rucksack Reorganization | π | π | -| Day 4: Camp Cleanup | π | π | -| Day 5: Supply Stacks | π | π | -| Day 6: Tuning Trouble | π | π | -| Day 7: No Space Left On Device | π | π | -| Day 8: Treetop Tree House | π | π | -| Day 9: Rope Bridge | π | π | -| Day 10: Cathode-Ray Tube | π | π | -| Day 11: Monkey in the Middle | π | π | -| Day 12: ??? | | | -| Day 13: ??? | | | -| Day 14: ??? | | | -| Day 15: ??? | | | -| Day 16: ??? | | | -| Day 17: ??? | | | -| Day 18: ??? | | | -| Day 19: ??? | | | -| Day 20: ??? | | | -| Day 21: ??? | | | -| Day 22: ??? | | | -| Day 23: ??? | | | -| Day 24: ??? | | | -| Day 25: ??? | | | +| Day | Part 1 | Part 2 | +| ------------------------------- | :----: | :----: | +| Day 1: Calorie Counting | π | π | +| Day 2: Rock Paper Scissors | π | π | +| Day 3: Rucksack Reorganization | π | π | +| Day 4: Camp Cleanup | π | π | +| Day 5: Supply Stacks | π | π | +| Day 6: Tuning Trouble | π | π | +| Day 7: No Space Left On Device | π | π | +| Day 8: Treetop Tree House | π | π | +| Day 9: Rope Bridge | π | π | +| Day 10: Cathode-Ray Tube | π | π | +| Day 11: Monkey in the Middle | π | π | +| Day 12: Hill Climbing Algorithm | π | π | +| Day 13: Distress Signal | π | π | +| Day 14: ??? | | | +| Day 15: ??? | | | +| Day 16: ??? | | | +| Day 17: ??? | | | +| Day 18: ??? | | | +| Day 19: ??? | | | +| Day 20: ??? | | | +| Day 21: ??? | | | +| Day 22: ??? | | | +| Day 23: ??? | | | +| Day 24: ??? | | | +| Day 25: ??? | | | diff --git a/aoc-2022-dotnet/aoc-2022-dotnet.sln b/aoc-2022-dotnet/aoc-2022-dotnet.sln index 6881d92..cf90abd 100644 --- a/aoc-2022-dotnet/aoc-2022-dotnet.sln +++ b/aoc-2022-dotnet/aoc-2022-dotnet.sln @@ -34,7 +34,11 @@ Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day09", "Day09\Day09.fsproj EndProject Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day10", "Day10\Day10.fsproj", "{FD0F0852-30E0-485E-9423-B25CB6C4C035}" EndProject -Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "Day11", "Day11\Day11.fsproj", "{79DDA3B8-91C1-4F6D-A26C-3FA35609126E}" +Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day11", "Day11\Day11.fsproj", "{79DDA3B8-91C1-4F6D-A26C-3FA35609126E}" +EndProject +Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day12", "Day12\Day12.fsproj", "{3A931587-D31B-4ED7-8AB4-D663175AA7B0}" +EndProject +Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "Day13", "Day13\Day13.fsproj", "{60CC1225-2988-48A1-BA37-477053E3CE98}" EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution @@ -94,6 +98,14 @@ Global {79DDA3B8-91C1-4F6D-A26C-3FA35609126E}.Debug|Any CPU.Build.0 = Debug|Any CPU {79DDA3B8-91C1-4F6D-A26C-3FA35609126E}.Release|Any CPU.ActiveCfg = Release|Any CPU {79DDA3B8-91C1-4F6D-A26C-3FA35609126E}.Release|Any CPU.Build.0 = Release|Any CPU + {3A931587-D31B-4ED7-8AB4-D663175AA7B0}.Debug|Any CPU.ActiveCfg = Debug|Any CPU + {3A931587-D31B-4ED7-8AB4-D663175AA7B0}.Debug|Any CPU.Build.0 = Debug|Any CPU + {3A931587-D31B-4ED7-8AB4-D663175AA7B0}.Release|Any CPU.ActiveCfg = Release|Any CPU + {3A931587-D31B-4ED7-8AB4-D663175AA7B0}.Release|Any CPU.Build.0 = Release|Any CPU + {60CC1225-2988-48A1-BA37-477053E3CE98}.Debug|Any CPU.ActiveCfg = Debug|Any CPU + {60CC1225-2988-48A1-BA37-477053E3CE98}.Debug|Any CPU.Build.0 = Debug|Any CPU + {60CC1225-2988-48A1-BA37-477053E3CE98}.Release|Any CPU.ActiveCfg = Release|Any CPU + {60CC1225-2988-48A1-BA37-477053E3CE98}.Release|Any CPU.Build.0 = Release|Any CPU EndGlobalSection GlobalSection(SolutionProperties) = preSolution HideSolutionNode = FALSE |