From 752b4045fc9d58a22933c847a12d3788e1fda627 Mon Sep 17 00:00:00 2001 From: Ben Harris Date: Mon, 20 Dec 2021 01:52:10 -0500 Subject: day 20 --- aoc2021.test/DayTests.cs | 2 + aoc2021/Day20.cs | 80 +++++++++++++++++++++++++++++++++++++ aoc2021/aoc2021.csproj | 1 + aoc2021/input/day20.in | 102 +++++++++++++++++++++++++++++++++++++++++++++++ aoc2021/input/test20.in | 7 ++++ 5 files changed, 192 insertions(+) create mode 100644 aoc2021/Day20.cs create mode 100644 aoc2021/input/day20.in create mode 100644 aoc2021/input/test20.in diff --git a/aoc2021.test/DayTests.cs b/aoc2021.test/DayTests.cs index 27fca45..ff0346d 100644 --- a/aoc2021.test/DayTests.cs +++ b/aoc2021.test/DayTests.cs @@ -40,6 +40,7 @@ public class DayTests [DataRow(typeof(Day17), "12090", "5059")] [DataRow(typeof(Day18), "4289", "4807")] // [DataRow(typeof(Day19), "338", "9862")] // takes too long and i don't feel like optimizing + [DataRow(typeof(Day20), "5306", "17497")] public void CheckAllDays(Type dayType, string part1, string part2) { var s = Stopwatch.StartNew(); @@ -89,6 +90,7 @@ public class DayTests [DataRow(typeof(Day17), "45", "112")] [DataRow(typeof(Day18), "4140", "3993")] [DataRow(typeof(Day19), "79", "3621")] + [DataRow(typeof(Day20), "35", "3351")] public void CheckTestInputs(Type dayType, string part1, string part2) { Day.UseTestInput = true; diff --git a/aoc2021/Day20.cs b/aoc2021/Day20.cs new file mode 100644 index 0000000..0c54458 --- /dev/null +++ b/aoc2021/Day20.cs @@ -0,0 +1,80 @@ +namespace aoc2021; + +/// +/// Day 20: +/// +public sealed class Day20 : Day +{ + private readonly ImmutableArray _enhancementAlgorithm; + private readonly Image _initialImage; + + public Day20() : base(20, "Trench Map") + { + _enhancementAlgorithm = Input.First().Select(ch => ch == '#').ToImmutableArray(); + _initialImage = Parse(Input.Skip(2).ToList()); + } + + private Image Enhance(Image image, int count) => + Enumerable.Range(0, count).Aggregate(image, (current, _) => EnhanceOnce(current)); + + private Image EnhanceOnce(Image image) + { + var bounds = image.Bounds.Grow(); + + var result = bounds.Points + .Where(pt => _enhancementAlgorithm[image.GetEnhanceInput(pt)]) + .ToImmutableHashSet(); + + return new(bounds, result, image.InfiniteValue + ? _enhancementAlgorithm.Last() + : _enhancementAlgorithm.First()); + } + + private static Image Parse(IEnumerable grid) + { + var image = ImmutableHashSet.CreateBuilder(); + foreach (var (line, y) in grid.Select((a, i) => (a, i))) + { + image.UnionWith(line.Select((ch, i) => (x: i, isLit: ch == '#')) + .Where(p => p.isLit) + .Select(p => new Point(p.x, y))); + } + + var bounds = new Rect(image.Min(p => p.X), image.Min(p => p.Y), image.Max(p => p.X), image.Max(p => p.Y)); + return new(bounds, image.ToImmutable()); + } + + public override object Part1() => + Enhance(_initialImage, 2).PixelCount; + + public override object Part2() => + Enhance(_initialImage, 50).PixelCount; + + private record struct Point(int X, int Y); + + private record Rect(int MinX, int MinY, int MaxX, int MaxY) + { + public IEnumerable Points => + Enumerable.Range(MinY, MaxY - MinY + 1) + .SelectMany(_ => Enumerable.Range(MinX, MaxX - MinX + 1), (y, x) => new Point(x, y)); + + public bool Contains(Point pt) => pt.X >= MinX && pt.X <= MaxX && pt.Y >= MinY && pt.Y <= MaxY; + public Rect Grow() => new(MinX - 1, MinY - 1, MaxX + 1, MaxY + 1); + } + + private record Image(Rect Bounds, ImmutableHashSet Pixels, bool InfiniteValue = false) + { + private bool this[Point pt] => + Bounds.Contains(pt) ? Pixels.Contains(pt) : InfiniteValue; + public int PixelCount => Pixels.Count(Bounds.Contains); + + public int GetEnhanceInput(Point pt) + { + var values = + Enumerable.Range(pt.Y - 1, 3) + .SelectMany(_ => Enumerable.Range(pt.X - 1, 3), (yi, xi) => this[new(xi, yi)] ? 1 : 0); + + return values.Aggregate(0, (p, n) => (p << 1) | n); + } + } +} \ No newline at end of file diff --git a/aoc2021/aoc2021.csproj b/aoc2021/aoc2021.csproj index 7180a09..b554430 100644 --- a/aoc2021/aoc2021.csproj +++ b/aoc2021/aoc2021.csproj @@ -15,6 +15,7 @@ + diff --git a/aoc2021/input/day20.in b/aoc2021/input/day20.in new file mode 100644 index 0000000..a0ef982 --- /dev/null +++ b/aoc2021/input/day20.in @@ -0,0 +1,102 @@ +#.#.##...###......#.##..#..##....#.#.##...#..###....##...#####.#...#.#.#...#..###..#...#......####..#.#..########.#.###......##.##...###.###..######.....####.#..#.#..##..###..####..#....####..######.###..###.........##.##.###......##...#####.######..#.....##..#..#...#.#...#..#..#.#..#..#.##..#####..##.###.####...#..#....##....####...#.#.#.#.#.###...##..#....##......####.##.###...#####..##..#.#...#..#.#..####.###..###..#..####....#.#.##.#..#...#.#...##...#..#.#.##...##..##.####..#...###.#...#####.######..... + +...#.#...####.##.####.#...#..##.###..##...###..#.#.#.#...##....#####..#...##.#.##.#.#.....###.#....# +.##.####......##.#.#..#.#.#.#.##....#..##...###.#..#..#.##...##.#..##.###.#......###....#..##.###..# +####.#.####...#.#.#.#....#...#.##..###.#####..#...#.#..#.#.#.####...##.##..#.#.#..##.########..###.. +.####......#.##.##.##.#.#.....##..#.##....#######.##..##.####.#..#.#.#.#.#.###.#..#......#.#.#..###. +..#.#.####..#.#.#....##....#...######..##......#.......###.#..###.#.#.#.#.###.##..#.####.....#.##.#. +.#..##..#####.....#....#.#.#..###..#.###.#.###.##..##.#.###...#.##....##...#.###.#.##....#...###..## +.#.##.####.##.##..#..#.##..##.##..##..#.##..#.######..####.##.#.##....##..#.##.####.##...####....##. +##..#.#####.#.#.#..#...#...#.....##.#...#.##.#.#.#.#.....##...#.#.....##..##..###.#.####..#...##...# +##..#.#.##.####....##.#.#..#.#.#.###.#.#..#.#.....#..##.##.#.#...##....##.########.#..#.....##...### +######......#..#.#.####.#.###.#################.##..#.###.##.#...#..###.##..##..##..#..#.##..#.##.## +...##.#.###.........#...#...##.###...######..#.#...#........##.#...###.###.###...#...#.......#####.# +.#....##...##.#.#.##.#..########.#..#..#..#.##.##..###.##.#..##.#.#.#....#..##...###..###.##.#.##.## +.##.......##.#.#...#.##.##..#.#...#..####.#....###..#.#.....#.###....#...#.##.....#..#...##.##...### +..###.#..##..#....#...#.#.##.##.#.#.#.##.###.#####..###....#......##.....##..#..####.#....#####.#... +#...#.##.#.#.#...#####.#..##.######......##.#.#.#..#..#.##.######..#.##...##.##.##..#.#....##.###..# +##.##.##..#.##.########.##..##.##..####..#...####.######.####..####.#.#.#.#..#.##....#.##.#..#..###. +#..#####.##..#.###.#.##.##.###....###.#..#.####..##...#...###.#..#.....##...#..####.#...###.#.####.. +....#.#####..##.###..#..#.....##..##.#...#.#..##.##.#.##..##....#.##..##..###...##.#..#.#.###..#..#. +.#########..####.###...#.##.#.##..###....##.#..#...##....#.####.#..#.###.#.###....#......#...#.##.#. +.#######....####..##..#..#....#..#.####........#.##.#..##.######.#.###.###.###..##..####...##..#.##. +.#....###.####.###..#..##......##.##.##...#..##...##.####..##....######..####.#..##..#######.#.#...# +.#.####..########.#.#.######...##.###...#.....#...###....###..####.........#.###.#.....#.###.##..##. +...#.#.#..#.###..###.##.#.#.##...#..####.#..#.#...#....##.##.###.####.###...##..#.#......##..#...... +.#...######.#.##....##.##.##.....#...#.#.#######.#.#..###.#.#...##...#....#.#...#...#...##.###.###.. +.#...#..##.##.###.....##..#.###..####.##.########...#.##.....####...##...#.#..#....#...##.#.#..####. +..##...##.#..####...#.#...##.##..##..##..##..#..#...##..#..###.#..###..#..#....#..##....##...######. +##..###...##...##.#.#######..#.#.#..#...#.#..#..#....###..#.#####.##.#...##..#.....#..##.###..#.##.. +###.#.#..##.#.####..######....#.#.##....###.##.#.##..###.#.#...#..#####....#########...##..#....#.## +#..#####.....##.#.#.###.#.#.......####..#.##.#.####.#..#...#...#.#.###.######.##..##..#.......####.. +...#####..#.####.#..##.####.#####...#.#...#####.##.##..#..#...##.###..#.#.###.#....#..##..###.##.#.# +.##..#.##...##..#.#.##.#.#...#..####..#......##.###.#.##.#.#....####..#..#.####..###..#..#.#.###.#.# +#.#####..#.###.#.#.###.#.#...#.#....###.#..#.####...#####.#..##...##......###.##..#.###.#..####.#.#. +#..#......###...#.#...###....###.#####....#.#.###.##.#.#...##.....#.#####................#.###..#..# +#....##....#.#..####..#.##.####.###.###..####.##.....###.##.##...#..#...#.###...#####......#...#.... +##.#..#.##..##..##.#.#.#.#.##.######.#..#.#..###.#....#...#.#.#.#.....#....##..##....####..#.##..### +.##..#.#.####...##...#.######.....#.#...#####...##########.....##.###..#..######..#.#.....##..###..# +####..#.#...#...###.#####.##.#...#####..#.....#.#####.##..#.##.#.#.###.#...#.#.#####.......##.####.# +...###.##..###.#.#.#..##..#####......#####..#..##.##.....####..###...#...#####.....#.#....###...#.#. +..#..#.#.....##.#.#...#.......##.###.....###..#####.#####.#..###..###..#..#.#.#.#..###.#.###..#.#.## +####..#.##.##...#.#.#.##.#.#.#..#..#####..##.#.####.#..#######.####.#....#..###.##.#...##...###.#.#. +..#...#..#...#.####.##..##..#######.#.##.####.#..#......#.#.###.##.#..#.#.....##....#.#.#.#.##.###.# +.###..###.#...##..#....#.#..##..#.###.#...##.######.####.###.#..##..###.##.#.#....#.#...#...###.##.# +#....#.#....#..#####..##..#.##.#.#..##.##.#.....#.##..##..##........#.##...##.#.#..##.#.#..###....#. +##...#......#.#.#.#......#..#.#..#######...#.####..#...###..#...#..#...####..#.#.##....#...##..#.... +.####...##..###.##....#.#..#...#.##.#.##.#####.####.....#...#..#..#..##.#..####.#.#..###....##...#.# +#..####.#.#.######.####.#..#####..#.####...#.#.#.##..##..#.##.#.#.##.#..#..##.###.#.#..#.##..####.## +.#.###.....###....#...#..#.#####..#####..###..#..#...##...#.###..#..#.##..#..####..##..##########... +.#.....##..#.#.##...#...#.#.#.#.#..#.###...##.#.####.....#....#.....#.#.####..###.#######..#..##.#.. +....##...#...####..###.##.#.#.#...##.##...####..##..###..#.#.######.##.....#............#.######.#.. +..#....#....#..##.....#.#.##....###.##..###.#####...#....#.#.#....##.#.#.#.#.....#.#.....##...#.#.#. +.##...#.#.##.######..#.####..######.##.....##.##..##....#...#..##.#..#....#.##...#....#.##...##.#.## +#...#.#...##.#.##.##..#..####.#...###.#...##.##....#.#..##.......##....####...#...#.......#....####. +.#.##..###.##.##...##.#..##.###.#.#.#####.#.###...#.##....#...#..##..###..#..##.##.#..##.#.#....##.. +###.##.##..##.#.###.#...###.#..#.#.####..###.##.##..###.#####...##.....####.#.##.###..####.#..#.#.## +#....#.#.##...##.#...#......#####..###.#.##..#.####..##..#..##..###...###.#.#.##.##..####.###.....#. +#.##..#...#.#..##..##..#..###..##.#.###....#.#.####.##.##.###.#..#.##...#.###.##.#...#.#.##...#..... +#......#......#.#.#.######.##.#.###.###..#..####...##.#.######..#.....###..#.....#########.#####.##. +.#.#.#.##.#.###...#..#.##...#...##.#####.###..####.##..........####..#.#####.####..#.##.#####..###.. +...##.###.#.####.###.#.#.#.##...#####.#.......##.##...####.#..###....###.#..###..#.#####..#.###..#.. +#.#....#....###.###..##.##.##.##.#..###.##.....#.##.###...#.###....###.####...#.####...#.###.#.##### +##....#..#......##.###.....##.###.##..##.#.##...#..#.##.##.##..##.#...#...#...#.#.#.#.##.###.....### +.###..##.#....#..###..#.#.#..####.#.#.#.##.#...###.#.##....##..###.....#.##.....#......###.####..#.. +.....##.#...#####.#..###....#.#.#.#..##.###.#########.#.##..##.#.#.####..##..##..##.#..#.....#.#.#.. +#.####.#....##..#########...#.####..#.......#....##.#...##.#.##.##...#.#.#...#..###.#.#..#####.##..# +..#####...#.#.###......#....#...###...##.##...##.#..##.#.#..##.##.###.#....##.##...#####.......####. +#..##.###.....#...#.#.###.####..###.#....#..#...###.##.....#.##..##..###..##.##.###..#.#..#..#...#.. +##.###.....##.....##.#######.#.##....###.####.....#..##.#.###.#.#......##..####.#.####.##.#.##...### +###..#..######..#.#.#...##..#.#...####...##........####....#...#..#########.#.###.##.##.#####...##.. +..#####.#.####...#.######.#..#.#.#.#....#...#.###...###.###..#...##..##..#####..#####.###..#.#.#.##. +##.#..###..###.#.......##..####..######.#..#.####.##....#####.#.#.###.#..###..########..####..#..#.. +##.#.####....#.#.##..#..#..######.#..##.#.##..###.#..#.#....#.##...#.##.####...####.....##.##.##..## +####..##....#..#.#.#.....#..#...#.#...#..###...##.#.###.#...#.##..##..###..###....#..########.#....# +##..#...#.#.....#####..##..##....#......##.#.#...#..#####....##..#.##.........#.#.##...#.#.#..#.#.#. +##...###..#.###...###.###.##...##.#.##...#...####..#.#.#.###...######......##..###.....#..#.##...#.# +#.#....#.####.##.#.#.#.##..#.##.......#..##..#..##.##.##.#..##..#.##.#.#####.......#####..#........# +.#.#..###..#....#.#.....#.##..#....#..##..##..##.#....###..#.######.#.#...#..###......####....####.. +.#...###.....#...#....#.##.##.#........####.####..#....#..#....#.#.#..#.#.##.#.######.#...###.##.### +...#.#.#..##.#..#.##.#.#.##.##...##....###.....#####...#.#..#.##.#.####..##..#..#....#.##.##.##..##. +####....###..#..####.##.#..##.#..##.#.......###..#.##....#..#####.##..##.#...####..#.#..#.#.####...# +.#..###....#..#####.##..##...#.#...#.##.#..#....#.#.##.#.#.......#.#....#...#....#...#...#..##.#.... +#.#...####.#.##..###..#.##.##.#.##.#..##.#.##.###..#.###.#..##.#..#..#.#.####.#.###.##..#..#....##.. +.....#...#.####.#..##..#######.#.#.#...#.#####.#.#...#...####.....###.###.##..##..#..#..#.#..######. +#..#.#.####..###.###..#.##...##..###.##.###..#.####.#####.....###..###..#.#...#.#.########.#.##..##. +####..###..#...###.#.##.#.###..#.#...##.##....#####......###..##....###..#.#.#..##..######..####.#.. +...#....##.###..#.##.##..##..#.#.##.##...######....#....##.#.#.#.##.#...####...##...#.####.#.#.##.#. +...##...#.##..###.###...#.#.#.#.##.####...#.###..####..#...###.....#....####..##.#..##......#..#.#.. +.#.#..#.....#.#.###....#.###.#..#..###...#.#####....#.....###.#..###.##.#..#...#.####..#.###.####... +.####..#..##....#.##.##.#...#.###....#....#.##..#...#...##...#...###....###.##.#..#.###.#.##.#..###. +##.###.#...#.....#.#.#......#.##..#.#.##.##...###...#.###.####..###..#..###.#..#.#...#...#......##.. +######...##.##..#...##.#.###.#.####.#.##.##...###.#.#.....###.##.##....##.##....##.##.#..##..#.##### +#...#..#...####.#.###.##...#...#..##.#..##.....##.#..#.#..#....##.##..##..#..#.###..###.#......#..## +.##.##.######..#.##....#...#.....#.#.###....######..#.#..##.###......##.#..#.#.####..#...###.###.#.# +..#.#...##.#.....######.....####...##.###.#..#..#..######....###.....##...###..#.#####.#..##.###.### +###........#.##..##.........#.##.....#..#.####.##...........###...#.#.###..###..#..###...#......#### +#...#.......#.##.#.#.##.#.#.##.#.#..#...##..#..#####.#.##.##.#####.####...#..##.#.###...#..##..##... +..#......#..#####.....#.##.....#..#..#####..#.....###..##.####.###...#####.#...##.#..#.......#.....# +###..#.#.###.#.#..##..##..##...#.#........#...#...#.#.#..#.##.##.....#.##.###############.##...#.#.. +.#.#....#..##.......#........#..#...#.#.##.#...##.#.#.#.#.#..##...#.####.##.#.#...#...##.##########. +.######.##.........#.########....#.######....##.##.#..####.###.##.#..##..##..####.#...#####...##.#.# +...#..#.#..#.#..#.#.#########.#..##.#.#.#.#.#########....#...####...#.#..#.......#.##....####....### diff --git a/aoc2021/input/test20.in b/aoc2021/input/test20.in new file mode 100644 index 0000000..8fa4bd4 --- /dev/null +++ b/aoc2021/input/test20.in @@ -0,0 +1,7 @@ +..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..# + +#..#. +#.... +##..# +..#.. +..### -- cgit 1.4.1