aboutsummaryrefslogtreecommitdiff
path: root/aoc-2022-dotnet
diff options
context:
space:
mode:
authorTomasz Chojnacki <tomaszchojnacki2001@gmail.com>2022-12-21 11:45:04 +0100
committerTomasz Chojnacki <tomaszchojnacki2001@gmail.com>2022-12-21 11:45:04 +0100
commit9e378a9f80260c2f729daaf83d8e74f7bad70b16 (patch)
treedb61e67a7222cd0666ea7fe4976e2fded327599a /aoc-2022-dotnet
parenta8c844a12fa2d91410fda7b37f08c58f5be34ed9 (diff)
downloadgleam_aoc2020-9e378a9f80260c2f729daaf83d8e74f7bad70b16.tar.gz
gleam_aoc2020-9e378a9f80260c2f729daaf83d8e74f7bad70b16.zip
Finish day 17
Diffstat (limited to 'aoc-2022-dotnet')
-rw-r--r--aoc-2022-dotnet/Common/Util.fs16
-rw-r--r--aoc-2022-dotnet/Common/Vec2.fs13
-rw-r--r--aoc-2022-dotnet/Day17/Day17.fsproj26
-rw-r--r--aoc-2022-dotnet/Day17/Program.fs155
-rw-r--r--aoc-2022-dotnet/README.md56
-rw-r--r--aoc-2022-dotnet/aoc-2022-dotnet.sln10
6 files changed, 245 insertions, 31 deletions
diff --git a/aoc-2022-dotnet/Common/Util.fs b/aoc-2022-dotnet/Common/Util.fs
index acf89af..568f2c2 100644
--- a/aoc-2022-dotnet/Common/Util.fs
+++ b/aoc-2022-dotnet/Common/Util.fs
@@ -38,7 +38,11 @@ module Util =
let mAt matrix (Vec2 (col, row)) = Array2D.get matrix row col
- let composition n f = List.replicate n f |> List.reduce (>>)
+ let rec composition n f x =
+ if n = 0 then
+ x
+ else
+ composition (n - 1) f (f x)
let notIn set element = not <| Set.contains element set
@@ -51,6 +55,16 @@ module Util =
| h :: t -> min h x :: (insertSorted (max h x) t)
| [] -> [ x ]
+ let liftList xs =
+ match List.forall Option.isSome xs with
+ | true -> Some(List.map Option.get xs)
+ | false -> None
+
+ let cycle =
+ function
+ | h :: t -> h, t @ [ h ]
+ | [] -> failwith "Empty list!"
+
let topN n xs =
Seq.fold
(fun acc x ->
diff --git a/aoc-2022-dotnet/Common/Vec2.fs b/aoc-2022-dotnet/Common/Vec2.fs
index 8835a5a..61b313d 100644
--- a/aoc-2022-dotnet/Common/Vec2.fs
+++ b/aoc-2022-dotnet/Common/Vec2.fs
@@ -13,6 +13,8 @@ type Vec2 =
static member down = Vec2(0, -1)
static member left = Vec2(-1, 0)
+ static member upRight = Vec2(1, 1)
+ static member upLeft = Vec2(-1, 1)
static member downLeft = Vec2(-1, -1)
static member downRight = Vec2(1, -1)
@@ -22,6 +24,16 @@ type Vec2 =
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)
@@ -34,6 +46,7 @@ type Vec2 =
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 lineBetween(Vec2 (x1, y1), Vec2 (x2, y2)) =
if x1 = x2 then
diff --git a/aoc-2022-dotnet/Day17/Day17.fsproj b/aoc-2022-dotnet/Day17/Day17.fsproj
new file mode 100644
index 0000000..795d59c
--- /dev/null
+++ b/aoc-2022-dotnet/Day17/Day17.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="FSharpPlus" Version="1.3.2" />
+ </ItemGroup>
+
+ <ItemGroup>
+ <ProjectReference Include="..\Common\Common.fsproj" />
+ </ItemGroup>
+
+</Project>
diff --git a/aoc-2022-dotnet/Day17/Program.fs b/aoc-2022-dotnet/Day17/Program.fs
new file mode 100644
index 0000000..70374f4
--- /dev/null
+++ b/aoc-2022-dotnet/Day17/Program.fs
@@ -0,0 +1,155 @@
+module Day17
+
+open System.IO
+open FSharpPlus
+open Common
+
+type Dir =
+ | Left
+ | Right
+
+ static member movesFromInput(input: string) =
+ input
+ |> String.trimWhiteSpaces
+ |> Seq.map Dir.fromChar
+ |> List.ofSeq
+
+ static member private fromChar =
+ function
+ | '<' -> Left
+ | '>' -> Right
+ | c -> failwithf "Invalid character: %c" c
+
+ static member shiftOp =
+ function
+ | Left -> (<<<)
+ | Right -> (>>>)
+
+module Row =
+ let full = 0b1111111uy
+ let empty = 0b0000000uy
+
+ let private countBlocks row =
+ let rec helper =
+ function
+ | 0uy -> 0
+ | n -> int (n &&& 1uy) + helper (n >>> 1)
+
+ helper (row &&& full)
+
+ let shift dir shape settled =
+ let shape' = (Dir.shiftOp dir) shape 1
+
+ let overflow = countBlocks shape' <> countBlocks shape
+ let collision = shape' &&& settled <> empty
+
+ match overflow || collision with
+ | true -> None
+ | false -> Some(shape')
+
+module Chamber =
+ let private shapes =
+ [ [ 0b0011110uy ] // horizontal line
+
+ [ 0b0001000uy
+ 0b0011100uy
+ 0b0001000uy ] // cross
+
+ [ 0b0000100uy
+ 0b0000100uy
+ 0b0011100uy ] // L-shape
+
+ [ 0b0010000uy
+ 0b0010000uy
+ 0b0010000uy
+ 0b0010000uy ] // vertical line
+
+ [ 0b0011000uy; 0b0011000uy ] ] // square
+
+ let private makeSpaceFor shape settled =
+ (List.replicate (List.length shape + 3) Row.empty)
+ @ settled
+
+ let private shift dir (shape, settled) =
+ let shiftedRows = List.map2Shortest (Row.shift dir) shape settled
+
+ let shape =
+ shiftedRows
+ |> Util.liftList
+ |> Option.defaultValue shape
+
+ shape, settled
+
+ let private fall (shape, settled) =
+ let (shape', settled') =
+ match settled with
+ | [ _ ] -> [], shape
+ | h :: t when h = Row.empty -> shape, t
+ | _ -> Row.empty :: shape, settled
+
+ let collision =
+ List.map2Shortest (&&&) shape' settled'
+ |> List.exists ((<>) Row.empty)
+
+ if collision then
+ [],
+ (List.map2Shortest (|||) shape settled)
+ @ List.skip (List.length shape) settled
+ else
+ shape', settled'
+
+ let private stateFingerprint moves shapes tower =
+ hash (moves, List.head shapes, List.truncate 128 tower)
+
+ let towerHeight n moves =
+ let rec helper (moves, shapes, tower, cache, n) =
+ let cacheKey = stateFingerprint moves shapes tower
+ let towerHeight = int64 <| List.length tower
+
+ if Map.containsKey cacheKey cache then
+ let (oldCount, oldHeight) = cache[cacheKey]
+ let countDiff = oldCount - n
+ let heightDiff = towerHeight - oldHeight
+ let skippedCycles = n / countDiff
+ let skippedHeight = skippedCycles * heightDiff
+ let leftoverCount = n - skippedCycles * countDiff + 1L
+
+ skippedHeight
+ + helper (moves, shapes, tower, Map.empty, leftoverCount)
+ else
+ let cache = cache |> Map.add cacheKey (n, towerHeight)
+
+ let (shape, shapes) = Util.cycle shapes
+ let tower = tower |> makeSpaceFor shape
+
+ let rec step moves shape tower =
+ let (move, moves) = Util.cycle moves
+ let (shape, tower) = shift move (shape, tower)
+ let (shape, tower) = fall (shape, tower)
+
+ if List.isEmpty shape then
+ (moves, tower)
+ else
+ step moves shape tower
+
+ let (moves, tower) = step moves shape tower
+
+ let n = n - 1L
+
+ if n = 0L then
+ towerHeight
+ else
+ helper (moves, shapes, tower, cache, n)
+
+ helper (moves, shapes, [], Map.empty, n)
+
+let solution n =
+ Dir.movesFromInput >> Chamber.towerHeight n
+
+let test = File.ReadAllText("test.txt")
+assert (solution 2022 test = 3068)
+assert (solution 1_000_000_000_000L test = 1514285714288L)
+
+let input = File.ReadAllText("input.txt")
+printfn "%d" <| solution 2022 input
+printfn "%d" <| solution 1_000_000_000_000L input
diff --git a/aoc-2022-dotnet/README.md b/aoc-2022-dotnet/README.md
index 506101c..25192a0 100644
--- a/aoc-2022-dotnet/README.md
+++ b/aoc-2022-dotnet/README.md
@@ -1,31 +1,31 @@
# Advent of Code 2022 in F#
![F#](https://img.shields.io/badge/F%23-grey?logo=.NET)
-![Stars](https://img.shields.io/badge/🌟%20stars-32/50-orange)
+![Stars](https://img.shields.io/badge/🌟%20stars-34/50-orange)
-| Day | Problem Name | Part 1 | Part 2 | Practiced Concepts |
-| :----: | --------------------------------------------------------------- | :----: | :----: | ---------------------------------------------------- |
-| **01** | [Calorie Counting](https://adventofcode.com/2022/day/1) | :star: | :star: | `Seq`, `\|>` and `>>`, FSharpPlus |
-| **02** | [Rock Paper Scissors](https://adventofcode.com/2022/day/2) | :star: | :star: | ADTs, type members, patterns |
-| **03** | [Rucksack Reorganization](https://adventofcode.com/2022/day/3) | :star: | :star: | ASCII code, `Set` |
-| **04** | [Camp Cleanup](https://adventofcode.com/2022/day/4) | :star: | :star: | ranges, FParsec |
-| **05** | [Supply Stacks](https://adventofcode.com/2022/day/5) | :star: | :star: | functional stacks, `List.transpose`, `Seq.fold` |
-| **06** | [Tuning Trouble](https://adventofcode.com/2022/day/6) | :star: | :star: | `Seq.windowed`, `Set` |
-| **07** | [No Space Left On Device](https://adventofcode.com/2022/day/7) | :star: | :star: | patterns, ADTs, FParsec |
-| **08** | [Treetop Tree House](https://adventofcode.com/2022/day/8) | :star: | :star: | `Array2D`, slices |
-| **09** | [Rope Bridge](https://adventofcode.com/2022/day/9) | :star: | :star: | vectors, Chebyshev distance, `Seq.scan` |
-| **10** | [Cathode-Ray Tube](https://adventofcode.com/2022/day/10) | :star: | :star: | `Map`, `Seq.fold` |
-| **11** | [Monkey in the Middle](https://adventofcode.com/2022/day/11) | :star: | :star: | records, type abbrevs, `List.choose`, tail recursion |
-| **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) | :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) | | | |
-| **18** | ??? | | | |
-| **19** | ??? | | | |
-| **20** | ??? | | | |
-| **21** | ??? | | | |
-| **22** | ??? | | | |
-| **23** | ??? | | | |
-| **24** | ??? | | | |
-| **25** | ??? | | | |
+| Day | Problem Name | Part 1 | Part 2 | Practiced Concepts |
+| :----: | ---------------------------------------------------------------- | :----: | :----: | ---------------------------------------------------- |
+| **01** | [Calorie Counting](https://adventofcode.com/2022/day/1) | :star: | :star: | `Seq`, `\|>` and `>>`, FSharpPlus |
+| **02** | [Rock Paper Scissors](https://adventofcode.com/2022/day/2) | :star: | :star: | ADTs, type members, patterns |
+| **03** | [Rucksack Reorganization](https://adventofcode.com/2022/day/3) | :star: | :star: | ASCII code, `Set` |
+| **04** | [Camp Cleanup](https://adventofcode.com/2022/day/4) | :star: | :star: | ranges, FParsec |
+| **05** | [Supply Stacks](https://adventofcode.com/2022/day/5) | :star: | :star: | functional stacks, `List.transpose`, `Seq.fold` |
+| **06** | [Tuning Trouble](https://adventofcode.com/2022/day/6) | :star: | :star: | `Seq.windowed`, `Set` |
+| **07** | [No Space Left On Device](https://adventofcode.com/2022/day/7) | :star: | :star: | patterns, ADTs, FParsec |
+| **08** | [Treetop Tree House](https://adventofcode.com/2022/day/8) | :star: | :star: | `Array2D`, slices |
+| **09** | [Rope Bridge](https://adventofcode.com/2022/day/9) | :star: | :star: | vectors, Chebyshev distance, `Seq.scan` |
+| **10** | [Cathode-Ray Tube](https://adventofcode.com/2022/day/10) | :star: | :star: | `Map`, `Seq.fold` |
+| **11** | [Monkey in the Middle](https://adventofcode.com/2022/day/11) | :star: | :star: | records, type abbrevs, `List.choose`, tail recursion |
+| **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) | :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 |
+| **18** | [Boiling Boulders](https://adventofcode.com/2022/day/18) | | | |
+| **19** | [Not Enough Minerals](https://adventofcode.com/2022/day/19) | | | |
+| **20** | [Grove Positioning System](https://adventofcode.com/2022/day/20) | | | |
+| **21** | [Monkey Math](https://adventofcode.com/2022/day/21) | | | |
+| **22** | ??? | | | |
+| **23** | ??? | | | |
+| **24** | ??? | | | |
+| **25** | ??? | | | |
diff --git a/aoc-2022-dotnet/aoc-2022-dotnet.sln b/aoc-2022-dotnet/aoc-2022-dotnet.sln
index e533c60..c8afbfc 100644
--- a/aoc-2022-dotnet/aoc-2022-dotnet.sln
+++ b/aoc-2022-dotnet/aoc-2022-dotnet.sln
@@ -42,9 +42,11 @@ Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day13", "Day13\Day13.fsproj
EndProject
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}"
+Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "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}"
+Project("{6EC3EE1D-3C4E-46DD-8F32-0CC8E7565705}") = "Day16", "Day16\Day16.fsproj", "{4CABEF49-D9D8-4211-8714-95E118820C8F}"
+EndProject
+Project("{F2A71F9B-5D33-465A-A702-920D77279786}") = "Day17", "Day17\Day17.fsproj", "{7DEA7521-24E1-4ED4-9530-70E91731ADB3}"
EndProject
Global
GlobalSection(SolutionConfigurationPlatforms) = preSolution
@@ -124,6 +126,10 @@ Global
{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
+ {7DEA7521-24E1-4ED4-9530-70E91731ADB3}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+ {7DEA7521-24E1-4ED4-9530-70E91731ADB3}.Debug|Any CPU.Build.0 = Debug|Any CPU
+ {7DEA7521-24E1-4ED4-9530-70E91731ADB3}.Release|Any CPU.ActiveCfg = Release|Any CPU
+ {7DEA7521-24E1-4ED4-9530-70E91731ADB3}.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 10:32:41 +0000