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

Whoo! After yesterday's palate-cleansing interpreter, I'm ready to move on to new things. I'm managing to stay on top of this year's challenge so far, and I think it's the longest I've managed it so consistently. But we'll see how things go. We're not even halfway yet.

The Puzzle

In today’s puzzle, we're tasked with finding a weakness in the XMAS data cypher system (which consists of streams of numbers with requirements about sums) by finding the number that doesn't fit the pattern. As long as it doesn't have a big complicated string to parse, I'm happy.

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 03:09PM 12/12/2020 PST.

Language	Count
JavaScript	4
Python	3
Rust	3
Ruby	3
TypeScript	2
Haskell	1
C#	1
COBOL	1
Go	1
C	1
Elixir	1

Merry Coding!

Comments

[Neil Gall]

Another good problem for Rust. Because my stated goal is learning the Rust library better I'm doing it all in a text editor without an IDE, which forces you to read the docs rather than rely on autocomplete. I feel I'm writing more code between doc searches now, which is great!

use std::fs::File;
use std::io::prelude::*;


// --- file read

fn read_file(filename: &str) -> std::io::Result<String> {
    let mut file = File::open(filename)?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    Ok(contents)
}

fn parse_input(input: &str) -> Vec<i64> {
    input.split_ascii_whitespace().map(|s| s.parse().unwrap()).collect()
}

// --- problems

fn sum_of_two_is(sum: i64, vec: &[i64]) -> bool {
    vec.iter().enumerate()
        .flat_map(|(i, a)| vec.iter().skip(i+1).map(move |b| a + b))
        .find(|x| *x == sum)
        .is_some()
}

fn find_first_invalid(vec: &Vec<i64>, preamble: usize) -> Option<i64> {
    let index = (preamble..vec.len()).find(
        |index| !sum_of_two_is(vec[*index], &vec[index-preamble..*index])
    );

    index.map(|i| vec[i])
}

fn find_contiguous_set_summing_to(target: i64, vec: &[i64]) -> Option<&[i64]> {
    let mut start = 0;
    let mut end = 1;
    let mut sum: i64 = vec[start..=end].iter().sum();

    while end < vec.len() {
        if sum == target {
            return Some(&vec[start..=end]);
        }
        if sum > target {
            sum -= vec[start];
            start += 1;
        } else {
            end += 1;
            sum += vec[end];
        }
    }

    None
}

fn sum_of_min_and_max(vec: &[i64]) -> Option<i64> {
    vec.iter().min()
        .and_then(|min|
            vec.iter().max().map(|max| 
                min + max
            )
        )
}

fn part1(sequence: &Vec<i64>) -> Option<i64> {
    find_first_invalid(sequence, 25)
}

fn part2(sequence: &Vec<i64>) -> Option<i64> {
    let target = part1(sequence).unwrap();
    find_contiguous_set_summing_to(target, sequence)
        .and_then(sum_of_min_and_max)
}   


fn main() {
    let input = read_file("./input.txt").unwrap();
    let sequence = parse_input(&input);
    println!("part1 {:?}", part1(&sequence));
    println!("part2 {:?}", part2(&sequence));
}


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_parser() {
        assert_eq!(parse_input("1 2 3 4"), vec![1, 2, 3, 4]);
        assert_eq!(parse_input("15\n16\n0\n99"), vec![15, 16, 0, 99]);
    }

    #[test]
    fn test_sum_of_two_is() {
        assert!(sum_of_two_is(3, &vec![1,2,3,4,5]));
        assert!(sum_of_two_is(6, &vec![1,2,3,4,5]));
        assert!(sum_of_two_is(9, &vec![1,2,3,4,5]));
        assert!(!sum_of_two_is(20, &vec![9,8,7,6,5]));
    }

    #[test]
    fn test_find_first_invalid() {
        let input = vec![35,20,15,25,47,40,62,55,65,95,102,117,150,182,127,219,299,277,309,576];
        assert_eq!(find_first_invalid(&input, 5), Some(127));
    }

    #[test]
    fn test_find_first_invalid_when_close_to_end() {
        let input = vec![35,20,15,25,47,40,62,55,65,95,102,117,150,182,127,219];
        assert_eq!(find_first_invalid(&input, 5), Some(127));
    }

    #[test]
    fn test_find_contiguous_set_summing_to() {
        let input = vec![35,20,15,25,47,40,62,55,65,95,102,117,150,182,127,219,299,277,309,576];
        let expect: &[i64] = &vec![15,25,47,40];
        assert_eq!(find_contiguous_set_summing_to(127, &input), Some(expect));     
    }

    #[test]
    fn test_sum_of_min_and_max() {
        let input = vec![15,25,47,40];
        assert_eq!(sum_of_min_and_max(&input), Some(62));
    }
}

[Ryan Palo]

I like your sort of “inchworm” approach to part 2!

[Neil Gall]

It's neat and it passed the tests and got the right answer for me, but I'm not convinced it's totally correct for all input data. I'm sure there are cases it could miss by inching the end forward too far before moving the start.

[Derk-Jan Karrenbeld]

Because of the contiguous set limitation, it always works. You can't ever go down in value by moving the right end, and you can't ever go up in value by moving the left end.

It's the right approach.

[Derk-Jan Karrenbeld]

This is the first day I did not OOP it up, because I felt lazy. Part 2 is still nicely linear, but didn't bother to optimise Part 1. Here's Ruby:

require 'benchmark'

def find_sum_of_uniques(candidates, check)
  skip = check / 2.to_f

  candidates.each do |x|
    next if x == skip

    candidates.each do |y|
      next if y == skip
      return true if x + y == check
    end
  end

  false
end

def find_invalid(numbers, preamble: 25)
  pointer = preamble
  candidates = numbers[0...preamble]


  while pointer < numbers.length
    check = numbers[pointer]

    unless find_sum_of_uniques(candidates, check)
      return check
    end

    candidates.shift
    candidates.push(numbers[pointer])

    pointer += 1
  end
end

def find_sum_set(numbers, match)
  pointer_left = 0
  pointer_right = 1

  sum = numbers[pointer_left..pointer_right].sum

  checks = 0

  while sum != match
    checks += 1

    # puts "#{match} != #{numbers[pointer_left]} + (...#{[pointer_right - pointer_left - 2, 0].max} numbers) + #{numbers[pointer_right]}"

    if sum < match
      pointer_right += 1
      sum += numbers[pointer_right]
    elsif sum > match
      sum -= numbers[pointer_left]
      pointer_left += 1
    end
  end

  numbers[pointer_left...pointer_right].tap do |x|
    # puts "#{match} == #{numbers[pointer_left..pointer_right].sort.join(" + ")}"
    puts "\nChecked #{checks} sets to find the sum set"
  end
end

numbers = File.readlines('input.txt').map(&:to_i)

Benchmark.bmbm do |b|
  b.report do
    invalid = find_invalid(numbers, preamble: 25)
    set = find_sum_set(numbers, invalid)

    puts "xmas: #{set.minmax.sum}"
  end
end

[Kudos Beluga]

Rust solution with more recursion than I do normally.
I had to create 3 variables to store the numbers because of annoying lifetime problems among other things.

use std::fs;
use std::iter::FromIterator;
fn parse(toparse: &str) -> usize { toparse.parse::<usize>().unwrap() }
fn part1(data: &Vec<usize>,index: usize) -> usize {
    let mut haspassed: bool = false;
    let num = data[index];
    let previous25 = Vec::from_iter(data[index-25..index].iter().cloned());
    for i in &previous25 {
        for l in &previous25 {
            if i+l == num {
                if i != l {
                    haspassed = true;
                }}}}
    if haspassed == true { part1(data,index+1) } else { num }
}
fn part2(data: Vec<usize>,num: &usize,mut index: usize,mut len: usize) -> usize {
    if data.get(index+len) == None {
        index = 0;
        len += 1;
    }
    let currentvec: Vec<usize> = Vec::from_iter(data[index..index+len].iter().cloned());
    let currentnum: usize = currentvec.iter().sum();
    if currentnum == *num {
         return match currentvec.iter().min() { Some(x) => x,None => &0} + match currentvec.iter().max() { Some(x) => x,None => &0}
         } else {
             return part2(data,num,index+1,len)
            }
}
fn main() {
    let data = fs::read_to_string("./day9.txt").unwrap();
    let mut data2 = data.split("\n").collect::<Vec<_>>();
    // Sometimes EOF is counted as a newline?
    if match data2.last() { Some(x) => if x == &"" { true } else { false }, _ => false } {
        data2.pop();
    }
    let parseddata = data2.iter().map(|x| parse(x)).collect::<Vec<_>>();
    let part1answer = part1(&parseddata,25);
    let part2answer = part2(parseddata,&part1answer,0,2);
    println!("Part 1: {}\nPart 2: {}",part1answer,part2answer);
}

[Kudos Beluga]

Here's my js solution,toggle part2 to true or false depending on your needs :

const fs = require("fs"),
    part2 = false;
fs.readFile("input.txt", "utf8", (err, data) => {
    if (err) throw err;
    let d = data.split("\n").map(e => Number(e));
    for (let i = 25; i < d.length; i++) {
        let first25 = d.slice(i - 25, i),
            matched;
        for (j in first25) {
            for (k in first25) {
                if ((first25[j] != first25[k]) && ((first25[k] + first25[j]) == d[i])) matched = true;
            }
        }
        if (!matched && !part2) console.log(d[i]);
        else if (!matched && part2) {
            for (let j = 0; j < d.length; j++) {
                for (let l = 0; l < d.length; l++) {
                    let arr = [];
                    for (let k = l; k < j + l; k++) {
                        arr.push(d[k]);
                    }
                    arr = arr.filter(e => e);
                    if (arr.length > 1) {
                        if (arr.reduce((total, num) => total + num) == d[i]) console.log(Math.min(...arr) + Math.max(...arr));
                    }
                }
            }
        }
    }
})

)

[Harry Gibson]

Python, should be a reasonably efficient way of doing it although in part 2 it may be better to test the longer sequences first as there are fewer of them.

from collections import deque

def pair_is_summable_to(n, iterable):
    seen = set()
    for x in iterable:
        target = n - x
        if target in seen:
            return True
        seen.add(x)
    return False


def part1(lines,  preamble_len=25):
    queue = deque(lines[:preamble_len], preamble_len)
    for i, n in enumerate(lines[preamble_len:]):
        if pair_is_summable_to(n, queue):
            queue.append(n)
        else:
            return n, i


def part2(target_weakness, lines):
    # test all contiguous sets of length 2 then all of length 3 etc
    for test_len in range(2, len(lines)):
        queue = deque(lines[:test_len], test_len)
        for pos in range(test_len, len(lines)):
            if sum(queue) == target_weakness:
                w_0 = min(queue)
                w_1 = max(queue)
                return w_0+w_1, test_len, pos
            else: 
                queue.append(lines[pos])


lines = [int(l.strip()) for l in open('input.txt', 'r')]

target_weakness, at_row = part1(lines)
print(f"Part 1: result is {target_weakness} which is at line {at_row}")

weakness, seq_len, at_row = part2(target_weakness, lines)
print(f"Part 2: result is {weakness} from a sequence of length {seq_len} ending at row {at_row}")

[Dirk Fraanje (the Netherlands)]

C# solution.
Top 3 love rank:

1. Day 8
2. Day 9
3. Day 3

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

namespace AdventOfCode2020
{
    static class Day9
    {
        //Declaring numberToConsider so it can easily be changed when testing
        static int numberToConsider = 25;
        static List<long> input;
        static int firstposition = numberToConsider;
        static long faultingNumber;
        public static void Execute()
        {
            input = File.ReadAllLines("//input").Select(r=> long.Parse(r)).ToList();

            //Added a imer just for fun
            var timer = new Stopwatch();
            timer.Start();

            while (true)
            {
                faultingNumber = input[firstposition];
                if (!SumFound(faultingNumber, firstposition))
                    break;
                firstposition++;
            }
            //Part 2:
            var answerPart2 = FindSumUpToAnswer();

            timer.Stop();
            Console.WriteLine($"Part1 answer:  {faultingNumber}");
            Console.WriteLine($"Part2 answer:  {answerPart2}");
            Console.WriteLine($"Executed in: {timer.ElapsedMilliseconds} milliseconds");
        }

        private static long FindSumUpToAnswer()
        {
            firstposition = 0;
            var secondPosition = 1;


            while (true)
            {
                var listToCheck = input.GetRange(firstposition, secondPosition-firstposition);
                var rangeResult = listToCheck.Sum();
                if (rangeResult == faultingNumber)
                {
                    return listToCheck.Min() + listToCheck.Max();
                }
                //By adding to either the first or second position a window is created and results are re-used instead of creating a new list every time
                if (rangeResult < faultingNumber)
                    secondPosition++;
                else
                    firstposition++;
            }
        }

        private static bool SumFound(long nextNumberToCheck, int position)
        {
            var workingList = input.Skip(position - numberToConsider).Take(numberToConsider).ToList();
            workingList.Sort();
            for (int i = 0; i < numberToConsider-1; i++)
            {
                var valueNeeded = nextNumberToCheck - workingList[i];
                var result = workingList.BinarySearch(valueNeeded);
                if (result >= 0)
                    return true;
            }
            return false;
        }
    }
}

`

[Christopher Kruse]

+1 Rust solution.

I started out with isize because I just knew that the second half would add negative numbers somehow. Then it didn't. :/

I got part 1 done rather quickly comparatively. I then spent far to long arguing with the rust compiler over lifetimes of slices and the ability to sum on borrowed vs. non-borrowed values.

Ultimately I moved into using a more C-style for-loop driven solution, where we walk down the entry vector until we're too big, and then step down to the next item.

Didn't get the elegant interator-driven solution, but meh - a win's a win. :)

As always, on Github.

use aoc_runner_derive::{aoc, aoc_generator};
use std::cmp::Ordering;

#[aoc_generator(day9)]
fn parse_input_day9(input: &str) -> Vec<isize> {
    input
        .lines()
        .map(|line| str::parse(line).unwrap())
        .collect()
}

fn process_xmas(input: &Vec<isize>, preamble_count: usize) -> &isize {
    let mut buffer: Vec<isize> = input.iter().copied().take(preamble_count).collect();
    input
        .iter()
        .skip(preamble_count)
        .find(|num| {
            match buffer.iter().find(|buf_num| {
                buffer
                    .iter()
                    .any(|buf_addend| *buf_addend + *buf_num == **num)
            }) {
                Some(_n) => {
                    buffer.push(**num);
                    buffer.remove(0);
                    false
                }
                None => true,
            }
        })
        .unwrap()
}

#[aoc(day9, part1)]
fn find_target_value(input: &Vec<isize>) -> isize {
    let preamble_count = 25;
    *process_xmas(input, preamble_count)
}

#[aoc(day9, part2)]
fn hit_weak_point_for_massive_damage(input: &Vec<isize>) -> isize {
    let preamble_count = 25;
    let target_value = *process_xmas(input, preamble_count);
    let mut span: &[isize];
    for (idx, _) in input.iter().enumerate() {
        let mut slider = idx.clone();
        let mut over = false;
        while !over {
            span = &input[idx..slider];
            match target_value.cmp(&span.iter().sum::<isize>()) {
                Ordering::Greater => {
                    slider += 1;
                }
                Ordering::Equal => {
                    return *span.iter().min().unwrap() + *span.iter().max().unwrap();
                }
                Ordering::Less => {
                    over = true;
                }
            }
        }
    }
    -1
}

[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;
        }
    }

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;
        }
    }

[Ryan Palo]

Had some extra time tonight so I got ahead of the curve. The time complexity isn't great, with the loops being a nasty hairy mess, but it works fine :)

#include "Day9.h"

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

#include "parsing.h"

/// Day 9: Encoding Error
/// 
/// Find the number that can't be made by a combination of the numbers
/// preceding it.

#define MAX_NUMBER_STRING_SIZE 16

/// Parse the input file into a list of integers, one per line.
int* parse(const char* filename, int* count) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Couldn't open file.\n");
    exit(EXIT_FAILURE);
  }

  *count = count_lines(fp);
  int* numbers = (int*)malloc(sizeof(int) * *count);
  for (int i = 0; i < *count; i++) {
    char buf[MAX_NUMBER_STRING_SIZE] = {0};
    fgets(buf, MAX_NUMBER_STRING_SIZE, fp);
    numbers[i] = atoi(buf);
  }
  fclose(fp);
  return numbers;
}

/// Decides if a number is a 'valid number,' i.e. there is some
/// combination of two numbers in the preceding 'preamble_length' 
/// numbers that add up to it.
bool valid_number(int* numbers, int i, int preamble_length) {
  // Add each pair of numbers in the preceding 'preamble_length' #'s
  // If there's any pair that add up to the i'th number, it's valid.
  for (int j = 0; j < preamble_length; j++) {
    for (int k = j + 1; k < preamble_length; k++) {
      if (numbers[i - preamble_length + j] + numbers[i - preamble_length + k] == numbers[i]) {
        return true;
      }
    }
  }
  return false;
}

/// Find the one number that isn't 'valid' per the above definition.
int part1(const char* filename, int preamble_length) {
  int count = 0;
  int* numbers = parse(filename, &count);

  for (int i = preamble_length; i < count; i++) {
    if (!valid_number(numbers, i, preamble_length)) {
      return numbers[i];
    }
  }
  return -1;
}

/// There is a set of contiguous numbers, two or greater in length,
/// that, when added up, equal the invalid number from part 1.
/// Return the minimum number in that set + the max in that set.
int part2(const char* filename, int preamble_length) {
  int count = 0;
  int* numbers = parse(filename, &count);

  int invalid_target = part1(filename, preamble_length);

  // Check each size from 2 all the way up to all of the numbers
  for (int size = 2; size <= count; size++) {

    // At each size, shift the window from front to back, one by one.
    for (int i = 0; i + size - 1 < count; i++) {

      // Add up that window of numbers and see if it matches
      int total = 0;
      for (int j = 0; j < size; j++) {
        total += numbers[i + j];
      }

      // If it matches, find the min and max values in that window
      // and return their sum.
      if (total == invalid_target) {
        int min = INT_MAX;
        int max = 0;

        // Simultaneously find the min and max in the range.
        for (int j = 0; j < size; j++) {
          if (numbers[i + j] > max) max = numbers[i + j];
          if (numbers[i + j] < min) min = numbers[i + j];
        }
        return min + max;
      }
    }
  }
  return -1;
}

/// Run both parts
int day9() {
  printf("====== Day 9 ======\n");
  printf("Part 1: %d\n", part1("data/day9.txt", 25));
  printf("Part 2: %d\n", part2("data/day9.txt", 25));
  return EXIT_SUCCESS;
}

[Benjamin Trent]

This one seemed simple to me. Basic dynamic programming.

fn two_number_sum(desired_sum: &usize, preamble: &usize, numbers: &[usize]) -> bool {
    if numbers.len() < *preamble {
        return false
    }
    for (i, val) in numbers[0..*preamble - 1].iter().enumerate() {
        for other_val in numbers[i+1..*preamble].iter() {
            if val + other_val == *desired_sum {
                return true;
            }
        }
    }
    return false;
}

fn first_without_sum(preamble: &usize, input: &[usize]) -> usize {
    for i in 0..input.len() - preamble {
        if !two_number_sum(&input[i + preamble].clone(), &preamble, &input[i..]) {
            return input[i+preamble]
        }
    }
    return 0
}

fn contiguous_set_sum(val: &usize, input: &[usize]) -> usize {
    for (i, v) in input.iter().enumerate() {
        let mut sum = *v;
        let mut vals = vec![v];
        for other_val in input[i+1..].iter() {
            vals.push(other_val);
            sum += other_val;
            if sum == *val {
                return *vals.iter().min().unwrap() + *vals.iter().max().unwrap()
            }
            if sum > *val {
                break;
            }
        }
    }
    return 0
}



#[aoc(day9, part1)]
fn last_value_before_rerun(input: &Vec<usize>) -> usize {
    first_without_sum(&25, &input[..])
}

#[aoc(day9, part2)]
fn code_break(input: &Vec<usize>) -> usize {
    let desired_sum = first_without_sum(&25, &input[..]);
    contiguous_set_sum(&desired_sum, &input[..])
}