diff options
Diffstat (limited to 'aoc-2022-dotnet')
| -rw-r--r-- | aoc-2022-dotnet/Common/Util.fs | 10 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day15/Day15.fsproj | 27 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day15/Program.fs | 103 | ||||
| -rw-r--r-- | aoc-2022-dotnet/README.md | 6 | ||||
| -rw-r--r-- | aoc-2022-dotnet/aoc-2022-dotnet.sln | 8 |
5 files changed, 145 insertions, 9 deletions
diff --git a/aoc-2022-dotnet/Common/Util.fs b/aoc-2022-dotnet/Common/Util.fs index 8505f58..0086ac8 100644 --- a/aoc-2022-dotnet/Common/Util.fs +++ b/aoc-2022-dotnet/Common/Util.fs @@ -40,12 +40,12 @@ module Util = let composition n f = List.replicate n f |> List.reduce (>>) - let topN n xs = - let rec insertSorted x = - function - | h :: t -> min h x :: (insertSorted (max h x) t) - | _ -> [ x ] + let rec insertSorted x = + function + | h :: t -> min h x :: (insertSorted (max h x) t) + | [] -> [ x ] + let topN n xs = Seq.fold (fun acc x -> if List.length acc < n then diff --git a/aoc-2022-dotnet/Day15/Day15.fsproj b/aoc-2022-dotnet/Day15/Day15.fsproj new file mode 100644 index 0000000..ede5b83 --- /dev/null +++ b/aoc-2022-dotnet/Day15/Day15.fsproj @@ -0,0 +1,27 @@ +<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" /> + <PackageReference Include="FSharp.Collections.ParallelSeq" Version="1.2.0" /> + </ItemGroup> + + <ItemGroup> + <ProjectReference Include="..\Common\Common.fsproj" /> + </ItemGroup> + +</Project> diff --git a/aoc-2022-dotnet/Day15/Program.fs b/aoc-2022-dotnet/Day15/Program.fs new file mode 100644 index 0000000..e158346 --- /dev/null +++ b/aoc-2022-dotnet/Day15/Program.fs @@ -0,0 +1,103 @@ +module Day15 + +open System.IO +open FSharp.Collections.ParallelSeq +open FParsec +open Common + +let tuner = 4_000_000 + +type Sensor = + { Pos: Vec2 + Radius: int + NearestBeacon: Vec2 } + +let rangeCount (first, last) = max 0 (last - first + 1) + +type RangeSet = + | RangeSet of (int * int) list + + static member empty = RangeSet [] + + static member private merge = + function + | ((_, l1) as r1) :: ((f2, _) as r2) :: t when l1 + 1 < f2 -> r1 :: RangeSet.merge (r2 :: t) + | (f1, l1) :: (_, l2) :: t -> RangeSet.merge <| (f1, max l1 l2) :: t + | other -> other + + static member add set range = + if rangeCount range = 0 then + set + else + let (RangeSet list) = set + RangeSet(RangeSet.merge (Util.insertSorted range list)) + + static member count(RangeSet list) = List.map rangeCount list |> List.sum + + static member gap = + function + | (RangeSet ([ (_, x); _ ])) -> Some(x + 1) + | _ -> None + +let sensorList = + let parseSensor line = + let ppos = + tuple2 (pstring "x=" >>. pint32) (pstring ", y=" >>. pint32) + |>> Vec2 + + let pline = + pstring "Sensor at " >>. ppos + .>> pstring ": closest beacon is at " + .>>. ppos + + let (sensorPos, beaconPos) = Util.parse pline line + + { Pos = sensorPos + Radius = Vec2.mahattanDist sensorPos beaconPos + NearestBeacon = beaconPos } + + Seq.map parseSensor >> List.ofSeq + +let rowCoverages y sensors = + let coverage ({ Radius = radius; Pos = pos }) = + let offset = radius - abs (Vec2.y pos - y) + (Vec2.x pos - offset, Vec2.x pos + offset) + + sensors + |> Seq.map coverage + |> Seq.fold RangeSet.add RangeSet.empty + +let solution1 y input = + let sensors = sensorList input + + let beaconsInRow = + sensors + |> Seq.choose (fun ({ NearestBeacon = b }) -> + if Vec2.y b = y then + Some(Vec2.x b) + else + None) + |> Util.countDistinct + + sensors + |> rowCoverages y + |> RangeSet.count + |> (fun count -> count - beaconsInRow) + +let solution2 input = + let sensors = sensorList input + + seq { 0..tuner } + |> PSeq.pick (fun y -> + sensors + |> rowCoverages y + |> RangeSet.gap + |> Option.map (fun x -> int64 x * int64 tuner + int64 y)) + +let test = File.ReadLines("test.txt") +assert (solution1 10 test = 26) +assert (solution2 test = 56000011) + +let input = File.ReadLines("input.txt") +printfn "%A" <| solution1 2_000_000 input +printfn "%A" <| solution2 input diff --git a/aoc-2022-dotnet/README.md b/aoc-2022-dotnet/README.md index 0e2bd98..8bcfa97 100644 --- a/aoc-2022-dotnet/README.md +++ b/aoc-2022-dotnet/README.md @@ -1,6 +1,6 @@ # Advent of Code 2022 in F#  - + | Day | Problem Name | Part 1 | Part 2 | Practiced Concepts | | :----: | --------------------------------------------------------------- | :----: | :----: | ---------------------------------------------------- | @@ -18,8 +18,8 @@ | **12** | [Hill Climbing Algorithm](https://adventofcode.com/2022/day/12) | :star: | :star: | functional graphs, functional BFS, `Array2D` | | **13** | [Distress Signal](https://adventofcode.com/2022/day/13) | :star: | :star: | `IComparable`, ADTs, patterns, FParsec | | **14** | [Regolith Reservoir](https://adventofcode.com/2022/day/14) | :star: | :star: | `Seq.unfold`, `Seq.pairwise`, functional DFS | -| **15** | [Beacon Exclusion Zone](https://adventofcode.com/2022/day/15) | | | | -| **16** | ??? | | | | +| **15** | [Beacon Exclusion Zone](https://adventofcode.com/2022/day/15) | :star: | :star: | ranges, mahattan distance, parallel computing | +| **16** | [Proboscidea Volcanium](https://adventofcode.com/2022/day/16) | | | | | **17** | ??? | | | | | **18** | ??? | | | | | **19** | ??? | | | | diff --git a/aoc-2022-dotnet/aoc-2022-dotnet.sln b/aoc-2022-dotnet/aoc-2022-dotnet.sln index fb017eb..b8ae123 100644 --- a/aoc-2022-dotnet/aoc-2022-dotnet.sln +++ b/aoc-2022-dotnet/aoc-2022-dotnet.sln @@ -40,7 +40,9 @@ Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day12", "Day12\Day12.fsproj EndProject 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}" +Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day14", "Day14\Day14.fsproj", "{3241E7B6-B58B-4032-9746-DF87B1F0D666}" +EndProject +Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "Day15", "Day15\Day15.fsproj", "{52EA45CC-A60B-4B2D-B91F-A7B3874879BB}" EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution @@ -112,6 +114,10 @@ Global {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 + {52EA45CC-A60B-4B2D-B91F-A7B3874879BB}.Debug|Any CPU.ActiveCfg = Debug|Any CPU + {52EA45CC-A60B-4B2D-B91F-A7B3874879BB}.Debug|Any CPU.Build.0 = Debug|Any CPU + {52EA45CC-A60B-4B2D-B91F-A7B3874879BB}.Release|Any CPU.ActiveCfg = Release|Any CPU + {52EA45CC-A60B-4B2D-B91F-A7B3874879BB}.Release|Any CPU.Build.0 = Release|Any CPU EndGlobalSection GlobalSection(SolutionProperties) = preSolution HideSolutionNode = FALSE |