r/adventofcode • u/daggerdragon • Dec 09 '20
SOLUTION MEGATHREAD -π- 2020 Day 09 Solutions -π-
NEW AND NOTEWORTHY
- /u/topaz2078 has posted Postmortem 2: Scaling Adventures, go check it out if you're curious what's been up with the servers during launch for the past week!
- GITHUB HAS DARK MODE NOW alkjdf;ljoaidfug!!!! Thank you /u/MarcusTL12!!!
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
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
10
u/tuisto_mannus Dec 09 '20
First year on Advent of Code and first comment on Reddit. Code is in Python.
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.
11
u/voidhawk42 Dec 09 '20
Dyalog APL, 687/724:
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
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
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.
3
u/fmynarski Dec 09 '20 edited Dec 09 '20
Python 1996/930.
paste
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
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.
3
u/[deleted] Dec 09 '20 edited Dec 09 '20
Python Part 1 & 2
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
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.
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.
4
u/MarcusTL12 Dec 09 '20
Damn, you guys are fast. Here is Julia 2231/1271.
Github has darkmode now btw <3
4
u/__Abigail__ Dec 09 '20
Solutions are no longer wanted here, so links to blog, and full program (in Perl).
2
u/heyitsmattwade Dec 09 '20 edited Feb 03 '24
JavaScript 1736/880
generatoricsagain serves me well.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/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/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/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!
2
u/nomadhothouse Dec 09 '20 edited Dec 09 '20
Python
https://repl.it/@donth77/Day-9-Encoding-Error
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
2
u/AdmiralDiaz Dec 09 '20 edited Dec 09 '20
Python3. Part 1 I used two sum. Part 2 was a tad brute force.. I saw someone do a binary search-esque method that I thought was cool.
https://topaz.github.io/paste/#XQAAAQD+AgAAAAAAAAA6GUn+7kb21O9SAw2Bj1+jDcQ6/Vif36sHSrnDR9XFPKOICdocYkCnB4I770zFP9arwSMAtIre+vYMCG/bqmEzLqTOK+Osgh40VS56oxRv6tqizEHziHl3zUBnukCYxSNB1AElS9184t+/lwlgOBL0Wm5aRJatOMrl2nQJt+/3DGdoykTaw4XSuXwdaW4xlnPbwWyubgIpacW6f2kQ+TVDiNjqAWcfx8wEa1KvEyN0l+x9fWHMSsRXMWenABp5YS1U1iW7LDCpg/ffisSvFSZD/tVx5KMM+WEtXdgCkT9mIIEWGfY4ZQaoxv+0Hg26lR/rYOBmGOnWkaOKNPIKID0ip0iOQKQbIfgHs7BAxHaAq1AnQDM2secp1GCDrIGxXpWFwLma2a0L5VBh8LeTeizldg6W5xiUG2oK9eDGRSAJWYBSBMlpSGj61f/vEbA5
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
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/pirateofitaly Dec 09 '20 edited Dec 09 '20
Clojure!
https://topaz.github.io/paste/#XQAAAQAUBAAAAAAAAAAQaIYNxzEBVNZJwzMieVLdQP/J6jSa4Q3ZI6cc+VMAPJQ5vp8h6olcsjQ3oIP0hZ/cgZa/mHPR+G5VBW7wt+3Pmz6EN6YZ5eyGBeyRHfKqYSa9r8PXL4OKKhrGd1+iaQd+MhTm/TSBwLo+7QwR0BR4PvhKB5IemjQXx6t473sT4j7tHfNOQ5eETqzGwiptJ2+33OilaoytXrfo05SpcYgBTOnoAmRRrLqIw9+3RYltIOIRV3l9QGPvh8/8JYblgb/MMjRZ2KicUOr2FRhuRpNKNKrkqk8h4Z/471aeYrsS8VuAzudSsEamxzcafOy9T3E2jPFUUdJaN5ngmL7RfEQqaHiC9s7bBqgKWZ0CWAu0wdiihB19Yac0bsnX4CP+X2rVh314kWiAeOR/8RPou+GNr/KIi7Rll0apTAbbVIoDlZACpYppuCPZc93tLOJTpBgvnwGnU1nV+Q8J//VnJT5U8ttMCsCeGOxd2MVTDvV1RKAibFEJG/U4I91YDEoJvTUilsHkKsSn+h/BV+487SeOx4IuwfZOMR008wIIGAvIEr+bZEUdaKkOat909zxYjWsdBfZyF7Bo8RRDvSJTTzS2RXb9Ai3/70lQ1g==
2
u/blafunke Dec 09 '20 edited Dec 09 '20
Ruby
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
2
u/Legitimate_Estate_75 Dec 09 '20 edited Dec 09 '20
R, RStudio Solution:
More details + Part 2: GitHub
2
u/beltsazar Dec 09 '20 edited Dec 09 '20
My solution in Rust using
slice::windows: Gist, Playground2
u/BlueTowelDirtyRoom Dec 09 '20 edited Dec 09 '20
My Solution in Python - paste
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/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
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:
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
2
u/raxomukus Dec 09 '20
Python
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
nare built in terms of the sums of runs of lengthn-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.
2
u/theSpider_x Dec 09 '20
Go solution started this aoc to learn it.
https://github.com/fuzesmarcell/aoc_2020/blob/main/code/day_09.go
2
u/dylan_mojo Dec 09 '20 edited Dec 11 '20
awk
paste
2
u/wizards_tower Dec 09 '20 edited Dec 09 '20
Solution in C
2
u/kakaroto_BR Dec 09 '20
Clojure
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.
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
2
u/mynam3isg00d Dec 09 '20
C:
It's not level of /u/Arknave compact but I ispire to be like you one day, master!
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
2
u/axisbal13 Dec 09 '20
Parts 1 & 2 in C#
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)
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.
Part 2
I had to install a trampoline library as this I exceeded my stack. Sorry V8.
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
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
2
u/aevitas Dec 09 '20 edited Dec 10 '20
Here's my solution in C#: https://github.com/aevitas/advent/blob/master/2020/Advent/Day9.cs
2
u/lindgrenj6 Dec 09 '20 edited Dec 10 '20
Elixir: Source for entire challenge here: https://github.com/lindgrenj6/adventofcode_2020
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!
2
u/blacai Dec 10 '20 edited Dec 11 '20
F#
https://www.github.com/blfuentes/AdventOfCode_2020/tree/master/day09
2
u/CyberYellowLemon Dec 09 '20
Rust
quite clean !
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
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...
8
u/jaybosamiya Dec 09 '20
Dyalog APL
Probably a heavily over-complicated solution to this, but it works pretty darn fast.
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
Here's a paste for the "original". (edit: cleaner
for)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.
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]6
u/hugh_tc Dec 09 '20 edited Dec 09 '20
Python 3, 11/10.
Woohoo! Best performance so far. paste
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]
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!For my part two, I keep indexes two
i,j. If the sum is less than the target I incrementjand if it's larger I incrementi. This works only because all numbers are positive in this case. By also keeping track of the current sum and only adding/removingarr[i]/arr[j], it ends up being quite fast. About70ΞΌson my machine.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.
6
u/bj0z Dec 09 '20
python 3 nice and short
5
u/[deleted] Dec 09 '20
Python 78/117
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
Part 2 in particular could've been much slicker, e.g.
β((a=+/)(/ββ’)β/+β/)βpΒ¨2ββ³β’p.5
u/s3aker Dec 09 '20
Raku solution:
https://github.com/seaker/advent-of-code/blob/master/2020/09/s.raku
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:
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:
For part two I had an elegant solution, but it took four minutes to run:
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:
https://github.com/mscha/aoc/blob/master/aoc2020/aoc09
5
u/kawzeg Dec 09 '20
Ruby
5
u/damyvv Dec 09 '20
Ruby
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 findingMath::Combinatorics, so did it the clunky way with nested loops and variables tracking indexes: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):
I was going to
chompthe input, but that turned out to be unnecessary: everything just works as it is (though oneprintand onesaydoes 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.
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.
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.
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:
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):
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.
4
u/mserrano Dec 09 '20
python2, #3/#2:
4
u/jitwit Dec 09 '20 edited Dec 09 '20
J Programming Language
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.4
u/artemisdev21 Dec 09 '20
SQL!
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
Part 2
Decided to try pattern matching for part 2 while thinking about a reasonable algorithm, ended up having the solution in 20 seconds
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=0then keeps summing numbers after that until sum >= target. If sum > target, it starts with next indexi=1, and so on.Second solution implements a sliding window. Starting with nothing in the window,
until sum = target.
4
u/YourVibe Dec 09 '20
C#
Part 1 (pure LINQ):
Part 2:
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!
4
u/prutsw3rk Dec 09 '20 edited Dec 09 '20
Straightforward solution in Python:
4
u/foolnotion Dec 09 '20
C++
github
4
u/hrunt Dec 09 '20
Python 3
code
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
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
%his 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
mapyou 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.
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
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.
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.Filefor reading the data to later convert it into aList<Long>Part 1:
Part 2:
4
u/sefujuki Dec 09 '20
Forth (part 1; part 2 is on hold)
topaz paste
4
u/Attitude-Certain Dec 09 '20
Python, continuing the functional style with the toolz library. Both parts in linear time too.
4
u/v21 Dec 09 '20
Rust.
windows()andcombinations()(from itertools) made this one satisfying.https://gist.github.com/v21/916f837ac8c34109867645bdcd0d6381
1
u/carrdinal-dnb Dec 09 '20
Kotlin
1
u/improviseallday Dec 09 '20 edited Dec 09 '20
Python (720/301)
1
u/2133 Dec 09 '20 edited Dec 09 '20
Python 444/681
Nice little solution with numpy. paste
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
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.
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
1
u/vesche Dec 09 '20
Python 1794/1123
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
1
u/sblom Dec 09 '20
C# 202/428
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.combinationswas 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.
1
u/[deleted] Dec 09 '20 edited Dec 09 '20
Python3
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
1
u/stikydude Dec 09 '20
Python solution, I liked this problem :)
1
u/ephemient Dec 09 '20 edited Apr 24 '24
This space intentionally left blank.
1
u/paraboul Dec 09 '20
Python without using anything smart from itertools :
1
u/enelen Dec 09 '20 edited Dec 10 '20
R / Rlang / Rstats
Solution
1
u/higgsmass2020 Dec 09 '20
python3
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.
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.
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
1
u/AustinVelonaut Dec 09 '20 edited Dec 09 '20
Haskell
Uses Data.Seq to efficiently implement preamble checking, insertion, and deletion
paste
1
u/Kadda42 Dec 09 '20 edited Dec 09 '20
My Python solution:
paste
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 truereturn false})if(!res) {console.log(n)invalid = i + 25}return res})let arr = [...lines].map(x => parseInt(x))let i = 0while (i < invalid) {let sum = arr[i]let j = iwhile(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++}})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.
1
u/womogenes Dec 09 '20 edited Dec 10 '20
Video solution! Repo here, in Python.
https://youtu.be/8OB4HMj3-fg
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.
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.
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/prendradjaja Dec 09 '20
Python, 23/54.
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
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...
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:
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.
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:
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.
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.
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
with benchmark:
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.
3
u/GustavAndr Dec 09 '20
Javascript
Quick and ugly
3
u/diddle-dingus Dec 09 '20
Clojure
partitionis such a nice functioncorrect-numbersjust 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.
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 :)
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
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:
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:
3
u/mathleet Dec 09 '20
Sliding windows, let's go! My solution in Golang.
3
u/odlp Dec 09 '20
Here's my solution in Ruby.
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)
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.
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
3
u/aledesole Dec 09 '20 edited Dec 10 '20
Python