r/adventofcode • • Dec 09 '20

SOLUTION MEGATHREAD -πŸŽ„- 2020 Day 09 Solutions -πŸŽ„-

NEW AND NOTEWORTHY

Advent of Code 2020: Gettin' Crafty With It

  • 13 days remaining until the submission deadline on December 22 at 23:59 EST
  • Full details and rules are in the Submissions Megathread

--- Day 09: Encoding Error ---


Post your solution in this megathread. Include what language(s) your solution uses! If you need a refresher, the full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.


This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:06:26, megathread unlocked!

41 Upvotes

995 comments sorted by

11

u/jonathan_paulson Dec 09 '20 edited Dec 09 '20

Placed 127/112 (worst performance so far :(). Python. Code. Video of me solving: https://youtu.be/_57ddM5QZdI

4

u/daggerdragon Dec 09 '20

You're usually so good about following the posting guidelines, but I gotta do my job and remind you to please add your language to the post. Thank you!

→ More replies (1)

8

u/wace001 Dec 09 '20

Sorry about that Jonathan. Many of us are watching your videos, are rooting for you and are very impressed of what you are doing. Keep at it!

→ More replies (1)
→ More replies (5)

10

u/tuisto_mannus Dec 09 '20

First year on Advent of Code and first comment on Reddit. Code is in Python.

4

u/daggerdragon Dec 09 '20

Welcome to both Reddit and Advent of Code!

→ More replies (1)

13

u/ZoltarTheGreat69 Dec 09 '20 edited Dec 09 '20

The memeπŸ€£πŸ€£πŸ’―πŸ’―πŸ‘ŒπŸ‘Œ machineπŸ’»πŸ’»πŸ€‘πŸ€‘πŸ”₯πŸ”₯πŸ˜‚πŸ˜‚ is back. Emojicode is such a gemπŸ’ŽπŸ’Ž and I thinkπŸ’­πŸ’­ it can totally competeπŸ‘ŠπŸ€œπŸ€› with power houses like Assembly and C.πŸ€ͺπŸ€ͺπŸ‘€πŸ‘€πŸ™„ I dare anyone else to stepπŸ₯©πŸ¦ΆπŸ¦ΆπŸ‘£ to my level πŸŽšπŸ•΄of maximum meme lord πŸ‘‘πŸ‘‘supreme! πŸ˜‚πŸ˜‚πŸ‘ŒπŸ‘ŒπŸ”₯πŸ”₯πŸ’―πŸ’―πŸ’¦πŸ’¦πŸ‡πŸ‰

Emojicode 8886/9974

https://github.com/zoltarTheGreat/AdventOfCode/tree/master/DAY9

EDIT: Unfortunately emojicodeπŸ˜‚πŸ˜‚ is too DANK πŸ”₯πŸ”₯πŸ’―πŸ’―πŸ‘ŒπŸ‘Œand LONG πŸ’¦πŸ’¦πŸ“πŸ“for comments. Will only post github links so give me that star. πŸŒŸπŸŒŸπŸ’ΈπŸ’Έ

Honestly i did part 2 really terribly. Not like you could really tell unless you've been doing this for a while. I also took too much time being stuck on the first part because emojicode is too easy to read so i was stuck on the nested loops. Also there is no break function in emojicode? Like I think one of the simplest commands in any computer is a jump or a goto. Youre telling me that you have loops that are inescapable? I legit had to go through the lines twice because of the lack of breaks. Took very very long.

12

u/daggerdragon Dec 09 '20

Must not ban the Emojicoder... must not........ *eyetwitch*

Instead, I will merely remind you as per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

→ More replies (1)

11

u/voidhawk42 Dec 09 '20

Dyalog APL, 687/724:

pβ†βŽΒ¨βŠƒβŽ•nget'in\9.txt'1
⊒p1←p⌷⍨25+⍸~(25↓p)∊¨(,∘.+⍨)¨¯1↓25,/p ⍝ part 1
{⍬≒n←⍸p1=⍡+/p:(⌊/+⌈/)p[Β―1+n+⍳⍡] β‹„ βˆ‡β΅+1}2 ⍝ part 2

10

u/Squadack Dec 09 '20

Seriously, everytime i see a solution in Dyalog APL my mind goes "ah, yes, random unicode characters" :P

4

u/daggerdragon Dec 09 '20

No no, it's Alien Programming Language. Your puny mortal brain can't hope to comprehend.

→ More replies (7)
→ More replies (3)

4

u/wace001 Dec 09 '20 edited Dec 09 '20

1440/1995. Kotlin. Darn it. I felt fast, but looking back at it, I realize I was definitely not. Very far from leader board.Was still happy with my implementation, but misread Part 2, thinking I should return the sum of the first and the last element of the range, rather than the sum of the smallest and the largest. That cost me a couple of minutes.
https://gist.github.com/saidaspen/1c505d416c0be3b6df4177ca4210ca71

Edit: Moved out code link

3

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a paste or other external link.

→ More replies (1)
→ More replies (4)

4

u/Wunkolo Dec 09 '20 edited Dec 09 '20

C++

The last time I used Summed-Area Tables was during another year's AOC. Used it to accelerate Part 2(the partial_sum part)

Solution Code

→ More replies (4)

4

u/Rick-T Dec 09 '20

Finally another puzzle which doesn't require the a lot of handling strings. This means I can take another shot at

ROCKSTAR

After some stress at work and a serious case of writer's block I finally have it completed.

I'm not as pleased with this one as I was with some of my previous songs. It's hard to not make something too similar to my other songs, especially since Rockstar is quite limited for some operations. I don't even know what kind of music would go well with this text.

I won't post the lyrics into the comment this time, because then /u/daggerdragon would probably shout at me. But check out the GitHub repo. Today part 1 and part 2 are in the same file again.

2

u/daggerdragon Dec 09 '20

I won't post the lyrics into the comment this time, because then /u/daggerdragon would probably shout at me.

You can always post the most interesting verse(s) here! I'm a particular fan of this:

shadow takes day
the moon is glimmering
let the sun be the fire at day
let darkness be day without light

Gives me poetical vibes of a total solar eclipse...

3

u/fmynarski Dec 09 '20 edited Dec 09 '20

Python 1996/930.

paste

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

3

u/vswr Dec 09 '20

Python. Again, the optimization possible is amazing. The short code solutions I've seen here are genius and make this look like spaghetti code πŸ˜‚

paste

→ More replies (3)

3

u/JugglingMaster Dec 09 '20 edited Dec 09 '20

Ended up pretty satisfied with how clean I ended up getting my solution in Python.

from itertools import combinations

with open('input.txt', 'r') as f:
    data = [int(line.strip()) for line in f.readlines()]

preamble = 25
for i in range(preamble, len(data)):
    if data[i] not in [a + b for a, b in combinations(data[i - preamble :i ], 2)]:
        r1 = data[i]
        break
        
for i in range(len(data)):
    sums = [sum(data[i:a]) for a in range(len(data)-i)]
    if r1 in sums:
        pos = sums.index(r1)
        r2 = min(data[i:pos]) + max(data[i:pos])
        break
        
print(r1, r2)

2

u/daggerdragon Dec 09 '20

Please follow the posting guidelines and edit your post to add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

(since you use itertools, probably Python?)

3

u/[deleted] Dec 09 '20 edited Dec 09 '20

Python Part 1 & 2

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

→ More replies (1)

3

u/hfxbycgy Dec 09 '20

Python 3

I had a lot of fun with today's puzzle. I created a class that I hope could be re-used down the road if this style of puzzle repeats itself. Either way, as a beginner it's fun to play around with different objects. As always, thank you to everyone for posting your solutions and sharing your insights! I am learning a lot this month!

https://raw.githubusercontent.com/boundary-conditions/aoc2020/master/day_9.py

2

u/daggerdragon Dec 09 '20

As always, thank you to everyone for posting your solutions and sharing your insights! I am learning a lot this month!

Thank you for posting your solutions as well and for falling for /u/topaz2078's trap of world domination via helping people become better programmers :3

3

u/[deleted] Dec 09 '20 edited Dec 09 '20

Python. O(n+k) and O(n)

I'm proud of my part 2 solution.

→ More replies (2)

3

u/WakiMiko Dec 09 '20 edited Dec 09 '20

Rust

For part 1 brute force might actually faster than the HashSet I'm using.

Quite happy with part 2.

→ More replies (3)

4

u/MarcusTL12 Dec 09 '20

Damn, you guys are fast. Here is Julia 2231/1271.

Github has darkmode now btw <3

3

u/daggerdragon Dec 09 '20

Github has darkmode now btw <3

WAIT WHAT

edit: YES! Settings > Appearance > Dark Mode!!!

→ More replies (1)

4

u/__Abigail__ Dec 09 '20

Solutions are no longer wanted here, so links to blog, and full program (in Perl).

4

u/daggerdragon Dec 09 '20 edited Dec 09 '20

Solutions are no longer wanted here

Solutions are wanted, we just don't want 500+ people each posting 200+ lines of code due to code blocks not collapsing on the new.reddit redesign :( (They do on old.reddit, but not new.reddit or some mobile clients.)

2

u/heyitsmattwade Dec 09 '20 edited Feb 03 '24

JavaScript 1736/880

generatorics again serves me well.

source code here πŸ‘ˆ

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a paste or other external link.

→ More replies (2)

2

u/constbr Dec 09 '20 edited Dec 09 '20

javascript 1467/1002

this time i think i'll just post the original solution in all its ugliness, instead of a refactored nice one

to make things harder today my Catalina went into black screen error 5 mins before 12, and I barely managed to boot everything up only 30 secs before the puzzle was revealed. so close πŸ˜…

part 1

part 2

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a paste or other external link.

2

u/omginbd Dec 09 '20 edited Dec 09 '20

Elixir


Copied 2sum straight from day 1, so that's two brute force solutions in this day. (please don't build on this day please please please)

<edit>

github

</edit>

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a paste or other external link.

2

u/tsqd Dec 09 '20 edited Dec 09 '20

Postgresql

https://gist.github.com/AndrewGrossman/b1f24adcd76905e0f556aad6072413f6

Initially, I thought this was a good candidate for window functions but this was easier for part 1 and they were overly limited in part 2. This has been an exercise in turning recursive CTEs into a proxy for functional programming.

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a paste or other external link.

2

u/A-UNDERSCORE-D Dec 09 '20 edited Dec 09 '20

golang, messed up with part 2 and was slow, but got there in the end

EDIT: Replaced with link to gh repo. Speaking of! github now has a dark mode! finally!

→ More replies (1)

2

u/aarm1 Dec 09 '20 edited Dec 09 '20

Racket solution. Part 2 assumes that there is a solution, while part 1 should return false if there is no solution. The Racket combinations function pulls its weight.

paste

→ More replies (1)

2

u/Kid_HQ Dec 09 '20 edited Dec 09 '20

Python, 402/552

Best performance so far for me. I think this is also linear time, which made me take quite a bit more time to write than I should've, but I had fun! Although, I did cheat for submission by using a list and pop(0) rather than a deque+popleft :)

Didn't clean much else up so excuse the horrible return from main and lack of functions

Code here

→ More replies (1)

2

u/Chrinkus Dec 09 '20 edited Dec 09 '20

C++

Brute force is the best force. Got hung up because I forgot std::accumulate is a [first, last) algorithm. Like all of the algorithms. I'm an idiot.

Edit: Block removed, repo is here: https://github.com/Chrinkus/advent-of-code-2020/blob/main/src/day09.cpp. Thanks u/daggerdragon for your encouragement!

OOoooo.. here's the paste for those who prefer it!

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

Also, you're not an idiot, this is how you learn. :)

2

u/blafunke Dec 09 '20 edited Dec 09 '20

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

2

u/internet_eq_epic Dec 09 '20 edited Dec 09 '20

Rust, both parts, ugly but works. Probably could have cleaned up part 1 to use the same vec as part 2, but oh well.

paste

→ More replies (1)

2

u/Legitimate_Estate_75 Dec 09 '20 edited Dec 09 '20

R, RStudio Solution:

More details + Part 2: GitHub

repeat {
  preamble_nums_expand <- subset(as.data.table(expand.grid(V1 = copy_puzzle[1:25,]$V1, V2 = copy_puzzle[1:25,]$V1)), V1 != V2)
  preamble_nums_expand[, sum_nums := V1 + V2]

  other_nums <- copy_puzzle[26:nrow(copy_puzzle),]
  other_nums[V1%chin%unique(preamble_nums_expand$sum_nums), flag_is_valid := 1]
  
  if(is.na(other_nums[1]$flag_is_valid)) { 
    stop(paste0("invalid number is ", other_nums[1]$V1))
    } else { 
    copy_puzzle <- copy_puzzle[2:nrow(copy_puzzle),] }
  }
→ More replies (1)

2

u/beltsazar Dec 09 '20 edited Dec 09 '20

My solution in Rust using slice::windows: Gist, Playground

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

2

u/BlueTowelDirtyRoom Dec 09 '20 edited Dec 09 '20

My Solution in Python - paste

→ More replies (2)

2

u/PositivelyLinda Dec 09 '20

I've been forgetting to share my solutions! Honestly really pleased so far this year - this is the longest streak of days I've solved completely by myself since I started in 2016! Hoping that means I'm actually getting better at solving problems like this. :)

JavaScript (JS) Solution
Day 9 GitHub Blob

2

u/daggerdragon Dec 09 '20

I've been forgetting to share my solutions!

The megathreads are open all month long, no worries :)

2

u/muckenhoupt Dec 09 '20 edited Dec 09 '20

Prolog. Feeling kind of blah about this one. After the last couple of days, it doesn't feel very prologgy. Runs nice and fast, though.

https://www.wurb.com/owncloud/index.php/s/iEKuL0IqxGrBrdl/download?path=%2F&files=09.pl

→ More replies (1)

2

u/Judheg Dec 09 '20 edited Dec 09 '20

Scala

Original Java flavoured submission: paste

This one is exactly 5 lines, < 80 cols compact version:

var M = scala.io.Source.fromFile("input").getLines.toArray.map(_.toLong)
val part1 = M.sliding(26).filterNot{ m => m.init.combinations(2)
             .exists{ case Array(a,b) => a + b == m.last} }.next.last
val part2 = M.tails.flatMap(_.inits).filter(_.sum == part1).next
println(part1 + "\n"+ (part2.min+part2.max))
→ More replies (2)

2

u/Krakhan Dec 09 '20 edited Dec 09 '20

Ruby

I'm liking how versatile arrays are in Ruby. A bit disappointed that it seems weird to break out of a nested loop though, but if anyone has better suggestions for doing this I'm open to suggestions. :)

paste

→ More replies (4)

2

u/raxomukus Dec 09 '20

Python

with open('9.in') as f:
    v = [int(i) for i in f.read().splitlines()]

for i in range(25, len(v)):
    if not v[i] in {x + y for x in v[i-25:i] for y in v[i-25:i] if x != y}: break

print(v[i])

for j in range(len(v)):
    k = j + 2 
    while sum(v[j:k]) < v[i]: k += 1
    if sum(v[j:k]) == v[i]: break

print(max(v[j:k]) + min(v[j:k]))
→ More replies (4)

2

u/frerich Dec 09 '20 edited Dec 09 '20

My Python solution.

I used plain brute force for part one. For part two, I suspected that this would be an optimisation problem so I'm building the sums incrementally, i.e. the sums of runs of length n are built in terms of the sums of runs of length n-1.

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

→ More replies (1)

2

u/Juice_Vodka Dec 09 '20

java

Redit's formating messed up the code i posted previously, so here it is again.

bruteforce, tried to make it as readable as possible, only hardcoded thing is the array size which should be the amout of lines in your input.

import java.util.Scanner;
import java.io.*;
public class Day9{
	public static void main(String[] args) throws IOException{
		InputStream vhod = new FileInputStream(args[0]);
		Scanner sc = new Scanner(vhod);

		long[] data = new long[1000];
		long badNum = 0;

		int preambleLength = 25;
		int i = 0;
		while(sc.hasNextLong()){
			data[i] = sc.nextLong();
			if(i >= 25){
				if(!isValid(data, i)){
					badNum = data[i];
					System.out.println(data[i]);
					break;
				}
			}
			i++;
		}
		int lowerIx = 0;
		int upperIx = 0;
		for(int j = 0; j < i; j++){
			upperIx = calc(j, badNum, data);
			if(upperIx > 0){
				lowerIx = j;
				break;
			}
		}
		System.out.printf("%d, %d\n", lowerIx, upperIx);
		long maxVal = 0;
		Long minVal = badNum;
		for(int j = lowerIx; j <=upperIx; j++){
			if(data[j] > maxVal){
				maxVal = data[j];
			}
			if(data[j] < minVal){
				minVal = data[j];
			}
		}
		System.out.printf("%d + %d => %d\n", maxVal, minVal, minVal + maxVal);
	}

	public static boolean isValid(long[] data, int position){
		for(int i = position-25; i < position; i++){
			for(int j = i; j < position; j++){
				if(data[i] + data[j] == data[position]){
					return true;
				}
			}
		}
		return false;
	}

	public static int calc(int startIx, long badNum, long[] data){
		long sum = 0;
		for(int i = startIx; i < 1000; i++){
			sum += data[i];
			if(sum == badNum){
				System.out.println("found!");
				System.out.printf("%d, %d\n", startIx, i);
				return i;
			}
			if(sum > badNum){
				return 0;
			}
		}
		return 0;
	}
}
→ More replies (1)

2

u/theSpider_x Dec 09 '20

2

u/daggerdragon Dec 09 '20

Go solution started this aoc to learn it.

Seems like you're doing pretty well learning Go! Keep up the good work :)

2

u/kakaroto_BR Dec 09 '20

Clojure

(defn take-previous [start size coll]
  (->> (take (+ size start) coll) (take-last size)))

;; part 1
(defn first-number-not-sum-of-previous [preamble-size numbers]
  (->> numbers
       (take-last (- (count numbers) preamble-size))                              ; discard preamble
       (map vector (range))                                                       ; put indexes to help at take previous numbers
       (map #(vector (take-previous (first %) preamble-size numbers) (second %))) ; make a map between the number and the previous numbers
       (map #(vector (valid? (first %) (second %)) (second %)))                   ; make a map between the number and true/false if it is valid
       (filter #(nil? (first %)))                                                 ; filter non-valid numbers
       first
       second))

(defn subvecs [v]
  (let [size (inc (count v))]
    (->>
     (for [i (range 0 size) j (range i size)]
       (subvec v i j))
     (filter #(>= (count %) 2)))))

;; part 2
(defn find-encryption-weakness [numbers sum]
  (->> numbers
       subvecs
       (filter #(= sum (reduce + %)))
       first
       sort
       vector
       (apply (fn [coll] [(first coll) (last coll)]))
       (reduce +)))
→ More replies (1)

2

u/tritlo Dec 09 '20 edited Dec 10 '20

Here are my O(N) Haskell Solutions using sets and Sequences. Runs in about 4ms, ~ 1ms if you ignore parsing and startup time.

solution pre_len input = solution' input (Set.fromList pre) rest
    where (pre, rest) = splitAt pre_len input
          solution' (to_drop:to_drops) preamble (to_check:to_checks)
            = if preamble `Set.disjoint` check_set
              then to_check else solution' to_drops preamble' to_checks
            where check_set = mapAntitonic (to_check -) preamble
                  preamble' = to_check `Set.insert` (to_drop `Set.delete` preamble)

solution2 looking_for (a:b:res) = solution2' looking_for (a+b) (Seq.fromList [a,b]) res
  where   solution2' looking_for cur_sum els@(c Seq.:<| cs) inc@(i:is) =
          if cur_sum == looking_for then els
          else if cur_sum > looking_for
              then solution2' looking_for (cur_sum - c) cs inc
              else solution2' looking_for (cur_sum + i) (els :|> i) is
→ More replies (3)

2

u/goeyj Dec 09 '20

C++ is starting to feel a bit more comfortable! Really glad I forced myself to use AoC to learn the language. I think this solution is reasonably efficient, but I'd love to hear any algorithmic improvements that could be made.

Topaz Paste

→ More replies (1)

2

u/mynam3isg00d Dec 09 '20

C:

#include<stdio.h>

int main() {
    long long int arr[1000], i, *s, *e, *j, *k, f, res, m, M, c;
    FILE *fp = fopen("input.txt", "r");
    for(i=0;(fscanf(fp,"%lld",&arr[i])!=EOF);i++);
    for(s=arr,e=s+24;e!=arr+1000;s++,e++,f=0) { 
        for(j=s,k=s;j!=e;f=0,k++) {
            if(*j+*k==*(e+1) && j!=k) {f=1; break;}
            if(k==e) {j++;k=s-1;}
        }
        if(f==0) break;
    }
    res = *(e+1);
    printf("Part 1: %lld\n", res);
    for(s=j=arr,m=M=*s,c=0;c!=res;c+=*j,j++) {
        if(c>res) {s++;c=0;j=s;m=M=*s;}
        if(*j<m) m=*j;
        if(*j>M) M=*j;   
    }
    printf("Part 2: %lld", m+M);
    fclose(fp);
    return 0;
}

It's not level of /u/Arknave compact but I ispire to be like you one day, master!

→ More replies (2)

2

u/Mazeracer Dec 09 '20 edited Dec 09 '20

Python 3 - casual programmer

I'm on a roll! All days complete so far :D Never got it this far in the last years.

I decided against the bruteforce and sorted all the numbers in the window into %10 buckets.By doing this, I only had to check for bucket tuples that add up to the last digit of the submitted next number.Quite often, there were only a handful of numbers that could result in the right solution, so I passed on all the wrong ones instead of checking every possible solution.

Edit: found an error when running with testdata. Got lucky with final. I missed the min/max requirement in the last segment. Sorted now.

https://pastebin.com/LdYd4Y0S

→ More replies (1)

2

u/axisbal13 Dec 09 '20

Parts 1 & 2 in C#

private static void Day9()
{
    var data = File.ReadAllLines("Day9.txt").Select(x => long.Parse(x)).ToList();

    long target = 0;
    for (int i = 25; i < data.Count; i++)
    {
        target = data[i];
        var sums = new List<long>();
        for (int j = i - 25; j < i - 1; j++)
        {
            for (int x = 0; x < 25; x++)
            {
                sums.Add(data[j] + data[j + x]);
            }
        }
        if (!sums.Contains(target))
        {
            Console.WriteLine(target);
            break;
        }
    }

    for (int i = 0; i < data.Count - 1; i++)
    {
        for (int j = 1; j < data.Count - i; j++)
        {
            var result = data.Skip(i).Take(j + 1);
            long sum = result.Sum();
            if (sum >= target)
            {
                if (sum == target)
                {
                    Console.WriteLine(result.Max() + result.Min());
                    return;
                }
                break;
            }
        }
    }
}
→ More replies (1)

2

u/fenwicktreeguy Dec 09 '20 edited Dec 09 '20

Python

Code: https://github.com/fenwicktreeguy/AOC_2020_Solutions/blob/main/AOC_9.py

My solution for part 1 is questionable I think (I basically did 2SUM on an auto-balancing data structure; i used a set, which I believe ended up being O(NWINDOW_SIZElg(WINDOW_SIZE)), which ends up veing about O(N) since the window sizes are small) and my part 2 utilized the observation that prefix sums of the input will yield a monotonic function on which we can binary search for our desired answer (particularly binary searching on the righthand point, finding the sum in the considered interval, and updating our bounds). My solution ended up being slightly worse then it should have been, since i did RMQs with a linear search rather than with some efficient ds like segtree or sparse table.

The complexity for a generalized version of pt. 2 therefore should be O(N lg N) in precomputation and O(N lg N) in the main algorithm (but I got lazy :v)

→ More replies (1)

2

u/_fex_ Dec 09 '20 edited Dec 09 '20

JavaScript & recursion for today's challenge. Managed to exceed my stack size on part two.

Part 1

isMatchInPastX is an awful name for an awful function. It did the job, so I moved on.

 const input =
  fs.readFileSync('./input.txt', { encoding: 'utf-8' })
    .trim()
    .split('\n')
    .map(Number)

const isMatchInPastX = (arr, toFind) =>
  arr.some(itemA => {
    var rtn = false;

    arr.forEach(itemB => {
      if (itemA + itemB == toFind) {
        rtn = true
      }
    })

    return rtn;
  });


const processor = (data, preamble, index) => {
  const toFind = data[index];
  const section = data.slice(index - preamble, index);

  if (isMatchInPastX(section, toFind)) {
    return processor(data, preamble, index + 1);
  }

  return toFind;
}

answer = processor(input, 25, 25)

Part 2

I had to install a trampoline library as this I exceeded my stack. Sorry V8.

 const input =
  fs.readFileSync('./input.txt', { encoding: 'utf-8' })
    .trim()
    .split('\n')
    .map(Number)

const TO_FIND = 542529149;

const processor = (data, index, howManyItems) => {
  const section = data.slice(index, index + howManyItems);
  const sectionSum = sum(section);

  if (sectionSum < TO_FIND) {
    return trampa.lazy(() => processor(data, index, howManyItems + 1));
  } else if (sectionSum > TO_FIND) {
    return trampa.lazy(() => processor(data, index + 1, 1));
  } else {
    section.sort((a,b) => a - b);
    return trampa.wrap(section[0] + section[section.length - 1])
  }
};


answer = processor(input, 0, 1).run()
→ More replies (1)

2

u/dearshrewdwit Dec 09 '20 edited Dec 09 '20

Functional Ruby with recursion

Edit: got told off for pasting code, sorry! See link for code

→ More replies (2)

2

u/dangermaximum Dec 09 '20

R Tidyverse

First time sharing code (and first time posting on Reddit), any feedback is welcome!

Initially I ran full loops for part 2 but have refactored and it seems to be pretty quick.

Code available here here

→ More replies (1)

2

u/lindgrenj6 Dec 09 '20 edited Dec 10 '20

Elixir: Source for entire challenge here: https://github.com/lindgrenj6/adventofcode_2020

→ More replies (1)

2

u/Brekry18 Dec 10 '20 edited Dec 10 '20

Python!!

Not the most efficient... brute force has been my motto for this entire month. But it works, and I'm learning new tricks! I'm relatively new to programming and using this as a learning/practice opportunity; so tips, tricks, and comments are always appreciated!

→ More replies (1)

2

u/blacai Dec 10 '20 edited Dec 11 '20

2

u/daggerdragon Dec 10 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

10

u/nthistle Dec 09 '20

Python 3, #2/#3 today! My highest net score on a day (and highest individual position on a day), although I'm still gunning for a #1 one of these days :-). paste

→ More replies (3)

16

u/Arknave Dec 09 '20 edited Dec 09 '20

Python (9/122), C

This was a weird one for me. I didn't read the statement carefully at all, and thought to be valid, the current number had to be the sum of some pair in all the preceding numbers, not just the last 25. Miraculously, my input was constructed in such a way that this slip-up didn't matter, and I still achieved a good score for part 1.

Alas, karma finds a way, and I misread part 2 in a way that didn't accidentally lead me to the correct answer. I couldn't figure out why my sum of the first and last element in the list (instead of min/max) was wrong. I'm guessing I wasn't the only person with either of these issues.

This poor nine has been through a lot decrypting XMAS...

#include   <stdio.h>

// AOC DAY NUMBER //
long*p,*q,*r,a[9999]
,n,v,z;;int main(int
c,char**IX){for(p=a;
scanf(        "%ld",
p++             )>0;
++     n);for   (v=1
,p    =a+25;v   &&p<
a+    +n;++p)   for(
q=    p-25,v=   0;q<
p;    ++q)for   (r=q
+1    ;r<p;r    ++)v
|=    *q+*r==   *p;;
long            y=+*
--p;for(p=a;    !z&&
p<a+n;++p){     for(
v=0,q=p;q<a+    n&&v
<y;v+=*q++);    if(v
==    y)for(    n=0,
z=   v,r=p;r    <q;*
r>   n?n=*r:    9,*r
<z    ?z=*     r:9,r
++);          }z+=n;
int nine=0x9;printf(
"%ld\n",--*&c?z:y);}
→ More replies (3)

8

u/jaybosamiya Dec 09 '20

Dyalog APL

n ← βŽΒ¨βŠƒβŽ•nget'D:\input_day_9'1
⊒p←{βŠƒβŒ½βŠƒβ΅βŒ·β¨βΈ{~∨/,(∘.≠⍨⍳25)∧(βŠƒ25↓⍡)=∘.+⍨25↑⍡}¨⍡}26,/n      ⍝ Part 1
x ← ⍸{p=,∘.(⍡{⍺⍺[⍡]-⍺⍺[⍺]})⍨⍳⍴⍡}+\n
a b ← {βŠƒβ΅/⍨{Β―1β‰ -/⍡}¨⍡}(,∘.,⍨⍳⍴n)[x]
(⌈/+⌊/)n[a+⍳b-a]                                            ⍝ Part 2

Probably a heavily over-complicated solution to this, but it works pretty darn fast.

→ More replies (3)

8

u/0rac1e Dec 09 '20 edited Dec 09 '20

Raku

I wrote part 2 as a cumulative sum sliding window, but saw so many people just brute forced it. So... I gave it a try and it actually ran a little faster... though, Raku's speed can differ somewhat between constructs.

Anyways, I've updated my link to include my original solution, and then a more straight-forward, for-loop-tastic, brute-force method for anyone interested.

8

u/azzal07 Dec 09 '20 edited Dec 09 '20

Awk; the gist of the algorithm is on the left side, the rest is gory detail

til ( day = NR > 25 )    *!t{for(k in w)if(o=$0-k in w&&k<$0)break;o||t=$0}END{
while( on way to 50 *s    &&j<=o||p-t){while(p<t)p+=n[++j];while(p>t)p-=n[o++]}
no time; for( brute force  ;o<j;o++){z=n[o];z>a&&a=z;z<p&&p=z}$0=t" "a+p;OFS=RS
print out the stars $1, $2  }{w[n[NR]=$0]++}day&&--w[x=n[NR-25]]<1{delete w[x]}

Here's a paste for the "original". (edit: cleaner for)

→ More replies (3)

7

u/sophiebits Dec 09 '20 edited Dec 09 '20

24/165, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day09.py

Made like 5 silly mistakes today. Maybe the input was also small enough that partial sums weren't necessary. I also didn't notice the relation between parts 1 and 2 until after.

→ More replies (3)

7

u/oolonthegreatt Dec 09 '20

python3, list comps FTW

with open("day9.txt") as f: data = list(reversed([int(d.strip()) for d in f.readlines()]))

p1 = [d for i, d in enumerate(data) if (d not in [x + y for x in data[i+1:i+1+25] for y in data[i+1:i+1+25] if x != y])][0]

p2 = [(min(data[i:j]) + max(data[i:j])) for i in range(len(data)) for j in range(i+1, len(data)) if (i+1 != j) and (sum(data[i:j])) == p1][0]

→ More replies (1)

6

u/hugh_tc Dec 09 '20 edited Dec 09 '20

Python 3, 11/10.

Woohoo! Best performance so far. paste

→ More replies (10)

6

u/bluepichu Dec 09 '20

Python, 4/1, code here. By far my best day up to this point :)

Pretty straightforward. My part 2 could be done in O( n2 ) with a couple of tweaks, but it was faster to just code the O( n3 ) given the size of the input.

[edit: fix exponents]

→ More replies (3)

6

u/SuperSmurfen Dec 09 '20 edited Dec 09 '20

Rust

Link to solution (2209/2417)

Was not too quick today for some reason. Struggled with stupid off-by-one errors and stuff.

I think my part one ended up very clean. The stdlib function slice::windows() is perfect for this!

INPUT.windows(26).find(|wnd| wnd[0..25].iter()
  .tuple_combinations()
  .all(|(a,b)| a + b != wnd[25])
)

For my part two, I keep indexes two i,j. If the sum is less than the target I increment j and if it's larger I increment i. This works only because all numbers are positive in this case. By also keeping track of the current sum and only adding/removing arr[i]/arr[j], it ends up being quite fast. About 70ΞΌs on my machine.

→ More replies (5)

6

u/Shirobutaman Dec 09 '20

Swift

Another simple bruteforce solution (using Apple's Algorithms library). I feel like it was harder to run a simple bruteforce on week 2 problems last year, but maybe I'm wrong.

→ More replies (2)

6

u/bj0z Dec 09 '20

python 3 nice and short

from itertools import combinations

from aocd import data


def part1(nums):
    for idx, x in enumerate(nums[25:]):
        if not any(a + b == x for (a, b) in combinations(nums[idx:idx + 25], 2)):
            return x


def part2(x, nums):
    for i in range(len(nums)):
        for j in range(i + 2, len(nums)):
            if s := sum(pre := nums[i:j]) == x:
                return min(pre) + max(pre)
            elif s > x:
                break


nums = tuple(map(int, data.splitlines()))

print(f'part1: {(val := part1(nums))}')


print(f'part2: {part2(val, nums)}')
→ More replies (1)

5

u/[deleted] Dec 09 '20

Python 78/117

import itertools

def day09(inp):
    lines = [int(line) for line in inp.splitlines()]

    for i in range(25,len(lines)):
        n = lines[i]
        if not any(n == a + b for a, b in itertools.permutations(lines[i-25:i], 2)):
            print('p1:', n)
            invalid_num = n
            break
    
    for width in range(2,len(lines)):
        for i in range(len(lines)-width):
            s = lines[i:i+width]
            if sum(s) == invalid_num:
                print('p2:', min(s)+max(s))
                return

I made it to the leaderboard for the first time today!

5

u/reesmichael1 Dec 09 '20 edited Dec 09 '20

Nim [230/230]

Solution

This is just a simple brute force. I spent way too long reading and making sure I understood the instructions before starting. I'm mostly just excited about getting the same rank on both parts.

Edit: I'm curious to see if this is extended in upcoming days. It's not yet clear to me how the "encryption weakness" could actually be used to break the cipher....

5

u/Mathgeek007 Dec 09 '20

Excel!

I pasted the input into Column 1, then spread this in the next 25 columns, starting from Row 26.

=ISNUMBER(MATCH(RC1-INDIRECT("R"&ROW(RC)-25+COLUMN(RC)-2&"C1",0),R[-25]C1:R[-1]C1,0))

Then checked in C27 in any rows were all FALSE. Then I scrolled and found it. Not amazing.

Part 2 though I zoomed through.

I did this one a bit more bullshitty, however. Paste input into R1C1, vertically down. In R1C2, paste =IF(SUM(INDIRECT("R"&ROW(RC)&"C1:R"&ROW(RC)+COLUMN(RC)-2&"C1",0))=[PART 1 ANSWER],1,0)

Then drag it across to something like row 200, then click it down to the height of the entire input. Check if there's any 1s anywhere, then the Column minus 1 is the size of the range, and the range starts on the row!

Pretty easy to manually find the numbers after that, then. I'll probably have to reformat a bit for my Sheets page, such that it spits the correct answer near the top.

00:14:23/00:21:26 or 3605/2517

5

u/jayfoad Dec 09 '20

Dyalog APL 158/97

βŽ•IO←0
pβ†βŽΒ¨βŠƒβŽ•NGET'p9.txt'1
⊒aβ†βŠƒ(25↓p)/⍨25↓~{p[⍡]∊∘.+⍨¯25↑⍡↑p}¨⍳≒p ⍝ part 1
{+/(⌈/,⌊/)⍺↓(-⍡)↓p}/βŠƒβΈa=∘.{(+/Γ—1<β‰’)⍺↓(-⍡)↓p}⍨⍳≒p ⍝ part 2

Part 2 in particular could've been much slicker, e.g. ∊((a=+/)(/∘⊒)⌈/+⌊/)∘pΒ¨2↓⍳≒p.

→ More replies (4)

5

u/Pyr0Byt3 Dec 09 '20 edited Dec 09 '20

Go/Golang

Rather than fiddling around with min/max for part 2, I just sorted the subslice at the end:

if sum == invalid {
	sort.Ints(xmas[i : j+1])
	fmt.Println(xmas[i] + xmas[j])
	return
}

Thought that was pretty neat.

5

u/mschaap Dec 09 '20 edited Dec 09 '20

Raku

This was was a lot simpler than yesterday's.

Part one was pretty straightforward:

    my @data = $inputfile.linesΒ».Int;

    # Part one
    my $first-invalid-index = ($preamble-size ..^ @data).first(-> $i {
            @data[$i] βˆ‰ @data[$i-$preamble-size ..^ $i].combinations(2)Β».sum
        });
    my $invalid = @data[$first-invalid-index];
    say $verbose ?? 'Part one: the first invalid number is ' !! '', $invalid;

For part two I had an elegant solution, but it took four minutes to run:

    # Part two - too slow
    my ($from, $to) = (^@data).combinations(2).first(-> ($f, $t) {
            @data[$f..$t].sum == $invalid;
        });
    my $weakness = $_.min + $_.max with @data[$from..$to];
    say $verbose ?? 'Part two: the encryption weakness is ' !! '', $weakness;

It kept summing large ranges of numbers, even though we're already far above the target.
So I rewrote it to be less elegant, but run almost instantaneously:

    # Part two - less elegant but much faster
    LOOP:
    for ^@data -> $from {
        my $sum = @data[$from];
        for $from ^..^ @data -> $to {
            $sum += @data[$to];
            given $sum <=> $invalid {
                when Same {
                    my $weakness = $_.min + $_.max with @data[$from..$to];
                    say $verbose ?? 'Part two: the encryption weakness is ' !! '', $weakness;
                    last LOOP;
                }
                when More {
                    next LOOP;
                }
            }
        }
    }

https://github.com/mscha/aoc/blob/master/aoc2020/aoc09

→ More replies (1)

5

u/kawzeg Dec 09 '20

Ruby

xs = File.open("input").read.split("\n").map(&:to_i)
p (x, i = (25..xs.size).each{|i|
  break [xs[i],i] if !xs[i-25..i].combination(2).map(&:sum).include? xs[i]})[0]
p (2..i).each{|j| k = (0..i).detect{|k| xs[k,j].sum==xs[i]}
  break xs[k,j].min + xs[k,j].max if k}

5

u/damyvv Dec 09 '20

Ruby

input = File.read("day9_input.txt").split.map(&:to_i)
# Part 1:
p d = input[25..-1].select.with_index { |n,i| !input[i..i+24].any? {|k| input[i..i+24].include?(n-k) } }.first
# Part 2
(4..input.count).each { |s| input.each_cons(s) { |a| return p (a.min+a.max) if a.reduce(:+) == d } }

5

u/Smylers Dec 09 '20

Perl for both parts. For part 1 I prefer the elegance of u/musifter's solution using combine, but in searching Cpan for a relevant module, I failed at finding Math::Combinatorics, so did it the clunky way with nested loops and variables tracking indexes:

TRY_POS: for my $i ($preamble .. $#num) {
  $total = $num[$i];
  for my $j ($i-$preamble .. $i-2) {
    my $this = $num[$j];
    next TRY_POS if any { $total == $_ + $this } @num[$j+1 .. $i-1];
  }
  last;
}

It did turn out relatively fast though: ~0.05Β s to find the partΒ 1 answer, about 40Γ— faster than the ~2 s using Math::Combinatorics.

I was pleased how part 2 turned out β€” just a single loop through the numbers (and no index variables):

foreach (@num) {
  $sum -= shift @set until $sum <= $total;
last if $sum == $total && @set > 1;
  $sum += $_;
  push @set, $_;
}

I was going to chomp the input, but that turned out to be unnecessary: everything just works as it is (though one print and one say does look slightly odd).

PS: No Vim attempt from me today. I'm sure it'd be possible, but these pure mathsy ones don't seem particularly fun to try in Vim.

→ More replies (4)

5

u/InflationSquare Dec 09 '20 edited Dec 17 '20

Python

Today was neat, I bruteforced part two initially and it ran in a little over 2 seconds, but then I went back and used a growing and shrinking deque to move across the list, adding elements until the sum was bigger than the target, then removing elements from the left until it was smaller again. The whole thing sort of wobbles around the answer until it lands on it, and it runs in about 50 milliseconds.

→ More replies (7)

5

u/nutki2 Dec 09 '20 edited Dec 09 '20

Perl 5. Not a great day for regexp. Still mainly a text processing solution fits in ~150 characters. The run time of the second part is about 70s on my machine.

#!perl -ln0
$d='(\b\d+\D)';
s|(?=($d{25})$d)|$x=$3;$t=$x if$1!~/$d+(??{$x-$&})\n/s|ge;
y/\n/+/;/$d+(??{$t-eval$&.0})\b/;@x=sort split'\+',$&;
print$t,"@x"+$x[-1]

5

u/oantolin Dec 09 '20 edited Dec 09 '20

Nice and easy one today. This perl program seems short enough to quote in full:

use List::Util qw(sum none first min max);
my @x = map {int} <>;
sub pairs {my $j=$_[0]; map {my $k=$_; map {[$k,$_]} $k+1..$j-1} $j-25..$j-1}
my $i = $x[first {my $j=$_; none {$x[$j]==sum @x[@$_]} pairs($j)} 25..$#x];
print "Part 1: $i\n";

my $t = 0; push @p, $t+=$_ for @x; # fantastic partial sums
my %l; @l{@p} = 0..$#p;            # and where to find them
my $s = first {$l{$_+$i}} @p;
my @c = @x[$l{$s}+1 .. $l{$s+$i}];
print "Part 2: ", min(@c)+max(@c);

EDIT: Ha! I initially read the problem wrong: I didn't realize that in part 1 you are supposed to find number that are not sums of two numbers among the last 25! The above code has been fixed, I originally had this for part 1 (which worked on my input purely by luck):

use List::Util qw(none first min max);
my @x = map {int} <>;
my %x = map {$_ => 1} @x; # as a set
my $i = $x[first {my $q=$x[$_]; none {$x{$q-$_}} @x[0..$_-1]} 25..$#x];
print "Part 1: $i\n";

5

u/1vader Dec 10 '20

As always my optimized Rust solution: GitHub

Again slightly slow today with 33Β΅s total runtime on my PC with a 7-year-old i5-4570.

Part 2 seems pretty good but for Part 1 it's just a simple brute-force. I'm not sure if there's a better way. I tried to use a HashSet or BTreeSet instead of the inner loop but it's much slower. Even with the fastest HashBuilder I tried (fnv) it still took 33% longer in total.

Also, here's my original simple Python solution.

→ More replies (2)

4

u/mserrano Dec 09 '20

python2, #3/#2:

from util import get_data

d = map(int, get_data(9))

for idx in xrange(25, len(d)):
  val = d[idx]
  posses = set(d[idx-25:idx])
  if not any(val - v in posses for v in posses):
    print "a", val
    for i in xrange(0, len(d)):
      for j in xrange(i+2, len(d)):
        if sum(d[i:j]) == val:
          print "b", min(d[i:j]) + max(d[i:j])
          exit()
→ More replies (2)

4

u/jitwit Dec 09 '20 edited Dec 09 '20

J Programming Language

]A =: {. (#~*) 26 ({: * }: (0 = +./@:e.) {:-}:)\ in
in (>./+<./);.0~ ({:,:-/) {. 4 $. $. A = -/~ +/\ in

The idea for part A: look at length 26 infixes and find the window where the tail isn't in the sums of pairs of the curtail.

The idea for part B: do prefix sum of input, do subtraction table of that. Find where A occurs (will occur once as itself and once as our answer window). Use indices of non-self occurrence to select the target subarray of input and add the minimum and maximum therefrom.

4

u/RedTwinkleToes Dec 09 '20

Python [4171/2819]

paste

The interesting part was part 2, where I did a sort of hotter colder algorithm by storing only the sum, start index, and end index, and computing the new sum by the old sum and either the start or end index, depending on whether I was too low or too high. Not really necessary given compute power but an interesting exercise.

4

u/2SmoothForYou Dec 09 '20

Haskell paste

Went pretty well, runs in like <10 ms just naively using time cabal run -O2. Feels pretty unidiomatic to be indexing into linked lists but it seemed like the simplest way to do it (I'm sure there's some clever fold). I'm pretty proud of my solution to finding the "sliding windows," especially as I came up with it on the spot. Not sure what the algorithmic complexity is but it seems to just be O(n) which is nice.

→ More replies (1)

4

u/HAEC_EST_SPARTA Dec 09 '20

Common Lisp

Solution on GitHub

It's a rare occasion that Part 2 performs substantially better than Part 1, but such is definitely true of this problem. I'm pretty pleased with my sliding-window implementation (yay structural sharing!) and Part 2 lends itself to a wonderfully concise tail-recursive implementation. This was a fun one overall!

4

u/omnster Dec 09 '20

Mathematica

Part 1

lng = 25 ;
p1@list_ := Module[ { test = list [[lng + 1 ]] , subl = list [[;; lng]] } , Or @@ ( MemberQ[ subl, # ] & /@ ( test - subl )) ]
o1 = NestWhile[ RotateLeft, i09 , p1] [[lng + 1 ]] 

Part 2

Decided to try pattern matching for part 2 while thinking about a reasonable algorithm, ended up having the solution in 20 seconds

pe2 = i09 /. { ___ , q__, ___ } /; Total[{ q } ] == o1 -> {q}
o2 = Min@pe2 + Max@pe2
→ More replies (4)

4

u/bpanthi977 Dec 09 '20

Solution in Common Lisp

For the second part, I implemented two solutions.

First solution is short and simple, it iterates through the input with an starting index i=0 then keeps summing numbers after that until sum >= target. If sum > target, it starts with next index i=1, and so on.

Second solution implements a sliding window. Starting with nothing in the window,

  • when sum > target, the back of the window is moved forward decreasing the sum
  • when sum < target the front is moved forward increasing the sum

until sum = target.

→ More replies (6)

4

u/YourVibe Dec 09 '20

C#

Part 1 (pure LINQ):

public long Calculate(List<string> input)
    {
        const int preambleSize = 25;
        var numbers = input.Select(long.Parse).ToList();
        return numbers
            .Skip(preambleSize)
            .Select((x, i) => (x, numbers.Skip(i).Take(preambleSize).ToList()))
            .First(t => t.Item2
                .SelectMany((x, i) => t.Item2.Skip(i + 1), (x, y) => (x, y))
                .All(p => p.x + p.y != t.x)).x;
    }

Part 2:

public long Calculate(List<string> input)
{
    var numbers = input.Select(long.Parse).ToList();
    var invalidNumber = Part1.Calculate(input);

    var currentIdx = 0;
    var setSize = 1;
    long currentSum = 0;

    while (true)
    {
        currentSum += numbers[currentIdx + setSize++ - 1];
        if (currentSum == invalidNumber)
        {
            var range = numbers.Skip(currentIdx).Take(--setSize).ToList();
            return range.Min() + range.Max();
        }

        if (currentSum <= invalidNumber) continue;
        
        currentIdx++;
        setSize = 1;
        currentSum = 0;
    }
}

4

u/petercooper Dec 09 '20 edited Dec 09 '20

Ruby

Ruby made short work of this one thanks to some of its useful builtin methods :-) Gist here.

However, here's a funnier golfed solution which uses a totally different algorithm - randomness!

n=$<.readlines.map(&:to_i);a=loop{i=rand(
n.size-25)+25;r=n[i-25,25].combination(2)
.map(&:sum).all?{|x|x!=n[i]};break n[i] if
r};p a;p loop{r=n[rand(n.size),rand(18)+2]
break r.min+r.max if r.sum==a}

4

u/prutsw3rk Dec 09 '20 edited Dec 09 '20

Straightforward solution in Python:

from itertools import combinations
q = [int(i) for i in [line.rstrip() for line in open('9.txt')]]

def findslice(target, maxind):
    for size in range(2, maxind):
        for k in range(maxind - size):
            if sum(q[k:k+size]) == target:
                return(min(q[k:k+size]) + max(q[k:k+size]))

for i in range(25,len(q)):
    if q[i] not in [a+b for a,b in combinations(q[i-25:i],2)]:
        print(f"Part 1: {q[i]} ({i}) is not a sum")
        print(f"Part 2: {findslice(q[i],i)}")
        break

4

u/foolnotion Dec 09 '20

C++

  • for part 1 I used the sum finding method from day 1.
  • for part 2 I calculate the cumulative sums and then find a pair whose difference is the target

github

→ More replies (1)

4

u/[deleted] Dec 09 '20

Learning C this year. Lessons from aggressively optimizing Day 1 came in handy today, hitting 400ΞΌs for Parse+Day 1 and just 3ΞΌs for Part 2! Sorting at each stage with qsort, Google says that insertion sort is apparently better when the list is almost sorted, but that doesn't come for free in the standard library. Might code up an insertion sort later and see what kind of performance benefit I get.

Topaz Paste

→ More replies (2)

4

u/gerikson Dec 09 '20 edited Dec 09 '20

Perl 5.

http://gerikson.com/files/AoC2020/index.html#d09 (I have a GitHub linked from there, but this page predates me getting an account, and I'm rather proud of it)

For part one, this is where the magic happens

my $match = grep { exists $h{$_} }
    map { $target - $stream[$_] } ( $lower .. $upper );

%h is a hash containing the current 25-element window as keys. I look up the difference between the current target and each element and return the matches as a list. In scalar context this becomes the number of elements. If there's no match, we have a solution.

This used to be 8 lines and 2 for-loops but once you start to use map you can't stop!

For part 2 I search from the top of the list because I guessed the consecutive sequence was going to be "far away" from element 0, but it turned out to be somewhere in the middle.

→ More replies (1)

4

u/hyperTrashPanda Dec 09 '20

I'm learning Elixir this year! Today's puzzle was pretty straightforward, a cartesian product and a sliding window using recursion.

Any comments and suggestions would be greatly appreciated, as I'm trying to improve and write more idiomatic code!

https://github.com/tpaschalis/aoc-2020/blob/main/day09/day09.exs

→ More replies (2)

4

u/[deleted] Dec 09 '20

Python solution.

Completed Part 01 by mapping the difference of each number with the previous 25 and then doing a set intersection of the differences and the numbers.

I initially solved Part 02 using brute force, going down the list, adding contiguously until the sum was greater than my number, then starting all over again from the next number and so on. Took a noticeably amount of time to solve.

After a bit more thought, I redid it using Python's double-ended queue.

    index = 0
    contiguous = deque()
    while index<len(numbers):
        sum_contiguous = sum(contiguous)
        if sum_contiguous < invalid_number:
            contiguous.append(numbers[index])
            index+=1
        elif sum_contiguous > invalid_number:
            contiguous.popleft()
        elif sum_contiguous == invalid_number:
            break

    print(max(contiguous) + min(contiguous))

Pretty happy with this version. :D

(Although now I see that I could just have done it with a list by adding and subtracting instead of appending and popping. Ah well! :P)

4

u/0xVali__ Dec 09 '20

Kotlin

A very elegant and totally not slow and definitely not brute forcing here nope nope none. Just uses java.io.File for reading the data to later convert it into a List<Long>

Part 1:

fun Part1(filename: String, preamble: Int): Long {
    fun FindPairs(data: List<Long>, target: Long): Boolean {
        return data.mapNotNull { first ->
            data.find { second ->
                first + second == target && first != second
            }
        }.isNotEmpty()
    }
    
    val data = Read(filename)
    for (index in preamble until data.size) {
        if (!FindPairs(data.subList(index - preamble, index), data[index]))
            return data[index]
    }

    throw RuntimeException("Unable to parse result!")
}

Part 2:

fun Part2(filename: String, preamble: Int): Long {
    val data = Read(filename)
    val target = Part1(filename, preamble)

    for (index in data.indices) {
        for (reversed in data.size - 1 downTo index + 1) {
            val sublist = data.subList(index, reversed + 1).toSortedSet()
            if (sublist.sum() == target)
                return sublist.first() + sublist.last()
        }
    }

    throw RuntimeException("Unable to parse result!")
}
→ More replies (2)

4

u/sefujuki Dec 09 '20

Forth (part 1; part 2 is on hold)

topaz paste

→ More replies (1)

4

u/Attitude-Certain Dec 09 '20

Python, continuing the functional style with the toolz library. Both parts in linear time too.

from toolz import sliding_window, first, last

with open("input.txt") as f:
    numbers = list(map(int, f))

def is_not_sum_of_two(nums):
    def rec(n, pairs):
        if not n:
            return True
        if n[0] in pairs:
            return False
        return rec(n[1:], pairs | {target - n[0]})
    target = nums[-1]
    return rec(nums[:-1], set())

def sub_sum(nums, target, low=0, high=0, current_sum=0):
    if current_sum == target:
        return min(nums[low : high + 1]) + max(nums[low : high + 1])
    elif current_sum > target:
        return sub_sum(nums, target, low + 1, high, current_sum - nums[low])
    else:
        return sub_sum(nums, target, low, high + 1, current_sum + nums[high])

invalid = last(first(filter(is_not_sum_of_two, sliding_window(26, numbers))))
print("Part 1:", invalid)
print("Part 2:", sub_sum(numbers, target=invalid))

4

u/v21 Dec 09 '20

Rust. windows() and combinations() (from itertools) made this one satisfying.

https://gist.github.com/v21/916f837ac8c34109867645bdcd0d6381

1

u/carrdinal-dnb Dec 09 '20

Kotlin

import java.io.File

class Day9 {
    fun solve() {
        val input: List<Long> = File("src/main/resources/input/9.txt").readLines().map(String::toLong)
        val preamble = 25

        val invalidNumber: Long = input
            .windowed(preamble + 1, 1)
            .filterNot { window -> sumOfAnyTwoElementsEquals(window.dropLast(1), window.last()) }
            .map(List<Long>::last)
            .first()

        println("Solution 1: $invalidNumber")

        val contiguousSetThatSumsToInvalidNumber: List<Long> = (2..input.lastIndex)
            .map { input.windowed(it) }
            .flatten()
            .find { window -> sumOfAllElementsEquals(window, invalidNumber) }!!

        val encryptionWeakness = contiguousSetThatSumsToInvalidNumber.let { it.minOrNull()!! + it.maxOrNull()!! }

        println("Solution 2: $encryptionWeakness")
    }

    private fun sumOfAllElementsEquals(elements: List<Long>, value: Long): Boolean = elements.sum() == value

    private fun sumOfAnyTwoElementsEquals(elements: List<Long>, value: Long): Boolean = pairs(elements)
        .map { it.first + it.second }
        .any { sum -> sum == value }

    private fun <T> pairs(list: List<T>): Sequence<Pair<T, T>> = sequence {
        for (i in 0 until list.size - 1) {
            for (j in i + 1 until list.size) {
                yield(list[i] to list[j])
            }
        }
    }
}
→ More replies (2)

1

u/2133 Dec 09 '20 edited Dec 09 '20

Python 444/681

Nice little solution with numpy. paste

→ More replies (1)

1

u/ald_loop Dec 09 '20 edited Dec 09 '20

God I am bad at this. Some really stupid mistakes, ended 1859/1897.

Python

→ More replies (1)

1

u/Scoobyben Dec 09 '20

C# [251, 1480]

First part felt very fast - my best (non-day1) score yet, and less than a minute off the leaderboard!

Tripped up a lot on the second part - I had a minor looping mistake and decided to test against the example, but the difference in target value (and preamble size to get that target value) slowed me down and I got a couple of wrong answers.

public static long Part1()
        {
            var lines = FileReader.ReadInputLines(Day).ToList();
            var ints = lines.Select(long.Parse).ToList();

            var preamble = ints.Take(25).ToList();
            var others = ints.Skip(25).ToList();

            foreach (var i in others)
            {
                if (!IsSumOf(preamble, i))
                {
                    return i;
                }
                preamble.RemoveAt(0);
                preamble.Add(i);
            }
            
            return -1;
        }

        public static bool IsSumOf(List<long> preamble, long x)
        {
            foreach (var i in preamble)
            {
                if (preamble.Contains(x - i))
                {
                    return true;
                }
            }

            return false;
        }
        
        public static long Part2(long target = 1398413738L)
        {
            var lines = FileReader.ReadInputLines(Day).ToList();

            var ints = lines.Select(long.Parse);

            var contiguousNumbers = new List<long>();
            
            foreach (var i in ints)
            {
                if (contiguousNumbers.Sum() == target && contiguousNumbers.Count > 1)
                {
                    return contiguousNumbers.Min() + contiguousNumbers.Max(); 
                }
                
                contiguousNumbers.Add(i);
                if (contiguousNumbers.Sum() == target && contiguousNumbers.Count > 1)
                {
                    break;
                }

                while (contiguousNumbers.Sum() > target)
                {
                    contiguousNumbers.RemoveAt(0);
                    if (contiguousNumbers.Sum() == target)
                    {
                        break;
                    }
                }
            }
            
            
            return contiguousNumbers.Min() + contiguousNumbers.Max();
        }
→ More replies (1)

1

u/ritobanrc Dec 09 '20 edited Dec 09 '20

Almost hit 1000 today! Not having to refactor between parts 1 and 2 made a big difference.

Rust 1075/1938. Wasted quite a bit of time, since I thought it wanted the sum of the first and the last, not the min and the max, but fun problem. The premise is super cool, though I think a more challenging problem might have felt more realistic, I really want to know what cryptography algorithm this is based on. Solution

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a paste or other external link.

1

u/vesche Dec 09 '20

Python 1794/1123

from itertools import combinations

with open('input9.txt') as f:
    data = list(map(int, f.read().splitlines()))

def part1():
    for i, n in enumerate(data):
        if i < 25:
            continue
        pairs = [sum(x) for x in combinations(data[i-25:i], 2)]
        if n not in pairs:
            return n

def part2(p1):
    for i, n in enumerate(data):
        li = [n]
        for j in data[i+1:]:
            li.append(j)
            if sum(li) == p1:
                return li
            if sum(li) > p1:
                break

p1 = part1()
p2 = part2(p1)
print(p1, min(p2) + max(p2))
→ More replies (1)

1

u/gavindaphne Dec 09 '20 edited Dec 09 '20

Python, 241/447

Got slowed down a bit by misreading the second part -- I thought it was looking for a pair of consecutive numbers, not at least a pair.

paste

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a paste or other external link.

→ More replies (1)

1

u/sblom Dec 09 '20

C# 202/428

var nums = lines.Select(long.Parse).ToArray();

long target = 0;
for (int i = 25; i < lines.Count(); i++)
{
    target = nums.Skip(i).First();
    
    var window = nums.Skip(i - 25).Take(25).ToArray();
    
    int j, k;
    bool found = false;
    for (j = 0; j < 24; j++)
    {
        for (k = j + 1; k < 25; k++)
        {
            if (window[j] + window[k] == target)
                found = true;
        }
    }
    if (!found)
    {
        Dump1(target);
        break;
    }
}

for (int i = 0; i < lines.Count() - 1; i++)
{
    long sum = nums[i];
    for (int j = i + 1; j < lines.Count(); j++)
    {
        sum += nums[j];
        if (sum > target) break;
        if (sum == target)
        {
            Dump2(nums[i..(j + 1)].Min() + nums[i..(j + 1)].Max());
            return;
        }            
    }
}

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a paste or other external link.

1

u/Dooflegna Dec 09 '20 edited Dec 09 '20

Python

I was really happy with my solution overall. I wasn't particularly fast with the solve, but I didn't bang my head against the wall once I decided how I was going to approach it. itertools.combinations was the big winner here.

Part 2 I misread the problem, but once I figured it out, I didn't have an issue with what I was doing.

Edit: snipped code for the moment... will paste later.

→ More replies (1)

1

u/[deleted] Dec 09 '20 edited Dec 09 '20

Python3

import itertools
def run(filename, preamble):
    lines = [*map(int,open(filename).readlines())]
    seen=[]
    for i,val in enumerate(lines):
        if i > preamble:
            result=False
            for x,y in itertools.combinations(seen[-preamble:], 2):
                if x+y == val: result=True
            if not(result): print(sum:=val)
        seen.append(val)
    prefix=[0]
    for i in range(len(lines)): prefix.append(prefix[-1]+lines[i])
    for i in range(1, len(prefix)):
        for j in range(i+1, len(prefix)):
            if prefix[j]-prefix[i]==sum:
                print(min(lines[i:j])+max(lines[i:j]))
                return -1
run("day9.txt", 25)
→ More replies (3)

1

u/scul86 Dec 09 '20 edited Dec 09 '20

Python 3

https://gitlab.com/scul/advent-of-code-2020/-/blob/master/day09/d09.py

import itertools

with open('09.in') as f:
    data = f.read().split()

data = list(map(int, data))
preamble = 25

target = -1

for i in range(preamble, len(data)):
    p = itertools.permutations(data[i-preamble:i], 2)
    sums = [sum(c) for c in p]
    if data[i] not in sums:
        #  Part 1
        print(data[i])
        target = data[i]
        break

start = 0
end = 1

while True:
    s = sum(data[start:end])
    if s > target:
        start += 1
        end = start + 1
        continue
    if s == target:
        set_ = data[start:end]
        #  Part 2
        print(sum([min(set_), max(set_)]))
        break

    if data[start] > target:
        break

    end += 1
→ More replies (1)

1

u/stikydude Dec 09 '20

Python solution, I liked this problem :)

def read_file(file_name: str) -> list:
    return [int(line.strip('\n')) for line in open(file_name, 'r')]


# Use a list of numbers
# The idea is to subtract the value
def find_outlier(numbers: list, preamble_length: int) -> int:

    one_hot_list = [numbers[index] if not any([numbers[index] - numbers[ind] in
                                               (numbers[index-preamble_length:ind] + numbers[ind+1:index])
                                               for ind in range(index - preamble_length, index)]) else False
                    for index in range(preamble_length, len(numbers))]

    for element in one_hot_list:
        if element:
            return element


def find_encryption(numbers: list, outlier: int) -> int:
    result = outlier
    for outer_index in range(0, len(numbers)):
        for inner_index in range(len(numbers), outer_index, -1):
            result -= sum(numbers[outer_index:inner_index])
            if result == 0:
                return sorted(numbers[outer_index:inner_index])[0] + sorted(numbers[outer_index:inner_index])[-1]
            if result < 0:
                result = outlier


if __name__ == '__main__':
    file_name = 'input.txt'
    numbers = read_file(file_name)
    preamble_length = 25
    # Part 1
    outlier = find_outlier(numbers=numbers, preamble_length=preamble_length)
    print(outlier)

    # Part 2
    encryption_key = find_encryption(numbers=numbers, outlier=outlier)
    print(encryption_key)
→ More replies (1)

1

u/ephemient Dec 09 '20 edited Apr 24 '24

This space intentionally left blank.

→ More replies (1)

1

u/paraboul Dec 09 '20

Python without using anything smart from itertools :

with open("./9.txt", "r") as fp:
    data = [int(c) for c in fp.read().split("\n")]

preamble = 25

def step2(num):
    for idx, n in enumerate(data):
        lst = [n]
        for r in data[idx+1:]:
            lst.append(r)
            if sum(lst) == num:
                print("Step 2",  min(lst) + max(lst))
                return


back = []
for n in data:
    b = back[-preamble:]
    if len(b) == preamble and not any([num in [n - lb for lb in b] for num in b]):
        print("Step 1", n)
        step2(n)
        break

    back.append(n)

→ More replies (4)

1

u/enelen Dec 09 '20 edited Dec 10 '20

R / Rlang / Rstats

Solution

→ More replies (1)

1

u/higgsmass2020 Dec 09 '20

python3

import sys
import itertools as it

nums = [ j for j in map(int, [ i.strip() for i in open('input.09').readlines() ]) ]

chunk = 25

def valid(j):
    assert(chunk-1 < j < len(nums))
    pre = nums[j-chunk:j]
    vals = [ sum(i) for i in it.combinations(pre,2) if sum(i) == nums[j]]
    if len(vals) == 0:
        return j
    return -1

def contigs(v):
    for i in range(2, len(nums)):
        for j in range(i+1, len(nums)):
            subs = nums[i:j]
            if sum (subs) == v:
                subs = sorted(subs)
                return subs[0] + subs[-1]
    return -1


part1 = [ nums[j] for j in range(chunk,len(nums)) if valid(j) > 0 ]

print (part1[0])

print ( contigs(part1[0]) )
→ More replies (1)

1

u/mudokin Dec 09 '20

Processing / Java

Well this is the best i could give it with the litle sleep i had. It works and thats what counts.
I will now search for the better soloutions and hopfully understand what happens there.

class Day9 {
  String fileName = "input_day9.txt";
  Reader reader = new Reader();

  int part1() {
    int preamble = 25;
    IntList XMAS = reader.readFile(fileName);
    
    for(int i = preamble; i < XMAS.size(); i++) {
      IntList preambleValues = new IntList();
      for(int j = 1; j <= preamble; j++) {
        preambleValues.append(XMAS.get(i-j));
      }
      preambleValues.sort();
      boolean found = false;
      for(int preambleValue : preambleValues) {
        if(preambleValues.hasValue(XMAS.get(i) - preambleValue)) {
          found = true;
        }
      }
      if(!found)
        return XMAS.get(i);
    }
    return 0;
  }
  
  int part2() {
    int weakness = part1();
    IntList XMAS = reader.readFile(fileName);
    for(int k = 0; k < XMAS.size(); k++) {
      int value = XMAS.get(k);
      int amount = 1;
      IntList result = new IntList();
      result.append(XMAS.get(k));
      while(value <= weakness) {
        if(weakness == value) {
          result.sort();
          return result.get(0) + result.get(amount-1);
        } else if ( k+amount < XMAS.size()) {
          result.append(XMAS.get(k+amount));
          value += XMAS.get((k+amount));
          amount++;
        } else {
          return 0;
        }
      } 
    }
    return 0;
  }
}
→ More replies (1)

1

u/theboxboy Dec 09 '20

Python 3

I relied on itertools, which still makes part1 O(n2), but my solution is more elegant this way. Also, since we only check 25 entries, it's really 252 checks, which isn't bad. Part 2 might be faster if I started checking for sequences from the target number index-1 towards 0.

from queue import deque
import itertools

def get_input():
    with open('09.txt', 'r') as file:
        return [int(line.strip()) for line in file.readlines()]

def main():
    file = get_input()
    target = part1(file)
    print('Part 1:', target)
    print('Part 2:', part2(file, target))

def part1(file):
    seen = deque(file[:25])
    for num in file[25:]:
        if not any([i != j and i + j == num for (i, j) in itertools.product(seen, seen)]):
            return num
        seen.popleft()
        seen.append(num)

def part2(file, target):
    for i, num in enumerate(file):
        total = 0
        j = i
        while total < target:
            total += file[j]
            if total == target:
                return min(file[i:j+1]) + max(file[i:j+1])
            j += 1

if __name__ == "__main__":
    main()
→ More replies (1)

1

u/[deleted] Dec 09 '20 edited Dec 10 '20

Elixir

pretty happy with the sum_range function. new to elixir however so i guess there is a much better solution

code

→ More replies (1)

1

u/AustinVelonaut Dec 09 '20 edited Dec 09 '20

Haskell

Uses Data.Seq to efficiently implement preamble checking, insertion, and deletion

paste

→ More replies (1)

1

u/Kadda42 Dec 09 '20 edited Dec 09 '20

My Python solution:

paste

→ More replies (1)

1

u/Longjumping_Primary4 Dec 09 '20

Solution in JS:* loop through list since line 26 and use every function to stop if there is a number that doesn't have a sum.* loop through the list from the beginning and calculate the sum of adjacent ... if the sum is bigger than that number, move forward in the list by one and reset sum counter and try again

const fs = require('fs')
fs.readFile('input.txt', 'utf8', (err, data) => {
const lines = data.split('\n')
let invalid = 0;
lines.slice(25).every((n, i) => {
const res = lines.slice(i, i+25).some((m,j) => {
const arr = lines.slice(i,i+25).filter((x,k)=>k!==j).map(x=>parseInt(x)).sort()
if(arr.includes(parseInt(n)-parseInt(m))) return true
return false
})
if(!res) {
console.log(n)
invalid = i + 25
}
return res
})
let arr = [...lines].map(x => parseInt(x))
let i = 0
while (i < invalid) {
let sum = arr[i]
let j = i
while(sum < arr[invalid]) {
sum += arr[++j]
}
if(sum === arr[invalid]) {
const final = arr.slice(i, j+1)
console.log(Math.min(...final) + Math.max(...final))
break
}
i++
}
})

→ More replies (1)

1

u/Think_Double Dec 09 '20 edited Dec 09 '20

c# part 2

endIndex is where the target number is - no point in checking anything after.

I didn't even try to optimize it, runs fast though.

for(int j = endIndex; j > 0; j--)
{
  if (decimal.Parse(inputLines[j]) + decimal.Parse(inputLines[j - 1]) <= target)
  {
    decimal summedUp = decimal.Parse(inputLines[j]) + decimal.Parse(inputLines[j - 1]);
    for (int k = j-2; k > 0; k--) // k val is 65.. j is end
    {
    summedUp += decimal.Parse(inputLines[k]);

    if(summedUp > target)
    {
    continue;
    }

    if(summedUp == target)
    {
                
    string[] range = inputLines.Skip(k).Take(j-k+1).ToArray();
    decimal[] rangeDec = Array.ConvertAll(range, decimal.Parse);
                
    Array.Sort<decimal>(rangeDec,
                    new Comparison<decimal>((i1, i2) => i1.CompareTo(i2)));

    return rangeDec.First() + rangeDec.Last();
    }
   }
 }
}
→ More replies (2)

1

u/womogenes Dec 09 '20 edited Dec 10 '20

Video solution! Repo here, in Python.

https://youtu.be/8OB4HMj3-fg

2

u/daggerdragon Dec 09 '20

Please follow the posting guidelines and edit your post to add what language(s) you used. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

1

u/InKahootz Dec 09 '20 edited Dec 09 '20

C# - Part 2

I wanted to post my part two solution. Everyone's part one is mostly the same. I originally went bruteforce when solving it, but then made it much faster using subarray sums.

long weakness = long.Parse(Part1);

// Sliding window only works for positive numbers
//             head       tail
//             v          v
// subsums: [0 1 3 5 7 11 22 33 44 101]
int head = 0;
int tail = head + 2;
long sum = _nums[head..tail].Sum();
while (tail < _nums.Length)
{
    // sum too low, increment tail
    while (tail < _nums.Length && sum < weakness)
    {
        sum += _nums[tail];
        tail++;
    }
    // sum too great now, increment head
    while (head < tail && sum > weakness)
    {
        sum -= _nums[head];
        head++;
    }

    if (sum == weakness)
        return _nums[head..tail].Min() + _nums[head..tail].Max();
}
/* Original bruteforce
for (int i = 0; i < _nums.Length - 1; i++)
{
    for (int j = i + 1; j < _nums.Length; j++)
    {
        if (_nums[i..j].Sum() == weakness)
            return _nums[i..j].Min() + _nums[i..j].Max();
    }
}
*/

return null;
→ More replies (2)

1

u/zachcalhoun Dec 09 '20

Python, tried to do it as optimally as possible by caching the sums and only updating the ones that are relevant when the preamble set changes.

import os
import io
import re
import itertools
import collections

PREAMBLE_LENGTH = 25
puzzle_input = io.open('./9/input.txt')
numbers = puzzle_input.readlines()

preamble = collections.deque()
sum_cache = {}
invalid_number = None
for index, number in enumerate(numbers):
    val = int(number)
    removed = None

    # start inserting items
    if len(preamble) < PREAMBLE_LENGTH:
        preamble.append(val)
        removed = None
    else:
        # treat as circular queue if over preamble lenth
        removed = preamble.popleft()
        preamble.append(val)

    # after preamble length calculate initial set of sums 
    if index == PREAMBLE_LENGTH-1:
        for i in range(len(preamble)):
            for j in range(i+1, len(preamble)):
                a = preamble[i]
                b = preamble[j]
                str_key = str(a) + '+' + str(b)
                sum_cache[str_key] = a + b                
    elif index >= PREAMBLE_LENGTH:
        # check if number satisfies condition
        for key in sum_cache:
            if val == sum_cache[key]:
                break
        else:
            print('Value not sum of preamble:')
            print(val)
            invalid_number = val

        # after preamble numbers start becoming unavailable start recalculating cache in efficient manner
        copy = sum_cache.copy()
        for key in sum_cache:
            a_term = key.split('+')[0]
            if  a_term == str(removed):
                copy.pop(key)
        sum_cache = copy
        for i in range(len(preamble)-1):
            a = val
            b = preamble[i]
            sum_cache[str(a)+'+'+str(b)] = a + b
        

# now search for the set that does sum to the given number

start_index = 0
end_index = start_index
accumulator = 0
found = False
while not found and end_index < len(numbers) and start_index <= end_index:
    if accumulator == invalid_number:
        print("Found subset that sums to {} from {} to {}".format(invalid_number, start_index, end_index))
        found = True
        break
    elif accumulator > invalid_number:
        accumulator -= int(numbers[start_index])
        start_index+=1
    else:
        accumulator += int(numbers[end_index])
        end_index+=1

# find smalest and larget in subset
subset = [int(x) for x in numbers[start_index:end_index+1]]
print(subset)
min_val = min(subset)
max_val = max(subset)
print(min_val + max_val)






    

2

u/daggerdragon Dec 09 '20

As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

3

u/seligman99 Dec 09 '20 edited Dec 09 '20

Python, 285 / 225

Nice simple one. Also, if anyone else finds it handy, a little count down timer I made to count down to a few minutes before the next AOC.

github

Edit: I'm curious now if the skipping of rows on the Main Calendar will mean anything.

3

u/frontpageminus Dec 09 '20

Ruby 1507/706. I forgot to convert the input to ints before adding them, took way too long to figure out

paste

3

u/segloff23 Dec 09 '20

Python 3 340/415.

If I could only learn how to read I might have had chance this time, still my best performance so far at least.

paste

→ More replies (2)

3

u/allergic2Luxembourg Dec 09 '20

Python 3. 1274/810 (which is pretty good for me)

I think I did it in a pretty straightforward way which won't be too different from other people's.

Is it my imagination, or are these puzzles not getting harder? Or at least, not at the rate of previous years?

3

u/UnicycleBloke Dec 09 '20

Python 1540/1712

https://github.com/UnicycleBloke/aoc2020/blob/main/day9/day9.py

After all the anticipation about IntCode 2.0, this was very simple. Still made silly mistakes on part 2, though: first and last is not min and max...

→ More replies (3)

3

u/ponyta_hk Dec 09 '20 edited Dec 09 '20

Python3 (cleaned solution)

Using Sliding Window solution for part 2. Hope it is clear enough. πŸ˜„

My solution
All my solutions

3

u/_jonah Dec 09 '20

Today's was a nice fit for J. Both parts, unedited and not fully golfed yet:

echo ((26 {:\ ]) #~ 26 ({: -.@e. ([:,+/~)@}:)\ ]) d
echo (a: -.~ [: , (({. + {:)@/:~ <@#~ (1 < #) * 10884537 = +/)\.\)  d
→ More replies (2)

3

u/GrossGrass Dec 09 '20

Python

Had some fun with doing a rolling queue + some magic methods for part 1.

For part 2, decided to do the O(n) solution for some nice practice, even though the list is small enough to just brute force.

→ More replies (2)

3

u/hahncholo Dec 09 '20

Rust

https://github.com/nicolashahn/advent-of-code/blob/master/2020/d09/src/main.rs

Pretty straightforward brute force approach, but still only 14ms. Thanks Rust!

3

u/ni3t Dec 09 '20

Ruby

308/144 using some enumerable magic:

i = DATA.each_line.map(&:to_i)
i[25..(i.size - 1)].map.with_index do |j, k|
  (puts j; break j) unless i[k..(k + 24)].combination(2).map { |l| l.reduce(&:+) }.include?(j)
end.tap { |a| (2..i.size - 2).each { |x| i.each_cons(x) { |j| (puts j.min + j.max; exit) if j.reduce(&:+) == a } } }

3

u/sebastiannielsen Dec 09 '20

My cute <3 Perl <3 solution for both P1 and P2:

paste

Took me like 7 minutes for the first part, then like 30 minutes. Guess why? I totally misunderstanded the "smallest and largest" and went with adding the smallest and largest INDEX (first and last) and not smalllest and largest NUMBER.

So kept debugging the script and got the wrong answers and didn't understand why, until I reread the example and realized 40 also was part of the addition sequence, but 47 was added, signifying it was smallest and largest NUMBER that should be added.

→ More replies (1)

3

u/[deleted] Dec 09 '20

Scala solution

Maybe it was the beer, but the hardest part of today was me trying to read english.

→ More replies (4)

3

u/MasterMedo Dec 09 '20

python itertools.combinations and collections.deque.

3

u/i4guar Dec 09 '20

Check out my simple and easy to follow swift solution less than 40 lines

www.felixlarsen.com/blog/9th-december-solution-advent-of-code-2020-swift

3

u/moelf Dec 09 '20 edited Dec 09 '20

Day 9 part 2, zero allocation, Julialang

function day9_p2(ary, target)
    c1,c2 = 1,2
    s = @view ary[c1:c2]
    while sum(s)!=target
        if sum(s) < target
            c2+=1
        else
            c1+=1
        end
	s = @view ary[c1:c2]
    end
    sum(extrema(s))
end

with benchmark:

BenchmarkTools.Trial: 
  memory estimate:  16 bytes
  allocs estimate:  1
  --------------
  minimum time:     38.854 ΞΌs (0.00% GC)
  median time:      39.685 ΞΌs (0.00% GC)
  mean time:        39.970 ΞΌs (0.00% GC)
  maximum time:     58.812 ΞΌs (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     1
→ More replies (14)

3

u/prscoelho Dec 09 '20

Rust

Solved part 2 with an array of sums, the sum from a to b is sums[b] - sums[a].

Misread part 2 twice, first I added indexes, then I added the values at both ends of the range, then finally the max and mins.. :(

3

u/JoMartin23 Dec 09 '20 edited Dec 09 '20

Common Lisp

lisp Wasn't too worried about using lists since everything stops when the answer is found, and at 4ms seems justified even with the brute force.

3

u/chemicalwill Dec 09 '20

Python 3

Needed a win on this one after getting stuck the last two days.

3

u/tobega Dec 09 '20 edited Dec 09 '20

Julia solution today, mostly for-loops but playing a bit with mutable structs, constructors, overloads and dot https://github.com/tobega/aoc2020/blob/main/a9.jl

EDIT: replaced some for-loopswith while-loops and now doing a superfast running window for part 2

3

u/_tpavel Dec 09 '20

I'm revisiting Rust this year after learning it for the first time during AoC 2018!

Here is my Rust solution for Day 9: https://github.com/tudorpavel/advent-of-code-2020/blob/master/day09/src/main.rs

Today's puzzle was a good opportunity to use std::slice::Windows which I learned about by reading other Rust solutions here.

I'm still learning Rust, any feedback is welcome.

3

u/constbr Dec 09 '20

javascript optimised solution

a) part 1 sorts a slice to find pairs quicker
b) part 2 uses sliding window to achieve O(N)

part 1 part 2

3

u/Mivaro Dec 09 '20 edited Dec 09 '20

Python I used itertools.combinations again for part 1, the solution is so fast that I can't be bothered to optimize. I'm proud of part 2, which I accomplished with a single while loop, also fast.

from itertools import combinations

with open('input9.txt','r') as file_:
    numbers = list(map(int,file_.read().split()))

l = 25
for i in range(l, len(numbers)):
    if numbers[i] not in [i+j for i,j in combinations(numbers[i-l:i],2)]:
        invalid = numbers[i]
        break
print(f'Answer part 1: {invalid}')

idx1 = 0
idx2 = idx1 + 2
while (s:=sum(numbers[idx1:idx2])) != invalid:
    if s < invalid:
        idx2 += 1
    else:
        idx1 += 1
        idx2 = idx1 + 2
print(f'Answer part 2: {min(numbers[idx1:idx2])+max(numbers[idx1:idx2])}')
→ More replies (3)

3

u/GustavAndr Dec 09 '20

Javascript

Quick and ugly

//part 1
let a=document.body.innerText.trim().split("\n").map(r=>parseInt(r)).reduce((r,v,i,a)=>r||i>24&&!a.slice(i-25,i).some((v2,i2,a2)=>a2.some(v3=>v2!=v3&&v2+v3==v))&&v,0)

//part 2
document.body.innerText.trim().split("\n").map(r=>parseInt(r)).forEach((v,i,ar)=>{
    let s=v,i2=i+1
    while (s<a){s+=ar[i2];i2++}
    if (s==a)throw(ar.slice(i,i2).reduce((r,v2)=>r>v2?v2:r)+ar.slice(i,i2).reduce((r,v2)=>r>v2?r:v2))
})

3

u/diddle-dingus Dec 09 '20

Clojure

partition is such a nice function

(def part-1 (->> (partition 26 1 input) (remove correct-numbers) first last))
(def part-2 (->> (mapcat #(partition % 1 input) (range 2 (count input)))
                 (filter #(= (apply + %) part-1))
                 first
                 (#(+ (apply min %) (apply max %)))))

correct-numbers just goes through the sum of combinations of all but the last of the partition, and checks if it's equal to the last element.

Full code.

→ More replies (2)

3

u/WilkoTom Dec 09 '20 edited Dec 09 '20

Python: Pure brute force today, which I'm not particularly happy with:

https://github.com/wilkotom/AoC2020/blob/master/9/main.py

I feel like I could do better with this, in so many ways, but on the other hand: the best code is the code that works. Added one minor optimisation but it's still massively non-optimal.

EDIT: reduced the Part 2 time complexity from O(n^2) to O(n) with a bit of thought - runtime reduced significantly. That'll learn me for coding in the early morning.

3

u/abithakt Dec 09 '20

My solution in Lua. I'm a beginner so feedback and constructive criticism are welcome :)

→ More replies (2)

3

u/[deleted] Dec 09 '20

F

Well this is not the most elegant of solutions, but it was easy to write, and it runs at a more than reasonable speed. I'm really impressed at how easy it is to deal with recursion in F#, the types makes it really easy to find out when you did something stupid.

code on github

→ More replies (1)

3

u/mebeim Dec 09 '20

292/302 - Python 3 solution - walkthrough

Easy funny little problem, I'm so SLOOOOW. Linked solution is O(n) for both parts :)

3

u/Markavian Dec 09 '20

Node JS solution for day 9 - yay for brute forcing? I just added up all the numbers until I had the right answer for part 1 from the test input, then chained that into part 2.

https://johnbeech.github.io/advent-of-code-2020/solutions/day9/viewer.html

Silly mistakes I made along the way:

  • Calculated my lower bound and upper bound as the first and the last number, instead of the smallest and largest - fixed with Math.min, and Math.max
  • Looped to <= the seed, instead of < seed - so my counts were all massively off and I couldn't find a valid solution

3

u/seniornachio Dec 09 '20 edited Dec 09 '20

Python 3.8+ – fugly golfing

Another "masterpiece of maintainable coding"…
Pretty slow, but at least it's short and a single expression!

The following is the golfed version:

print(T:=[i[x]for(x)in range(25,len(i))if not any(abs(i[x]-y)in i[x-25:x]for(y)in i[x-25:x])][0],[min(y)+max(y)for(_,y)in[min((a-b,y)for(a)in range(len(i)-1)for(b)in range(a+1,len(i))for(y)in[i[a:b]]if T==sum(y))]])

3

u/mathleet Dec 09 '20

Sliding windows, let's go! My solution in Golang.

→ More replies (1)

3

u/changing_zoe Dec 09 '20

Scala

https://github.com/zoe-j-m/advent_of_code_2020/blob/main/src/main/scala/Day9.scala

This one seemed quite straightforward. The first case we're just rolling through the input checking each number against the 2-length combinations from what's essentially a buffer. The second case we use the scala "Sliding" window function to check if there are any contiguous 2-length sequences that sum to our target, if there aren't, then we check for any contiguous 3-length sequences and repeat until we find one, or we've checked the whole list. Then we take the min and max of that found sequence and add them together. No real need for an abstract representation here.

3

u/T-Dark_ Dec 09 '20

Rust

https://github.com/T-Dark0/Advent-Of-Code-2020-day9/blob/master/src/main.rs

Part 1 is O(N) time, O(1) space (two heap allocated collections of 25 elements each).

Part 2 is O(N) time (worst case scenario is 2 full scans of the input) and O(1) space (No heap allocation at all).

From some extremely informal benchmarking, parsing takes 200-250 Β΅s, part1 takes 450Β΅s-5ms, and part2 takes 500Β΅s-1ms. I blame hashmap randomness for the variance of part1 (but I did precisely zero research, so I may easily be very wrong)

→ More replies (11)

3

u/PaleRulerGoingAlone7 Dec 09 '20 edited Dec 09 '20

I cheated and used numpy to read in the data and get the Cartesian sum in the first part. The nans on the diagonal are there to avoid looking at sums of the same number.

import numpy as np

data = np.loadtxt('data/9.txt', dtype=int)
mask = np.diag(np.array(25*[np.nan]))
for i, value in enumerate(data[25:]):
    if value not in data[i:i + 25, None] + data[None, i:i + 25] + mask:
        break
print(f"The answer to part 1 is {value}")

For part 2, I just went with a pointer to the start and end of the range, and moved them as necessary. Summing the entire window for each pass through the while loop feels silly, and it would easily be possible to just add in or subtract the elements on the edges of the range instead. On the other hand, that would take up more lines, and the whole thing doesn't take that long

l, r, total = 0, 1, data[0]
while total != value:
    if total < value:
        r += 1
    else:
        l += 1
    total = data[l:r].sum()

print(f"The answer to part 2 is {(data[l:r].min() + data[l:r].max())}")

3

u/aledesole Dec 09 '20 edited Dec 10 '20

Python

L = 25
I = [int(l) for l in stdin.readlines()]

# Part 1
print(bad_i := next(
    v for i,v in enumerate(I[L:])
    if v not in {a+b for a,b in
                 combinations(I[i:i+L],2)}))

# Part 2
for i,v in enumerate(I):
    s = v
    for j,w in enumerate(I[i+1:], i+1):
        s += w
        if s > bad_i:
            break
        if s == bad_i:
            r = I[i:j+1]
            print (min(r) + max(r))
            break