You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

106 lines
2.5 KiB

3 years ago
3 years ago
3 years ago
3 years ago
3 years ago
  1. using System;
  2. using static System.Console;
  3. using System.Collections.Generic;
  4. using System.IO;
  5. using System.Linq;
  6. using System.Text.RegularExpressions;
  7. using Xunit;
  8. namespace AdventOfCode {
  9. public class Day09 {
  10. static bool Valid(List<long> longs, int preambleSize, int target) {
  11. for (int i = target - preambleSize; i < target - 1; i++) {
  12. for (int j = i + 1; j < target; j++) {
  13. if (i == j) {
  14. continue;
  15. }
  16. if (longs[i] + longs[j] == longs[target]) {
  17. return true;
  18. }
  19. }
  20. }
  21. return false;
  22. }
  23. static long FindInvalid(List<long> longs, int preambleSize) {
  24. for (int target = preambleSize; target < longs.Count(); target++) {
  25. if (!Valid(longs, preambleSize, target)) {
  26. return longs[target];
  27. }
  28. }
  29. throw new Exception("didn't find an invalid int");
  30. }
  31. static long CalculateWeakness(List<long> longs, int minIndex, int maxIndex) {
  32. long largest = 0;
  33. long smallest = long.MaxValue;
  34. for (int i = minIndex; i <= maxIndex; i++) {
  35. if (longs[i] > largest) {
  36. largest = longs[i];
  37. }
  38. if (longs[i] < smallest) {
  39. smallest = longs[i];
  40. }
  41. }
  42. return smallest + largest;
  43. }
  44. static long FindWeakness(List<long> longs, long target) {
  45. for (int i = 0; i < longs.Count() - 1; i++) {
  46. long total = 0;
  47. for (int j = i; j < longs.Count() && total < target; j++) {
  48. total += longs[j];
  49. if (total == target) {
  50. return CalculateWeakness(longs, i, j);
  51. }
  52. }
  53. }
  54. throw new Exception("didn't find a weakness");
  55. }
  56. static long Part1() {
  57. string[] input = File.ReadAllLines(Util.RootDir + "day09.txt");
  58. List<long> longs = input.ToList().Select(long.Parse).ToList();
  59. return FindInvalid(longs, 25);
  60. }
  61. static long Part2(long target) {
  62. string[] input = File.ReadAllLines(Util.RootDir + "day09.txt");
  63. List<long> longs = input.ToList().Select(long.Parse).ToList();
  64. return FindWeakness(longs, target);
  65. }
  66. [Fact]
  67. public static void Test() {
  68. string[] example =
  69. @"35
  70. 20
  71. 15
  72. 25
  73. 47
  74. 40
  75. 62
  76. 55
  77. 65
  78. 95
  79. 102
  80. 117
  81. 150
  82. 182
  83. 127
  84. 219
  85. 299
  86. 277
  87. 309
  88. 576".Split('\n');
  89. List<long> longs = example.ToList().Select(long.Parse).ToList();
  90. Assert.Equal(127, FindInvalid(longs, 5));
  91. long invalidNumber = Part1();
  92. Assert.Equal(50047984, invalidNumber);
  93. Assert.Equal(5407707, Part2(invalidNumber));
  94. }
  95. }
  96. }