Advent of Code 2020: 25x2 coding puzzles for December

It’s almost that time again.

If you’re not familiar, here’s a quick synopsis, courtesy of @gadgetgirl:

More information can be found on their website.

This isn’t the first time we’ve done this, here are links to the previous years’ discussions:

I’ve set up a private leaderboard. You can be a member in more than one, so don’t worry about that, but be aware that your name will appear as it does on the Advent of Code website. In other words, it could show your real name. I login via GitHub for this group, and via Google for work. If you want to join this leaderboard, the code is 256706-bb2717ff.

I’ll tag the others that were active last year:

I set up a gitlab repo in 2018, and I neglected to upload any code to it last year, but I will try to do a better job of it this year.

I did 2018’s puzzles in Python (and C#?) and I did 2019’s puzzles in C#. I’m not sure what I’ll do for 2020, but I’d like to try to work the solutions in both C# and Python if I can, since these days I spend most of my time writing build and release pipelines in YAML.

Feel free to post questions and solutions in this thread, but please be kind and blur out any spoilers.

2 Likes

Oh, for goodness sakes… I haven’t even had a chance to go back and make another attempt on the one I got stuck on. Where the heck has the year gone…?

no, that’s rhetorical, I’m sure we all have a good idea where it went

3 Likes

Here we go again… let’s see how long before I give up or lose interest. :confounded:

2 Likes

Day 1 complete.

I spent more time fighting with the new IDE (VS Code) and its idiosyncrasies than I did solving the problem. Once I got everything behaving the way I wanted it to, it was just a matter of using Python’s itertools and math modules, making the code extremely straightforward. It took just a little refactoring of the code for part 2, so overall not too bad for the first day. I’m sure it will get much more difficult before the end.

Of course due to an outage, there are no points for the day. :sob:

The code is checked into the repo linked above if you’re interested, although I don’t have CI working yet.

Here’s the core of the solution:

def find_expenses(self, expenses, length, target):
        for c in itertools.combinations(expenses, length):
            if sum(c) == target:
                return c
        return None

Here’s what calling that looks like:

er = ExpenseReport()
c = er.find_expenses(expenses, 2, 2020)
print(math.prod(c))
#part 2
c = er.find_expenses(expenses, 3, 2020)
print(math.prod(c))
1 Like

If I had the time and focus, I’d probably try learning more python for it… you seem to get a heck of a lot of mileage out of itertools on these. But, I did it the quick and dirty way with nested for loops instead.

…and then I found a perl analog for itertools and worked out a translation of your method…

use List::Util qw (sum product);
use Algorithm::Combinatorics qw(combinations);

my @input = <>;
chomp @input;

my @result = find_expenses(\@input, 2, 2020);
print join(" + ", @result) . " = 2020\n";
print join(" * ", @result) . " = " . product(@result) . "\n";

#########
# Utility Functions

sub find_expenses (\@$$) { my($list, $length, $total) = @_;
   foreach my $c (combinations($list, $length)) {
      if(sum(@$c) == $total) {
         return(@$c);
      }
   }
}
1 Like

(I don’t think this is too spoilery…)
A note about day 2: in part 2, where it says something is “irrelevant”, be careful that it doesn’t throw you off of what actually is relevant.

This one’s fairly straightforward but that portion’s written weirdly IMO. Not strictly wrong, just easy to misinterpret.

1 Like

Day 3 was fairly easy, though I ran into an off-by-one error that I had to waste a lot of time building debugging to catch. My algorithm ended up being a basic array wrap for the x position, finding x modulo line_length.

Day 4 is text processing - easy (depending on language, anyways), but a bit of a slog. I don’t think I’d ever want to show my incredibly ugly final code to anyone who might be a potential employer, I’m sure I could have simplified it, and I ended up troubleshooting far too many bugs due to silly mistakes…

2 Likes

Finally got some time to work on these. I’m exhausted so this year I’m not fucking around with new stuff — I’m just going with what’s know and coding with C# and the .Net framework. (Well, I guess in a tiny little twist I’m using .Net Core on my Mac, but that’s not really consequential.)

I didn’t yet finish day 4 part 2 because my laptop battery died before I could wrap up the stricter validation but I know what I need to do to solve it.

Everything’s feeling pretty easy thus far which probably means in a few days the difficulty is going to crank up in a major way.

Anyway here’s my GitHub if anybody cares to see my hacky solutions:

I’m not really proud of how I brute forced Day 1 but after spending some time writing a fancy recursive method to handle any combination of cases I decided it wasn’t worth my time and I moved on.

3 Likes

(I don’t think this is spoilery)

When I was working on Day 4 part 1 I made an initial assumption that the data would be well formed and then realized it wasn’t in many cases. I pretty much knew at that point that part 2 would be something along the lines of “now actually validate the data is correct”.

2 Likes

Day 5 - I’ve always been rather fond of bsp trees (not spoilery since it spells that one out in the problem text).

Day 6 - I went straightforward on this one, and just tracked totals in a hash and tested them afterwards.

Day 7 - containers within containers, and a bit of a jump in difficulty. Once I got past the (somewhat odd) text processing portion of this, it was “hello recursion, my old friend” - I’ve always liked working the logic of this kind of problem. My solution for part 2 consistently returns a result one greater than the correct answer across all of the available datasets, but I’m too tired to worry about that minor detail. :slight_smile:

1 Like

Day 8 looks like the first big jump in difficulty I’ve seen. It’s the typical simple interpreter problem (which seems to be a common one they revisit each year), but part 2 requires some code analysis.

There’s no telling whether this interpreter will end up coming back to haunt later puzzles… but, just in case, I re-used most of the modular code I wrote for last year’s “intcode” interpreter. I probably could have written a new non-modular one for the problem in the same time or faster… but some name changes, some ripping out of (currently) unnecessary opcodes and minor changes to the parsing code, and it was up and running and have a framework to support any possible future uses.

On part 2… I’m not entirely certain how you’re supposed to quickly find the answer. I started to brute-force it, but screwed up my code and didn’t notice until a few iterations in… and then when I fixed my code, the brute-force iteration I had randomly stopped on just happened to be the answer. :confused: :man_shrugging: :partying_face:

1 Like

Haven’t yet been motivated to continue yet and work has been sucking my desire to code outside of working hours, so hopefully later this week I can get caught up.

I was just thinking to myself over Thanksgiving that it was about time for Advent of Code to start and that I should do that again this year, and then I totally spaced it off until a couple days ago. Now I’m playing catch-up, but given that I’ve never gotten more than about halfway through the whole thing in past years, I doubt I’ll ever actually catch up with the current day’s puzzle. :slight_smile:

I’ve been working on my PowerShell chops lately, so that’s what I’m using for these puzzles. I was actually mildly pleased with myself that I didn’t have to spend much time looking up syntax or functions etc. for the first few days of puzzles, so that was nice.

That’s the thing I kind of like and at the same time don’t like about these sorts of coding puzzles/challenges. I like them because the problems are usually more varied than what I typically work on day-to-day and they’re a nice opportunity to stretch a bit and learn something new. But at the same time, Advent of Code is pretty explicitly about coming up with a solution in the shortest amount of time, and not necessarily writing performant or even readable code (at least the way I do it :grin:).

Day 4 was the first day I wrote something that made me want to give it the side-eye. My “passport validation” function was basically a single if statement with a bunch of nested expressions all crammed into the conditional.

But Day 7 was where it started to go totally off the rails for me. My first impulse was to whip up a little custom class and implement some sort of directed, weighted graph data structure and then just crawl it to find the requested container relationships. But I’m a little fuzzy on the details of value types vs. reference types in PowerShell, and I noticed that if I just ignored the number of bags contained in other bags (which I strongly suspected would bite me in terms of re-using anything for the second puzzle of the the day, and – spoiler alert – it did), I could probably solve it with a hash table of string arrays and a little recursion. It worked, but man, was it ugly by the time I was finished.

1 Like

Finished part 4 without too much drama. I kept screwing up my validation which wasted some time but whatever, it’s done.

Day 5 ended up being really easy but I found the “spec” (i.e the web site) to be so thoroughly confusing that I didn’t really make the immediate connection between the sequence of letters just being a bit mask before looking at some spoilers - and then it was super easy. This is not an uncommon problem I’ve found with these AoC challenges: unclear, abstract, or unnecessarily requirements making the simple solution less obvious. Sometimes just having to parse what the cute story actually wants can be more challenging than the coding.

Day 6 was hard only because of my own stupidity. I kept getting wrong numbers over and over again and I kept thrashing at it rather than pausing, stepping back, and doing the obvious: testing my code against the sample data set. Once I did that, it became immediately obvious that in my processing loop that I simply wasn’t accounting for the very last data set in my calculations. Oops. When in doubt, test your assumptions against a known good. I should know better.

1 Like

Ooh, yeah, I think I ran into the same kind of issue, but I caught it on the test data. I ended up tossing in a very hacky “if this is the last line of the input” test and calling it “good enough”. :smiley:

Haven’t done the last few days yet… I was having a hard time wrapping my head around day 9, mostly due to work issues getting in the way. Wrote up pseudocode for it on the night it unlocked, but just haven’t had time to concentrate enough to translate it into action yet.

2 Likes

I had the exact same issue as both of you on the Day 6 puzzle. I was thinking of the blank line between customs surveys as “separators”, but the code I actually wrote was treating them as “terminators”. So instead of fixing my code, I just added an extra blank line to the end of the input file. Problem solved! :grin:

I did something similar with the Day 7 puzzle where, based on a cursory manual inspection of the input file, I assumed that the number of contained bags would never exceed 9, i.e. one digit, which let me simplify the parsing of the input file. I’d never make that kind of assumption about real-world data, so it felt kind of dirty when I did it, but in this case I knew there would only ever be this one file so it was, as you say “good enough”.

2 Likes

I did strongly consider adding a blank line to the input. Modifying the input just made me feel more dirty than throwing in an ugly extra test, though. If I’d really been trying I would have just re-shuffled the order of statements so it wouldn’t matter, but being a hack was easier. :smiley:

Now that I think about it, I could have just pushed an extra empty cell onto the input array after I slurped everything into it, which wouldn’t technically be changing the input. Still feels kinda dirty though, and wouldn’t have worked if I’d wanted to mod things to process the file directly line-by-line rather than using up memory for a cache. :wink:

2 Likes

That’s a good and fair point. I’ve got a decent chunk of RAM on this box, so I haven’t had any issues yet, but I fully expect that at some point (if I stick with it long enough this year) I’ll hit a puzzle for which the naive and/or brute-force approach simply doesn’t scale and I’ll have to start considering performance in my solutions.

Fingers crossed. :sweat_smile:

2 Likes

I do remember at least a couple of the puzzles near end-game in one of the earlier years were pretty much impossible to brute-force, either due to the amount of memory they’d take up or the sheer amount of time involved.

I’m pretty cavalier with resources on these problems, what with the interpreted languages and abuse of hashes I usually get up to. But there’s still that little voice in the back of my head screaming, “after the time spent learning to hand-optimize ASM just to display something on the screen, what the hell are you doing!!!:smiley:

2 Likes

I’ve written assembly exactly once as a professional (a date-window function to address a Y2K bug on an IBM-370).

My hat is off to you, sir.

2 Likes