aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTomasz Chojnacki <tomaszchojnacki2001@gmail.com>2022-12-29 23:01:54 +0100
committerTomasz Chojnacki <tomaszchojnacki2001@gmail.com>2022-12-29 23:01:54 +0100
commit62a2e6fb7175f683a4d315374efd5bc4ea331dc5 (patch)
tree6424e50caf9a0c6bb42d8ebc42698558113e5db4
parentee408551b5327b196cd94bb1b857bcdc9f8b10b1 (diff)
downloadgleam_aoc2020-62a2e6fb7175f683a4d315374efd5bc4ea331dc5.tar.gz
gleam_aoc2020-62a2e6fb7175f683a4d315374efd5bc4ea331dc5.zip
Finish day 23
Diffstat
-rw-r--r--README.md2
-rw-r--r--aoc-2022-dotnet/Common/Vec2.fs86
-rw-r--r--aoc-2022-dotnet/Day12/Program.fs5
-rw-r--r--aoc-2022-dotnet/Day23/Day23.fsproj22
-rw-r--r--aoc-2022-dotnet/Day23/Program.fs89
-rw-r--r--aoc-2022-dotnet/README.md6
-rw-r--r--aoc-2022-dotnet/aoc-2022-dotnet.sln8
7 files changed, 182 insertions, 36 deletions
diff --git a/README.md b/README.md
index 608545e..ea19602 100644
--- a/README.md
+++ b/README.md
@@ -10,7 +10,7 @@ Repository storing my solutions to Advent of Code. See other people's solutions
### [2022](aoc-2022-dotnet)
![F#](https://img.shields.io/badge/F%23-grey?logo=.NET)
-![Stars](https://img.shields.io/badge/🌟%20stars-41/50-orange)
+![Stars](https://img.shields.io/badge/🌟%20stars-43/50-orange)
[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 61b313d..438135b 100644
--- a/aoc-2022-dotnet/Common/Vec2.fs
+++ b/aoc-2022-dotnet/Common/Vec2.fs
@@ -4,8 +4,8 @@
type Vec2 =
| Vec2 of int * int
- static member x(Vec2 (x, _)) = x
- static member y(Vec2 (_, y)) = y
+ static member inline x(Vec2 (x, _)) = x
+ static member inline y(Vec2 (_, y)) = y
static member zero = Vec2(0, 0)
static member up = Vec2(0, 1)
@@ -18,43 +18,73 @@ type Vec2 =
static member downLeft = Vec2(-1, -1)
static member downRight = Vec2(1, -1)
+ static member directionsUp =
+ Set [ Vec2.upLeft
+ Vec2.up
+ Vec2.upRight ]
+
+ static member directionsRight =
+ Set [ Vec2.upRight
+ Vec2.right
+ Vec2.downRight ]
+
+ static member directionsDown =
+ Set [ Vec2.downLeft
+ Vec2.down
+ Vec2.downRight ]
+
+ static member directionsLeft =
+ Set [ Vec2.upLeft
+ Vec2.left
+ Vec2.downLeft ]
+
static member directions4 =
- [ Vec2.up
- Vec2.right
- Vec2.down
- Vec2.left ]
+ Set [ Vec2.up
+ Vec2.right
+ Vec2.down
+ Vec2.left ]
static member directions8 =
- [ Vec2.up
- Vec2.upRight
- Vec2.right
- Vec2.downRight
- Vec2.down
- Vec2.downLeft
- Vec2.left
- Vec2.upLeft ]
-
- static member inline (~-) = Vec2.map (~-)
- static member inline (+)(Vec2 (x1, y1), Vec2 (x2, y2)) = Vec2(x1 + x2, y1 + y2)
- static member inline (-)(v1, v2) = v1 + Vec2.op_UnaryNegation (v2)
- static member inline (*)(v1, k) = Vec2.map ((*) k) v1
+ Set [ Vec2.up
+ Vec2.upRight
+ Vec2.right
+ Vec2.downRight
+ Vec2.down
+ Vec2.downLeft
+ Vec2.left
+ Vec2.upLeft ]
+
+ static member inline private _map f (Vec2 (x, y)) = Vec2(f x, f y)
+ 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 map f (Vec2 (x, y)) = Vec2(f x, f y)
- static member inline sign = Vec2.map sign
+ 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 neighbours8 v = List.map ((+) v) Vec2.directions8
+
+ static member inline private _nb d v = Set.map ((+) v) d
+ static member neighboursUp = Vec2._nb Vec2.directionsUp
+ static member neighboursRight = Vec2._nb Vec2.directionsRight
+ static member neighboursDown = Vec2._nb Vec2.directionsDown
+ static member neighboursLeft = Vec2._nb Vec2.directionsLeft
+ static member neighbours4 = Vec2._nb Vec2.directions4
+ static member neighbours8 = Vec2._nb Vec2.directions8
+
+ static member boundingRectangle vs =
+ (Seq.reduce (Vec2._combine min) vs, Seq.reduce (Vec2._combine max) vs)
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))
+ Seq.map (fun y -> Vec2(x1, y)) (seq { min y1 y2 .. max y1 y2 })
elif y1 = y2 then
- seq { min x1 x2 .. max x1 x2 }
- |> Seq.map (fun x -> Vec2(x, y1))
+ Seq.map (fun x -> Vec2(x, y1)) (seq { min x1 x2 .. max x1 x2 })
else
failwith "Points must be in a vertical or horizontal line!"
@@ -64,4 +94,4 @@ type Vec2 =
&& row >= 0
&& row < Array2D.length1 matrix
- static member toIndexOf matrix (Vec2 (col, row)) = (Array2D.length2 matrix) * row + col
+ static member inline toIndexOf matrix (Vec2 (col, row)) = (Array2D.length2 matrix) * row + col
diff --git a/aoc-2022-dotnet/Day12/Program.fs b/aoc-2022-dotnet/Day12/Program.fs
index 77417c5..7e1a409 100644
--- a/aoc-2022-dotnet/Day12/Program.fs
+++ b/aoc-2022-dotnet/Day12/Program.fs
@@ -72,11 +72,10 @@ let solution distanceCalculation =
>> Util.mapEachToSeq (fun matrix pos square ->
(square,
Vec2.neighbours4 pos
- |> Seq.filter (fun np ->
+ |> Set.filter (fun np ->
Vec2.inMatrix matrix np
&& Square.canTraverse square (Util.mAt matrix np))
- |> Seq.map (Vec2.toIndexOf matrix)
- |> Set))
+ |> Set.map (Vec2.toIndexOf matrix)))
>> Seq.indexed
>> Map.ofSeq
>> Graph
diff --git a/aoc-2022-dotnet/Day23/Day23.fsproj b/aoc-2022-dotnet/Day23/Day23.fsproj
new file mode 100644
index 0000000..b9a3919
--- /dev/null
+++ b/aoc-2022-dotnet/Day23/Day23.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/Day23/Program.fs b/aoc-2022-dotnet/Day23/Program.fs
new file mode 100644
index 0000000..df30361
--- /dev/null
+++ b/aoc-2022-dotnet/Day23/Program.fs
@@ -0,0 +1,89 @@
+module Day23
+
+open System.IO
+open Common
+
+type Grove =
+ { Elves: Set<Vec2>
+ Intents: (Vec2 * (Vec2 -> Set<Vec2>)) list }
+
+ static member private initialIntents =
+ [ Vec2.up, Vec2.neighboursUp
+ Vec2.down, Vec2.neighboursDown
+ Vec2.left, Vec2.neighboursLeft
+ Vec2.right, Vec2.neighboursRight ]
+
+ static member private cycleIntents = Util.cycle >> snd
+
+ static member private positionsFree elves = Set.forall (Util.notIn elves)
+
+ static member private isElfUnsettled elves =
+ Vec2.neighbours8
+ >> Grove.positionsFree elves
+ >> not
+
+ static member isUnsettled({ Elves = elves }) =
+ Set.exists (Grove.isElfUnsettled elves) elves
+
+ static member parse input =
+ { Elves =
+ input
+ |> Seq.rev // bottom left should be (0, 0)
+ |> array2D
+ |> Util.mapEachToSeq (fun _ pos char -> if char = '#' then Some(pos) else None)
+ |> Seq.choose id
+ |> Set
+ Intents = Grove.initialIntents }
+
+ static member private proposeNextPos ({ Elves = elves; Intents = intents }) elfPos =
+ if Grove.isElfUnsettled elves elfPos then
+ intents
+ |> List.tryPick (fun (offset, neighbours) ->
+ match elfPos |> neighbours |> Grove.positionsFree elves with
+ | true -> Some(elfPos + offset)
+ | false -> None)
+ |> Option.defaultValue elfPos
+ else
+ elfPos
+
+ static member doRound grove =
+ { Elves =
+ grove.Elves
+ |> Set.fold
+ (fun map oldPos ->
+ Map.change
+ (Grove.proposeNextPos grove oldPos) // destination position
+ (fun ps -> Some(oldPos :: Option.defaultValue [] ps)) // list of source positions
+ map)
+ Map.empty
+ |> Seq.collect (fun kv ->
+ match kv.Value with
+ | [ _ ] -> [ kv.Key ] // only one elf proposes the position, keep new position
+ | ps -> ps) // many elves propose the position, revert to old positions
+ |> Set
+ Intents = Grove.cycleIntents grove.Intents }
+
+let solution1 input =
+ let grove =
+ input
+ |> Grove.parse
+ |> Util.composition 10 Grove.doRound
+
+ let (Vec2 (minX, minY), Vec2 (maxX, maxY)) = Vec2.boundingRectangle grove.Elves
+ let area = (maxX - minX + 1) * (maxY - minY + 1)
+ area - Set.count grove.Elves
+
+let solution2 =
+ Grove.parse
+ >> Seq.unfold (fun grove -> Some(grove, Grove.doRound grove))
+ >> Seq.takeWhile Grove.isUnsettled
+ >> Seq.length
+ >> (+) 1
+
+let test = File.ReadLines("test.txt")
+assert (solution1 test = 110)
+assert (solution2 test = 20)
+
+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 97d275f..5bb91e0 100644
--- a/aoc-2022-dotnet/README.md
+++ b/aoc-2022-dotnet/README.md
@@ -1,6 +1,6 @@
# Advent of Code 2022 in F#
![F#](https://img.shields.io/badge/F%23-grey?logo=.NET)
-![Stars](https://img.shields.io/badge/🌟%20stars-41/50-orange)
+![Stars](https://img.shields.io/badge/🌟%20stars-43/50-orange)
| Day | Problem Name | Part 1 | Part 2 | Practiced Concepts |
| :----: | ---------------------------------------------------------------- | :----: | :----: | ---------------------------------------------------- |
@@ -20,12 +20,12 @@
| **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) | :star: | :star: | graphs, dynamic programming, `Seq` |
-| **17** | [Pyroclastic Flow](https://adventofcode.com/2022/day/17) | :star: | :star: | cycle detection, bitwise operators, hashing |
+| **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 |
| **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) | | | |
+| **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) | | | |
| **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 9cfa122..3b78609 100644
--- a/aoc-2022-dotnet/aoc-2022-dotnet.sln
+++ b/aoc-2022-dotnet/aoc-2022-dotnet.sln
@@ -54,7 +54,9 @@ Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day20", "Day20\Day20.fsproj
EndProject
Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day21", "Day21\Day21.fsproj", "{7168DBF8-A03D-43A5-A429-FBAF87D55FF6}"
EndProject
-Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "Day25", "Day25\Day25.fsproj", "{3CBC73E3-821C-45FC-85F8-877C29810E67}"
+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}"
EndProject
Global
GlobalSection(SolutionConfigurationPlatforms) = preSolution
@@ -154,6 +156,10 @@ Global
{3CBC73E3-821C-45FC-85F8-877C29810E67}.Debug|Any CPU.Build.0 = Debug|Any CPU
{3CBC73E3-821C-45FC-85F8-877C29810E67}.Release|Any CPU.ActiveCfg = Release|Any CPU
{3CBC73E3-821C-45FC-85F8-877C29810E67}.Release|Any CPU.Build.0 = Release|Any CPU
+ {E6AEEB69-7669-4026-AC28-94D7B4467838}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+ {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
EndGlobalSection
GlobalSection(SolutionProperties) = preSolution
HideSolutionNode = FALSE
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-23 22:12:21 +0000