diff options
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Common/Vec2.fs | 17 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day12/Program.fs | 7 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day14/Day14.fsproj | 26 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day14/Program.fs | 80 | ||||
| -rw-r--r-- | aoc-2022-dotnet/README.md | 4 | ||||
| -rw-r--r-- | aoc-2022-dotnet/aoc-2022-dotnet.sln | 8 |
7 files changed, 135 insertions, 9 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/Vec2.fs b/aoc-2022-dotnet/Common/Vec2.fs index 11c94aa..8835a5a 100644 --- a/aoc-2022-dotnet/Common/Vec2.fs +++ b/aoc-2022-dotnet/Common/Vec2.fs @@ -1,14 +1,21 @@ ο»Ώnamespace Common +[<StructuralEquality; StructuralComparison>] type Vec2 = | Vec2 of int * int + static member x(Vec2 (x, _)) = x + static member y(Vec2 (_, y)) = y + 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 downLeft = Vec2(-1, -1) + static member downRight = Vec2(1, -1) + static member directions4 = [ Vec2.up Vec2.right @@ -28,6 +35,16 @@ type Vec2 = 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 lineBetween(Vec2 (x1, y1), Vec2 (x2, y2)) = + if x1 = x2 then + seq { min y1 y2 .. max y1 y2 } + |> Seq.map (fun y -> Vec2(x1, y)) + elif y1 = y2 then + seq { min x1 x2 .. max x1 x2 } + |> Seq.map (fun x -> Vec2(x, y1)) + else + failwith "Points must be in a vertical or horizontal line!" + static member inMatrix matrix (Vec2 (col, row)) = col >= 0 && col < Array2D.length2 matrix diff --git a/aoc-2022-dotnet/Day12/Program.fs b/aoc-2022-dotnet/Day12/Program.fs index 0ccaab7..ca827ba 100644 --- a/aoc-2022-dotnet/Day12/Program.fs +++ b/aoc-2022-dotnet/Day12/Program.fs @@ -57,11 +57,8 @@ type Graph<'T> = Some(depth) else bfsExplore - (neighbours - |> Seq.choose (fun n -> - match Set.contains n explored with - | true -> None - | false -> Some(n, depth + 1)) + (neighbours - explored + |> Seq.map (fun n -> (n, depth + 1)) |> Seq.append qt |> List.ofSeq) (explored + neighbours)) diff --git a/aoc-2022-dotnet/Day14/Day14.fsproj b/aoc-2022-dotnet/Day14/Day14.fsproj new file mode 100644 index 0000000..358ef88 --- /dev/null +++ b/aoc-2022-dotnet/Day14/Day14.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/Day14/Program.fs b/aoc-2022-dotnet/Day14/Program.fs new file mode 100644 index 0000000..02e028c --- /dev/null +++ b/aoc-2022-dotnet/Day14/Program.fs @@ -0,0 +1,80 @@ +ο»Ώmodule Day14 + +open System.IO +open FParsec +open Common + +let sandSpawnPos = Vec2(500, 0) + +let sandMoveOffsets = + [ Vec2.down + Vec2.downLeft + Vec2.downRight ] + +let notIn set element = not <| Set.contains element set + +let buildCaveScan = + let parsePath = + let py = pint32 |>> (~-) // mirror Y coordinate + let ppoint = pint32 .>> (pchar ',') .>>. py |>> Vec2 + let ppath = sepBy ppoint (pstring " -> ") + Util.parse ppath + + let pathToPositions = + Seq.pairwise + >> Seq.collect Vec2.lineBetween + >> Set + + Seq.map (parsePath >> pathToPositions) + >> Seq.reduce (+) + +let solution1 input = + let initialCaveScan = buildCaveScan input + let voidY = initialCaveScan |> Seq.map Vec2.y |> Seq.min + + let settleNewUnit caveScan = + let rec fall pos = + if Vec2.y pos <= voidY then + None + else + sandMoveOffsets + |> Seq.map ((+) pos) + |> Seq.tryFind (notIn caveScan) + |> function + | Some (nextPos) -> fall nextPos + | None -> Some(pos) + + caveScan + |> match fall sandSpawnPos with + | Some (settledPos) -> Set.add settledPos + | None -> id + + initialCaveScan + |> Seq.unfold (fun caveScan -> Some(caveScan, settleNewUnit caveScan)) + |> Seq.pairwise + |> Seq.takeWhile (fun (a, b) -> a <> b) + |> Seq.length + +let solution2 input = + let caveScan = buildCaveScan input + let floorY = caveScan |> Seq.map Vec2.y |> Seq.min |> (+) -2 + + let neighbours pos = + sandMoveOffsets + |> List.map ((+) pos) + |> List.filter (fun pos -> notIn caveScan pos && Vec2.y pos <> floorY) + + let rec dfs stack visited = + match stack with + | h :: t -> dfs (List.filter (notIn visited) (neighbours h) @ t) (Set.add h visited) + | [] -> Set.count visited + + dfs [ sandSpawnPos ] Set.empty + +let test = File.ReadLines("test.txt") +assert (solution1 test = 24) +assert (solution2 test = 93) + +let input = File.ReadLines("input.txt") +printfn "%d" <| solution1 input +printfn "%d" <| solution2 input diff --git a/aoc-2022-dotnet/README.md b/aoc-2022-dotnet/README.md index dbcb833..84a39ce 100644 --- a/aoc-2022-dotnet/README.md +++ b/aoc-2022-dotnet/README.md @@ -1,6 +1,6 @@ # Advent of Code 2022 in .NET  - + ## Progress | Day | Part 1 | Part 2 | @@ -18,7 +18,7 @@ | Day 11: Monkey in the Middle | π | π | | Day 12: Hill Climbing Algorithm | π | π | | Day 13: Distress Signal | π | π | -| Day 14: ??? | | | +| Day 14: Regolith Reservoir | π | π | | Day 15: ??? | | | | Day 16: ??? | | | | Day 17: ??? | | | diff --git a/aoc-2022-dotnet/aoc-2022-dotnet.sln b/aoc-2022-dotnet/aoc-2022-dotnet.sln index cf90abd..fb017eb 100644 --- a/aoc-2022-dotnet/aoc-2022-dotnet.sln +++ b/aoc-2022-dotnet/aoc-2022-dotnet.sln @@ -38,7 +38,9 @@ Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day11", "Day11\Day11.fsproj 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}" +Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day13", "Day13\Day13.fsproj", "{60CC1225-2988-48A1-BA37-477053E3CE98}" +EndProject +Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "Day14", "Day14\Day14.fsproj", "{3241E7B6-B58B-4032-9746-DF87B1F0D666}" EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution @@ -106,6 +108,10 @@ Global {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 + {3241E7B6-B58B-4032-9746-DF87B1F0D666}.Debug|Any CPU.ActiveCfg = Debug|Any CPU + {3241E7B6-B58B-4032-9746-DF87B1F0D666}.Debug|Any CPU.Build.0 = Debug|Any CPU + {3241E7B6-B58B-4032-9746-DF87B1F0D666}.Release|Any CPU.ActiveCfg = Release|Any CPU + {3241E7B6-B58B-4032-9746-DF87B1F0D666}.Release|Any CPU.Build.0 = Release|Any CPU EndGlobalSection GlobalSection(SolutionProperties) = preSolution HideSolutionNode = FALSE |