Advent of Code 2020 Solution Megathread - Day 1: Report Repair

It's back! It's finally back! One of my favorite things on the internet is the yearly Advent of Code challenge. It's a programming challenge that runs from December 1st to December 25th. Each day, a new two-part puzzle is released. There is usually a plain text file input provided, and you have to write some code in any language you want to process it in some way. If you submit the correct answer to their question, you get a star. If you solve both parts correctly, you get two stars! The goal is to get 50 stars by Christmas day.

There are a bunch of people who get super-competitive and try to finish it as soon after midnight (when the puzzles are released) as possible. Personally, I just try to keep up and not get overwhelmed, since the second parts are usually pretty hard and require some algorithmic cleverness. (Or... and hear me out... some GPU compute. Just throw 1000 computers at the problem! 🙃)

In any case, what we usually do here on DEV is have a post here every day where members of the community can post their solutions so you can see how a bunch of different people approached it in a bunch of different languages. So, when you've solved that day's puzzle, please join in and comment with your solution. And, if you're not ready for spoilers yet, stay away from the comments section!

Every year there is a theme, and this year, you're going on vacation! The stars are currency that you need to pay for your room at the end of your stay. I'm sure nothing bad will happen. It rarely does on these Advent of Code adventures.

The Puzzle

Here's today's puzzle: apparently your trip expense report isn't adding up! You are tasked with hunting through your expense entries to find the two that add up to 2020 exactly. The answer is the result of multiplying those two values together. A nice warm-up puzzle to get us back into the groove this year.

The Leaderboard

If anyone is interested, I've generated a leaderboard code for a little less globally competitive DEV leaderboard.
It's not an officially sponsored DEV thing, just a leaderboard that some DEV peeps have used over the last couple of years. There's still quite a bit of room, so feel free to jump in if you'd like using this code:

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.

Previous Day's Languages

Last year, they made an effort to keep track of how many people used each language for their solutions for the previous day. I'll try to do that as time allows. I could imagine a bot that could poll each thread daily and update the following day's count. But that may be outside of what I have time for as well. If anybody wants to come up with something like that, I'm all for integrating it into the process. Otherwise, I'll do my best.

Merry Coding!

Comments

[Ali Spittel]

Hey!! So excited that it's this time again here is my code. I would have just done loops without sets but the servers were down when I was trying to get my full input so I just went ahead and did a tiny optimization :).

def part_one(nums, set_nums):
    for num in nums:
        if 2020 - num in set_nums:
            return num * (2020 - num)


def part_two(nums, set_nums):
    for num in nums:
        for num2 in nums:
            if (2020 - num - num2) in set_nums:
                return num * (2020 - num - num2) * num2


with open("input.txt") as _file:
    nums = [int(line) for line in _file]
    set_nums = set(nums)

    print("Part 1", part_one(nums, set_nums))
    print("Part 2", part_two(nums, set_nums))

[Ryan Palo]

Oooh! That's a really slick way to drop out a level of nesting. I like it!

[Patryk Woziński]

Hi! It was also my first time in Advent of Code.

There is my solution for the first day in Elixir: click, GitHub

Except input setup the code looks like:

  def part1() do
    numbers = Enum.map(@numbers, &String.to_integer(&1))

    [res | _] = for x <- numbers,
      y <- numbers,
      x + y == 2020,
      do: x * y

    res
  end

  def part2() do
    numbers = Enum.map(@numbers, &String.to_integer(&1))

    [res | _] = for x <- numbers,
      y <- numbers,
      z <- numbers,
      x + y + z == 2020,
      do: x * y * z

    res
  end

[David Clothier]

SQL works for me. Easy and fast ;)

Get this table naming 'day1':

1.2. Solution

SELECT
       a1.num*a2.num*a3.num
FROM
       day1 a1
     , day1 a2
     , day1 a3
WHERE
       a1.num + a2.num + a3.num = 2020
LIMIT 1

[Benjamin Trent]

Here is my solution in rust (minus all the code required to grab the input and parse it)

fn sums_to<'a>(
    sum: &'_ usize,
    curr: &'a usize,
    rest: &'a [usize],
) -> Option<(&'a usize, &'a usize)> {
    if rest.len() == 0 {
        return Option::None;
    }
    for re in rest {
        if re + curr == *sum {
            return Option::Some((curr, re));
        }
    }
    sums_to(sum, &rest[0], &rest[1..])
}

fn tri_sums_to<'a>(
    sum: &'_ usize,
    x: &'a usize,
    rest: &'a [usize],
) -> Option<(&'a usize, &'a usize, &'a usize)> {
    if rest.len() == 0 {
        return Option::None;
    }
    if x < sum {
        let sub_sum = *sum - x;
        for i in 0..(rest.len() - 1) {
            if let Some((a, b)) = sums_to(&sub_sum, &rest[i], &rest[i + 1..]) {
                return Option::Some((x, a, b));
            }
        }
    }
    tri_sums_to(sum, &rest[0], &rest[1..])
}

async fn day1_1() -> Result<usize> {
    let input = input_to_vec(1).await?;
    let (v1, v2) = sums_to(&2020, &input[0], &input[1..]).unwrap();
    Ok(v1 * v2)
}

async fn day1_2() -> Result<usize> {
    let input = input_to_vec(1).await?;
    let (v1, v2, v3) = tri_sums_to(&2020, &input[0], &input[1..]).unwrap();
    Ok(v1 * v2 * v3)
}

[Christopher Kruse]

Hey - I'm working on the problems in Rust this year, too! I'm putting all mine in Github, but will share here, too.

(I found a cool cargo plugin that provides helpful macros and makes doing AoC stuff easier - cargo-aoc)

use aoc_runner_derive::{aoc, aoc_generator};

#[aoc_generator(day1)]
fn parse_input_day1(input: &str) -> Vec<usize> {
    input
        .lines()
        .map(|v| v.parse().expect("Failed to parse input!"))
        .collect()
}

#[aoc(day1, part1)]
fn find_2020_entries(input: &Vec<usize>) -> usize {
    let pair = input.iter().enumerate().find_map(|(idx, &item)| {
        match input
            .iter()
            .enumerate()
            .find(|(idx2, &second)| idx2 != &idx && (item + second == 2020))
        {
            Some((_, second)) => Some(item * second),
            None => None,
        }
    });
    pair.unwrap_or(1)
}

#[aoc(day1, part2)]
fn find_2020_entries_with_three(input: &Vec<usize>) -> usize {
    let result = input.iter().enumerate().find_map(|(idx, &item)| {
        input.iter().enumerate().find_map(|(idx2, &second)| {
            match input.iter().enumerate().find(|(idx3, &third)| {
                idx2 != idx && &idx != idx3 && &idx2 != idx3 && (item + second + third == 2020)
            }) {
                Some((_, third)) => Some(item * second * third),
                None => None,
            }
        })
    });
    result.unwrap_or(1)
}

[Florian Rohrer]

I am also gonna be doing aoc this year. Here is my Python solution:

with open("input.txt") as f:
    l = [int(x.strip()) for x in f]

for i, n1 in enumerate(l):
    for j, n2 in enumerate(l[i+1:]):
        if n1 + n2 == 2020:
            part1 = n1 * n2
        for n3 in l[i+j+1:]:
            if n1 + n2 + n3 == 2020:
                part2 = n1 * n2 * n3

print(part1)
print(part2)

[willsmart]

Yep, this'll be another year fighting the urge to pre-optimise xmas code 🤦

Anyway, here's a nice efficient implementation in JS... (linear for part one, which is nice. Square for part two which could be improved but, like, why?)

const input = JSON.parse(require('fs').readFileSync('1a.json', 'utf-8'));

// sort ascending
input.sort((a, b) => a - b);


function go(c, tgt) {
  // tgt is the target sum we're aiming for
  // a is an index which moves through the array, 
  // b is ahead of a but retreats to maintain a sum <= to target.

  for (let a = c, b = input.length - 1; a < input.length; a++) {
    let { [a]: av, [b]: bv } = input;
    while (av + bv > tgt && b >= a) bv = input[--b];
    if (av + bv == tgt) return { a, b };
  }
}

let res;
// Part 1
(res = go(0, 2020)) &&
  console.log({
    part: 1,
    sum: input[res.a] + input[res.b],
    prod: input[res.a] * input[res.b],
  });

// Part 2
for (const c in input)
  (res = go(c, 2020 - input[c])) &&
    console.log({
      part: 2,
      sum: input[res.a] + input[res.b] + input[c],
      prod: input[res.a] * input[res.b] * input[c],
    });

[willsmart]

I'm liking Ryan's idea of using this to practice new languages and get out of the comfort zone (though JS is just so comfy now 😌 )
Plan is to make myself a twister-style spinner with 5 or so languages, and force myself to use whichever one the arrow lands on on the day.

[Ryan Palo]

I'm going to try to do my solutions in C. C is something I'm learning, so if anybody has any pointers (LOL), please don't hesitate to critique my code.

I didn't do anything crazy today. I just threw loops at it to see if it was fast enough. It solved before I could blink, so I'm not going to work any harder at improving speed.

/// Day 1: Report Repair
/// 
/// My expense report for my trip is messed up and entries need
/// adjusting.

#include <stdio.h>
#include <stdlib.h>

/// Parse the input file, which contains one positive integer per line.
int* parse(const char* filename, size_t* count) {
  FILE *fp;

  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Could not open input file.\n");
    exit(EXIT_FAILURE);
  }

  // Count how many we need
  size_t lines = 0;
  while (!feof(fp)) {
    if (fgetc(fp) == '\n') lines++;
  }
  lines++;  // The last line has no newline, but we should count it.
  rewind(fp);

  int* entries = malloc(sizeof(int)*lines);

  char buff[5];  // No numbers greater than 4 digits
  for (size_t i = 0; i < lines; i++) {
    fgets(buff, 6, fp);
    entries[i] = atoi(buff);
  }
  fclose(fp);

  *count = lines;
  return entries;
}

/// Part 1 finds the two entries that add up to 2020 exactly and returns
/// their product, or -1 if none are found.
int part1(int* entries, size_t count) {
  for (size_t i = 0; i < count; i++) {
    for (size_t j = i + 1; j < count; j++) {
      if (entries[i] + entries[j] == 2020) {
        return entries[i] * entries[j];
      }
    }
  }
  return -1;
}

/// Part 2 is the same as Part 1, but we're looking for a trio of numbers
/// that sum up to 2020.  Returns their product or -1 if no trio is found.
int part2(int* entries, size_t count) {
  for (size_t i = 0; i < count; i++) {
    for (size_t j = i + 1; j < count; j++) {
      for (size_t k = j + 1; k < count; k++) {
        if (entries[i] + entries[j] + entries[k] == 2020) {
          return entries[i] * entries[j] * entries[k];
        }
      }
    }
  }
  return -1;
}

int main() {
  size_t count;
  int* entries = parse("day1/day1.txt", &count);
  printf("The 2020 pair product is: %d\n", part1(entries, count));
  printf("The 2020 triplet product is: %d\n", part2(entries, count));
  return EXIT_SUCCESS;
}

[Johnny]

I'm also doing it in C this year! I'm also fairly new to the language and pretty much the only thing I've done differently is use fscanf instead of fgets in conjunction with atoi

(+ I've optimised a little bit to do both parts in the same loop)

[pihentagy]

Python, why make it complicate if it is so siple?

for (a,b) in itertools.combinations([int(n) for n in open('input')], 2): 
    if a+b == 2020: 
        print(a*b) 

[ttyago]

My solution is the same but yours is also more slim!
Good job!

[Jimmy Klein]

Hi !
Here is my solution in PHP.

I try to make a generic function that can handle 2, 3 or more number in the expense report.

Full size here : Advent of Code - Day 1

[Anna]

COBOL:

   IDENTIFICATION DIVISION.
   PROGRAM-ID. Advent-of-Code-2020-day-1-part-2.
   AUTHOR. ANNA KOSIERADZKA.

   ENVIRONMENT DIVISION.
   INPUT-OUTPUT SECTION.
   FILE-CONTROL.
       SELECT INPUTFILE ASSIGN TO "d1.input"
       ORGANIZATION IS LINE SEQUENTIAL.

   DATA DIVISION.
   FILE SECTION.
     FD INPUTFILE.
     01 INPUTRECORD PIC 9(4).
   WORKING-STORAGE SECTION.
     01 FILE-STATUS PIC 9 VALUE 0.
     01 WS-ARRAY-LEN PIC 9(3) VALUE 200.
     01 WS-ARRAY PIC 9(4) OCCURS 0 to 200 DEPENDING ON WS-ARRAY-LEN.
     01 WS-SUM PIC 9(4).
     01 WS-PRODUCT-1 PIC 9(8).
     01 WS-PRODUCT-2 PIC 9(12).

   LOCAL-STORAGE SECTION.
     01 I USAGE UNSIGNED-INT VALUE 1.
     01 J USAGE UNSIGNED-INT VALUE 1.
     01 K USAGE UNSIGNED-INT VALUE 1.

   PROCEDURE DIVISION.
   001-MAIN.
        OPEN INPUT INPUTFILE.
        PERFORM 002-READ UNTIL FILE-STATUS = 1.
        CLOSE INPUTFILE.
        PERFORM 004-LOOP.
        STOP RUN.

   002-READ.
        READ INPUTFILE
            AT END MOVE 1 TO FILE-STATUS
            NOT AT END PERFORM 003-WRITE-TO-TABLE
        END-READ.

   003-WRITE-TO-TABLE.
       COMPUTE WS-ARRAY(I) = INPUTRECORD
       ADD 1 to I.

   004-LOOP.
       PERFORM VARYING I FROM 1 BY 1 UNTIL I > WS-ARRAY-LEN
       AFTER J FROM 1 BY 1 UNTIL J > WS-ARRAY-LEN
       AFTER K FROM 1 BY 1 UNTIL K > WS-ARRAY-LEN
         ADD WS-ARRAY(I) WS-ARRAY(J) WS-ARRAY(K) GIVING WS-SUM
         IF WS-SUM = 2020 THEN
           MULTIPLY WS-ARRAY(I) BY WS-ARRAY(J) GIVING WS-PRODUCT-1 
           MULTIPLY WS-PRODUCT-1 BY WS-ARRAY(K) GIVING WS-PRODUCT-2
           DISPLAY WS-PRODUCT-2
           EXIT PERFORM
         END-IF
       END-PERFORM.

[Ryan Palo]

This is awesome! I'm so happy I get to add COBOL to the list  😁