From ae4a45ddadb5ba403824602c81c909507f6bc31d Mon Sep 17 00:00:00 2001 From: Ben Harris Date: Sat, 4 Dec 2021 12:52:07 -0500 Subject: day 4 --- aoc2021.test/DayTests.cs | 2 + aoc2021/Day04.cs | 85 +++++++ aoc2021/input/day04.in | 601 +++++++++++++++++++++++++++++++++++++++++++++++ aoc2021/input/test04.in | 19 ++ 4 files changed, 707 insertions(+) create mode 100644 aoc2021/Day04.cs create mode 100644 aoc2021/input/day04.in create mode 100644 aoc2021/input/test04.in diff --git a/aoc2021.test/DayTests.cs b/aoc2021.test/DayTests.cs index df97b57..6e2a340 100644 --- a/aoc2021.test/DayTests.cs +++ b/aoc2021.test/DayTests.cs @@ -7,6 +7,7 @@ public class DayTests [DataRow(typeof(Day01), "1616", "1645")] [DataRow(typeof(Day02), "2272262", "2134882034")] [DataRow(typeof(Day03), "3009600", "6940518")] + [DataRow(typeof(Day04), "8580", "9576")] public void CheckAllDays(Type dayType, string part1, string part2) { var s = Stopwatch.StartNew(); @@ -40,6 +41,7 @@ public class DayTests [DataRow(typeof(Day01), "7", "5")] [DataRow(typeof(Day02), "150", "900")] [DataRow(typeof(Day03), "198", "230")] + [DataRow(typeof(Day04), "4512", "1924")] public void CheckTestInputs(Type dayType, string part1, string part2) { Day.UseTestInput = true; diff --git a/aoc2021/Day04.cs b/aoc2021/Day04.cs new file mode 100644 index 0000000..dc7fca9 --- /dev/null +++ b/aoc2021/Day04.cs @@ -0,0 +1,85 @@ +namespace aoc2021; + +/// +/// Day 4: +/// +public sealed class Day04 : Day +{ + private readonly List _call; + private readonly List> _boards; + + public Day04() : base(4, "Giant Squid") + { + _call = new(Input.First().Split(',').Select(int.Parse).ToList()); + _boards = new(); + + List currentBoard = new(); + foreach (var line in Input.Skip(2)) + { + if (string.IsNullOrWhiteSpace(line)) + { + _boards.Add(currentBoard); + currentBoard = new(); + continue; + } + + currentBoard.AddRange(line + .Split(' ', StringSplitOptions.TrimEntries | StringSplitOptions.RemoveEmptyEntries).Select(int.Parse)); + } + + if (currentBoard.Any()) _boards.Add(currentBoard); + } + + public override string Part1() + { + int i = 1, b = FirstWin(i); + while (b == -1) + { + i++; + b = FirstWin(i); + } + + var called = _call.Take(i).ToHashSet(); + return $"{called.Last() * _boards[b].Where(x => !called.Contains(x)).Sum()}"; + } + + private int FirstWin(int i) + { + var c = _call.Take(i).ToHashSet(); + for (var j = 0; j < _boards.Count; j++) + if (HasWin(c, _boards[j])) return j; + return -1; + } + + private static bool HasWin(IReadOnlySet c, IReadOnlyList b) => + c.Contains(b[0]) && c.Contains(b[1]) && c.Contains(b[2]) && c.Contains(b[3]) && c.Contains(b[4]) || + c.Contains(b[5]) && c.Contains(b[6]) && c.Contains(b[7]) && c.Contains(b[8]) && c.Contains(b[9]) || + c.Contains(b[10]) && c.Contains(b[11]) && c.Contains(b[12]) && c.Contains(b[13]) && c.Contains(b[14]) || + c.Contains(b[15]) && c.Contains(b[16]) && c.Contains(b[17]) && c.Contains(b[18]) && c.Contains(b[19]) || + c.Contains(b[20]) && c.Contains(b[21]) && c.Contains(b[22]) && c.Contains(b[23]) && c.Contains(b[24]) || + c.Contains(b[0]) && c.Contains(b[5]) && c.Contains(b[10]) && c.Contains(b[15]) && c.Contains(b[20]) || + c.Contains(b[1]) && c.Contains(b[6]) && c.Contains(b[11]) && c.Contains(b[16]) && c.Contains(b[21]) || + c.Contains(b[2]) && c.Contains(b[7]) && c.Contains(b[12]) && c.Contains(b[17]) && c.Contains(b[22]) || + c.Contains(b[3]) && c.Contains(b[8]) && c.Contains(b[13]) && c.Contains(b[18]) && c.Contains(b[23]) || + c.Contains(b[4]) && c.Contains(b[9]) && c.Contains(b[14]) && c.Contains(b[19]) && c.Contains(b[24]); + + public override string Part2() + { + Dictionary wonBoards = new(); + for (var i = 0; i < _boards.Count; i++) + wonBoards[i] = false; + + var j = 0; + while (wonBoards.Values.Count(b => b) != wonBoards.Count - 1) + { + var c = _call.Take(j).ToHashSet(); + for (var u = 0; u < _boards.Count; u++) + wonBoards[u] = HasWin(c, _boards[u]); + j++; + } + + var called = _call.Take(j).ToHashSet(); + var b = wonBoards.Single(kvp => !kvp.Value).Key; + return $"{called.Last() * _boards[b].Where(x => !called.Contains(x)).Sum()}"; + } +} diff --git a/aoc2021/input/day04.in b/aoc2021/input/day04.in new file mode 100644 index 0000000..b12a836 --- /dev/null +++ b/aoc2021/input/day04.in @@ -0,0 +1,601 @@ +69,88,67,56,53,97,46,29,37,51,3,93,92,78,41,22,45,66,13,82,2,7,52,40,18,70,32,95,89,64,84,68,83,26,43,0,61,36,57,34,80,39,6,63,72,98,21,54,23,28,65,16,76,11,20,33,96,4,10,25,30,19,90,24,55,91,15,8,71,99,58,14,60,48,44,17,47,85,74,87,86,27,42,38,81,79,94,73,12,5,77,35,9,62,50,31,49,59,75,1 + +78 27 82 68 20 +14 2 34 51 7 +58 57 99 37 81 + 9 4 0 76 45 +67 69 70 17 23 + +38 60 62 34 41 +39 58 91 45 10 +66 74 94 50 17 +68 27 75 97 49 +36 64 5 98 15 + +17 50 13 53 20 +68 57 76 10 86 + 2 91 67 27 11 +94 70 84 69 25 +32 90 45 75 41 + +71 84 42 49 81 +26 40 24 73 18 +41 37 19 25 75 +76 63 48 56 55 +85 51 29 88 23 + +27 10 11 75 59 +61 96 44 58 64 +24 68 90 60 87 +28 55 34 80 9 +41 98 91 78 62 + +91 95 70 64 30 +34 43 32 16 57 +49 80 87 51 62 +61 10 8 75 21 +85 66 2 55 56 + +50 4 11 58 48 +30 10 57 16 95 +93 96 68 92 81 +94 17 69 86 79 +52 34 99 6 19 + + 2 16 50 26 84 +97 24 32 51 8 +70 0 3 52 9 + 1 59 43 64 80 +22 23 17 92 88 + +84 7 37 71 81 +80 97 17 94 9 +27 95 39 25 5 +98 46 58 77 2 +60 1 73 23 18 + + 1 14 67 20 48 +75 51 36 87 73 +57 84 74 47 19 +89 8 13 50 24 +61 12 65 46 83 + +82 87 8 9 85 +16 22 98 91 55 +26 69 42 11 93 +65 15 2 63 43 +71 37 28 88 12 + +59 7 51 1 43 +17 45 15 96 93 +49 88 79 84 92 +40 36 25 18 22 +70 57 34 62 6 + + 1 18 5 47 46 +12 27 24 40 2 +53 54 20 14 42 +15 51 26 58 9 +31 92 34 74 7 + +41 84 14 32 8 +38 1 60 22 88 +64 70 10 91 97 +94 90 65 54 50 + 7 58 18 87 33 + +93 25 26 71 42 +86 85 61 32 51 +20 88 67 35 29 +46 28 92 9 16 +34 30 97 91 44 + +34 88 90 99 83 +22 24 4 25 18 +51 41 29 53 72 +75 42 66 98 79 +74 7 0 73 33 + +99 24 44 83 47 + 2 21 94 35 4 +96 87 31 1 22 +67 3 37 43 46 +85 55 10 6 80 + + 4 75 29 54 15 +66 17 89 98 27 +46 5 64 3 22 +97 50 0 51 52 +26 39 30 32 48 + +39 17 46 48 63 +52 13 98 40 91 +14 80 28 23 60 +90 88 15 89 74 +56 7 2 41 58 + +82 51 6 7 22 +87 9 60 63 95 +80 0 5 8 77 +85 3 68 84 39 +15 45 31 55 26 + +48 82 38 29 55 +87 46 79 61 51 + 1 97 69 91 83 +35 89 45 59 39 +43 28 21 44 24 + +71 97 34 43 23 +44 65 92 90 31 +74 87 54 79 93 +55 88 66 12 53 +14 56 17 52 83 + +91 33 20 59 67 +71 78 15 94 68 + 8 90 72 57 36 +27 40 92 1 44 +18 80 7 32 19 + +67 20 94 89 10 +85 78 70 35 0 +87 66 75 73 23 +36 8 17 83 21 +40 52 93 62 96 + + 8 37 66 26 63 + 7 90 21 18 33 +31 56 81 77 55 +34 15 19 27 57 +13 85 0 59 4 + +67 77 48 26 6 +31 72 89 76 45 +66 4 7 43 78 +15 53 81 85 70 + 0 10 40 30 94 + +79 37 8 29 27 +41 14 12 99 28 +75 40 30 25 77 +36 78 39 32 11 +91 58 17 96 51 + +36 8 35 30 51 +28 61 4 95 67 +29 69 32 80 48 +55 63 98 10 22 +27 87 83 62 21 + +24 36 52 72 16 +53 1 4 96 37 +31 7 69 47 57 +38 97 3 26 59 +74 14 29 32 40 + + 8 73 68 62 38 +43 92 15 69 46 +56 58 48 28 44 +25 64 13 50 97 +66 34 21 49 10 + +63 41 71 22 18 +56 82 95 60 35 +53 48 79 30 86 +17 51 57 70 27 +75 66 42 32 43 + +60 59 40 42 90 +65 22 43 0 49 +82 96 29 52 73 +67 17 20 53 24 +72 5 91 50 85 + +94 47 2 93 74 +90 10 27 17 5 +92 26 28 77 88 +69 43 33 19 53 +34 50 54 36 60 + +73 36 90 50 37 +11 80 81 93 74 +78 56 86 6 39 +15 94 7 91 42 +33 8 64 40 28 + +73 37 57 65 0 +64 26 52 79 69 +15 41 3 2 1 +71 48 8 43 31 + 5 93 86 42 27 + +59 35 19 17 83 +15 93 53 2 4 +26 51 85 71 22 +31 52 74 12 57 +70 40 68 39 24 + + 3 6 45 81 20 +82 30 15 62 80 +21 70 56 23 32 +68 19 50 16 14 +46 89 72 59 40 + +17 27 72 36 12 +55 30 6 88 69 +34 91 87 45 82 +48 15 18 21 7 +44 4 81 14 93 + +55 84 58 24 53 +99 44 88 54 37 + 2 56 57 50 35 +13 90 26 30 96 + 7 97 12 19 71 + +31 26 87 54 76 +68 24 20 27 98 +53 75 15 95 8 +63 2 45 50 9 +49 17 88 55 1 + +91 78 45 26 30 +63 95 67 60 58 +34 39 44 20 11 +38 29 73 22 80 +56 12 77 37 4 + +24 18 65 21 6 +76 45 85 2 78 +67 69 55 91 57 +96 61 39 36 83 + 8 54 12 38 70 + +33 71 24 82 84 +53 32 45 9 34 +89 28 30 42 96 +49 95 69 51 12 +80 41 31 48 75 + +40 60 0 92 13 +87 9 45 98 77 +14 91 35 1 95 +79 39 19 89 51 +61 56 8 97 32 + +89 70 2 81 34 +21 59 39 84 64 +28 94 97 29 30 +35 27 99 32 55 +23 47 14 88 0 + +46 14 92 49 94 +90 80 2 65 30 +54 32 35 56 27 +29 55 97 39 37 +81 72 47 66 42 + +53 1 0 34 82 +26 28 30 65 41 +17 4 57 49 40 +84 46 27 35 91 +56 38 20 81 86 + +10 31 98 66 22 +87 99 24 34 93 + 7 95 28 78 73 +61 25 14 5 1 +42 85 16 47 43 + +92 43 9 68 40 +41 65 18 69 89 +35 88 62 67 75 +64 4 17 42 93 +78 33 94 87 81 + +18 61 10 19 87 +46 99 55 3 28 +16 41 45 39 27 + 8 13 43 64 52 +23 34 47 11 92 + +21 59 74 36 38 +81 29 79 80 44 +84 30 37 62 57 +69 82 60 10 52 + 7 55 93 12 0 + +37 23 52 2 94 +19 96 8 68 29 +99 57 53 9 48 +62 11 35 95 98 +93 72 58 16 36 + +80 53 82 29 76 +77 17 85 62 81 +34 92 25 55 20 +91 39 23 50 31 +64 37 79 96 2 + +40 5 57 36 14 +91 53 56 73 27 +11 55 74 7 9 +90 58 12 22 26 +82 38 59 97 85 + +54 79 75 0 30 + 7 15 26 84 40 +91 76 42 3 19 +65 77 53 21 67 +45 50 2 14 46 + +23 51 40 13 72 +54 61 59 18 14 + 0 41 5 24 82 +73 11 46 36 17 +16 28 25 60 4 + +85 42 22 54 18 + 3 27 12 15 99 +13 26 89 93 76 +23 87 77 64 25 + 9 17 74 57 81 + +47 64 85 69 89 +59 17 4 83 88 +80 70 53 7 67 +73 18 81 44 30 +45 37 90 57 3 + +72 48 35 39 31 +44 85 91 52 46 +73 61 68 66 12 +74 95 76 75 36 +83 21 15 2 10 + +63 82 95 31 51 +93 3 53 15 70 + 0 36 44 19 5 +11 17 62 55 83 +80 91 4 18 66 + +44 8 45 90 64 +30 33 9 27 47 +68 53 81 77 35 +63 4 82 80 67 + 3 28 66 22 43 + +48 86 57 16 7 +69 51 11 8 61 +25 12 43 88 71 +83 36 31 77 5 +50 21 9 76 63 + +27 39 6 87 49 +16 66 3 25 10 + 7 70 8 94 42 +95 20 55 9 29 + 0 46 36 79 18 + +27 21 36 14 79 +23 48 56 74 94 +18 99 73 93 32 +98 77 37 35 69 +43 34 63 59 9 + +27 96 78 94 20 +34 5 49 84 99 +68 74 21 57 1 +93 85 29 47 65 +54 97 42 70 40 + +29 28 64 26 46 +39 48 13 51 2 +42 91 96 93 66 +12 60 70 8 24 +18 21 83 56 45 + +64 43 76 40 97 +30 10 22 84 53 +51 13 68 93 15 +75 27 18 39 82 +62 61 91 12 88 + +72 6 61 10 45 +65 62 57 2 91 +30 24 76 42 69 +32 36 43 63 75 +92 44 58 82 49 + +30 39 58 75 76 +62 53 59 70 97 +29 31 54 27 89 +90 32 37 86 1 + 7 34 42 61 91 + +98 94 10 72 26 +96 78 69 77 44 +45 5 88 42 73 +74 91 25 22 99 +16 79 60 71 37 + +44 33 34 27 87 +46 89 75 37 4 +71 63 16 35 17 +83 99 28 51 97 +66 86 14 61 9 + + 2 54 7 32 79 +33 36 37 35 81 +25 50 84 59 21 +18 16 48 26 15 +94 73 61 67 44 + +18 34 66 57 31 +74 92 71 59 19 +36 94 16 80 24 +35 54 58 87 64 +73 90 41 49 88 + +74 5 57 40 21 +61 11 50 80 66 +35 58 52 10 56 +92 67 82 46 72 +32 18 33 34 55 + +66 79 27 24 46 +98 4 30 80 49 +19 23 68 18 90 +41 91 83 63 77 +84 12 8 10 21 + +23 47 58 5 20 +30 32 61 6 28 +24 11 8 33 10 +52 93 95 0 45 +22 27 3 82 40 + +11 51 47 83 38 +28 85 9 10 48 +80 60 46 55 32 +89 14 90 71 50 + 0 65 24 40 19 + +12 2 37 62 93 +78 69 53 43 33 +85 76 26 21 92 +36 54 89 46 91 +29 18 72 9 51 + +82 36 47 95 30 +65 2 98 92 12 +93 73 44 48 6 +31 74 62 27 42 +32 13 11 99 50 + +89 31 94 1 78 +77 24 46 64 26 +11 16 28 30 45 +80 22 5 8 52 +32 38 76 65 90 + +92 96 35 86 51 +47 75 17 87 30 +43 29 55 50 11 +77 99 48 24 20 +37 7 91 23 8 + +26 12 82 95 78 +41 65 80 53 44 +75 43 32 46 84 +63 99 69 45 88 +56 48 87 38 49 + + 8 87 21 27 15 +84 44 26 61 82 +10 66 29 95 65 + 4 86 38 91 28 +14 49 22 52 54 + +27 43 13 35 33 +20 66 77 70 31 + 5 17 94 98 83 +11 22 39 55 75 +53 61 46 38 89 + +84 49 52 32 51 +90 46 97 91 54 + 2 42 65 10 25 +80 77 31 81 16 +58 17 15 26 55 + +19 83 57 21 95 + 4 29 11 64 0 +17 63 13 27 58 +14 96 43 22 56 +97 84 81 67 94 + +47 49 4 70 65 +60 88 9 77 3 +63 72 33 50 97 +68 84 98 78 89 +10 79 25 24 54 + +81 70 39 73 11 +86 30 38 14 91 + 9 18 72 21 24 +54 83 80 78 66 +23 93 36 31 53 + +34 58 18 69 28 +57 70 54 50 64 +35 36 4 56 72 +32 16 45 33 17 +83 60 39 22 47 + +31 73 56 21 63 +66 14 42 45 80 +60 57 47 36 78 +93 75 44 22 11 +68 89 58 88 17 + +74 16 65 13 45 +86 20 6 34 15 +70 46 59 75 57 +28 62 67 71 98 +77 63 25 61 64 + +71 20 42 65 47 +29 80 53 78 99 +70 57 18 45 32 +86 46 35 77 26 +15 91 93 55 67 + +27 16 31 41 42 +77 34 10 90 18 +28 99 44 20 68 +98 82 3 75 62 +88 85 47 17 71 + +31 95 98 60 93 +80 81 23 35 70 + 4 57 38 69 76 +18 0 41 86 54 +47 26 90 65 39 + +79 86 59 66 50 +49 64 65 95 6 +90 67 36 32 46 +10 20 25 27 1 +87 21 17 78 13 + +16 8 95 35 43 +14 0 72 89 68 +52 11 12 67 25 +63 64 13 32 15 +53 98 55 81 75 + +51 85 15 91 10 +24 68 80 22 8 +55 18 36 30 66 +27 21 46 63 26 +81 5 14 2 13 + +71 39 19 40 69 +58 70 65 46 78 +98 14 59 94 60 +12 55 68 91 0 +18 35 25 61 86 + +85 74 56 43 44 +98 78 17 95 8 +70 30 66 55 94 +57 62 82 49 77 +61 32 97 88 58 + +23 1 53 65 30 +45 15 9 26 28 + 2 21 42 27 12 +84 68 71 19 13 +58 57 35 77 14 diff --git a/aoc2021/input/test04.in b/aoc2021/input/test04.in new file mode 100644 index 0000000..cabc5cc --- /dev/null +++ b/aoc2021/input/test04.in @@ -0,0 +1,19 @@ +7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1 + +22 13 17 11 0 + 8 2 23 4 24 +21 9 14 16 7 + 6 10 3 18 5 + 1 12 20 15 19 + + 3 15 0 2 22 + 9 18 13 17 5 +19 8 7 25 23 +20 11 10 24 4 +14 21 16 12 6 + +14 21 17 24 4 +10 16 15 9 19 +18 8 23 26 20 +22 11 13 6 5 + 2 0 12 3 7 \ No newline at end of file -- cgit 1.4.1