Advent of Code 2021
adventofcode.com
adventofcode.com
I don't like missing out on the stars.... I mean it's the only way you get to see the awesome ascii art when you collect all 50 for the year.
Many thanks to Eric and team for what must be a huge effort to run such a fun programme.
Oh, the other thing I do: I don't even start until sometime in January :) far less stress and keeps the whole family much happier ;)
I'm checking out Elixir this year, because I write 95 % Ruby at work and I'm getting really intrigued by the functional stuff seeping into it.
The leaderboard is occasionally interesting to me for the first week of December, but, realistically, I can't see getting invested in it without also moving far, far to the west of where I live now.
Still enjoy whatever I get done
But I love the format and what I’d enjoy is a similar project where the difficulty doesn’t really increase, but each day is a different problem domain. Breadth not depth.
For example, perhaps we start with some data processing from a file. Then answer some basic statistics question about the data. Then maybe some basic signal processing. We form an image. We transform the image. We play the image as audio. We break it into packets of some sort then share it on a “network.” We reassemble it. We build a state machine and pass it the reassembled data in some way. We discover some new output.
Etc. etc. culminating with some fun discovery that inside that original data was a secret code or whatever.
And instead of an intense challenge, we’ve just had a fun walk through an intro to two dozen subdomains of CS/sweng. You may not have immediately known the answer to each puzzle but you never felt lost.
The game is relatively easy. You never feel lost. But there’s some thinking involved. And before you even realize it, you’ve implemented a linked list in Assembly.
BTW, there is a great book that is right up this alley -- maybe you know it -- "The New Turing Omnibus: 66 Excursions in Computer Science"[0]
I discovered "Omnibus" from Peter / Catonmat [1]
It's 66 short, manageable topics, each ~5-8 pages:
1 Algorithms
2 Finite Automata
3 Systems of Logic
4 Simulation
5 Godel's Theorem
6 Game Trees
7 The Chomsky Hierarchy
8 Random Numbers
9 Mathematical Research
10 Program Correctness
11 Search Trees
12 Error-Corecting Codes
13 Boolean Logic
14 Regular Languages
15 Time and Space Complexity
16 Genetic Algorithms
17 The Random Access Machine
18 Spline Curves
19 Computer Vision
20 Karnaugh Maps
21 The Newton-Raphson Method
22 Minimum Spanning Trees
23 Generative Grammars
24 Recursion
25 Fast Multiplication
26 Nondeterminism
27 Perceptrons
28 Encoders and Multiplexers
29 CAT Scanning
30 The Partition Problem
31 Turing Machines
32 The Fast Fourier Transform
33 Analog Computing
34 Satisfiability
35 Sequential Sorting
36 Neural Networks That Learn
37 Public Key Cryptography
38 Sequential Cirucits
39 Noncomputerable Functions
40 Heaps and Merges
41 NP-Completeness
42 Number Systems for Computing
43 Storage by Hashing
44 Cellular Automata
45 Cook's Theorem
46 Self-Replicating Computers
47 Storing Images
48 The SCRAM
49 Shannon's Theory
50 Detecting Primes
51 Universal Turing Machines
52 Text Compression
53 Disk Operating Systems
54 NP-Complete Problems
55 Iteration and Recursion
56 VLSI Computers
57 Linear Programming
58 Predicate Calculus
59 The Halting Problem
60 Computer Viruses
61 Searching Strings
62 Parallel Computing
63 The Word Problem
64 Logic Programming
65 Relational Data Bases
66 Church's Thesis
[0] https://www.amazon.com/New-Turing-Omnibus-Sixty-Six-Excursio...
I have been porting my old solutions in other languages into Kotlin over the time, and will be again doing them in Kotlin. I find it a nice language for AOC since custom extensions and DSL possibilities, it has a good builtin libraries and you can always fallback on Java, even if it has some shortcomings.
Regarding the AOC per se, I take it as a fun daily challenge, I know I won't be able to be part of the top 100, at least I would with some luck during the first 3 days, and then.. nope, that's life, try not to be too competitive. Last year it took me 8 hours to solve day 20, but it's a game, you should have fun doing it (I had), if not people should stop.
However, I strive in trying to write pretty, compact, idiomatic and as functional as possible code, which means that sometimes I will write an ugly solution in 5 minutes, and will take an hour to make it beautiful.
Besides I like to read the story, I know plenty of friends who don't even read the adventures of Santa, they just solve the puzzle and that's it, they don't even know they saved Christmas :-D !
I think I spent 2 hours last night just playing around with different methods of solving it after my initial version. Other libraries, slightly altered algorithms. I think that's one of the parts I enjoy the most, solving the puzzles is fun. Trying a dozen different variations is, for me, more fun (and more edifying).
I'd like to say it only happened once, but, it happened again later that year... And then never again (because I pulled out code to always strip newlines after reading it in ;)
It just redirects to the advent site but I've grown to love it :)
Then somewhere between day 10 and 15, there will be a steep increase in difficulty and I'll tap out for the year. Then come back to the puzzles over the course of the year and maybe knock out another one or two.
library(tidyverse) # pre-typed
lines = readLines("data/day1.txt") %>% as.numeric() # Read data
diff(lines) %>% .[. > 0] %>% length() # Part 1
https://adventofcode.com/2020/day/20
Did they hope the corner tiles had unique edges and look for those? (which would be unlikely under normal circumstances, considering there are more than a hundred tiles and only 256 different possible edges...)
> Tiles at the edge of the image also have this border, but the outermost edges won't line up with any other tiles.
So they didn't need to hope; the problem guaranteed it for them.
I remember being flabbergasted at first, and then realizing the above. My solution is here:
https://github.com/linus/aoc/blob/main/2020/js/day-20/app.js
Also, that's really nicely written code :)
It's not just measuring your problem solving abilities but also your famiarity with the author's writing style.
Apple's Dictionary (Oxford?)
> 2 the edge or boundary of something, or the part near it: the northern border of their distribution area | figurative : the unknown regions at the borders of physics and electronics.
https://www.merriam-webster.com/dictionary/border
> 1 : an outer part or edge
https://www.dictionary.com/browse/border
> the part or edge of a surface or area that forms its outer boundary.
I personally don't mind, if I spend 10 days learning a new language and solving some problems I'm satisfied. I'm still very excited when AoC comes up every year!
Theres a small community [0] of people who decided to try out Coalton [1], which is a Common Lisp DSL that has a strict, Haskell-like type system, and has strict evaluation (not lazy) semantics. Pattern matching, algebraic data types, all that jazz are supported directly in a Common Lisp environment.
For example, here is a function to read in the first problem's data, which makes use of the usual high order functions (map and filter), as well as currying (only one argument provided to /=, making it curried):
(declare read-aoc-data (Unit -> (List Integer)))
(define (read-aoc-data _)
"Read the data for problem 1."
(let ((data (fromSome "Couldn't read AOC1 data."
(read-file-into-string aoc1-input-file))))
(map parse-int-or-fail
(filter (/= "") (split-string #\Newline data)))))
There's a small contest [2] with all sorts of prizes for doing AoC in Coalton and contributing back to the project through tutorials, PRs, and bug reports.
[0] They hang out on Discord https://discord.gg/cPb6Bc4xAH
There's usually a lot of different solutions (including many in esoteric languages or code golfed) along with screencasts and visualizations to explain how they got there. I find that even when the puzzles are easy I still learn a lot from the community by seeing all the different ways to skin a cat!
On the flip side, it's a bit humbling to see people solving the difficult days extremely quickly or having very concise and elegant solutions.
"if you memorized some mathematical concepts and an obscure algorithm and also recognize that this exact algorithm is the only efficient solution to the problem then you can solve this in 5 seconds, otherwise it will never finish running with any other algorithm".
I immediately quit. I'm not doing these to prove I'm smarter than other people or memorized random math concepts, I'm doing this to practice writing code or to learn a new language.
Not sure if this is indicative of other years (This is the farthest I've persisted in the 3 I've tried) but it was EXTREMELY demotivating, and killed every desire to continue or to even try it again next year.
*EDIT*: Apologies, I was incorrect on the Day where this happened. It was actually Day 13, with the Chinese Remainder Theorem being the solution. I must have copy/pasted a solution in frustration and continued past that point. My mistake.
I didn't read it in depth, but it feels like you could build regexes on the fly to solve it. Perhaps I missed something crucial.
Edit: Ahh, day 13: https://adventofcode.com/2020/day/13
I wish Advent of Code puzzles were strictly algorithm focused without relying on specifics of mathematics. Skipping puzzles is demotivating for the completionist in me that lacks time to re-read math books.
Perhaps a compromise would be to start with an easy input that any pile of if statements can handle, then give a longer input that will break all but the best algorithms as a bonus.
Granted, I don't know the process of AoC in terms of vetting and building their puzzles, but it seems that the person/people involved all share very similar levels and domain of knowledge. Having more people reviewing or involved in the process that have a wider range of skillsets might avoid these situations.
Example from what I was talking about before: Day 13 of AoC2020 was basically "the answer is the Chinese Remainder Theorem". If you remembered that...great you could solve this in 10 seconds (hell some languages have a _function_ for that theorem!). If not....well good luck finding a solution that runs in under 6h. That has nothing to do with _programming_. Its just math, there wasn't even programming involved (literally some solutions were just "parse the input and pass it to mathlib.chinese_remainder()"). That's not satisfying to solve for the majority of people, I feel (opinion, I know).
result = 0
addend = 1
for divisor, desired_offset in [(7, 0), (13, 1), (59, 4), (31, 6), (19, 7)]:
# keep trying numbers until we find the one that, with
# the desired offset added to it, would divide without
# remainder
while (result + desired_offset) % divisor != 0:
result += addend
# adding another addend should not break previous results
# so make it divisible by all previous divisors
addend *= divisor
result %= 7*13*59*31*19 # Is it really needed? Eh.
print(result)Project Euler used to say something along the lines of "not everyone can solve every problem, and that's OK". Looks like they've removed that statement though. I remember encountering it early in my career and realizing some problems I cannot solve, even though others can.
IMO AoC should strife to be completable by 80% of programmers (number is out of thin air, but you got the idea).
Project Euler is a different beast.
Of course that's just my opinion.
For the other 20% where I don't even know where to start, I look up a solution on reddit, try to understand it and re-implement it myself, and learn something new. The 2020 day 13 problem mentioned by GP was indeed one of those for me last year.
[1]: https://www.reddit.com/r/adventofcode/comments/kcl7d2/2020_d...
I think AoC goes for slowly growing difficulty which helps keep more skilled people engaged.
What would be the point then, it will be just another leetcode
Its meant to be hard and meant to force you to learn.
See 2019's IntCode puzzles for instance for something very far from Project Euler. They also had the side-effect of benefiting anyone who spent time refactoring their initial versions to create a better interface, a later day (23?) has you run 50 IntCode computers concurrently and communicating with each other. This became very hard to actually implement for many people because of the structure of their simulator and how they'd handled concurrent simulations earlier.
For my personal goals, I want to get better at programming and not at math. When I find myself spending more time on the math rather than programming, I just skip the problem. I suspect many people abandon Project Euler for the same reasons I encountered.
With all that said, I agree that not everyone can solve every problem and that is ok.
When I was in college we used this (or an earlier version, that's a different URL than what I recall) in preparation for ACM programming competitions.
well that's just not true at all.
I had no idea WTF the Chinese Remainder Theorem was and just worked out the issue iteratively. All you had to know was that if you are trying to find some large number that is divisible by other prime numbers, the deltas between the candidates will be the product of the numbers.
as in, if you are trying to find a number that is divisible by both 37 and 41, you really just need to find numbers divisible by 1517.
I forget what the name for this mathematical concept is, but it's far less obscure than the CRT.
https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Comp... describes a few algorithms for doing that.
For comparison, let’s say the “sorting theorem” says “if you have n different numbers, you can place them in a sequence so that no number is larger than its predecessor”.
Now, you have two numbers. How do you apply that theorem to place them in a sequence so that no number is larger than its predecessor?
I've only done 2019 and 2020, but found 2020 to be a lot easier. I got stuck for a day or two on one of the 2019 ones. The one point I was briefly stuck in 2020 was when I was using the wrong data structure. (I don't want to spoil anything.)
"All you have to know is .. {this magic}" -- that really reminds me of my freshman year math classes where the TAs would just say, "well if you do it THIS WAY..." (when my main question was how the heck you stumble upon looking at the problem that way, vs all the failed ways)
Well you stumble through half a dozen failed ways first, is the usual method. Eventually you gain "intuition" that lets you jump straight to the way that works and you can't explain exactly how you thought up the correct method, but it just feels so natural and anyway, you can explain in great detail why nothing else would work.
I'm teaching calculus this year so I sympathise with both sides. The problem is that the answer to "how did you know to do it that way?" is experience, as in all fields. But students rarely have the time to accumulate experience and intuition before finals, so there's frustration all around.
What I'm saying is I'm not looking forward to grading six hundred finals where many students will inevitably spend too much time on approaches that were obviously (to me) doomed from the start because they haven't stumbled enough to know it yet.
Two buses make different circular routes from the same depot. One bus takes 3 hours to do a loop, the other takes 5. At what times from the start of the day will both buses be at the depot at the same time?
you could write a loop like this:
for t in range(0, 10000):
if t % 3 == 0 and t % 5 == 0:
print("same at", t)
same at 0
same at 15
same at 30
same at 45
same at 60
same at 75
same at 90
for t in range(0, 10000, 15):
print("same at", t)
But then again people have a much harder time applying concept they know to given situations than if they're told directly to do something.
I also wouldn't consider knowing properties of the GCD to be a "random math concept". It shows up in a reasonably large number of contexts. For example, in public key cryptography. A specific case is that at one point someone realized they could just collect hundreds of millions of RSA public keys and crack low entropy ones by checking for common divisors. Doing this naively by checking each pair would have been very costly, but they used properties of the GCD to massively reduce the cost by pooling keys [1].
[1]: Page 7 of https://www.quintessencelabs.com/wp-content/uploads/2020/03/...
It is.
Part 1 runs in ~0.5 msecs Part 2 runs in ~2 msecs
for each ID in list:
next_departure = round_up_to_next_integer(earliest_time / ID) * ID
delay[ID] = next_departure - earliest_time
nearest_bus = ID with lowest delay
return nearest_bus * delay[nearest_bus]
How do you even use CRT to solve this?
result = 0
addend = 1
for divisor, desired_offset in [(7, 0), (13, 1), (59, 4), (31, 6), (19, 7)]:
# keep trying numbers until we find the one that, with
# the desired offset added to it, would divide without
# remainder
while (result + desired_offset) % divisor != 0:
result += addend
# adding another addend should not break previous results
# so make it divisible by all previous divisors
addend *= divisor
print(result % (7*13*59*31*19))
And instead of talking down to people, it can be more productive if you walk through a solution instead of stating "This algorithm self-evidently works" like a jerk.
Also, the last modulo isn't needed.
After every iteration, "result" gives correct remainders for all divisors considered so far, so if the loop ends, the "result" will give correct remainders for all divisors. The only problem is whether it will end or not, and that I just tried experimentally: it stopped, so ok. Not really sure how to explain it further.
> Also, the last modulo isn't needed.
Good to know, I was not sure if I wouldn't step past it due to constantly increasing addend. I knew about this modular reduction from that one time when I needed to align/move/scroll things on a 80x25 grid.
It can be demotivating if you check the number of people who solved it quicker you, but just pretend they all cheated off one really really smart person and you'll feel much better :D
[1]: https://adventofcode.com/2020 shows the number order
I actually like when it teaches me something new. If you get stuck you could always google for the concepts you need and learn of them, or go to the subreddit and get hints but still solve the programming part yourself.
This year, my rule is that if it looks like the Chinese remainder theorem, then I can just look it up. There's no need to stay stuck on something that's supposed to be fun.
I also do a daily writeup of my solution, which helps make sure I understand the problem and help others who are learning. I found it super rewarding last year, so I'm doing it again this year. They're in my GH repo. Here's today's: https://github.com/xavdid/advent-of-code/tree/main/solutions...
My big tip is that you probably don't need to worry about competing for the leaderboard (unless you really want to). Go at your own pace, don't stay up weird hours, and take a break.
( Insert elements at the end and swap with the parent until the tree is correctly ordered again. Good luck figuring this out in 20 minutes if you don't know it ahead of time. )
( Now prepare yourself to remember how to insert/delete/search for elements in every other data structure with any number of different qualifiers when it's not going to be obvious at the outset of the question what kind of data structure to use )
( Oh and make sure you've memorized the time and space complexity )
( Not that I'm bitter or anything )
I’ve done dozens of leetcode contests (4 problems every Saturday) and never had to use knowledge of the implementation of a min-heap (though I did “import heapq” a few times) to solve any of the problems.
Are you using “leet coding” to refer to technical interviews that simply ask you to implement textbook data structures (somewhat boring imo), as opposed to solving leetcode problems?
Probably no one ever asks about them but it's a crapshoot.
Obviously for the folks who use <ObscureLanguageX> this wouldn't work but it would be a nice collaboration otherwise.
Here's an example – in part 2 of day 1 of this year (2021), there's no need to actually add up the 3 measurement range, since the middle 2 values will always cancel out. You simply need to loop through the array compare index i with i+3. Maybe there should be an extra point for people who figured this out?
Another problem is that the input set is always small enough to make a brute force solution the most favorable one. So what they are really judging is the speed at which someone can read/parse the input file and write some loops.
Maybe one way it could do the performance testing is: 24 hours after the puzzle is announced, a "speed test input" becomes available. The speed test input would be substantially larger than normal inputs. Because people have had time to write the code, all they have to do is dump the input into the code and put the output into the box the fastest. A notable bottleneck is that every problem does have to be solved by the server ahead of time, and if it starts taking ten minutes to solve each instance then that's expensive unless you use very small pools of inputs.
That's only true for, well, ok maybe 1/2-2/3rds of the days. The rest require something more complicated, either with more complicated algorithms or more clever algorithms to get performance to a reasonable level. See the other discussion here about 2020 Day 13. The naive solution worked on the samples, but would not have worked on the actual input.
In the last couple years I usually stopped up after a few days when I didn't find the time to do one of the puzzles or got stuck with the Rust borow checker. Maybe having a leaderboard helps with the motivation to keep on going! :)
Personally, joining leaderboards like this certainly help with motivation, though I couldn't say why.
F#, Lisp and so on
Maybe obscure is a better word here?
As discussed elsewhere, it's possible niche might be a better term to describe what I'm talking about here than obscure.
I was proud last year when I got to day 18 with Python, but I'm setting the bar much lower this year. I don't have any experience with C/C++ (just C# and a bit of Go), so thinking more carefully about memory mgmt is new to me. But the functional aspects of Rust are pretty exciting.
Some stats to confirm - https://preview.redd.it/jrhlcxrzy0761.png?width=2275&format=... - taken from from last years' unofficial survey - https://www.reddit.com/r/adventofcode/comments/kj53l1/unoffi...
(Since their solution is now being discussed, it's from here: https://www.reddit.com/r/adventofcode/comments/r66vow/2021_d...)
1⊖x
x < 1⊖x
¯1 ↓ x<1⊖x
+/ ¯1↓x<1⊖x
That's an online APL REPL with all the symbols listed at the top, hover to get a tooltip that tells you both how to type it into the REPL and what its name is. I'd forgotten what rotate was because my APL deep-dive was 2 or 3 years ago now. It's handy for discovering the symbols and breaking down the harder-to-understand one-liners (for novices or those unfamiliar with it).
I don't think their second solution actually works unless I'm missing something though : +/¯3↓x<3⊖x
This compares every element to the the one 3 positions before it, when the question was to take the sum of each 3 elements and check if it's smaller than the previous sum.
Anyone here currently on any kind of sabbatical to just decompress and learn new stuff?
Its great for those of us on the more OPS side of DEVOPS:
If you care to follow along:
is pretty simple but yeah.. i guess as the scope increases it may require a dist folder or scripts
edit: wow nevermind im seeing a sibling comment here is using the browser and it looks like a major headache..
Disclosure, just in case: I'm one of the ops in the channel.
But, that gets the competitive aspect of this challenge out of the way immediately so I can simply have fun with these problems :)
I am excited for them to become a bit more challenging because my friend and I are going to work on them together.
Compared to Python and Scala it is way more verbose for simple challenges as this.
I almost feel like I am back in the early 1990s of writing C.
I miss zip, sum, map and list comprehensions...
In fact at the link below you'll see one of the creators explicitly say they're easy to implement (and his own implementation pre-generics) but he doesn't think you should use them (Rob Pike). "Having written it a couple of years ago, I haven't had occasion to use it once. Instead, I just use "for" loops.
You shouldn't use it either."
I imagine with generics it could be greatly simplified, but I don't know Go well enough to venture how it would be done. Though if it weren't faster than that version I'd be shocked.
For clarity, I was looking at reduce.go, all the others seem to do similar tricks with reflection that would also add overhead that generics should eliminate.
Not really into the competitive aspect, although I guess it doesn't matter that much anyway.
There was on AoC a few years ago that got you to build a toy computer, to the point where you were running simple games on it. That was mind blowingly fun!
https://www.reddit.com/r/adventofcode/
https://www.reddit.com/r/adventofcode/comments/r66vow/2021_d...
It's interesting to see the various solutions, especially when you realize, "Oh, duh, I did more work than necessary." and can go back and improve your own with the new knowledge.
I would say the only thing that's "cheating" would be looking up solutions to "solve" the problem faster than other people, whether they be the rest of the world on the global leaderboard (which is unlikely since the people who make the leaderboard are good about not posting solutions until it's full) or some friends you're competing with on a private leaderboard.
Otherwise, let your conscience be your guide. As the saying goes, when you cheat, you're only cheating yourself.
Even then, if you go and look up solutions it's still up to you whether or not you call that cheating.
In short, it's a creative set of challenges released once/day for 25 days during December. It's also a creative community of people solving the problems (sometimes programming, sometimes with other tools, even just pencil & paper) and more than that creating visualizations and new programming languages, learning new programming languages...
It's just a fun ride. To me it's the digital equivalent of RAGBRAI, which is a rolling party across Iowa each year that happens to be on bicycle. Advent of Code is as much about the community as the problems.
(Minor wording edit.)
Would this have been named 'Kwanzaa of code' or 'Diwali of code' or 'lesser eid of code'? Of course not
Advent is a season of the liturgical year observed in most Christian denominations as a time of expectant waiting and preparation for both the celebration of the Nativity of Christ at Christmas and the return of Christ at the Second Coming. Advent is the beginning of the liturgical year in Western Christianity, and is part of the wider Christmas and holiday season.
Why does that make this offensive?
Also, starting a flamewar and then pouring fuel on the flames, as you did with https://news.ycombinator.com/item?id=29407387, is definitely not ok.