diff options
Diffstat (limited to 'aoc-2022-dotnet')
| -rw-r--r-- | aoc-2022-dotnet/Common/Util.fs | 8 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day12/Program.fs | 14 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day14/Program.fs | 16 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day16/Day16.fsproj | 26 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day16/Program.fs | 95 | ||||
| -rw-r--r-- | aoc-2022-dotnet/README.md | 4 | ||||
| -rw-r--r-- | aoc-2022-dotnet/aoc-2022-dotnet.sln | 6 |
7 files changed, 151 insertions, 18 deletions
diff --git a/aoc-2022-dotnet/Common/Util.fs b/aoc-2022-dotnet/Common/Util.fs index 0086ac8..436e9a0 100644 --- a/aoc-2022-dotnet/Common/Util.fs +++ b/aoc-2022-dotnet/Common/Util.fs @@ -40,6 +40,14 @@ module Util = let composition n f = List.replicate n f |> List.reduce (>>) + let notIn set element = not <| Set.contains element set + + let maxOrZero seq = + if Seq.isEmpty seq then + 0 + else + Seq.max seq + let rec insertSorted x = function | h :: t -> min h x :: (insertSorted (max h x) t) diff --git a/aoc-2022-dotnet/Day12/Program.fs b/aoc-2022-dotnet/Day12/Program.fs index ca827ba..77417c5 100644 --- a/aoc-2022-dotnet/Day12/Program.fs +++ b/aoc-2022-dotnet/Day12/Program.fs @@ -47,24 +47,24 @@ type Graph<'T> = |> Graph.withNewEdges graph static member distance spred epred (Graph nodes: Graph<'T>) = - let rec bfsExplore queue explored = - match queue with + let rec bfsExplore explored = + function | [] -> None - | (vi, depth) :: qt -> + | (vi, depth) :: queue -> (let (v, neighbours) = nodes[vi] if epred v then Some(depth) else bfsExplore + (explored + neighbours) (neighbours - explored |> Seq.map (fun n -> (n, depth + 1)) - |> Seq.append qt - |> List.ofSeq) - (explored + neighbours)) + |> Seq.append queue + |> List.ofSeq)) let si = Map.findKey (fun _ (v, _) -> spred v) nodes - bfsExplore [ (si, 0) ] (Set.singleton si) + bfsExplore (Set.singleton si) [ (si, 0) ] let solution distanceCalculation = array2D diff --git a/aoc-2022-dotnet/Day14/Program.fs b/aoc-2022-dotnet/Day14/Program.fs index 02e028c..b3ff4f9 100644 --- a/aoc-2022-dotnet/Day14/Program.fs +++ b/aoc-2022-dotnet/Day14/Program.fs @@ -11,8 +11,6 @@ let sandMoveOffsets = Vec2.downLeft Vec2.downRight ] -let notIn set element = not <| Set.contains element set - let buildCaveScan = let parsePath = let py = pint32 |>> (~-) // mirror Y coordinate @@ -39,7 +37,7 @@ let solution1 input = else sandMoveOffsets |> Seq.map ((+) pos) - |> Seq.tryFind (notIn caveScan) + |> Seq.tryFind (Util.notIn caveScan) |> function | Some (nextPos) -> fall nextPos | None -> Some(pos) @@ -62,14 +60,14 @@ let solution2 input = let neighbours pos = sandMoveOffsets |> List.map ((+) pos) - |> List.filter (fun pos -> notIn caveScan pos && Vec2.y pos <> floorY) + |> List.filter (fun pos -> Util.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 + let rec dfs vis = + function + | h :: t -> dfs (Set.add h vis) (List.filter (Util.notIn vis) (neighbours h) @ t) + | [] -> Set.count vis - dfs [ sandSpawnPos ] Set.empty + dfs Set.empty [ sandSpawnPos ] let test = File.ReadLines("test.txt") assert (solution1 test = 24) diff --git a/aoc-2022-dotnet/Day16/Day16.fsproj b/aoc-2022-dotnet/Day16/Day16.fsproj new file mode 100644 index 0000000..358ef88 --- /dev/null +++ b/aoc-2022-dotnet/Day16/Day16.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/Day16/Program.fs b/aoc-2022-dotnet/Day16/Program.fs new file mode 100644 index 0000000..a2c4b2e --- /dev/null +++ b/aoc-2022-dotnet/Day16/Program.fs @@ -0,0 +1,95 @@ +module Day16 + +open System.IO +open FParsec +open Common + +type ValveName = string + +type Valve = + { Flow: int + Neighbours: ValveName list } + +let parseValve = + let pSingleOrMulti str = pstring str .>>. opt (pchar 's') + let pValveName: Parser<ValveName, _> = anyString 2 + + let pValve = + pstring "Valve " >>. pValveName + .>> pstring " has flow rate=" + .>>. pint32 + .>> pstring "; " + .>> pSingleOrMulti "tunnel" + .>> pchar ' ' + .>> pSingleOrMulti "lead" + .>> pstring " to " + .>> pSingleOrMulti "valve" + .>> pchar ' ' + .>>. sepBy1 pValveName (pstring ", ") + |>> (fun ((name, flow), neighbours) -> (name, { Flow = flow; Neighbours = neighbours })) + + Util.parse pValve + +let distancesFrom valves start = + let neighbours v = (Map.find v valves).Neighbours + + let rec bfsExplore visited acc = + function + | (v, depth) :: queue -> + bfsExplore + (Set.add v visited) + (((start, v), depth) :: acc) + (queue + @ (neighbours v + |> List.filter (Util.notIn visited) + |> List.map (fun n -> (n, depth + 1)))) + | [] -> acc + + bfsExplore Set.empty [] [ (start, 0) ] + +let buildGraph input = + let valves = input |> Seq.map parseValve |> Map.ofSeq + + let flows = + valves + |> Map.map (fun _ v -> v.Flow) + |> Map.filter (fun v f -> f > 0 || v = "AA") + + let distances = + valves + |> Map.keys + |> Seq.collect (distancesFrom valves) + |> Map.ofSeq + |> Map.filter (fun (f, t) _ -> + f <> t + && Map.containsKey f flows + && Map.containsKey t flows) + + flows, distances + +let solution input = + let (flows, distances) = buildGraph input + + let rec findMaxPressure current remainingTime closedValves = + let closedValves = closedValves |> Set.remove current + + closedValves + |> Seq.choose (fun t -> + let remainingTime = remainingTime - (distances[(current, t)] + 1) + + if remainingTime > 0 then + Some( + flows[t] * remainingTime + + findMaxPressure t remainingTime closedValves + ) + else + None) + |> Util.maxOrZero + + findMaxPressure "AA" 30 (flows |> Map.keys |> Set.ofSeq) + +let test = File.ReadLines("test.txt") +assert (solution test = 1651) + +let input = File.ReadLines("input.txt") +printfn "%d" <| solution input diff --git a/aoc-2022-dotnet/README.md b/aoc-2022-dotnet/README.md index 8bcfa97..4b49309 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 | | :----: | --------------------------------------------------------------- | :----: | :----: | ---------------------------------------------------- | @@ -19,7 +19,7 @@ | **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) | :star: | :star: | ranges, mahattan distance, parallel computing | -| **16** | [Proboscidea Volcanium](https://adventofcode.com/2022/day/16) | | | | +| **16** | [Proboscidea Volcanium](https://adventofcode.com/2022/day/16) | :star: | | | | **17** | ??? | | | | | **18** | ??? | | | | | **19** | ??? | | | | diff --git a/aoc-2022-dotnet/aoc-2022-dotnet.sln b/aoc-2022-dotnet/aoc-2022-dotnet.sln index b8ae123..e533c60 100644 --- a/aoc-2022-dotnet/aoc-2022-dotnet.sln +++ b/aoc-2022-dotnet/aoc-2022-dotnet.sln @@ -44,6 +44,8 @@ Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day14", "Day14\Day14.fsproj EndProject Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "Day15", "Day15\Day15.fsproj", "{52EA45CC-A60B-4B2D-B91F-A7B3874879BB}" EndProject +Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "Day16", "Day16\Day16.fsproj", "{4CABEF49-D9D8-4211-8714-95E118820C8F}" +EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution Debug|Any CPU = Debug|Any CPU @@ -118,6 +120,10 @@ Global {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 + {4CABEF49-D9D8-4211-8714-95E118820C8F}.Debug|Any CPU.ActiveCfg = Debug|Any CPU + {4CABEF49-D9D8-4211-8714-95E118820C8F}.Debug|Any CPU.Build.0 = Debug|Any CPU + {4CABEF49-D9D8-4211-8714-95E118820C8F}.Release|Any CPU.ActiveCfg = Release|Any CPU + {4CABEF49-D9D8-4211-8714-95E118820C8F}.Release|Any CPU.Build.0 = Release|Any CPU EndGlobalSection GlobalSection(SolutionProperties) = preSolution HideSolutionNode = FALSE |