DEV Community

Discussion on: Advent of Code 2020 Solution Megathread - Day 9: Encoding Error

Collapse
mgasparel profile image
Mike Gasparelli

Today was the first day we got different params for the sample solution, so I had to think about how to make that work with my puzzle runner. I don't love the solution, but it works. Thinking I might do a quick post on the runner, not sure if that would interest anyone...

Overall this was a fun little exercise, not super challenging, though I did have a harder time trying to condense the code for this solution. Not something I typically do day-to-day, but it's a code challenge, not production code 🥳

Anyway, here's my solution for the day

Part1

public class Part1 : Puzzle<long[], long>
    {
        public override long SampleAnswer => 127;

        protected int preamble = 25;

        public override long[] ParseInput(string rawInput)
            => rawInput
                .Split(Environment.NewLine)
                .Where(line => line.Length > 0)
                .Select(line => long.Parse(line))
                .ToArray();

        public override long Solve(long[] input)
            => FindInvalidNumber(input) ?? throw new System.Exception("Result not found!");

        public override bool ValidateSample(long[] input)
        {
            // First time we hit a sample with different params as the solution.
            preamble = 5;

            return base.ValidateSample(input);
        }

        protected long? FindInvalidNumber(long[] input)
        {
            for(int i = preamble; i < input.Length; i++)
            {
                var window = input[(i - preamble)..(i)];

                if (TargetSumExistsInWindow(input[i], window) == false)
                {
                    return input[i];
                }
            }

            return null;    // not found
        }

        private bool TargetSumExistsInWindow(long target, long[] window)
        {
            bool found = false;
            for (var j = 0; j < window.Length; j++)
            {
                // Bail early. One half of the sum is already greater than the result.
                if (window[j] > target)
                {
                    continue;
                }

                // If already true, don't set back to false.
                found = window.Any(x => x != window[j] && x + window[j] == target) || found;
            }

            return found;
        }
    }
Enter fullscreen mode Exit fullscreen mode

Part 2

public class Part2 : Part1
    {
        public override long SampleAnswer => 62;

        public override long Solve(long[] input)
        {
            var invalidNumber = FindInvalidNumber(input) ?? throw new System.Exception("Result not found!");
            var range = FindRangeSummingTo(invalidNumber, input) ?? throw new System.Exception("Result not found!");

            return range!.Start + range!.End;
        }

        (long Start, long End)? FindRangeSummingTo(long target, long[] input)
        {
            for (var i = 0; i < input.Length; i++)
            {
                long sum = 0;
                for (var j = i; j < input.Length; j++)
                {
                    if ((sum += input[j]) == target)
                    {
                        return (input[i..j].Min(), input[i..j].Max());
                    }

                    if (sum > target)
                    {
                        break;
                    };
                }
            }

            return null;
        }
    }
Enter fullscreen mode Exit fullscreen mode