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

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

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

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

-- helper function to generate tuple perms of a list and pass to a function
perms :: Eq t => (t -> t -> a) -> [t] -> [a]
perms f xs = [f x y | (x:ys) <- tails (nub xs), y <- ys]

-- asserts if a number is XMAS encrypted correctly
valid :: [Int] -> Int -> Int -> (Bool,Int)
valid is l i = let ps = map (\(_,_,z) -> z) $ perms (\x y -> (x,y,x+y)) (take l is)
                   n  = is !! i
               in (n `elem` ps, n)

-- checks, for a given header length, that each input is valid 
check :: Int -> [Int] -> [(Bool, Int)]
check l is | length is <= l+1 = []
           | otherwise      =  valid is l l : check l (tail is)

-- find the first input that is not valid with respec to XMAS encryption 
task1 :: Int -> [Int] -> Int
task1 l = snd . head . filter (not . fst) . check l

-- find the a contiguous sequence whose sum is equal to the input (calulated by task1) and
-- sum the smallest and largest number in that sequence
task2 :: Int -> [Int] -> Int
task2 n = (\xs -> head xs + last xs) . snd . head . filter ((n==) . fst) . map (\xs -> (sum xs, sort xs)) 
                        . filter ((>1) . length) . (:) [] . filter (not . null) . concatMap tails . inits

main = do xs <- readFile "day9_input" <&> lines <&> fmap (read :: String -> Int)
          let x = task1 25 xs
          print x
          print (task2 x xs)

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[..])
}

function findWeaknessp2()
{
  let input = document.querySelector('pre')
                      .innerHTML
                      .split('\n')
                      .map(n => parseInt(n, 10));

  let win = 25;
  let fail = -1;
  let failIndex = -1;

  for(let i = win; i < input.length; i++)
  {
    let target = input[i];
    let options = input.slice(i-win, i);
    let found = options.reduce((val, opt) =>
    {
      if(val == -1)
      {
        val = options.indexOf(target-opt);
      }

      return val;
    },-1);

    if(found == -1)
    {
      fail = target;
      failIndex = i;
      break;
    }
  }

  let weakness = -1;

  for(let curWin = 2; curWin < failIndex/2; curWin++)
  {
    for(let i = 0; i < failIndex; i++)
    {
      let options = input.slice(i, i+curWin);
      let testVal = options.reduce((sum, val) => sum+val, 0);
      if(testVal == fail)
      {
        weakness = Math.min(...options) + Math.max(...options);
        break;
      }
    }

    if(weakness > -1)
    {
      break;
    }
  }

  return weakness;
}

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

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

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
}

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

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

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}")

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