diff options
Diffstat (limited to 'aoc-2022-dotnet')
| -rw-r--r-- | aoc-2022-dotnet/Common/Util.fs | 4 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Common/Vec2.fs | 28 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day14/Program.fs | 8 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day15/Program.fs | 12 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day24/Day24.fsproj | 22 | ||||
| -rw-r--r-- | aoc-2022-dotnet/Day24/Program.fs | 107 | ||||
| -rw-r--r-- | aoc-2022-dotnet/README.md | 6 | ||||
| -rw-r--r-- | aoc-2022-dotnet/aoc-2022-dotnet.sln | 8 |
8 files changed, 173 insertions, 22 deletions
diff --git a/aoc-2022-dotnet/Common/Util.fs b/aoc-2022-dotnet/Common/Util.fs index ac5d981..ad177db 100644 --- a/aoc-2022-dotnet/Common/Util.fs +++ b/aoc-2022-dotnet/Common/Util.fs @@ -4,6 +4,7 @@ module Util = open System.Globalization open FParsec open FSharpPlus + open FSharpPlus.Math.Generic let parse parser input = match run parser input with @@ -16,6 +17,9 @@ module Util = let charToInt = CharUnicodeInfo.GetDigitValue + let wrapInRangeInc lower upper x = + lower + remE (x - lower) (upper - lower + 1) + let cutInHalf xs = let half = Seq.length xs / 2 [ Seq.take half xs; Seq.skip half xs ] diff --git a/aoc-2022-dotnet/Common/Vec2.fs b/aoc-2022-dotnet/Common/Vec2.fs index 438135b..8183083 100644 --- a/aoc-2022-dotnet/Common/Vec2.fs +++ b/aoc-2022-dotnet/Common/Vec2.fs @@ -4,10 +4,14 @@ type Vec2 = | Vec2 of int * int - static member inline x(Vec2 (x, _)) = x - static member inline y(Vec2 (_, y)) = y + static member inline getX(Vec2 (x, _)) = x + static member inline getY(Vec2 (_, y)) = y + member inline this.x = Vec2.getX this + member inline this.y = Vec2.getY this static member zero = Vec2(0, 0) + static member ones = Vec2(1, 1) + static member up = Vec2(0, 1) static member right = Vec2(1, 0) static member down = Vec2(0, -1) @@ -44,6 +48,8 @@ type Vec2 = Vec2.down Vec2.left ] + static member directions5 = Vec2.directions4 |> Set.add Vec2.zero + static member directions8 = Set [ Vec2.up Vec2.upRight @@ -54,19 +60,20 @@ type Vec2 = Vec2.left Vec2.upLeft ] - static member inline private _map f (Vec2 (x, y)) = Vec2(f x, f y) + static member inline mapX f (Vec2 (x, y)) = Vec2(f x, y) + static member inline mapY f (Vec2 (x, y)) = Vec2(x, f y) + static member inline private _map f = Vec2.mapX f >> Vec2.mapY f static member inline private _combine fn (Vec2 (x1, y1)) (Vec2 (x2, y2)) = Vec2(fn x1 x2, fn y1 y2) static member inline (~-)(v) = Vec2._map (~-) v static member inline (+)(v1, v2) = Vec2._combine (+) v1 v2 static member inline (-)(v1, v2) = Vec2._combine (-) v1 v2 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 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 inline lengthSquared v = Vec2.dot v v + static member manhattanDist (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 inline private _nb d v = Set.map ((+) v) d @@ -75,8 +82,17 @@ type Vec2 = static member neighboursDown = Vec2._nb Vec2.directionsDown static member neighboursLeft = Vec2._nb Vec2.directionsLeft static member neighbours4 = Vec2._nb Vec2.directions4 + static member neighbours5 = Vec2._nb Vec2.directions5 static member neighbours8 = Vec2._nb Vec2.directions8 + static member dirFromChar = + function + | '^' -> Vec2.up + | '>' -> Vec2.right + | 'v' -> Vec2.down + | '<' -> Vec2.left + | c -> failwithf "Invalid direction: %c" c + static member boundingRectangle vs = (Seq.reduce (Vec2._combine min) vs, Seq.reduce (Vec2._combine max) vs) diff --git a/aoc-2022-dotnet/Day14/Program.fs b/aoc-2022-dotnet/Day14/Program.fs index b3ff4f9..018664a 100644 --- a/aoc-2022-dotnet/Day14/Program.fs +++ b/aoc-2022-dotnet/Day14/Program.fs @@ -28,11 +28,11 @@ let buildCaveScan = let solution1 input = let initialCaveScan = buildCaveScan input - let voidY = initialCaveScan |> Seq.map Vec2.y |> Seq.min + let voidY = initialCaveScan |> Seq.map Vec2.getY |> Seq.min let settleNewUnit caveScan = let rec fall pos = - if Vec2.y pos <= voidY then + if Vec2.getY pos <= voidY then None else sandMoveOffsets @@ -55,12 +55,12 @@ let solution1 input = let solution2 input = let caveScan = buildCaveScan input - let floorY = caveScan |> Seq.map Vec2.y |> Seq.min |> (+) -2 + let floorY = caveScan |> Seq.map Vec2.getY |> Seq.min |> (+) -2 let neighbours pos = sandMoveOffsets |> List.map ((+) pos) - |> List.filter (fun pos -> Util.notIn caveScan pos && Vec2.y pos <> floorY) + |> List.filter (fun pos -> Util.notIn caveScan pos && Vec2.getY pos <> floorY) let rec dfs vis = function diff --git a/aoc-2022-dotnet/Day15/Program.fs b/aoc-2022-dotnet/Day15/Program.fs index e158346..427c411 100644 --- a/aoc-2022-dotnet/Day15/Program.fs +++ b/aoc-2022-dotnet/Day15/Program.fs @@ -53,15 +53,15 @@ let sensorList = let (sensorPos, beaconPos) = Util.parse pline line { Pos = sensorPos - Radius = Vec2.mahattanDist sensorPos beaconPos + Radius = Vec2.manhattanDist 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) + let offset = radius - abs (pos.y - y) + (pos.x - offset, pos.x + offset) sensors |> Seq.map coverage @@ -72,11 +72,7 @@ let solution1 y input = let beaconsInRow = sensors - |> Seq.choose (fun ({ NearestBeacon = b }) -> - if Vec2.y b = y then - Some(Vec2.x b) - else - None) + |> Seq.choose (fun ({ NearestBeacon = b }) -> if b.y = y then Some(b.x) else None) |> Util.countDistinct sensors diff --git a/aoc-2022-dotnet/Day24/Day24.fsproj b/aoc-2022-dotnet/Day24/Day24.fsproj new file mode 100644 index 0000000..b9a3919 --- /dev/null +++ b/aoc-2022-dotnet/Day24/Day24.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/Day24/Program.fs b/aoc-2022-dotnet/Day24/Program.fs new file mode 100644 index 0000000..0446c06 --- /dev/null +++ b/aoc-2022-dotnet/Day24/Program.fs @@ -0,0 +1,107 @@ +module Day24 + +open System.IO +open FSharpPlus +open Common + +type Valley = + { MaxX: int + MaxY: int + ExpeditionSuperposition: Set<Vec2> + Walls: Set<Vec2> + Blizzards: Map<Vec2, Set<Vec2>> } + + static member private empty = + { MaxX = 0 + MaxY = 0 + ExpeditionSuperposition = Set.empty + Walls = Set.empty + Blizzards = + Vec2.directions4 + |> Set.map (fun d -> d, Set.empty) + |> Map.ofSeq } + + static member private withExpeditionAt target valley = + { valley with ExpeditionSuperposition = Set.singleton <| target valley } + + static member private hasReached target valley = + Set.contains (target valley) valley.ExpeditionSuperposition + + static member startOf({ MaxY = maxY }) = Vec2(1, maxY) + static member endOf({ MaxX = maxX }) = Vec2(maxX - 1, 0) + + static member parse input = + input + |> Seq.rev + |> array2D + |> Array2D.mapi (fun r c char -> Vec2(c, r), char) + |> Seq.cast + |> Seq.fold + (fun valley (pos, char) -> + match char with + | '.' -> valley + | '#' -> + { valley with + Walls = valley.Walls.Add(pos) + MaxX = max valley.MaxX pos.x + MaxY = max valley.MaxY pos.y } + | '^' + | '>' + | 'v' + | '<' -> + { valley with Blizzards = valley.Blizzards.Change(Vec2.dirFromChar char, Option.map <| Set.add pos) } + | c -> failwithf "Invalid valley character: %c" c) + Valley.empty + |> Valley.withExpeditionAt Valley.startOf + + member private valley.moveBlizzard offset pos = + pos + offset + |> Vec2.mapX (Util.wrapInRangeInc 1 (valley.MaxX - 1)) + |> Vec2.mapY (Util.wrapInRangeInc 1 (valley.MaxY - 1)) + + static member private step valley = + let valley = + { valley with Blizzards = Map.map (fun dir -> Set.map <| valley.moveBlizzard dir) valley.Blizzards } + + { valley with + ExpeditionSuperposition = + valley.ExpeditionSuperposition + |> Seq.collect Vec2.neighbours5 + |> Seq.filter (fun pos -> + pos.y >= 0 + && pos.y <= valley.MaxY + && Util.notIn valley.Walls pos + && Seq.forall (not << Set.contains pos) valley.Blizzards.Values) + |> Set } + + static member moveTo target valley = + Some(valley, 0) + |> Seq.unfold ( + Option.map + <| fun (v, m) -> + (v, m), + match Valley.hasReached target v with + | true -> None + | false -> Some(Valley.step v, m + 1) + ) + |> Seq.last + |> mapItem1 (Valley.withExpeditionAt target) + +let solution1 = Valley.parse >> Valley.moveTo Valley.endOf >> snd + +let solution2 input = + let valley = Valley.parse input + + let (valley, minutes1) = Valley.moveTo Valley.endOf valley + let (valley, minutes2) = Valley.moveTo Valley.startOf valley + let (_, minutes3) = Valley.moveTo Valley.endOf valley + + minutes1 + minutes2 + minutes3 + +let test = File.ReadLines("test.txt") +assert (solution1 test = 18) +assert (solution2 test = 54) + +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 5bb91e0..34d872f 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 | | :----: | ---------------------------------------------------------------- | :----: | :----: | ---------------------------------------------------- | @@ -23,9 +23,9 @@ | **17** | [Pyroclastic Flow](https://adventofcode.com/2022/day/17) | :star: | :star: | cycle detection, bitwise operators, `hash` | | **18** | [Boiling Boulders](https://adventofcode.com/2022/day/18) | :star: | :star: | functional DFS, 3D vectors, position bound checking | | **19** | [Not Enough Minerals](https://adventofcode.com/2022/day/19) | | | | -| **20** | [Grove Positioning System](https://adventofcode.com/2022/day/20) | :star: | :star: | linked lists, modulo & remainder | +| **20** | [Grove Positioning System](https://adventofcode.com/2022/day/20) | :star: | :star: | linked lists, remainder | | **21** | [Monkey Math](https://adventofcode.com/2022/day/21) | :star: | :star: | topological sort, ADTs, complex numbers | | **22** | [Monkey Map](https://adventofcode.com/2022/day/22) | | | | | **23** | [Unstable Diffusion](https://adventofcode.com/2022/day/23) | :star: | :star: | `Set`, 2D vectors, `Seq.unfold`, composition | -| **24** | [Blizzard Basin](https://adventofcode.com/2022/day/24) | | | | +| **24** | [Blizzard Basin](https://adventofcode.com/2022/day/24) | :star: | :star: | `Set`, 2D vectors, remainder, records | | **25** | [Full of Hot Air](https://adventofcode.com/2022/day/25) | :star: | | positional numeral systems, recursion | diff --git a/aoc-2022-dotnet/aoc-2022-dotnet.sln b/aoc-2022-dotnet/aoc-2022-dotnet.sln index 3b78609..a233bf2 100644 --- a/aoc-2022-dotnet/aoc-2022-dotnet.sln +++ b/aoc-2022-dotnet/aoc-2022-dotnet.sln @@ -56,7 +56,9 @@ Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day21", "Day21\Day21.fsproj EndProject Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day25", "Day25\Day25.fsproj", "{3CBC73E3-821C-45FC-85F8-877C29810E67}" EndProject -Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "Day23", "Day23\Day23.fsproj", "{E6AEEB69-7669-4026-AC28-94D7B4467838}" +Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day23", "Day23\Day23.fsproj", "{E6AEEB69-7669-4026-AC28-94D7B4467838}" +EndProject +Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "Day24", "Day24\Day24.fsproj", "{253313A4-C9F8-4A83-89A5-8FCB426004E0}" EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution @@ -160,6 +162,10 @@ Global {E6AEEB69-7669-4026-AC28-94D7B4467838}.Debug|Any CPU.Build.0 = Debug|Any CPU {E6AEEB69-7669-4026-AC28-94D7B4467838}.Release|Any CPU.ActiveCfg = Release|Any CPU {E6AEEB69-7669-4026-AC28-94D7B4467838}.Release|Any CPU.Build.0 = Release|Any CPU + {253313A4-C9F8-4A83-89A5-8FCB426004E0}.Debug|Any CPU.ActiveCfg = Debug|Any CPU + {253313A4-C9F8-4A83-89A5-8FCB426004E0}.Debug|Any CPU.Build.0 = Debug|Any CPU + {253313A4-C9F8-4A83-89A5-8FCB426004E0}.Release|Any CPU.ActiveCfg = Release|Any CPU + {253313A4-C9F8-4A83-89A5-8FCB426004E0}.Release|Any CPU.Build.0 = Release|Any CPU EndGlobalSection GlobalSection(SolutionProperties) = preSolution HideSolutionNode = FALSE |