DEV Community

loading...
Cover image for Advent of Code 2020 Solution Megathread - Day 9: Encoding Error

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

rpalo profile image Ryan Palo Updated on ・1 min read

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
Enter fullscreen mode Exit fullscreen mode

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!

Discussion (17)

pic
Editor guide
Collapse
neilgall profile image
Neil Gall • Edited

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));
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
rpalo profile image
Ryan Palo Author

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

Collapse
neilgall profile image
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.

Thread Thread
sleeplessbyte profile image
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.

Collapse
kudostoy0u profile image
Kudos Beluga • Edited

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));
                    }
                }
            }
        }
    }
})
Enter fullscreen mode Exit fullscreen mode


)

Collapse
harrygibson profile image
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}")
Enter fullscreen mode Exit fullscreen mode
Collapse
dirkfraanje profile image
Dirk Fraanje (the Netherlands) • Edited

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

Enter fullscreen mode Exit fullscreen mode


`

Collapse
ballpointcarrot profile image
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
}

Enter fullscreen mode Exit fullscreen mode
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
Collapse
kudostoy0u profile image
Kudos Beluga • Edited

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);
}
Enter fullscreen mode Exit fullscreen mode
Collapse
benwtrent profile image
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[..])
}
Enter fullscreen mode Exit fullscreen mode
Collapse
mellen profile image
Matt Ellen

More javascript. Still can't see a regex solution. Part 2 contains part 1, so I'll just post that:

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;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
rpalo profile image
Ryan Palo Author

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;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
sleeplessbyte profile image
Derk-Jan Karrenbeld • Edited

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
Enter fullscreen mode Exit fullscreen mode
Collapse
bgaster profile image
Benedict Gaster

Ah, this one lead to a nice relaxing day :-) Nothing fancy in my Haskell implementation, but fine all the same. Relies heavely on lazyness to avoid over production, but if the feature exists why not use it...

-- 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)
Enter fullscreen mode Exit fullscreen mode
Collapse
thibpat profile image
Thibaut Patel

My Javascript walkthrough: