More nutritious than 25 days of chocolate

December 1, 2018 6:40 AM

And we're off and running with the 2018 edition of Advent of Code, December's greatest nightly programming puzzle adventure game. Make friends with a new programming language you want to learn (but keep the old) and head on over to day 1 to collect stars and save Christmas! No CS degree or fancy computer necessary.

There's a timezone-biased global leaderboard of fastest solvers, but don't mind that. Have fun with it when you've got some time to spare. New puzzles are released at midnight EST/UTC-5.

posted by waninggibbon (340 comments total)

I've created a private leaderboard for MeFites. MeMail me or comment here and I'll send you the link to join. We can order it by number of puzzles solved rather than who was awake to solve it first.
posted by waninggibbon at 6:43 AM on December 1, 2018 [5 favorites]

I would like to join the MFLB, please.
posted by signal at 6:46 AM on December 1, 2018

"We've detected some temporal anomalies," one of Santa's Elves at the Temporal Anomaly Research and Detection Instrument Station tells you.

InverseTachyonPulse plotFixer = new InverseTachyonPulse();
posted by thelonius at 7:06 AM on December 1, 2018 [1 favorite]

I'd like to join the Mefi leaderboard. It would also be fun to share solutions. In 2015 and 2016 I created public github repositories of my solutions. If anyone's interested we could create a common repository and share different solutions to each problem via pull request.
posted by firechicago at 7:30 AM on December 1, 2018

To play, please identify yourself via one of these services:

[GitHub] [Google] [Twitter] [Reddit]

That's me out. Pity. Might have been fun otherwise.
posted by flabdablet at 7:50 AM on December 1, 2018 [8 favorites]

I'm wearing my T-shirt from last year, and I've completed puzzle number one (I want to try a few languages this year, and I've started with Go).

Please for the MeFi board link! (And this thread should be fascinating for the next month)
posted by Wrinkled Stumpskin at 7:55 AM on December 1, 2018

Ooof. I am finishing up my Data Structures course, and I don't think I can do anything else until I take my final on the 13th. But after that, I could try this! Do you have to do the whole thing, or can you jump in halfway through?
posted by ArbitraryAndCapricious at 8:02 AM on December 1, 2018

You can start wherever and whenever you want to. There are even past years available.
posted by waninggibbon at 8:07 AM on December 1, 2018

I'd be interesting in a Mefi leaderboard! Same username both places.
posted by muddgirl at 8:27 AM on December 1, 2018

flabdablet: Do you have some ideological barrier to making a throw-away account on one of those sites? They're not used for anything & you can be "anonymous user number XXX" on the site if you prefer.
posted by pharm at 8:31 AM on December 1, 2018 [1 favorite]

Anyway, AdventOfCode is great - I'm doing it in Haskell again by the looks of things. As usual, I suspect that for half the problems parsing the damn input will take me more time than actually solving the problem :)
posted by pharm at 8:32 AM on December 1, 2018

Ooh, I'm interested! I signed up through my GitHub account (lebaer) already, but I'd be interested in joining the MeFi leaderboard.
posted by Pandora Kouti at 8:39 AM on December 1, 2018

unsubscribe me from this list.
posted by srboisvert at 8:48 AM on December 1, 2018

I started this last year and my tech lead proceeded to, even after I asked him not to, keep telling me about his solutions to the ones I hadn't gotten to yet. This year, he's been basically promoted, go figure, but I'm hoping to try it again, although I might not actually be able to start it properly until middle of this week.
posted by Sequence at 9:09 AM on December 1, 2018

I'd like to join the leaderboard!
posted by grubby at 9:13 AM on December 1, 2018

Just completed the first puzzle and I'd also like to join the MeFi leaderboard!
posted by Is It Over Yet? at 9:44 AM on December 1, 2018

I too would like to join the leaderboard! This was fun. Well... part 1 anyways.
posted by one4themoment at 9:45 AM on December 1, 2018

As usual, I suspect that for half the problems parsing the damn input will take me more time than actually solving the problem :)

And this is why I end up doing interviews and puzzles in Python:

>> int("+6")
6
>>
posted by pwnguin at 10:23 AM on December 1, 2018 [3 favorites]

Uh, what are you supposed to do? I'm on the first "puzzle". It's just a list of numbers.
posted by runcibleshaw at 10:26 AM on December 1, 2018

There should be an instruction page somewhere on there (if you delete “/input” from the end of the URL it might take you there?) it explains how to process the list of numbers to get the desired output, in the form of a bizarre story about time traveling elves, and gives some smaller test cases.
posted by vogon_poet at 10:32 AM on December 1, 2018

The vignette style makes it a bit hard to parse, but here's the excerpted key bits:

"Below the message, the device shows a sequence of changes in frequency (your puzzle input)...
Starting with a frequency of zero, what is the resulting frequency after all of the changes in frequency have been applied?
To begin, get your puzzle input."
posted by pwnguin at 10:33 AM on December 1, 2018

add me to the leaderboard, please!
posted by the_blizz at 10:34 AM on December 1, 2018

I did last year in Python. Might switch it up this time and give JS and Observable notebooks a shot. Lots of Rust people in the Advent reddit community.
posted by waninggibbon at 10:35 AM on December 1, 2018

Oh, so you have to do it in an outside program? I'm out.
posted by runcibleshaw at 10:42 AM on December 1, 2018

i'd like to join!
posted by perihare at 10:47 AM on December 1, 2018

Oh, so you have to do it in an outside program? I'm out.

If I understand your comment, you do not have to do it with a program--you can just solve it using your Vulcan brain. All you submit is the answer.

I've never tried it before--took a few minutes for each of the first day problems. I believe they get harder, based on hearing people talk about it in the past. The hardest part, so far, is parsing the "bizarro story problem" presentation. But that's actually great practice for writing real programs for real people, who never describe the problem accurately because they usually have no idea what the problem actually is...

But, as we say, "the customer isn't always right, but they're always the customer."
posted by Gilgamesh's Chauffeur at 10:50 AM on December 1, 2018 [3 favorites]

Yes, the way these coding challenges typically work is that you are free to use whatever method you would like to use, as long as it gets you the answer. You could conceivably do day 1 in Excel or even with a pen&paper or a calculator if you are patient. These are a good opportunity to self-teach a language - I learned Python 2.x with Project Euler and Rosalind.
posted by muddgirl at 10:53 AM on December 1, 2018

If I understand your comment, you do not have to do it with a program--you can just solve it using your Vulcan brain. All you submit is the answer.

As is usually the case with me it's a problem of mismatched expectations. I thought this would be a programming puzzle game where there's some interface built in to it that you use to solve the puzzles, like a video game. Having to set up my own programming thingy to do it doesn't seem easy or fun to me in that context.
posted by runcibleshaw at 10:53 AM on December 1, 2018

If you don't already have an environment set up to work in, you can use something like REPL.it--if you scroll down to the bottom you don't need to sign up, just click on the language you want.
posted by Sequence at 11:01 AM on December 1, 2018 [2 favorites]

I did it in Chrome's Javascript console, no extra tooling needed. Here's one way to get the sample input data into an Array so you can start the real fun:

a = document.getElementsByTagName("pre")[0].innerText.trim().split('\n')

(Disclaimer: don't paste things into your browser's Javascript console that you find on the internet. I am a software engineer but I am not your software engineer.)
posted by lantius at 11:03 AM on December 1, 2018

Wow, the second question took me longer than it should have because I didn't read the instructions all the way through.
posted by signal at 11:04 AM on December 1, 2018

Sign me up please!
posted by fritillary at 11:08 AM on December 1, 2018

I messed up an eof() check and ended up cycling through the input file hundreds of thousands of times which was really messing with my head... but it was fun watching it all fly by on the console!!!
posted by one4themoment at 11:13 AM on December 1, 2018 [1 favorite]

I signed up using my Github, but would like to be on the MeFi leaderboard, please!
posted by tickingclock at 11:17 AM on December 1, 2018

I signed up with my github also (rustybrooks) and would like to be on the leaderboard
posted by RustyBrooks at 12:10 PM on December 1, 2018

After one day, this presents a nice level of challenge for me -- a very, very part-time hobby coder, at best. 25 days of random brainteasers soaking up my cognitive bandwidth is probably not the best thing for me over the next few weeks -- work/life/school carrying on apace and all -- but I'll chip away at these anyways. Fun -- thanks for the share!
posted by Theophrastus Johnson at 12:25 PM on December 1, 2018

I'd also like to be on the leaderboard, please!
posted by Law of Demeter at 12:50 PM on December 1, 2018

My favorite part about these kinds of challenges is learning the more efficient way of doing them after I write my clumsy brute-force method. It seems like for this challenge these are discussed in a daily solution megathread on the Advent of Code subreddit.
posted by muddgirl at 1:03 PM on December 1, 2018 [2 favorites]

Sign me (Joey DeVivre) up.
posted by Obscure Reference at 1:13 PM on December 1, 2018

I did day one entirely in bash, and now I'm tempted to do all of the rest of them that way because it's there and it's probably the "language" I use the most these days. Also, my first pass was stupidly non-efficient, so I spent an hour or two of time thinking about how to make it run multiple orders of magnitude faster before uploading it to github.
posted by togdon at 1:29 PM on December 1, 2018 [2 favorites]

I'd like to join the leaderboard.
posted by Pronoiac at 2:02 PM on December 1, 2018

My favorite part about these kinds of challenges is learning the more efficient way of doing them after I write my clumsy brute-force method.

Same! I've been trying to learn some more of the fancy Elixir features I don't often use day to day and these types of puzzles are great for that.
posted by Basil Stag Hare at 2:34 PM on December 1, 2018

That was fun! Went quickly using R but maybe I should switch it up and brush up on my python.

What happens if you enter the wrong answer? Do you get another chance or is it over for that question?
posted by yarrow at 2:57 PM on December 1, 2018

It told me that my answer was too low and I got another chance.
posted by muddgirl at 3:01 PM on December 1, 2018 [1 favorite]

I like the idea of having a common repository for sharing solutions, assuming that I manage to keep up with the puzzles.

Today's puzzles were a good opportunity to try out Pandas (Python data analysis library), which I've been meaning to look into in case I make a career switch to data science. Looking forward to tomorrow's!
posted by tickingclock at 3:10 PM on December 1, 2018

I can't actually lock the leaderboard ranking method to puzzles solved, it seems. Whose Line rules apply: the points don't matter.
posted by waninggibbon at 8:02 PM on December 1, 2018 [1 favorite]

Can I get a leaderboard invite? I logged in with Github (pocams).
posted by pocams at 8:16 PM on December 1, 2018

I did this last year, and it's fun, but I wish the challenges in some way recognized you for finding efficient solutions instead of rewarding you for banging out the first brute-force solution that comes to mind. Today (day 2's) second part is a good example: the puzzle input is so short that you're actively hurting your time if you implement the more complicated O(n) solution rather than the brute-force O(n²) one that runs in less than a second anyway.

Also, I'm a bit uneasy with the way this feels like it's a thinly disguised way to have people stack-rank themselves against programming interview questions.
posted by Pyry at 9:58 PM on December 1, 2018 [1 favorite]

My brute-force method took 2 minutes.
posted by muddgirl at 10:16 PM on December 1, 2018 [1 favorite]

I'd like to join too! Send me the link please.
posted by Literaryhero at 10:51 PM on December 1, 2018

the puzzle input is so short that you're actively hurting your time if you implement the more complicated O(n) solution rather than the brute-force O(n2) one that runs in less than a second anyway.

So my 'bad' solution took two minute to solve it, but after thirty seconds I decided this was gonna be one of 'those' problems killed it and thought about it for thirty minutes while making lunch. I don't think you can actually solve it in linear time, because that means evaluating each item once, doing a constant amount of work. But the more interesting thought is, why would brute force be quadratic? In fact, I'm pretty sure the efficient solution is quadratic, or maybe n log n or some variant. The naive method of simply iterating until you find a cycle surely has a more complicated analysis.

Anyways, I don't get too bent out of shape about this sort of thing, if you want to contemplate runtime complexity, that's what Euler project and grad school are for. So I re-ran the Python script just too see what would happen and it found a solution, so yay.
posted by pwnguin at 12:44 AM on December 2, 2018

My brute-force method took 2 minutes.
You must have a much faster computer (or programming language). I was waiting a full 4 minutes!

Can I join the party too please?
posted by eddieddieddie at 12:48 AM on December 2, 2018

I would also like to be on the MeFi leaderboard, please.
posted by Merus at 2:23 AM on December 2, 2018

My solutions for this year are going here. I see what you're saying, Pyry. My brute force solution for Day 2, Part 2 only took 12 ms to run on my laptop. Rewriting it got it down to 3 ms. I remember last year that some naive approaches were too inefficient, however.
posted by waninggibbon at 7:12 AM on December 2, 2018 [1 favorite]

The early puzzles are usually fairly straightforward to solve through brute computation. Later ones sometimes need a bit of thought.
posted by pharm at 8:03 AM on December 2, 2018

I don't think you can actually solve it in linear time, because that means evaluating each item once, doing a constant amount of work.

After reading this a few times I wonder if you're referring to day 1, not day 2. Day 1 is the one with the "cycles" which you refer to. Day 2 part 2 definitely has a naive O(n^2) solution but some O(n) solutions too.
posted by RustyBrooks at 8:49 AM on December 2, 2018

Day 1 part 2: I like to think that my initial one-liner bash script that appended each total to a text file and used grep to see if it was already there was not so much naive as it was bloody-minded. It didn't finish running before I got impatient and just did it in python.
posted by sfenders at 9:13 AM on December 2, 2018

For those who have done this before, how does this compare to r/dailyprogrammer challenges?
posted by zengargoyle at 9:57 AM on December 2, 2018

Oh no.

I did Day 1 puzzle 1 in Excel, just to be bloody minded. But Day 1 Puzzle 2 is too much for it.
Now I have to remember how to code.
posted by Just this guy, y'know at 10:08 AM on December 2, 2018 [1 favorite]

Can I get in on that leaderboard?

For Day 1 I did the first puzzle as an awk one-liner. Since then I've been using Matlab (well, actually Octave, because starting up Matlab makes me feel like I'm working).
posted by irrelephant at 11:07 AM on December 2, 2018

After reading this a few times I wonder if you're referring to day 1, not day 2.

Ah, yep. I read your parenthetical as part two, and assumed day 2 dropped at midnight pacific.
posted by pwnguin at 12:56 PM on December 2, 2018

Day 2 part 2 definitely has a naive O(n^2) solution but some O(n) solutions too.

Was wondering about O(n) for 2-2. Hey, is there somewhere we can set up a spoilers-ok version of this board, to talk about solutions?
posted by the_blizz at 5:31 PM on December 2, 2018 [1 favorite]

Hey, is there somewhere we can set up a spoilers-ok version of this board, to talk about solutions?

Could this be a series on fanfare?
posted by meaty shoe puppet at 6:03 PM on December 2, 2018

It's a pity these puzzles are too big to solve manually. For me, most of the fun is figuring out how one would do it, not figuring out which characters to copy where if one actually wants to do it. Oh, well, time to see how much Python I remember.
posted by meaty shoe puppet at 6:07 PM on December 2, 2018

I did day one entirely in bash, and now I'm tempted to do all of the rest of them that way because it's there and it's probably the "language" I use the most these days.

Here's my stash of bash solutions. Each of these started out as fragments tried out at the shell prompt before being cleaned up into little self-contained scripts that simply output the required answer when invoked.

Day 1, puzzle 2 is the only nastily slow one so far, mainly because it's making bash itself do a lot of looping and arithmetic and bash is slow at both.
posted by flabdablet at 9:42 PM on December 2, 2018

Man, I've been solving these in Processing, because it turns out it's the only thing I have installed on my home machine. Halfway decent string manipulation functions, and built in dictionary data structures are okay, but I should probably install and brush up on something that's more focused on succinctly writing what's required for this. I'm having a tough time cracking the top 1000 for the first assignment and there are about 10 people per puzzle who've submitted both results before I've finished understanding the requirements for the first one.

Bah. Time to start speed reading or just not bothering to worry about the main leaderboards.
posted by figurant at 10:43 PM on December 2, 2018

I should probably install and brush up on something that's more focused on succinctly writing what's required for this.

Day 3's first solver used python, which is a combination of useful, succinct, and understandable. And it's installed by default on linux and OSX. But the first solver also used regex, which is maybe not understandable. I wouldn't worry too much about leaderboards, they quickly devolve into degenerate 'cute' solutions built half out of reusable snippets from previous solutions.

On the other hand, once you get the hang of it, python is really great for whiteboard interviews for all the same reasons. And on the job because 90 percent of the time you just need to get something done once regardless of scale.
posted by pwnguin at 11:42 PM on December 2, 2018

the_blizz: spoilers-ok version of this board

Are spoilers not OK here? Not pasting the code, but discussing how things can be solved O(n) with the right data structure. Maybe with a slight embargo?
posted by Wrinkled Stumpskin at 4:01 AM on December 3, 2018

Did day 3 in C because 2D arrays are not only slow but needlessly painful in bash.
posted by flabdablet at 4:33 AM on December 3, 2018

What are you all using? I know a couple people doing it in Rust; I'm using Erlang (which I've used, but not for several years -- I mostly work in C now). My first solution was kind of slow, but that's an excuse to re-learn how to use the profilers. :) There may be something later on that needs several seconds of computation, but otherwise I'm going to shoot for completing under 100 msec before moving on.

Also, I did a bunch of Project Euler problems several years ago (in a mix of OCaml and Scheme), and started over in x86-64 assembly this summer -- that seemed like a good way to learn it, with the difficulty ramping up really slowly.
posted by silentbicycle at 6:26 AM on December 3, 2018

I've been using python just to keep my python skills in shape after not using it for a while, but my fastest version of today's one runs about 15 times slower than flabdablet's C version, or 20 times slower if I optimize the C a bit (to match what I did to the python). That seems excessive. It's not just the input parsing regex either, it's all about the lack of arrays in python. Those lists are nice, but not always what one wants. I tried cheating by using strings, but there's not even a way to efficiently replace a character in the middle of a string. Plus I keep forgetting the ':' at the end of the line. It's almost enough to make me go back to perl.
posted by sfenders at 8:09 AM on December 3, 2018

Can I join the leaderboard ? I don't have any points because I start these in the evening so my solutions come waaaay after everybody else has gotten their stars, but I don't mind :-)
posted by Pendragon at 8:55 AM on December 3, 2018

Only one of us has any points on the global leaderboard so far. You're in good company! My (cleaned up and optimized a bit) day 3 solution using numpy arrays is here. Takes 41 ms to run locally.
posted by waninggibbon at 9:30 AM on December 3, 2018

Yeah, I wish that the points were structured based on how quickly you solved the problem after opening it instead of time after midnight Eastern.

It'd be easy to cheat, of course (if you had multiple accounts or a friend who would tell you the puzzle before you logged in), so maybe it's a non starter, but I do these in the evening too and it'd be interesting to actually have some sense of how "competitive" I am.
posted by JDHarper at 9:37 AM on December 3, 2018

the way to go would be the speed between puzzle 1 and puzzle 2 I think.
posted by Just this guy, y'know at 10:32 AM on December 3, 2018

Shortly after commenting I remembered numpy arrays and was worried that I'd been unfair to python, but they don't make it go any faster for me. Turns out python also has a bytearray, which is great if what you want an array of is bytes, and seems like the ideal thing for getting rid of any unduly onerous lookups in this particular problem (day 3 part 1). It too didn't make a lot of difference; it turns out the added complexity for the interpreter of the simplest code I could come up with to address a one-dimensional byte array just about equals whatever gains I could get out of it. In the end my fastest python version compromises by using a list of bytearrays.

So, my python optimization advice: Make your code as short as possible. Even when you compile it first, that seems to make the most difference for problems in the area of this highly realistic workload. An extra line declaring a variable costs more than an extra int(l[2]). Even when you're compiling it's a wash. When I got it down to just 12 lines of python, it was only 11 times slower than the C.

Alternate, less-insane python optimization advice: Don't.
posted by sfenders at 10:52 AM on December 3, 2018 [1 favorite]

It'd be easy to cheat, of course, so maybe it's a non starter

IMO it would be better. Sure you'd have a large cohort of cheaters at the top of the scoreboard, but they'd be easy enough to ignore. It's not like there's any prize money at stake (I hope).
posted by sfenders at 11:00 AM on December 3, 2018

LOL I had two ways to do 3.1 in python (without arrays, because I don't know how to do that) and I picked the wrong one for doing 3.2.

I find the leaderboard to be pretty easy to ignore, because I'm not good at programming so even if puzzles dropped while I am drinking my coffee in the morning (the perfect time for me) I still wouldn't be competitive. It took me twice as long to figure out how to handle the input as it did to actually solve 3.1
posted by muddgirl at 11:03 AM on December 3, 2018

I tackled the day 2 and day 3 puzzles as soon as they dropped. It took me 38 minutes to finish day 2 and 42 minutes for day 3. It felt like I spent more time reading the problem and figuring out a way to approach it programmatically than I spent actually writing the code itself. I was pleased and surprised to find that I got the right results on my first try each time.

Then I looked at my rankings -- 1593 on day 2 and 1402 on day 3! Zero points obviously, cause only the first 100 finishers get any points. So yeah, I'm in the 'don't pay attention to the scoreboard' camp from here on out.

I used plain old ANSI C on my 2007 iMac, cause I'm a dinosaur.
posted by TwoToneRow at 1:57 PM on December 3, 2018

Looks like I'm going to pick up Go. I'm not sure if it'll make my time to completion any better, since I seem to be pathologically incapable of writing a for loop or conditional on the first try that doesn't accidentally include parentheses.
posted by figurant at 2:39 PM on December 3, 2018

I don't really understand the scoring in the private leaderboard: everyone's scores (including mine) seem to randomly fluctuate, and the leaderboard has reshuffled itself several times at the top in the past day despite everyone there having completed all three days.
posted by Pyry at 5:11 PM on December 3, 2018

If you click where it says "Ordering" at the top, it gives this explanation of the default scoring:

Local Score: which awards users on this leaderboard points much like the global leaderboard. If you add or remove users, the points will be recalculated, and the order can change. For N users, the first user to get each star gets N points, the second gets N-1, and the last gets 1. This is the default.

You can also choose other scoring systems but I don't see a way to make them stick.
posted by muddgirl at 5:20 PM on December 3, 2018

How can that change the ordering of people who've already done all the days? If a new user comes in, shouldn't everyone who's already done all six stars just get six extra points, preserving their order?
posted by Pyry at 5:30 PM on December 3, 2018

I've been doing this in Rust, and 90% of my time has been spent working out string parsing. Ugh.

I feel like some of these problems could potentially have deep, elegant solutions, but are small enough that you may as well brute-force them. Day 3, for example: everyone can spare a few megabytes to map the entire space. If the problem were to use floats rather than ints, though...
posted by phooky at 6:07 PM on December 3, 2018

Oh I see, somebody who already has times on the days can join the private leaderboard later and insert themselves in the middle of the rankings.

Day 3, for example: everyone can spare a few megabytes to map the entire space. If the problem were to use floats rather than ints, though...

This is a case where I think the brute-force option (rasterizing all the bounds) is in fact the more interesting/elegant problem. With floats we're talking about basically doing 2d bounding-box collision detection, where the algorithms are fiddly and don't really have great asymptotic complexity anyway (plus validating floating-point area solutions sounds like a pain).
posted by Pyry at 6:51 PM on December 3, 2018

Someone must have solved day 3 with a GIS library..
posted by waninggibbon at 6:55 PM on December 3, 2018

What do JS people do nowadays for things like itertools or collections in Python? Lodash? D3?
posted by waninggibbon at 7:43 PM on December 3, 2018

Like some some guy suggested so far these could be done in excel but wouldn't the fastest be APL? No lispers here?
posted by sammyo at 7:45 PM on December 3, 2018

I feel obligated to suggest, for non-software-engineers sneaking into this (like me) for whom this is not a reflex: the puzzle description always included a worked example input with expected outputs for that input. Save the example input and use it to test your code first until it produces the provided output, then run your code on the puzzle input. It'll simplify the debugging considerably...
posted by Upton O'Good at 11:40 PM on December 3, 2018 [3 favorites]

Day 4 forced me to relearn more SQL than I wanted to. Glad I went that way for part 1 though, because it made part 2 fall out with scarcely any changes.
posted by flabdablet at 6:51 AM on December 4, 2018

I'm doing this all in perl, because that's really the only thing I know (I can't see Atari BASIC being useful for this). I'm... well, not STUCK, but certainly struggling with 3.2.
posted by hanov3r at 8:02 AM on December 4, 2018

I'm doing this all in perl, because that's really the only thing I know (I can't see Atari BASIC being useful for this). I'm... well, not STUCK, but certainly struggling with 3.2.

Sometimes algorithms need a little encouragement. I find they do better when I play this song for them:
https://www.youtube.com/watch?v=NG2zyeVRcbs
posted by Balna Watya at 8:17 AM on December 4, 2018

I never click random YouTube links in December. #whamageddon
posted by hanov3r at 8:20 AM on December 4, 2018

certainly struggling with 3.2

Are you rendering rectangular regions as rasters, or trying to do it some clever way that finds collisions by comparing box co-ordinates? The second option struck me as way too fiddly.

The approach I used in C was essentially

* create a big rectangular array MAX_WIDTH cells wide and MAX_HEIGHT cells high, to represent square inches of the fabric.

* create a linear winners array with MAX_IDS cells. This has one element for each possible elf ID, which will be 0 if the corresponding elf has not managed to claim an unencumbered rectangle of the fabric and 1 if it has.

* Walk the input list of claims; for each claim, write the claimant's ID to every claimed square inch tile of the fabric array. Check the tile about to be written before writing it; if it already contained a valid ID then the current claim clashes with that of a previous claimant, so zero that previous claimant's entry in the winners array. If all of the current claim's square inches were previously empty, set the current claimant's entry in the winners array.

*After processing all claims, walk the winners array and output the ID for any nonzero cell.

Perl doesn't have real 2D arrays, but if you write $foo[$x][$y] = 1 it will pretend it does by doing something clever with references. The main reason I used C instead of Perl is that the arrays in this problem can all be made fixed-size, so all the stuff that other higher-level languages do for you with invisible memory management doesn't really buy much convenience. Also I got nostalgic for sscanf().
posted by flabdablet at 9:03 AM on December 4, 2018

flabdablet, I pretty much took that approach in perl, except I tried to notate claims with collisions and then write out the non-colliding ones instead of starting from a list of non-colliding claims and removing collisions. Let me... try that.
posted by hanov3r at 9:16 AM on December 4, 2018

Took me a while to work out that I actually did need to hold onto the colliding-or-otherwise status for every claim processed until I'd processed all of them; the fact that only one elf manages a successful claim in this puzzle is an accident of the data (nothing stops multiple cooperating elves from arranging non-collisions between each other) so the processing data structures need to allow for multiple winners even if this particular instance doesn't.
posted by flabdablet at 9:30 AM on December 4, 2018

AAAAAAAUGH

Today I have been reminded about the difference between "if (undef $thing)" and "if (!$thing)" and I'm going to go lie down.
posted by hanov3r at 9:38 AM on December 4, 2018

In a similar vein, I still can't quite forgive Ken Thompson for deciding that = should be an assignment operator and == should be the equality test so that if (thing = 3) does exactly the Wrong Thing, on no better basis than that assignments occur more frequently in typical programs than equality tests.
posted by flabdablet at 9:57 AM on December 4, 2018

My day 4 (cleaned up). I should have used a dict of minute counts...
posted by waninggibbon at 10:13 AM on December 4, 2018

Took me a while to work out that I actually did need to hold onto the colliding-or-otherwise status for every claim processed

Given that we did part one the same way, I'm surprised that my part 2 is so different. I just appended a for loop at the end of the code from part 1 that loops through all the claims again and checks each to see if all of its area was hit by exactly one claim.
posted by sfenders at 10:22 AM on December 4, 2018

I did a 2 dimensional array similar to flabdablet, but instead of 0 for unclaimed and 1 for claim, I just incremented each space in the array by 1 for each claim that touched it.

Which made the solution to part B much easier, basically the same as what sfenders did: loop over the list of claims, comparing it to the array I made in part 1, and returning the claim where were every point == 1.
posted by JDHarper at 12:45 PM on December 4, 2018

Argh, I spent way too long string-wrangling before I peeked at waninggibbon's code and finally realized that the problem statement explicitly says that naps only occur from 00:00 to 00:59.
posted by muddgirl at 12:52 PM on December 4, 2018

My day 4 is here. Some mistakes in retrospect: You can just sort each input line alphabetically to get them in chronological order rather than parsing the time stamps into representative integers like I did and sorting based on those. Also, I don't entirely have a handle on maps in Go yet, and mapping a guard ID to an array wasn't working for me so I did something more convoluted. I should probably write something to quickly extract integer values from within longer strings in Go because my current naive approach is pretty clumsy and it seems like something that comes up a lot in these problems so far.
posted by figurant at 1:21 PM on December 4, 2018

figurant, I'm also getting going with Go, and Sscanf is pretty helpful, as is time.Parse (which is really friendly other than the magic date).
posted by Wrinkled Stumpskin at 2:35 PM on December 4, 2018 [1 favorite]

Day 4 was surprisingly easy after my frustration over day 3, although I may have slightly cheated by just getting my perl to output what i needed and piping the output to sort rather than futzing with sorting and extraction in the script itself.
posted by hanov3r at 2:46 PM on December 4, 2018

Add me into the MeFi leaderboard please. User: #472301

I started out today and made it through the first 2 days using Perl6 one liners. Day 2 Part 2 was sorta annoying because they didn't specify that the answer was only accepted in the same order as the IDs themselves...

It's probably about time to clean things up for public display.
posted by zengargoyle at 4:09 PM on December 4, 2018

instead of 0 for unclaimed and 1 for claim, I just incremented each space in the array by 1 for each claim that touched it.

I did part 1 that way, using left-shift instead of increment; each array tile is a char initialized to '\xFF'. Tiles claimed exactly once would then end up containing '\xFE', while those claimed more than once would have their 0x02 bit cleared. I like left-shift for this kind of job because it makes for an automatically saturating counter, eliminating the need to check explicitly that the counter hasn't overflowed in order to avoid wrapping back around to the starting value.

But I missed the trick of using the same data structure and simply making a second pass over the claims list to solve part 2, which is annoying because it means my part 2 solution eats way more memory than part 1 did. Grrr.
posted by flabdablet at 6:14 PM on December 4, 2018

Sscanf is pretty helpful

Thank you. I quickly scanned through the strings package, didn't see anything, and got caught up in tackling the problem another way. That should smooth things out tonight.
posted by figurant at 7:18 PM on December 4, 2018 [1 favorite]

How the heck did someone beat both stars in under 4 minutes? That hardly seems like enough time to read the problem and type up an answer.

I mean, respect. I finished both stars in 37:47 and didn't even crack the top thousand.
posted by JDHarper at 9:54 PM on December 4, 2018

bash and sed made short work of day 5.
posted by flabdablet at 11:07 PM on December 4, 2018 [1 favorite]

I'd have gotten day 5 a LOT faster if I had followed Upton O'Good's advice above and tested the small sample data to begin with instead of after wasting time running the full data set until I became stumped.

Turned out that I was counting end-of-file characters at the end of the data as part of the test input. When I finally tested using the sample data, I got off-by-one results, and saw at once what was throwing me off.

It is pretty amazing that someone did both parts in under 4 minutes - heck, the slowest of the first 100 finishers did both parts in under 11 minutes! I can't imagine getting both parts in under 30 minutes at the fastest, counting reading the problem, coding, and testing. Anyway, I said I wasn't going to worry about speed and just have fun with the code, but still...
posted by TwoToneRow at 11:10 PM on December 4, 2018

How the heck did someone beat both stars in under 4 minutes? That hardly seems like enough time to read the problem and type up an answer.

I didn't get back from boardgame night till late, but if you're Actually Good at regex, in your language of choice, this was pretty easy. Part two was just 'do part one 26 times'. Half of my time was spent researching how python libs work because I am an imposter. There are smarter, faster ways to do it but my crap solution still ran in 37s.

I'd have gotten day 5 a LOT faster if I had followed Upton O'Good's advice above and tested the small sample data to begin with instead of after wasting time running the full data set until I became stumped.

This is put to good use in this day 5 spoiler screencast that came in #6/#4 to debug an error that arose due to boolean operation precedence. Speedrunners will note the youtuber submitted the answer first, then debugged it. The penalty for submitting a wrong answer is a 60 second lockout, which is probably shorter than the time it takes you debug using the test cases provided. Might as well skip them until you know you need them.
posted by pwnguin at 12:52 AM on December 5, 2018

This is another one where actually there's a lot of subtlety to the problem (like there's an interesting linear-time solution), but you can also just brute force it with string operations that are fast enough to still do it in under a second even though in principle most string replacement/regex solutions are O(n²).
posted by Pyry at 1:12 AM on December 5, 2018 [2 favorites]

(For fun, try timing your solution on an input which is 25k capital-'X' followed by 25k lowercase-'x': the end result should be zero remaining letters)
posted by Pyry at 1:39 AM on December 5, 2018 [1 favorite]

there's an interesting linear-time solution

(cogitates)

Why, so there is!

Here are some timings from this anaemic old single-core Celeron laptop.

Bash+sed search-and-replace-based solutions: 1.bash 432ms, 2.bash 11s
Shiny new C solutions with a linear-time algorithm: 1.c 3ms, 2.c 30ms

try timing your solution on an input which is 25k capital-'X' followed by 25k lowercase-'x': the end result should be zero remaining letters

1.bash 46.6s, 2.bash ANGTFT
1.c 3ms, 2.c 11ms

Heh.
posted by flabdablet at 5:43 AM on December 5, 2018

And to think I was pleased with having shaved a hundred milliseconds off my first cut at 1.bash by making sed do multiple replace passes with fixed search strings instead of a single replace with a honking great constructed regex like /aA|Aa|bB|Bb|cC|Cc ... Yy|zZ|Zz/.

:wq
posted by flabdablet at 5:55 AM on December 5, 2018

Just knowing that a linear solution existed was enough for me to figure it out... 20x speed improvement, and shorter code. If no-one had said, I would never have thought about it.

(Why doesn't Go have a stack data structure?)
posted by Wrinkled Stumpskin at 6:55 AM on December 5, 2018

Here are some timings from this anaemic old single-core Celeron laptop.

Things I learned today: 1. WTF, single-thread performance on my FX 4100 is somehow slower than a Celeron? Damn it. 2. sed scripts are waaaay faster than bash string replace. My version took 3 minutes to run.
posted by sfenders at 8:06 AM on December 5, 2018

hanov3rs-MacBook-Pro:~ hanov3r$ time perl polymer.pl flab_input.txt

0
real 0m9.612s
user 0m9.580s
sys 0m0.021s
posted by hanov3r at 8:42 AM on December 5, 2018

> flabdablet:
"1.c 3ms, 2.c 11ms"

Get even more of a speed up by passing the reduced polymer from Part 1 as your Part 2 input.
posted by waninggibbon at 8:44 AM on December 5, 2018 [1 favorite]

Huh. For the original AoC input, my perl... is surprisingly fast.

hanov3rs-MacBook-Pro:~ hanov3r$ time perl poly.pl
[OUTPUT ELIDED]
real 0m0.202s
user 0m0.193s
sys 0m0.005s
hanov3rs-MacBook-Pro:~ hanov3r$
posted by hanov3r at 8:50 AM on December 5, 2018

PS:

If I missed your request to join the leaderboard and you still want in, MeMail me (again).
posted by waninggibbon at 9:03 AM on December 5, 2018

Get even more of a speed up by passing the reduced polymer from Part 1 as your Part 2 input.

Is that sound? (thinky thinky think) Hmm. Can't see why it wouldn't be. (codey codey code) Holy crap. That's impressive.

stephen@jellynail:~/src/aoc/2018/05$ time ./2a
4944

real    0m0.017s
user    0m0.008s
sys     0m0.000s
stephen@jellynail:~/src/aoc/2018/05$ time ./2b
4944

real    0m0.003s
user    0m0.000s
sys     0m0.000s

posted by flabdablet at 10:22 AM on December 5, 2018

On my work machine, comparing my initial Day 5 approach to the roughly-linear version with waningibbon's optimization takes me from 7600 milliseconds to 190 on the AoC input file.
posted by figurant at 10:40 AM on December 5, 2018

(Why doesn't Go have a stack data structure?)
Because any language that implements a growable vector (a dynamic array in go, i guess) doesn't need one. Many languages just implement "pop" and "push" methods directly on the vectors; it looks like in Go you need to use append() and slicing operations to do the same thing.
posted by phooky at 12:48 PM on December 5, 2018 [1 favorite]

(Why doesn't Go have a stack data structure?)

Because any language that implements a growable vector (a dynamic array in go, i guess) doesn't need one.

It really depends on what you expect is included in the semantics of your stack. If you expect time complexity of O(1) for push() and pop(), a growable vector may or may not do that. I assume most implementations eventually call the moral equivalent of realloc() if they keep growing or shrinking, and that might have surprising effects on timing.

I finally figured out this linear-time algorithm people were talking about for day 5. Not only was the fastest version in my simple Python 3 world, but it was the simplest too. Thanks for being "hinty" without being "spoilery."
posted by Gilgamesh's Chauffeur at 1:48 PM on December 5, 2018 [1 favorite]

Finished up 3 (spent too much time confused about thinking top-left vs left-top) and 4 (didn't catch the out of order of the input for a while.... my state machine was way complicated).

I'm banging them out quick and dirty for the most part, but the Perl6 is coming back to me in bits and pieces making things get easier each time. Wonder if I'll ever hit the wall of performance.

Should be caught up by tomorrow hopefully.
posted by zengargoyle at 2:36 PM on December 5, 2018

Just catching up with this. I did day 3b a little differently - for day 3a I made a raster which had the sum of how many times a particular cell showed up in the individual rectangles.


Then, for 3b, I just extracted the cell values from master for each rectangle - the one that had all 1s was the winner.
posted by zug at 3:50 PM on December 5, 2018

Starting to reimplement some of my Python solutions in JavaScript using Observable notebooks.
posted by waninggibbon at 3:57 PM on December 5, 2018

Heh, Perl 6 regex is too slowwwwwww. (in the s/// way) but the .trans function is optimized.

I'm all caught up. Yay!
posted by zengargoyle at 4:03 PM on December 5, 2018

I put code up on GitHub - zengargoyle/AOC2018: Advent of Code 2018.

Totally haven't gone back and cleaned anything up. Prepare to be horrified.
posted by zengargoyle at 5:27 PM on December 5, 2018

I've been playing around with more efficient ways to do day 5 and have gotten execution times on part 1 down to 13ms on my 2007 iMac by storing the list of characters as a linked list, compared to a previous fastest run of 106 ms in a non-linked-list version.

Almost all of the execution time goes into creating the linked list from the file contents. Once the list is built, the actual reduction of the data is then very quick because removing the matching pairs of characters is accomplished just by changing a couple of list node pointers instead of having to move long strings of characters around in memory.

Testing with the extreme data set suggested by pyry above (250K 'X' followed by 250K 'x') runs as fast as with the normal problem data -- 13 ms, compared to 322 ms with my previous best (non-linked-list) program.

The drawback is of course added complexity -- twice as much code, and some fussy handling of edge cases like when the matching pair of characters is at the extreme head or tail of the list, or when the data is down to just a single matching pair, as happens in the extreme data set.

linked list version non-linked-list version
posted by TwoToneRow at 5:41 PM on December 5, 2018

Almost all of the execution time goes into creating the linked list from the file contents. Once the list is built, the actual reduction of the data is then very quick because removing the matching pairs of characters is accomplished just by changing a couple of list node pointers instead of having to move long strings of characters around in memory.

I think you'll really enjoy finding the O(n) algorithm.

Hint: in algorithms, as in code generally, it's quite often the case that the good stuff is what's left after you've deleted nine tenths of what you wrote.
posted by flabdablet at 8:13 PM on December 5, 2018

For anyone avoiding the subreddit in case of spoilers - there was a bug of some kind where correct answers were not accepted in day 6's puzzle. Now fixed.
posted by Wrinkled Stumpskin at 10:47 PM on December 5, 2018

Manhattan Voronois!
posted by waninggibbon at 8:09 AM on December 6, 2018 [1 favorite]

I was losing my mind trying to track down whether I had misread the problem or was computing distances wrong or something before I checked the subreddit in desperation. My solution worked fine after they fixed it.
posted by figurant at 9:04 AM on December 6, 2018

Twice now I entered the answer from the example input instead of the real input....

Let me tell you, a minute is a long time to wait before you can give the correct answer :-)
posted by Pendragon at 9:23 AM on December 6, 2018

Day 6 has a nice twist — whatever strategy you used for part 1, it's not going to help you for part 2.
posted by cyanistes at 3:13 PM on December 6, 2018

I thought day 6 part 2 was super easy, and used largely the same strategy. After solving part 1 in an hour, took me five minutes to answer part 2.
posted by pwnguin at 3:30 PM on December 6, 2018

I'm in analysis paralysis on 6. Can't decide how I want to try to do it fearing the input will crush me, or part2 will be the opposite. Seems this is the first actually complex problem that makes me want to either search for modules to do the heavy lifting, or to be a bit more generic and write the module. Maybe I'll just brute-force it and hope for the best.
posted by zengargoyle at 3:50 PM on December 6, 2018

Regarding cyanistes' and pwnguin's observations on day 6 parts -- my experience was much like pwnguin's. I spent more time on both parts than he did, but I likewise found part 2 to be easy after having done part 1.

Interestingly, my rankings for day 6 were around 1000 places better than for day 5, even though I took about an hour longer to complete day 6 than I did on day 5.
posted by TwoToneRow at 5:01 PM on December 6, 2018

Apparently nobody gets global points for day 6 because of the issue, which is unfortunate because I had a good rank.
posted by Pyry at 5:19 PM on December 6, 2018

Anyone do anything beyond the naive solution to 6? Here's my un-innovative JS.
posted by waninggibbon at 5:27 PM on December 6, 2018

Ugh. I wanted to beat my head on a table for day 4. Turns out I was solving part 2 without realizing it. I ended up downloading zengargoyle's code to confirm mine against which is how I finally figured out what was wrong.
posted by zug at 5:59 PM on December 6, 2018

I think my solution for day 6 is O(N**2) where N is the largest distance between any two specified points in one dimension. So, I don't know if that's innovative or not. I didn't see any faster solution, though the constant on mine is not so swell.
posted by Gilgamesh's Chauffeur at 6:51 PM on December 6, 2018

6a was the first puzzle I had serious trouble with. I eventually cheated and looked at someone else's answer on reddit and that turned out to be super educational. I had done a lot of the same things as MasterMedo on reddit (spoilers, this goes to the solutions megathread), but I couldn't figure out how to decide which points to throw out because they were "infinite." (That wording really threw me for a loop.)

But! The things I had done the same way, I had done much more clumsily. I've been using Python for years now, but I still find list comprehensions to be super unintuitive, and I learned about a bunch of handy functions that I had either never learned about or forgotten about.

So this has been good for learning, if not for showing off!
posted by JDHarper at 6:57 PM on December 6, 2018

I feel like there might be a way to first quickly discard the input points with infinite regions (this part is relatively straightforward although I didn't figure it out in my solution), and then iteratively grow out the regions of the remaining points until they fill in their boundaries. That's a bit more complicated approach than getting the puzzle solution required, but for large N or a much larger range of coordinate points it would greatly reduce the number of grid coordinates to evaluate.
posted by figurant at 7:20 PM on December 6, 2018

I've been making animations of the days.
posted by Pyry at 7:40 PM on December 6, 2018 [6 favorites]

I did some preliminary research on voronoi last night after brute forcing it, there might be an n log n solution to this problem, or possibly an n log log n. But like, these are straight up Real Algorithms whose pseudocode is a full screen of text at which point I noped out and watched a Studio Ghibli film.
posted by pwnguin at 7:48 PM on December 6, 2018

6a was the first one that really gave me trouble, too. I always mix up my X and Y in at least one spot and get completely confused, plus I inevitably have off-by-one errors somewhere. On the other hand, I'm starting to get the hang of some pieces of Rust that used to trip me up a lot, so I spent less time fighting with the compiler even as I spent more time screwing up the logic. And even my lousy Rust is faster than my decent Python, so I don't feel quite as bad about using brute force everywhere.

Pyry, those are stunning! Super cool designs.
posted by pocams at 7:51 PM on December 6, 2018

Neat! How are you making those animations?
posted by waninggibbon at 8:33 PM on December 6, 2018

I have a lua-based graphics engine I write them in. Day 3 is mostly directly twiddling pixels in a texture, day 4 is all nanovg, day 5 is using shader-based text rendering because nanovg's performance isn't great if you're trying to draw 20,000 characters on the screen (the animation I showed is only 5000 characters with an 8x16px font, but I have a 20k version with a 4x6 font), day 6 is rendered in 3d.
posted by Pyry at 8:59 PM on December 6, 2018 [1 favorite]

Welp, today's puzzle was spent trying to be too clever with coreutils, then adventures in debugging python so deep I had to actually learn how visual studio code's debugger works.
posted by pwnguin at 12:34 AM on December 7, 2018

Yeah, 7B did not make any friends in my household. Usually the B part is just "run a different report on the structure you've built up in the A part". This time it was like "you've already sunk a little bit of time into this dumb puzzle, now sink a lot more in".
posted by Balna Watya at 3:42 AM on December 7, 2018 [2 favorites]

Just got around to finishing day 6. Initially it struck me like a job that had k-d tree written all over it, and I spent a bit of time faffing about with those; then I took another look at the pitifully small size of the input and thought bugger it, let's see what can be done with a C compiler and brute force.

stephen@jellynail:~/src/aoc/2018/06$ time ./1
[correct output redacted]

real    0m0.036s
user    0m0.020s
sys     0m0.000s
stephen@jellynail:~/src/aoc/2018/06$ time ./2
[correct output redacted]

real    0m0.009s
user    0m0.008s
sys     0m0.000s

So no k-d trees for me today. Might stick with C for a bit; irritation at its fiddliness is starting to be made up for by all these low-milliseconds execution times.

I'm finding these puzzles much more fun from not making even a sliver of an attempt to get them done quickly.
posted by flabdablet at 5:22 AM on December 7, 2018

Day 7 part 1 totally kicked my ass because I didn't realise that some things were being passed by reference, not value, in Go, so my graph was being stealthily mutated as I traversed it. Then part 2 had exactly the same issue in a different guise and I wasted time again. I might rewrite it at the weekend, because I'm actually pretty upset by the mess of functions I made trying to isolate the problem.

Pyry, those animations are gorgeous!
posted by Wrinkled Stumpskin at 6:02 AM on December 7, 2018

Sweet holy god, day 7 is the first day for me where a lack of algorithms background is a real hindrance. I'm aware of the existence of graphs, but knowing something about how to manipulate and traverse them (like this possibly spoilery link gleaned from the subreddit afterward) would have saved me literal hours.
posted by Upton O'Good at 9:00 AM on December 7, 2018

Day 7: Graph schmaph :-)

stephen@jellynail:~/src/aoc/2018/07$ time ./1
[correct output redacted]

real    0m0.003s
user    0m0.000s
sys     0m0.000s
stephen@jellynail:~/src/aoc/2018/07$ time ./2
[correct output redacted]

real    0m0.003s
user    0m0.000s
sys     0m0.000s

Mad props to Pyry for all that wonderful beauty.
posted by flabdablet at 9:46 AM on December 7, 2018 [1 favorite]

Wow, glad I noped out of day 6 before I went to bed. JDHarper's mention of voronoi saved my life - in R, getting voronoi diagrams is trivial. Thanks for saving me from reimplementing it!
posted by zug at 10:54 AM on December 7, 2018

I'm thinking of just giving day 6 a pass. I keep starting to brute force it but know there are good ways to do it. All of my "let's be clever" is sort of 'meh'. But now I sorta want to know what part 2 is.... Such a dilemma.
posted by zengargoyle at 11:17 AM on December 7, 2018

Day 7 part 1 question: If we consider the example input/output, but swap D&F of the input, then the output should be exactly the same. Is that correct? But if we swap A&F, the answer would be CFABDE?
posted by muddgirl at 11:25 AM on December 7, 2018

No, wait, that's wrong, too. If we swap A&F it would be CAFBDE?
posted by muddgirl at 11:28 AM on December 7, 2018

Day 7 is /really/ easy if you use the right data structure. Needless to say, I did not & made a horrible meal of it. I am ... not proud of today’s code.
posted by pharm at 1:09 PM on December 7, 2018 [1 favorite]

Another ugly bash at it until it works (enough) solution for day 7. I should really start using more than hashes/arrays but meh.
posted by zengargoyle at 3:34 PM on December 7, 2018

Upton O'Good, that pseudocode would have saved me a good while: the example only had one node without antecedents, and I subconsciously included that as a condition in my code. Example worked fine, actual input produced a non-deterministic result.
posted by Wrinkled Stumpskin at 4:24 PM on December 7, 2018

Did anybody else eschew graphs entirely and use a bitmapped scheduling matrix instead? That's both easy and fast provided the number of tasks you're trying to schedule isn't more than the number of bits in an integer CPU register.
posted by flabdablet at 9:46 PM on December 7, 2018

What would be an interesting variant is if everyone submitted assembly programs (in RISC-V assembly, let's say) and the server itself ran and ranked programs zachtronics-style.
posted by Pyry at 9:55 PM on December 7, 2018 [1 favorite]

Not much to Day 8; 4ms each.
posted by flabdablet at 11:06 PM on December 7, 2018

I tried to do day 8 roughly starting around 9 pst and it's the kludgiest yet. I couldn't quite figure out how to sanely increment a node number through a recursive loop so I just made an array of "0...len(input)/2" and whacked a node number off whenever I needed one.
posted by muddgirl at 11:15 PM on December 7, 2018

I couldn't quite figure out how to sanely increment a node number through a recursive loop

In my experience, it's quite often the case that if I'm finding it insanely difficult to achieve some subtask I perceive as desperately necessary, that's a sign that I'm coming at the thing across its grain and should take a step back for a while until I can see it more clearly.

Which is exactly why I hate hate hate coding in a screaming hurry, and have no interest in the leaderboard aspect of this set of puzzles. Whatever I'm doing, I'd rather be pleased with the result itself than with how quickly I got it done. Which is probably why I am, at this point, essentially unemployable.
posted by flabdablet at 11:58 PM on December 7, 2018 [1 favorite]

flabdablet, I did scheduling for 7 with a list and a hash and a tick-clock (didn't even bother to skip to the next event, just loop and do nothing and tick the clock). It wasn't worthy of pulling out the graph theory. I did try tsort first just in case...

Programming wise, I usually bust out quick and dirty as Proof of Concept. Then make it nicer depending on whether it's actually needed in the long run. Then I do the error checking or try to trim down the big-O. Definitely a little first/fastest/done on one-day throw away type things.
posted by zengargoyle at 1:30 AM on December 8, 2018 [1 favorite]

I'm impressed by the speed of the top entrants! It took me 10 minutes to get both stars for today (day 8), but I see that the winner got there in under 4 minutes. I would find it tough just to type the necessary amount of code in that time. I guess that if you want to challenge for the top, then you need to be automating the fetching of the puzzle data and the submission of the results (these have predictable URLs), and optimizing everything else for speed of typing, for example by working in the REPL and using ad-hoc collections like lists rather than structured data with names that you would have to waste time declaring.
posted by cyanistes at 3:41 AM on December 8, 2018

tsort doesn't work because you need a lexicographical topo sort; standard topo sort algorithms won't do the trick.

and yes, the right approach ought to make any AoC problem relatively straightforward. Which is easier said than done sometimes!
posted by pharm at 4:02 AM on December 8, 2018

I used a JS generator function for reading day 8's input into the tree, so that's something new. JS always looks ugly to me, but I think I made my solution quite legible.
posted by waninggibbon at 11:16 AM on December 8, 2018

I sorta cheated on day 8 part 2. Added the metrics bit into the tree builder so it came out to being $tree<v>.say. Guess I should have done the same for part 1.
posted by zengargoyle at 1:29 PM on December 8, 2018

I really enjoyed day 8 after sort of muddling through day 7. It's very satisfying when you hit a puzzle that happens to lean on something you understand pretty well. I was surprised how much easier the code came today vs. a weekday evening when I've already spent all day programming.

zengargoyle: I sorta cheated on day 8 part 2. Added the metrics bit into the tree builder so it came out to being $tree.say. Guess I should have done the same for part 1.

Hmm, true. I built the tree in memory too, but I guess there's no need to keep the child nodes around after you calculate the numbers you need. flabdablet's solutions are lovely examples of that.
posted by pocams at 2:11 PM on December 8, 2018

Yay, finished day 9 in a snap. Takes 3m35.155s to do part 2 but whatever.
posted by zengargoyle at 12:01 AM on December 9, 2018

Day 9 was the first "OK you solved it, but does it scale?" part two. And mine didn't so I learned about containers in Go!
posted by Wrinkled Stumpskin at 3:35 AM on December 9, 2018

Quite hard to talk about Day 9 without utter spoilers, so I'll wait for a bit.
posted by flabdablet at 4:01 AM on December 9, 2018

Takes 3m35.155s to do part 2 but whatever

450ms :-)

But I can't help wondering whether there's some cunning mathematical analysis of the thing that makes it drop out in O(1) time.
posted by flabdablet at 4:27 AM on December 9, 2018

Also, it seems to me that this game would be far more plausible as an activity that sentient beings might find amusing if the numbered marbles got drawn out of a huge bag at random instead of being played sequentially.

There's a reason casinos use roulette wheels instead of just having the croupier go eeny meeny miney mo.
posted by flabdablet at 4:35 AM on December 9, 2018

Hmm! My script has been running on part 2 for more than 20 minutes so I'm gonna say it's not very scalable at all.
posted by JDHarper at 8:39 AM on December 9, 2018 [1 favorite]

Out of curiosity I let my C#, array based solution run all morning on part 9B. It finished after ~4 hours. :D
posted by Balna Watya at 9:26 AM on December 9, 2018

Part 1: takes 12 seconds
Me: Okay, I'll just multiply this parameter by 100 and come back in 20 minutes. Easy
Part 2: does not take 20 minutes
Me (looking closer at how my array-based solution is doing inserts and deletes): Oh right.
posted by figurant at 10:06 AM on December 9, 2018 [1 favorite]

Python lists aren't really lists, and even if they were, they aren't the right kind of lists. My final version, using Real Lists took around 1/2 second for part A and 72 sec for part B. I assume the nonlinearity is due to working set constraints on my ancient Mac laptop.

I found the description incomprehensible in the extreme, so good on them--again, it was very similar to a real-world experience with customers and stuff...

I agree with the people that say the leaderboard thing is bunk, but because of my monkey brain I find myself obsessively checking my position. Dammit, monkey brain.
posted by Gilgamesh's Chauffeur at 10:25 AM on December 9, 2018

Since Python doesn't have [REDACTED] as a basic data type I had to write a terrible one of my own to make part II work in a reasonable time, only to discover later that [REDACTED] are totally a thing in the library that would have done what I need. Still, I was happy with it, and did appreciate the vivid demonstration of appropriate choice of data structure.

And...any sort of consensus on how long after a Day opens up is posting spoilers acceptable? Everyone's sort of edging around how they did it, and then we're on to the next day...
posted by Upton O'Good at 11:40 AM on December 9, 2018

Day 9 was a good exercise in knowing the algorithmic complexity of the operations on your data structures. Earlier days had similar traps, but the input just wasn't big enough to really inconvenience you if you had accidentally written a quadratic algorithm. Imagine getting a thousand times as many boxes on day 2, for example, or a thousand times as many steps and workers on day 7.
posted by cyanistes at 12:02 PM on December 9, 2018

Assuming we only use links for actual solutions, maybe discussing approaches at T + 12H (when the next puzzle has less than 12 hours to drop) would be suitable? I tend to avoid this thread until I've finished the problem, but I strongly suspect at some point I'd like to be able to stop scratching my head and peek in here. Then again, most of the time the approach is OK for me, and I spend my time wrestling with the language, so maybe other people feel differently.

(I'm in Europe, so I'm not sure if T+12 is awkward for the US, I just wanted to stick a concrete number in there to start with)
posted by Wrinkled Stumpskin at 12:42 PM on December 9, 2018

Yeah, calling Python lists "lists" is a massive trap for the unwary isn’t it? They’re really variable length arrays, with O(1) element access and (oh god) O(N) insert / delete, except for pop/push on the far end. An efficient data structure for day 9 requires O(1) pop/push at both ends.

I used a circular doubly linked list in Haskell, which was not exactly /fast/^†, but it was O(1) in all the required operations.

^†Haskell can be very fast, but sometimes it treads on its on feet & this seems to be one of those times.
posted by pharm at 1:06 PM on December 9, 2018

I saw a comment on MeFi where the spoiler is revealed by toggling an arrow (or something of that nature). Can't remember how to do it. Anyone?
posted by waninggibbon at 1:22 PM on December 9, 2018

While I didn't have much time during the week, I've started catching up (just finished #5 this afternoon). I've been doing everything in Erlang, which I kinda-sorta know, but haven't used much in years, and particularly not for this sort of thing. (I'd typically solve problems like this in Lua or C.)

The second half of #5 is the first where performance has really been an issue, and it's a pretty clear indicator that I've forgotten the trade-offs of doing string-y things by different means (binaries, lists).

And, I too am trying to ignore the leaderboard ranking, beyond seeing what % of people have how many of the exercises done so far. I'm not likely to do any of them within a day or two of when they go live.
posted by silentbicycle at 1:26 PM on December 9, 2018

I went with assuming Perl 6 arrays were appropriately double-link like at least towards the ends. Then it boils down to a couple shift/push and a one in 23 move of 7 elements. The rules of the game play close enough around the current that it pays to keep current at the first element of the array. No inserts/deletes at random locations, no tracking of current.

Some quick tests have shown that push/shift is something P6 does faster than move whole chunk, at least when chunk size is small (like 2).

I sorta want to try flabdablet's part 1 C solution in P6 but in 3 ways: my $i (polymorphic duck-type); my Int $i (typed); my int $i (native types). Just to see how the compiler reacts. I think maybe the runtime is long enough for the JIT to kick in and start dropping the polymorphic type checks. The int case should get close to C. I'm not sure if there's enough easy native support to do the double list approach.
posted by zengargoyle at 1:29 PM on December 9, 2018

like this

sorta like this

I wish MeFi had a shortcut like thing for that.... It's also a block element so a bit of ugly in practical use other than a spoiler section.
posted by zengargoyle at 1:30 PM on December 9, 2018 [1 favorite]

<details><summary>Spoiler</summary>spoiler text</details>
posted by zengargoyle at 1:32 PM on December 9, 2018

lol, firefox/whatever put an arrow on that last comment even though it's not really arrow worthy.
posted by zengargoyle at 1:34 PM on December 9, 2018

duh nevermind, wrong arrow... I'll shut up now. It's details and summary.
posted by zengargoyle at 1:35 PM on December 9, 2018

Python's lists are a trap for unwary developers who expect "list" to mean "linked list". But linked lists are a bit of a rarely used data structure these days — you don't often come across a problem requiring a linked list when you are working in a modern language with arrays, hash tables, sets, heaps, priority queues and other kinds of collection at your disposal. The problem would need to require efficient insertion at a bunch of different points in a list of items, and this requirement doesn't seem to arise very often. Even in the case of day 9 you didn't need insertion at a bunch of different points, only at a single point near the current item, and so a

spoiler

double-ended queue

is adequate.
posted by cyanistes at 1:41 PM on December 9, 2018

I did part 1 as a kind of poor man's (very poor man's) literate programming exercise, where I essentially just pasted in the problem description and then broke it into comments followed by little chunks of code as I went. That made it very easy to replace its array-shuffling circle implementation with one based on a headerless doubly linked circular list for part 2 when it became obvious that array shuffling was buttering insufficient parsnips.

Execution times:

./1 471 72026: 231ms
./2 471 72026: 5ms
./2 471 7202600: 448ms

No timing is available for ./1 471 7202600 because it doesn't produce correct output; I couldn't be arsed doing dynamic memory management and 7202600 is more than 1.c's MAX_MARBLES value. But my first cut at Part 2, where I just upped Part 1's limits and fed it the big number, was still running long after I'd started to wonder whether I'd switched from C to bash by mistake.

Nice touch from the problem setter:

making part 2's correct result too big to fit in a signed int32_t :-)

posted by flabdablet at 1:43 PM on December 9, 2018

I think that's about my original thought. A doubly linked ring and a pointer to current. move, insert, delete all within 7 steps and only two cases. I'd do that with a couple of macro's for 2 forward and 7 behind. and probably macro for insert/delete. Those turned into just using an array and keeping current at index 0.

I just wish P6 Array.rotate were in-place and optimized and not a new array producing function. Then it would be all rotate/shift/unshift.
posted by zengargoyle at 1:56 PM on December 9, 2018

I'd do that with a couple of macro's for 2 forward and 7 behind

The entire beauty of a headerless linked ring is that it lets you write stuff like current->ccw->ccw->ccw->ccw->ccw->ccw to go six places counterclockwise with no special-case checking ever required; macro schmacro :-)
posted by flabdablet at 2:00 PM on December 9, 2018

For comparison with flabdablet's C implementation, here's a day 9 solution in Python. Takes four times as long to run, but there's a lot less typing!
posted by cyanistes at 2:16 PM on December 9, 2018 [1 favorite]

Takes four times as long to run

Measured at 7.2 seconds on the same crummy old laptop I used for the C timings, which is sixteen times as slow, but still: highly impressive performance for a does-everything-for-you language with a reputation for sloth.
posted by flabdablet at 2:39 PM on December 9, 2018

....and python3 manages 3.9 seconds. Nice!
posted by flabdablet at 2:43 PM on December 9, 2018

Yeah, modulo the zip and a working rotate, cyanistes' solution is about the same as mine. Perl 6 is even more of a sloth. :)

But I like my infinite lists and busting out when done. I wonder if zip would slow things down or not.
posted by zengargoyle at 2:46 PM on December 9, 2018

Whew,just changing things to int and losing the Inf got it down to 1m33.560s. Not sure if I want to check shift/unshift vs pop/push.
shakes fist at Python
posted by zengargoyle at 3:27 PM on December 9, 2018

I don't need no steenkin libraries! C source code here with home-rolled double-linked circular list.

Day 9 seemed simpler for me that the previous couple of days. The rules of the game pretty much spells out the algorithm sequence.

time ./go 9 25
WINNING SCORE = 32

real 0m0.046s
user 0m0.001s
sys 0m0.002s

time ./go 464 71730
WINNING SCORE = [REDACTED]

real 0m0.014s
user 0m0.008s
sys 0m0.004s

time ./go 464 7173000
WINNING SCORE = [REDACTED]

real 0m1.052s
user 0m0.754s
sys 0m0.223s


posted by TwoToneRow at 3:29 PM on December 9, 2018

> zengargoyle:
"I wish MeFi had a shortcut like thing for that...."

Here you go. Just added a spoiler shortcut userscript to the mefiscripts repository.
posted by waninggibbon at 3:31 PM on December 9, 2018

Is there some subtle gag I am missing here? Whenever someone shows their timings, they're not showing the actual input values. I didn't think the problem input was in any way a spoiler. Or maybe it's actually mutating the inputs for everyone? Has it done that for each problem? This may be more complicated than I imagined...
posted by Gilgamesh's Chauffeur at 3:39 PM on December 9, 2018

I don't bother to be generic enough to process multiple inputs. I just write code that works on a sample and input file. It's the same code, just changing a string or a couple of initialization values. Save it, run it, move on. I think everybody gets the same sample but different input and we can't even guarantee anything about runtime comparison without going and grabbing somebody else's input so we're testing the same thing. My input might be 3x as large as someone else's, or might hit all of the corner cases. Who knows.

It's all fun and games and a bit relative.
posted by zengargoyle at 3:50 PM on December 9, 2018 [1 favorite]

From the discussion of the day 6 bug on the subreddit, it looks like there are a finite set of inputs for each problem (which lets them beta test with a relatively high degree of confidence that everything works as expected) . I guess including your input and output values could be a spoiler.
posted by figurant at 4:08 PM on December 9, 2018

...we can't even guarantee anything about runtime comparison without going and grabbing somebody else's input so we're testing the same thing...

I never considered that AoC was providing different input values to individual users, and would be surprised if this is the case. Is there any justification for supposing this is true?

The test values that I used in the day 9 problem can be seen as the command line arguments in my timer output snapshots in my previous post. Part 1 specified 464 players and a last marble value of 71730 (so part 2 would call for input values of 464 and 7173000).

Out of curiosity, did anyone here get a problem input for day 9 other than 464 / 71730?

I do agree that comparing timer values is not particularly valuable, though, since they are directly related to the hardware that the program is running on. In my case, I'm programming on the same system that I primarily only use for web browsing (mid-2007 iMac with a 2 GHz Intel Core 2 Duo CPU and 4 GB of 667 MHz DDR2 SDRAM -- practically a museum piece).
posted by TwoToneRow at 4:18 PM on December 9, 2018

would be surprised if this is the case

Then we're both surprised. The inputs I got for day 9 are as shown in my timings, 471 / 72026.
posted by flabdablet at 4:27 PM on December 9, 2018

That's interesting: 476 and 71431 for me. So there's a range.
posted by figurant at 4:28 PM on December 9, 2018

If everybody's input were the same, there would be rampant cheating. Just punch in your friends answer and be finished in zero time.

I'd think they have a reference implementation of the solution (all fast as hell) and would throw some random inputs at it and pick a subset of them that run in about the same time. Then randomly give different users different inputs. But that way there's no guarantee that each input behaves the same under bad algorithms. The only behave the same under the same algorithm. Nevermind the speed of your machine or whether more and faster cores can help. But the problems aren't of the OMG need 32 cores and a parallel algorithm to get this done fast enough to win.
posted by zengargoyle at 4:29 PM on December 9, 2018

Huh, should have previewed ... thanks figurant, this was news to me. And yeah, I guess it does make individual runtimes even less meaningful.

What do y'all think in general about posting links to code in this thread? Too Spoilery?

I was hesitant to at first, but seeing others do it, I've put up a couple also. I make a point of not looking at comments here until after I've finished a day's problem and posted my results because not working it out completely on my own would spoil the fun entirely. On the other hand, it's interesting to see how others approached the problem once I'm finished myself.
posted by TwoToneRow at 4:34 PM on December 9, 2018

(It's late enough in the day that I figure it's OK to get a little more detailed here.)

I've been doing these in Rust, and Rust can get very... prescriptivist sometimes. Here's a place where that helped me. The standard collections crate includes a guide to selecting a data structure that pretty heavily discourages you from using LinkedList, which was what I immediately found myself reaching for. And after thinking about it for a minute, of course a double-ended queue is going to be way faster, even with all the manual pushing and popping the ends of the queue; a genuine linked list is a pretty heavyweight data structure and you're going to get cache misses all over the place. And sure enough, the deque was pretty snappy! Thanks, Rust.


$ time ./target/release/p9
411 7117000 => [redacted]

real 0m0.165s
user 0m0.125s
sys 0m0.040s
posted by phooky at 5:41 PM on December 9, 2018 [1 favorite]

it does make individual runtimes even less meaningful

...which is why it's fun to play with different data structures in the same language and time them on the same box.

So I wrote one with a deque made from a static array in C, and timed it on the same Celeron laptop where the doubly-linked headerless ring version achieved 448ms with the same inputs:

time ./3 471 7202600
3150377341

real    0m0.146s
user    0m0.100s
sys     0m0.040s

Booyah! Deque FTW.
posted by flabdablet at 5:55 PM on December 9, 2018

With PyPy:

gtime -p python day9.py

real 1.28
user 1.06
sys 0.14

With CPython 3:

gtime -p python day9.py

real 4.22
user 3.90
sys 0.21

Inputs (403, 7192000)
posted by waninggibbon at 6:03 PM on December 9, 2018

And JavaScript with the same inputs:

gtime -p node day9.js

real 0.88
user 0.81
sys 0.21

posted by waninggibbon at 6:09 PM on December 9, 2018

Is the double ended queue just the static version with the gap? (glance at flabdablet's C).
posted by zengargoyle at 6:58 PM on December 9, 2018

Yep. The array indexes are always incremented or decremented circularly, wrapping around at the ends of the array, so the array functions as a great big fixed-size ring containing two conceptually (though not always physically) contiguous regions: one full of marbles starting at index current, and an empty one starting at index gap. Incrementing current requires that the marble it's about to not index any more gets thrown backwards over the gap, and decrementing it requires that the last marble before the gap gets thrown forward into its spot.

If I were half smart I would have forced the array size to be a power of 2 so I could do the circular indexing with a mask instead of all that compare and branch nonsense... brb.

...nope! It's actually slower. CPU caches are weird.
posted by flabdablet at 7:38 PM on December 9, 2018

...and it's only slower because I accidentally made MAX_MARBLES sixteen times too big when bumping it up to a power of 2. If I drop it back from the 10000000 I had it at initially to 0x800000 instead (which is the same as 8388608, smaller than ten million but still big enough) then the runtime drops from 146ms to 139ms, with the masking version being maybe a millisecond or two faster.
posted by flabdablet at 7:54 PM on December 9, 2018

The Day 10 puzzle is my favorite so far, possibly because it's the closest to what I'm familiar with (trying to draw some meaning out of a pile of data).

Testing out the spoiler-hiding functionality:

I'd guessed we'd get the message when the grouping of the stars was maximally-compact, so I computed the total taxicab distance from all the stars to their x- and y- means and stepped through time until I got a minimum. Figured it'd be that one, or maybe a neighboring one if the velocity distribution was not in my favor, but the first one worked.

posted by Upton O'Good at 9:56 PM on December 9, 2018

Upton O'Good, ditto-ish. I'd maybe add horizontal/vertical segment length totals and hope that the font is expected. But too close to bedtime this one is.
posted by zengargoyle at 10:22 PM on December 9, 2018

Pondering

the maximal velocities of maximal opposite directions and the minimal velocities of maximal different directions are going to intersect at a point in time.

posted by zengargoyle at 10:33 PM on December 9, 2018

Spoilers

Upton O'Good, same here, although I cast a wider reasonable-sounding maximum height and width for the potential message timesteps, then just stepped through them until I saw text.

posted by figurant at 10:52 PM on December 9, 2018

Spoiler

The worst case I think is that the message implodes like a black hole. The minimum would be a '.' in the center of the universe. It's luck that the past/future message explodes (for a definition of explode) into a structure that isn't a single point. Any message could implode/explode into a spray of points that would at some time pass through a single point. Bad problem. :P

posted by zengargoyle at 11:01 PM on December 9, 2018

/me curses spoilers.... y'all on your own and let luck be in your favor, there's a mirror universe solution that's upside down and backwards.
posted by zengargoyle at 11:07 PM on December 9, 2018

I would LOL my ass off if the message was interpretable upside down and backwards... is it 'OH' or 'HO'. Now I just want to guess "OHOHOHO".
posted by zengargoyle at 11:17 PM on December 9, 2018

My Day 10 message looks suspiciously like it was generated uniquely for me.
posted by flabdablet at 12:59 AM on December 10, 2018

People seem to be solving day 10, so I suspect guessing the puzzle generator avoids degenerate cases that stymie naive approaches. The generator algorithm is probably something along the lines of:

1. Pick a string
2. pick a time in range(bignum, bignum*2)
3. Generate your message
4. Calculate some kind of average point / center of mass for the message
5. For each star in the message, formulate a tangent line, such that the star's current position is closest to the average point
6. Pick a point on the line, and call that the initial position; calculate your vector based on that.

Obviously this is imperfect given the discrete nature of vectors and the "sky" but would probably suffice if given enough space.
posted by pwnguin at 1:04 AM on December 10, 2018

The puzzles for day 10 are almost certainly generated by time reversal — that is, the server generates a random message, gets the coordinates of the pixels making up the letters in the message, chooses a random velocity for each point, chooses a random number of seconds, and subtracts velocity × seconds from each coordinate to get its starting position.

What this means is that

as you step time forward, the points come together and then fly apart again. So you can detect the time at which the message appears by stepping time forwards and computing the size of the rectangle spanned by the points. When the size of the rectangle reaches a minimum, you've found the message. Python code here.

posted by cyanistes at 1:51 AM on December 10, 2018

I might actually have written less code than a Pythonist today!

Hooray for fill down, Goal Seek and charts

posted by flabdablet at 2:02 AM on December 10, 2018

The generator algorithm is probably something along the lines of

I think it's even simpler than that:
1) Rasterize the message into points
2) Give each point a random velocity
3) Pick a random large time T
4) Run the simulation backwards (negative velocities) for T

(what cyanistes said)
posted by Pyry at 4:32 AM on December 10, 2018

This morning I was debating whether to drop out, but I decided to go ahead and ended up really enjoying this puzzle. My main mistake was that I managed to mess up the printing, such that it left out the last column of the answer. It was so baffling to have this perfect message coalesce out of chaos, and then for message to somehow not be the right one. (hopefully not a spoiler, the last letter for me was a "P" that my bugged printing algo showed as an "F") Lol.
posted by Balna Watya at 4:56 AM on December 10, 2018 [1 favorite]

Did some interactive plotting with Vega for Day 10.

Started out by futzing with matplotlib, but couldn't get it to update my plots rather than printing out thousands of new ones, StackOverflow answers be damned.
posted by waninggibbon at 6:59 AM on December 10, 2018

Since it was a few days ago now, here are some spoilers for day 7. I hope this is ok (and interesting).

Part 1 asks for the topological order of the steps, in particular, the alphabetically first topological order.

“Topological order” is one of the many terrible names we have in computer science. The name was given to this problem (or maybe just popularized) by Arthur B. Kahn, based, I can only assume, on an analogy with the problem of embedding a graph in a topological space, the space in this case being a line. But the analogy doesn’t quite work, and the name can only plausibly help people who are already familiar with topological graph theory, that is, almost nobody.

There is a simple algorithm for finding a topological order. Kahn makes a bit of a meal of it in his 1962 paper, but basically you keep a collection of sources (nodes with no incoming edges). At each step you output a node from the collection, and remove that node and all its outgoing edges from the graph. Removing an outgoing edge might leave the destination of that edge with no more incoming edges, in which case add that node to the collection of sources. Eventually there are no more sources, and if the graph is empty you’re done (if it’s not empty at this point then there is no topological order because the graph has a cycle).

To get the alphabetically first topological order, you have to pick the alphabetically first source at each step. This suggests that the collection of sources ought to be a priority queue, so that you can pick this node efficiently. But in day 7, every node in the graph is represented by an uppercase letter, so there are at most 26 sources, so nothing will go wrong if you use some other kind of collection and pick nodes naïvely.

Part 2 is suitable for solution by discrete event simulation. In this kind of simulation, you keep a collection of future events (in day 7, an event is “one of the workers finishes their task and becomes available for another task”), each associated with a time. At each step of the simulation you pick the event in the collection that occurs soonest (the one with the smallest time) and carry it out, possibly updating the collection with new future events.

The need to pick the soonest event again suggests that the collection of future events ought to be in a priority queue. But in day 7, the size of the collection is limited to the number of workers, which is only 5, so again nothing will go wrong if you use some other kind of collection. An observation that helps simplify the code is that there is no need to distinguish the workers or give them ids: the only thing we need to know is how many are busy working, which is the same as the size of the collection of future events. Python code for part 2, using heaps to implement the priority queues.

posted by cyanistes at 7:06 AM on December 10, 2018 [1 favorite]

Day 1 animations giving a visual intuition for the non-brute-force approach
Day 10 animation
posted by Pyry at 7:58 AM on December 10, 2018 [2 favorites]

Day 10 visualizations suggest we're all wrong about puzzle generation. There seems to be a limited number of starting points for stars ( plus or minus a bit of fuzzing). I imagine the chances of that setup producing a degenerate output is low -- you'd need all the edge stars to be moving towards the center after the message is shown.
posted by pwnguin at 9:51 AM on December 10, 2018

What the visualizations show is that there are a limited set of velocities: if you always scale your axes to fit all the points, then what happens is that at large scales all the points with the same velocity cluster together.
posted by Pyry at 10:33 AM on December 10, 2018 [2 favorites]

I haven't started day10 for the same sort of reason as day6: overthinking a simple problem looking for low O() and wanting clever. Plus I know I'll either have to lookup a module or write my own console frame buffer to read the answer.
posted by zengargoyle at 1:03 PM on December 10, 2018

I did as cyanistes suggested above. I'm not sure it's rigorous though, but it does pop out the right answer satisfyingly clearly. I wonder if you could maths it - I'm imagining trying to find the narrow bit of a splayed bundle of dry spaghetti.
posted by Wrinkled Stumpskin at 1:19 PM on December 10, 2018

Wrinkled, same here. The points and velocities make a set of lines that will intersect (if not parallel). On the grid world the intersection will be a point or a set of 4 points around the fractional intersection with the integer time tick. The space of the intersections will define the area of the solution. It's like a reverse of Pyry's observation that at scale the velocities group the points.

After checking a few of the points, the t should become apparent somehow (that's the troubling bit). Then there's the degenerate case of where the points were originally given a velocity that is proportional to the center of the message so that at time t+1 they would all fall into the middle, then at t+2 they would be the upside down mirror image of t-1. And the problem comes down to observation and recognizing the message. I only hope the randomness of velocity attachment makes the bad case not a big deal.

Metafilter: overthinking puzzles
posted by zengargoyle at 1:33 PM on December 10, 2018

OK, zengargoyle, I scribbled down my equations and implemented it. Now finishing in under 5ms on this machine.

The intuition was from your answer:

the maximum number of intersections is when the message is crisp and clear, so find the time with the maximum number of intersections

posted by Wrinkled Stumpskin at 2:50 PM on December 10, 2018

Well Wrinkled Stumpskin, that both made my day and annoyed me to no end. :)

I'm still trying to draw points to the console.

I guess it's really time to start using class/object or such to make things more manageable. Up to now things have been easy enough to just use basic data structures and some built-in methods.

I do hope 5m is fast.... :)
posted by zengargoyle at 3:50 PM on December 10, 2018

If everybody's input were the same, there would be rampant cheating. Just punch in your friends answer and be finished in zero time.

That would be true if the score were how long it took since you got the problem. But the score is instead based on the time since the problem dropped. I would assume it is just to make it less likely that someone will inadvertently reveal the one answer while bragging about their mighty solution. They have clearly put some thought into this ... no big surprise, I guess.
posted by Gilgamesh's Chauffeur at 6:09 PM on December 10, 2018

Day 10:

Spoiler

Solved it with a kludgy matplotlib animation, just skipping ahead a bunch of frames until I got to something that looked like letters. It took me an embarrassingly long time to figure out that my scatterplot was upside down

posted by JDHarper at 8:13 PM on December 10, 2018

some spoilers for day 7. I hope this is ok (and interesting).

It was both!

Here's why I didn't use any of it.

I looked at day 7 and immediately thought "graph", mainly because the problem description in part 1 has a graph right there up front. Then I looked at it again, thought "steps with single letter identifiers", and realized that 26 is less than the number of bits in a CPU word. It seemed to me that by the time a topo sort algorithm had got a graph even half built, a super simple brute force scan with a tight inner loop might well have finished the entire job.

So I just made a little prereq[26] array, where each entry is a 32-bit word where bit B of word W says whether or not step B is a prerequisite for step W. This can be built about as fast as the sample input can be read: the overwhelming bulk of the time spent on translating "Step B must be finished before step E can begin" to setting bit 1 of prereq[4] is occupied by the I/O buffer management and string scanning required to extract "B" and "E" from that input, pretty much regardless of how rigorous one gets about enforcing the format.

The same input parsing loop that builds prereq[] also builds incomplete, a one-word bitmap containing a 1 for each step that was mentioned in the input in any way; at the end of the loop, that forms a map of steps that have yet to be completed. So after reading

Step C must be finished before step A can begin.
Step C must be finished before step F can begin.
Step A must be finished before step B can begin.
Step A must be finished before step D can begin.
Step B must be finished before step E can begin.
Step D must be finished before step E can begin.
Step F must be finished before step E can begin.

we get the following, where # is a 1-bit, . is a 0-bit, and bits are numbered from 31 on the left down to 0 on the right:

incomplete

..........................######

prereq[]

.............................#..
...............................#
................................
...............................#
..........................#.#.#.
................................
(20 more words of zeroes)

Given this structure, finding the first step that's ready to be completed requires scanning prereq[] in order, iterating both a step index from 0 to 25 and step mask from

...............................#

to

......#........................

to find the first value where the logical AND of incomplete with the mask is nonzero (i.e. the step is not completed) but with prereq[index] is zero (i.e. all that step's prerequisites have completed). Since the index, the mask and incomplete can all be kept in registers and the prereq[index] lookup implemented by a single memory fetch instruction, this requires only a very short inner loop and very little CPU time.

Here's the object code generated by gcc for that inner loop. Register eax is being used for the index, ebx for the mask, ebp for incomplete, edi for the desired output, and r12 for the address of the prereq array.

 850:   31 c0                   xor    %eax,%eax
 852:   bb 01 00 00 00          mov    $0x1,%ebx
 857:   66 0f 1f 84 00 00 00    nopw   0x0(%rax,%rax,1)
 85e:   00 00 
 860:   85 dd                   test   %ebx,%ebp
 862:   89 c7                   mov    %eax,%edi
 864:   74 06                   je     86c
 866:   41 85 2c 84             test   %ebp,(%r12,%rax,4)
 86a:   74 24                   je     890
 86c:   48 83 c0 01             add    $0x1,%rax
 870:   01 db                   add    %ebx,%ebx
 872:   48 83 f8 1a             cmp    $0x1a,%rax
 876:   75 e8                   jne    860 

The body of the loop starts at offset 0x860 (the compiler having aligned it to that 16-byte boundary via the complicated no-op at 0x857) and is only 24 bytes long, so it fits inside one of an x86 CPU's internal 32-byte micro-operation cache lines and only needs fetching once. The data array it's scanning is only 26*4 = 104 bytes long, so it fits inside two 64-byte data cache lines. Even in the worst case where it has to go around all 26 times, this loop will use less CPU time than responding to an interrupt. It's a trivial amount of code.

Detecting when all steps have been completed is very easy as well: just use the bitmask value for each step to clear its associated bit in incomplete when it completes. This allows the outer loop's condition to be written as while (incomplete), which is kind of nice.

Of course, once the number of steps to be scheduled gets bigger than the number of bits in a CPU register, this kind of O(n²) approach more and more clearly becomes the Wrong Thing. But in this particular instance, it seems to me that brute force does score one of its rare wins on speed and elegance as well as on conceptual simplicity.

Pyry, the amount of work you're putting into your animations continues to astonish and delight, and I love your insightful non-brute-force analysis of day 1 part 2.
posted by flabdablet at 11:21 PM on December 10, 2018

Here's the request to pick some formatting for spoilers.

»Spoiler«

Spoiler text here.

Just because firefox at least doesn't make that clickable thing obvious. I was clicking on "It was both!" for no reason.

I'm too lazy to look up the unicode '>' thingy...

just a (my) UI experience rant.
posted by zengargoyle at 11:56 PM on December 10, 2018

Looking at day11, I think it's time to bite the bullet and make a Class that does integer grid type stuff. I keep confusing myself over the 1x1 pixel nature of things. I need a friggin' Manhattan Space data structure.
posted by zengargoyle at 12:26 AM on December 11, 2018

Here's why I didn't use any of it

Au contraire! The table of bits is the adjacency matrix of the graph; masking the table entries against incomplete corresponds to deleting the completed nodes from the graph; and the search for the first nonzero masked valued corresponds to finding a source (a node with no incoming edges). So this approach is the same as Kahn’s algorithm.
posted by cyanistes at 4:14 AM on December 11, 2018 [1 favorite]

Point is that in designing that code, I didn't have to think about graphs and nodes and edges at all.

The fact that a prerequisites bitmap constitutes the adjacency matrix of the corresponding dependency graph is interesting, as is the fact that some operations on that bitmap correspond 1-1 to operations on the graph itself. But I don't think it's fair to claim that scanning a bitmap is the same as Kahn's algorithm given that it requires the building of none of the data structures generally used by that algorithm, either explicitly or conceptually.

I've always liked bitwise logical operations as implemented by conventional CPUs, just because they so often go unrecognized as belonging squarely in the Single Instruction Multiple Data category and can be used to do stuff like check for completion of up to 64 separate dependencies in parallel using a single ALU operation.
posted by flabdablet at 4:47 AM on December 11, 2018

After checking a few of the points, the t should become apparent somehow (that's the troubling bit).

(spoiler) Doesn't have to be troubling.

What you can do there is just pick pairs of points more or less at random and treat the X and Y components of their worldline equations independently, as pairs of simultaneous equations to solve for X and t or Y and t.

If we have

x₁ = x0₁ + v₁t
x₂ = x0₂ + v₂t

and want to find out what value of t will make x₁ = x₂, we can just equate them:

x0₁ + v₁t = x0₂ + v₂t

Grouping like terms:

v₁t - v₂t = x0₂ - x0₁
t = (x0₂ - x0₁) / (v₁ - v₂)

Same thing works for the Y components. Treating X and Y separately is better, though, because it allows you to find a useful t even for worldlines that don't intersect because of being parallel or antiparallel.

I've uploaded a second spreadsheet that uses this technique to get a good starting hint for t by applying calculations like those above to pairs of points that just happen to be adjacent in the input, then averaging all the results. It works well enough that it charts the hidden message for the input AoC gave to me as soon as the input is pasted into it, with no twiddling or goal seeking on required for the generated hint time. I'd be interested to hear if it works equally well for other people's AoC input. There's a little bash script in the same folder that turns input as AoC presents it into a CSV that can easily be opened and pasted into the spreadsheet's Input sheet.

But now I really must cease to gibber and turn my attention to day 11's puzzle.
posted by flabdablet at 5:25 AM on December 11, 2018

So day 11 is all about penalizing simple-minded brute force again. And although it will undoubtedly take me far longer to work out the tidy way to do this than the 35 seconds the stupidest possible C program took to HULK SMASH its way to the correct answer, I really kind of want to. Because it really, really should be possible to do this in not many milliseconds at all.
posted by flabdablet at 7:58 AM on December 11, 2018

I got the solution to part two all three ways!

<SPOILERS>

Initially the deeply bogus O(n⁵) which took over an hour when I left it running as penance for not being a CS dude that knows algorithms. Once I entered the answer, I looked at the solutions thread. Partial sum (going along the edges of each new square and adding to the inner square) was less than 30 seconds, and finally the Summed Square Table which I presume is the only way to get this to run in less than 10 seconds on a 10 year old laptop, and took a second on mine.

All the rework on the solutions meant I ended up with a function entitled FindOptimalSquareOptimally, which suggests at least 3 more functions I should write if you complete that square. Inter alia, flabdablet, my hour-plus runtime suggests there is a stupider C program possible, but it won't fit in the margins of this comment.
posted by Wrinkled Stumpskin at 9:39 AM on December 11, 2018 [1 favorite]

(spoiler) OK, making some progress.

In a size-N grid, there are

N² 1×1 squares
(N-1)² 2×2 squares
...
(N-S)² S×S squares
...
1 N×N square

i.e. the total number of squares is the sum of the first n square numbers which is n(n+1)(2n+1)/6, so solving part 2 requires the evaluation of 300*301*601/6 = 9045050 results. Given that the rules for loading the grid amount to a pseudorandom number generator, albeit a fairly shitty one, I'm probably not going to find a better way to get the sums required than actually doing the adding up. So what's needed is a systematic way to address the grid in order to minimize the amount of superfluous addition by making good use of partial totals.

The code in 3.c is a step in that direction. With an 824ms runtime it appears to be doing about 1/42 the work of the HULK SMASH version in 2.c. It's down to four nested for loops, which is a fair improvement. If I can get it down to three I will be happy, given that the problem looks to me to be inherently O(n³) at an absolute minimum.

On preview: I seem to have reinvented the partial sum technique mentioned in Wrinkled Stumpskin's comment. Not having found my way to a "solutions thread", I plan to enjoy dreaming up the next optimization on my own :-)

posted by flabdablet at 10:06 AM on December 11, 2018

It seems the fastest solvers brute-forced it, printing out the max by width and inputting their answer before their program exited the loop.
posted by waninggibbon at 10:20 AM on December 11, 2018 [1 favorite]

(spoiler) Simple optimization is simple.

4.c simplifies the inner loop by moving the handling of the degenerate 1x1 case elsewhere, improving the speed by 7% to 780ms. But enough of this marginal nonsense. Time to sleep; with any luck I really will literally (literally literally, not figuratively literally) dream up something better.

By the way, this laptop is eleven years old and it was a sub-AU$400 piece of crap when it was new :-)

posted by flabdablet at 10:27 AM on December 11, 2018

So, today is the first day that I would like to punch somebody (other than myself). "1288, 302, 17" should be scored as though the spaces aren't significant. I think I ran my solution at least a dozen times, scrutinizing things and adding columns by hand and so forth before it occurred to me "gee, maybe they're doing something dumb parsing the input..."

This is the first one where I thought maybe I should find something faster than Python, but in the end even with a lot of debug output it ran in around 30 seconds on my elderly laptop. I have a feeling this would really scream on a GPU.
posted by Gilgamesh's Chauffeur at 4:41 PM on December 11, 2018 [1 favorite]

(spoiler) I think I've done all the optimization I care to on Day 11.

Going from brute-forcing Part B (with individual grid position values precomputed and stored in a 2D array) to my alternate version of storing the sums for each square size and using those values as a starting point for the next square size took me from 140 seconds to 2.7 on my home PC.

posted by figurant at 6:07 PM on December 11, 2018

Day 11: I'm surprised by how much faster a 2d array worked than a dictionary. (Python and JS solutions.)

Times:

CPython3 with dictionary summed-area table:

real 16.83
user 16.44
sys 0.14

CPython3 with 2d array:

real 10.91
user 10.63
sys 0.08

PyPy with dictionary:

real 7.06
user 6.55
sys 0.11

PyPy with 2d array:

real 0.37
user 0.30
sys 0.04

Node with dictionary:

real 12.35
user 11.88
sys 0.26

Node with 2d array:

real 0.29
user 0.26
sys 0.02

posted by waninggibbon at 6:07 PM on December 11, 2018

Day 12 pt. 2 has a clever trick but my implementation to get there feels very janky.
posted by figurant at 10:07 PM on December 11, 2018 [1 favorite]

Janky is relative, I'm reasonably pleased with my implementation [SPOILEROONIES] to find when to do the clever trick. But then as usual, now that I've answered I'm going to see how everyone did it better in three characters of bf.
posted by Wrinkled Stumpskin at 2:05 AM on December 12, 2018 [3 favorites]

5.c: When in doubt, throw RAM at it. 66 milliseconds for day 11 part 2.

The inner loop code that has to run 8955050 times in order to check every possible square of size 2x2 and upward is just

 870:   41 8b 03                mov    (%r11),%eax
 873:   41 2b 01                sub    (%r9),%eax
 876:   41 03 02                add    (%r10),%eax
 879:   2b 44 b5 f8             sub    -0x8(%rbp,%rsi,4),%eax
 87d:   01 c2                   add    %eax,%edx
 87f:   39 fa                   cmp    %edi,%edx
 881:   0f 4d fa                cmovge %edx,%edi
 884:   44 39 c2                cmp    %r8d,%edx
 887:   44 0f 4f fb             cmovg  %ebx,%r15d
 88b:   45 0f 4f f5             cmovg  %r13d,%r14d
 88f:   0f 4f ce                cmovg  %esi,%ecx
 892:   48 83 c6 01             add    $0x1,%rsi
 896:   49 81 c3 b4 04 00 00    add    $0x4b4,%r11
 89d:   49 81 c1 b0 04 00 00    add    $0x4b0,%r9
 8a4:   49 81 c2 b4 04 00 00    add    $0x4b4,%r10
 8ab:   4c 39 e6                cmp    %r12,%rsi
 8ae:   41 89 f8                mov    %edi,%r8d
 8b1:   75 bd                   jne    870 

So that will do nicely.

Now on to day 12.
posted by flabdablet at 5:32 AM on December 12, 2018

I just added a temporary squares_checked counter to the logic that tests whether the square just considered is the best one, to make sure there isn't a bug that makes it miss some, and there isn't; it really does increment squares_checked 9045050 times in those 66 milliseconds. That means the machine is checking squares at a rate of about one every 7 nanoseconds on average; less time than it takes for a photon emitted from my room light to reach my face.

Sometimes I am just gobsmacked by 21st century microprocessors. Even shitty old Celerons.
posted by flabdablet at 5:47 AM on December 12, 2018 [2 favorites]

Day 12: 3 milliseconds each.

Jankiness++
posted by flabdablet at 10:41 AM on December 12, 2018 [2 favorites]

For Day 12 part II, I think I may have outjankied the pack by

Spoiler

not actually coding the second part. I modified part I slightly to print number of pots left instead of pot score per generation, and ran it to 1000 generations, at which point the initial transients had died off and the number of valid pots wasn't changing. (At this point, there were 26 pots and a score of 26669.) I spot checked the pot count and pattern, and yep, it was the same pattern moving rightward one pot per generation, so I fed the linear extrapolation [(50000000000-1000)*26 +26669] in and it worked.

I feel less bad about this than maybe I should, since I'm pretty darn sure the long term behavior is entirely dependent on the details of the LLCRR data table you received. I could make a variant of the table which moved continuously left (...#. => #), which had fixed points (..#.. => #), or which fed both directions without cycling (.#.#. => #, ...#. => #, .#... => #). Sounds to me like a case where the right thing to do is solve the specific problem, perhaps without solving the general one.

posted by Upton O'Good at 8:12 PM on December 12, 2018 [1 favorite]

(spoiler) On data structures for Day 11

Having now allowed myself to look at what other people did for Day 11, I have to say that their partial-sum tables are better-constructed than mine.

My code builds two tables of partial sums. Each cell in above[row][col] contains the sum of all the cells in cells[][] with the same column index and a strictly smaller row index; each in left_of[row][col] contains the sum of all the cells in cells[][] with the same row index and a strictly smaller column index.

These tables allow for rapid calculation of the sum of any horizontal or vertical line of cells. To get the sum of all the cells between cell[row][left] and cell[row][right] inclusive, for example, requires only looking up left_of[row][right+1] and subtracting left_of[row][left]. The same thing works for vertical lines of cells using above[][].

The tables work hand in hand with an incremental way of building the sum of the cells in successively larger squares rooted at any given top left corner. For example, if I already have the sum for some 4x4 square then the sum for the 5x5 square that shares its top left corner can be built by adding on the sum for the 1x4 sub-row immediately below it, then the sum for the 5x1 sub-column immediately to its right, each of which costs two lookups and a subtraction in left_of[][] or above[][]. In all, each square ends up costing four lookups, two subtracts and two adds.

The partial-sum tables that others are using work differently. Rather than holding sums of rows or columns of cells, they hold the sums for entire rectangular regions. One way to construct such a table would be to call it upper_left_sum[row][col] and have each cell in it hold the sum of all the cells from the original cells[][] table with smaller or equal row and column indexes, but summing toward any corner will work.

Once we have such a table, then to get the sum for the region from cells[top][left] through cells[bottom][right] inclusive, we just retrieve upper_left_sum[bottom][right] and remove the contributions from regions strictly above and to the left of the target rectangle by subtracting both upper_left_sum[top-1][right] and upper_left_sum[bottom][left-1]. Since those removed regions overlap, we've removed too much and need to add back the sum for the overlapping region by adding upper_left_sum[top-1][left-1]. Four array lookups, two subtracts and an add is all it took.

In the end this is only one less add per rectangle than required by my own algorithm and data structures, but it has a couple of important advantages. One is that it no longer relies on needing to construct the sum for a given square by proceeding incrementally from a smaller one; the sum for any square at all (in fact any rectangle) can be calculated immediately, which simplifies the loop conditions and might allow the work to be done in a more cache-friendly order. But the most beautiful is the fact that because this kind of table doesn't need to be any bigger than the original cells[][] array and also supports retrieval of all the original information from cells[][] with no data loss, it could potentially replace the original array and achieve all this lovely speed at zero additional RAM cost.

I tip my hat to whoever came up with it. That shit is tidy.

posted by flabdablet at 9:09 PM on December 12, 2018 [1 favorite]

Upton, I came to the same conclusions and went about it in much the same way.

After turning on the debug output and seeing the thing drifting to the right I altered one loop boundary in the generator to give it a leftward bias, so that any pattern moving to the right would become stable instead, and saw stability achieved by generation 93.

posted by flabdablet at 9:18 PM on December 12, 2018

Still playing with the power cell grid thing from Day 11.

6.c uses a data structure I didn't design, as discussed in the above spoiler. It requires no more RAM than the stupidest solution, and it completes in 40 milliseconds.

Forty. Milliseconds. For a problem where the stupid way to do it in the same language on the same computer makes the fan run hard for 34 seconds. Four nanoseconds per tested square, on a Celeron from 2007. Holy snappin' duckshit.

This is why computer science is a thing, folks.
posted by flabdablet at 5:55 AM on December 13, 2018

Interestingly, the inner loop that occupies the bulk of the time for 6.c looks quite similar to that for 5.c:

 8f0:   41 8b 04 94             mov    (%r12,%rdx,4),%eax
 8f4:   41 2b 04 93             sub    (%r11,%rdx,4),%eax
 8f8:   2b 44 95 00             sub    0x0(%rbp,%rdx,4),%eax
 8fc:   03 04 93                add    (%rbx,%rdx,4),%eax
 8ff:   44 39 c0                cmp    %r8d,%eax
 902:   44 0f 4d c0             cmovge %eax,%r8d
 906:   44 39 c8                cmp    %r9d,%eax
 909:   41 0f 4f f2             cmovg  %r10d,%esi
 90d:   0f 4f fa                cmovg  %edx,%edi
 910:   41 0f 4f cd             cmovg  %r13d,%ecx
 914:   48 83 c2 01             add    $0x1,%rdx
 918:   45 89 c1                mov    %r8d,%r9d
 91b:   81 fa 2b 01 00 00       cmp    $0x12b,%edx
 921:   7e cd                   jle    8f0

It's four instructions and sixteen bytes shorter, but it's also using the x86's complicated base-plus-scaled-index addressing mode to get at the array memory where the earlier code uses plain register-indirect index addressing, so it's doing about the same amount of arithmetic inside the CPU on each pass through the loop.

I think the main reason it's so much faster is the pattern of memory accesses. If you look at all the instructions that hit memory here, they're all doing it using base addresses that stay the same for the entire inner loop plus an index that increments by one word each time through. That means that memory accesses are walking through four contiguous ranges of memory in sequential order, which is very cache-friendly behaviour.

The eariler code's memory accesses are all over the place by comparison, so I'm pretty sure that's where the relative performance hit is.
posted by flabdablet at 6:14 AM on December 13, 2018

That data structure is sometimes called a "summed area table" but if you want to sound really sophisticated you can call it an "integral image".
posted by Pyry at 10:32 AM on December 13, 2018 [1 favorite]

So, Day 13 was pretty much just work.

The elephant laboured and brought forth a 2ms. And then a 4ms, its slightly larger twin.
posted by flabdablet at 12:30 PM on December 13, 2018 [1 favorite]

Agreed 100%.
posted by Balna Watya at 9:00 PM on December 13, 2018

I don't think it's spoilery to say that it took me a long while to realize that not only is >-< a collision, but so is ><.
posted by Upton O'Good at 10:36 PM on December 13, 2018

Still looking for a less bogus approach to part 2 of Day 14, though first I'll try rewriting the inner loop in assembler; gcc makes a complete pig's breakfast of it.
posted by flabdablet at 12:25 AM on December 14, 2018

So it seems I owe gcc an apology. After spending quite a lot of time fiddling about with the C source to make it generate assembler that I thought was smaller and/or doing less work, it turns out that every single thing I tried actually made the code run slower. Some of those things actually looked quite close to what I would have written in assembler anyway, so I think I'll not bother. Those elves can just live with their 320ms solution.

It seems that the difficulty of beating machines at efficient code generation has roughly kept pace with the difficulty of beating them at chess, though I have yet to see anything out of gcc that I would describe as actually beautiful.
posted by flabdablet at 4:02 AM on December 14, 2018

not only is >-< a collision, but so is ><

So is >^ if > has to move first.
posted by flabdablet at 4:05 AM on December 14, 2018 [1 favorite]

Ha! That's true, but I am catching that case. It was more that

Spoiler

if you only checked for collisions at the end of every tick loop, it would catch the first case, but not the second (they phase through each other in some magical elven way). Eventually I realized I had to check after every individual cart move.

posted by Upton O'Good at 7:08 AM on December 14, 2018

The way I did my collision detection

makes it pretty hard to avoid doing it per cart. All I do is update the cart's position, then look at the next character it encounters in the playfield - which I would have to do in any case to deal with corners and intersections. Any character other than a piece of straight track compatible with the direction the cart's moving, or a corner or intersection, causes an instant cart crash.

This way, not only can carts crash into each other's <s and >s, but I can get my Gomez Addams on by sprinkling the playfield randomly with explosions and craters. I saw no reason why I should deprive the elves of all the joys of single cart accidents just because the AoC test cases are carefully constructed to avoid them.

The identity of the other cart involved in any two-cart crash doesn't emerge naturally from this, which was a small pain in my arse for part 2, but meh. It was just work.

posted by flabdablet at 7:38 AM on December 14, 2018

MeFi Adventers who haven't commented in a while: how's it going?

Having fun? Learned something new? Running into any issues?
posted by waninggibbon at 3:09 PM on December 14, 2018

Last minute holiday planning and Smash Bros are getting in the way of Daily late night 2h+ coding challenges.
posted by pwnguin at 3:22 PM on December 14, 2018

Day 13 was a total nightmare... part one was fine, all the examples were fine, and the final result was incorrect. I finally ended up reimplementing it using my own implementation of vectors and matrix multiplications to keep sane with directions and coordinates (I did a similar thing last year in Python). Ugh.

I did find an interesting failure mode on the way: detecting collisions and updating positions along the way, iterating through y and x coordinates to see if a cart was there, my carts going down or to the right could "surf" because their position was updated, then the focus moved right (or down), saw them again, and moved them again.

Anyhow, back up to date, now off to de-code my brain!
posted by Wrinkled Stumpskin at 3:46 PM on December 14, 2018

Also, I must have failed to post the comment saying thank you to flabdablet for the great digressions into how to think about really optimising these things. I'll probably never actually code well enough to think about CPU cache misses, but it's wonderful to peek under the bonnet.
posted by Wrinkled Stumpskin at 3:48 PM on December 14, 2018

Day 13 animation
posted by Pyry at 5:22 PM on December 14, 2018

I thought I finally had a good way to do an OO solution for day 13 - read in the tracks and build lots of little objects to connect together each loop - but a couple of details in the puzzle make doing it that way much more painful than making yet another 2 dimensional array, which the language I'm doing it in, Ruby, doesn't handle gracefully.

Day 12's plants puzzle ended up being not too difficult to do in Ruby, but my biggest problem was getting the final score after 50 billion generations, and it turns out I had an off-by-one error I didn't find for ages.

Obviously, doing it in Ruby means that I'm not worrying about efficiency.
posted by Merus at 7:06 PM on December 14, 2018

In general, I'm a little disappointed that many of these puzzles are presented to make it as easy as possible to do it in a way that's comfortable in a C++-style programming language, with fixed arrays and for loops. I've had to work out how to fake doing a for loop in Ruby, instead of using the comfortable each loop that Ruby makes very easy, simply because most of the arbitrary scoring systems these problems use involve 0-based arrays.
posted by Merus at 7:55 PM on December 14, 2018

detecting collisions and updating positions along the way, iterating through y and x coordinates to see if a cart was there

I had ruled out that approach

almost instantly on seeing the size of the input map, opting instead to iterate through a list of carts built from the map as it was first read in. This meant that the list needed to be re-sorted using grid coordinates as sort keys at the end of each tick so that the next tick would still process them in the specified order; without doing that, a -><- crash might happen at an off-by-one location.

For part 2 I was pleased to find that I could leverage the work that the sort was doing anyway, by adding a "crashed" flag to each cart and making the sort's comparator look at that ahead of the row coordinate. This meant that after a sort, all the crashed carts ended up at the end of the cart list, meaning that removing them required only decrementing the list count until the last remaining cart wasn't a crashed one.

posted by flabdablet at 9:37 PM on December 14, 2018

Day 13 animation

Can we get a leaderboard happening that only has Pyry on it?
posted by flabdablet at 9:39 PM on December 14, 2018

OK, so I'm opting out at Day 15. Everything that made Day 13 look like work is there in Day 15 as well, only more so. It's a large, very detailed spec, and the job amounts to nothing more challenging than translating it more or less paragraph by paragraph into code. This isn't solving a puzzle so much as interning at a game design house.

If there's something really interesting on a later day I'll bite the bullet and wrench the Day 13 solution into the shape required for this one in order to get there, but for the time being: good luck, elves, I'm going home for Christmas.
posted by flabdablet at 9:58 PM on December 14, 2018 [2 favorites]

Pathfinding around obstacles might be interesting, but it does sound like a lot for a Friday evening. Tomorrow perhaps.
posted by figurant at 10:07 PM on December 14, 2018

Damn it, figurant, now you've got me inventing data structures again. Once more unto the breach, dear friends, once more...
posted by flabdablet at 11:01 PM on December 14, 2018

You don't have to do every day, I did a later day because it looked fun and interesting and went back to earlier days.
posted by Merus at 3:46 AM on December 15, 2018

That probably counts as a spoiler :-)

I've had to work out how to fake doing a for loop in Ruby, instead of using the comfortable each loop that Ruby makes very easy, simply because most of the arbitrary scoring systems these problems use involve 0-based arrays.

When all you have is a hammer, everything looks like a nail.
When all you have is a set of precision Torx screwdrivers, nails are utter bastards.
posted by flabdablet at 3:51 AM on December 15, 2018

Yeaaaah, I'm skipping today's. Some of the previous days had crossed the line from fun puzzle to actual work, and this looks like the same thing but more so.
posted by JDHarper at 8:59 AM on December 15, 2018

The top two posts of the reddit solutions megathread for today are essentially "I've been debugging this for hours and can't figure out where I messed up." The fastest coder on the leaderboard solved in 35 minutes, compared to 6 minutes yesterday. The 60-100th place zone averages more than 2 hours, and that's for coders who are muuuch better than me.
posted by JDHarper at 9:05 AM on December 15, 2018

Yeah I stopped doing them at midnight when I reached the minecart one and just sat there sighing at how tedious that was going to be. I might do this one eventually (perhaps in my quarter-finished RISC-V assembly programming roguelike?) just because it might look interesting at least.
posted by Pyry at 9:29 AM on December 15, 2018

I ground this one out on account of me being a stubborn fucker. It is pretty much as much work as you expect.

There is actually some algorithmic interestness buried in the spec: how do you find the set of points reachable from a point, given a set of irregular obstacles? How do you find the set of shortest paths between two points, also given a set of irregular obstacles? There is also a lot of grungy bookkeeping. I recommend testing your code on every example provided; I had one bug that didn't show up until the last test case, which stresses your pathing implementation more than the others.

Once you have part I working, part II is fairly straightforward if

Spoiler

you didn't hardcode magic numbers everywhere for your attack power. Like the fuel cell one, it wants you to run the part I concept with different parameters.

I gave up on being fast about it and let it run while I wrapped Christmas presents.
posted by Upton O'Good at 11:07 AM on December 15, 2018

I'm not a programmer by trade, but a chunk of my day does involve programming. If there was more prep I would have tried to take a stab at the advent in a new language but I'm kind of glad I stuck with C and Python. Since I'm on the West coast, I can crack the puzzle open at 9pm and let it fester for a little bit and then maybe take a stab at it that night or maybe the next morning or over lunch.

While I do like the shorter puzzley days I think I prefer the 2+ hour head scratchers. I know I'm never going to catch the leaders when the leaderboard time is 6 minutes but if I had started exactly on time I would have made the top 100 (barely). Then again, I got to take in a movie with my wife and friends, have a drink, mosey home and cuddle with the dogs and cat and then think, "Hey, maybe let's do an advent tonight."

So, yeah, it's a little like work (but I do love pathfinding algorithms, even it today's is kind of brain dead BFS) I'm not racing to be number one and having a good time of it. Also, my pure Python solution of day 15 part 2 is about 1.65s on my laptop. :)
posted by flyingfox at 11:54 AM on December 15, 2018

6ms to get a plausible but wrong result. So I'm essentially quite pleased with the algorithm and data structures, but I need to work out exactly when it breaks which rule. Won't publish until it's generating correct answers.
posted by flabdablet at 4:47 PM on December 15, 2018

I have shortest distance pathfinding working, but not read-order-preferential pathfinding and I'm guessing that's going to be important. It's hurting my head at the moment. Time for a break.
posted by figurant at 5:38 PM on December 15, 2018

I'm guessing that's going to be important

Yah. My own pathfinder apparently achieved read-order-preferential for all the test cases, as I had expected it do given its design, but it fails to do so in some of the cases presented only as initial -> final summaries so I guess my expectation was ill-founded. Pretty sure I've worked out what I need to do to fix it, just a matter of finding a tidy way to do it.
posted by flabdablet at 4:49 AM on December 16, 2018

I skipped to day 16 and I enjoyed it much more. Although I overthought/misread part 1 and submitted about 3 or 4 very wrong answers.
posted by figurant at 6:21 PM on December 16, 2018

This year definitely has more time consuming puzzles than last year. In 2017 none had a fastest solve time >20 min. We've had two >30 min now.
posted by waninggibbon at 7:09 AM on December 17, 2018

I think many of these puzzles would be cool creative prompts but don't really work as puzzles: "write a bare bones roguelike", "write a discrete fluid simulation", and "write a tiny assembly interpreter" are fun prompts if you get to design them yourself, but are just work if you have to implement somebody else's specification, no matter how cute the elf-related fluff text is.
posted by Pyry at 7:39 AM on December 17, 2018 [1 favorite]

Agreed. But I now have a solution for Day 15 part 1 that gets the right result in 10ms, so it should be in pretty good shape for whatever horrible CPU power explosion is required for part 2.

450 lines of code that initially passed all the supplied test cases but generated an unacceptable result until after going through the spec with a fine tooth comb multiple times and designing test inputs to exercise multiple edge cases? Definitely Work.

I did manage to amuse myself by designing the thing in such a way that instead of reading the input file line by line into a 2D array like any sensible person would do, it just gulps the whole file into a buffer and mutates that in place. And I do quite like my pathfinder.
posted by flabdablet at 3:40 PM on December 17, 2018

In what, in retrospect, should probably not have been a surprise, I did day 17 with a modified

Spoiler

flood fill. Instead of adding all adjacents to a "to check" collection, I only added ones that obeyed water movement. There was some additional checking to handle settling temporary water into permanent water (and rechecking some grid squares afterward). The solution I used is here, and it turned out to serve for both parts I and II.

posted by Upton O'Good at 10:05 PM on December 17, 2018

19ms for Day 15 part 2.
posted by flabdablet at 4:29 AM on December 18, 2018

Playing catchup now. 3ms each for day 16 parts 1 and 2, but then neither is doing scarcely anything. I quite enjoyed the teeny-tiny binary sudoku feel of part 2.
posted by flabdablet at 10:09 AM on December 18, 2018

I did day 17 with a modified spoiler

I had already decided to

spoiler

re-purpose pieces of the elves and goblins code in much the same way

before opening your spoiler, so it didn't spoil anything even through I haven't started on day 17 yet :-)
posted by flabdablet at 10:26 AM on December 18, 2018

I quite enjoyed the teeny-tiny binary sudoku feel of part 2.

Hah, yes that was the best part. It strikes me that either that was really difficult to set up neatly when composing the puzzle inputs or it just falls out as a natural outcome of the opcode types but I'm not about to start trying to prove it.
posted by figurant at 10:35 AM on December 18, 2018

I just liked rediscovering the long-forgotten-though-enjoyed-beforehand fact that you can test whether a twos complement binary integer has only got a single 1 bit anywhere in it by bitwise ANDing it with itself minus 1.
posted by flabdablet at 10:43 AM on December 18, 2018

I think many of these puzzles would be cool creative prompts but don't really work as puzzles: "write a bare bones roguelike", "write a discrete fluid simulation", and "write a tiny assembly interpreter" are fun prompts if you get to design them yourself, but are just work if you have to implement somebody else's specification

I find that the design constraints in the puzzles help focus your attention on the goal. If I were writing a bare bones roguelike, I might get tied up figuring out terminal programming, or writing a map generator, or designing cool monsters, etc. Given a set of test cases and a clear goal, it's easier for me to push through and finish. Granted, you give up some of the creative fun of design, but having a clear finish line and crossing it is fun too.

For day 18, is anyone finishing part 2 "correctly" in a reasonable amount of time? I ended up

spoiler

re-using the day 12 technique of running until you see a pattern and extrapolating from that.

posted by pocams at 2:34 PM on December 18, 2018

My back-of-the-envelope estimate to completely simulate part 2 was 30 hours on my system. I imagine you could speed things up a bit by moving it to the GPU though. I actually might give that a try.
posted by figurant at 2:48 PM on December 18, 2018

I have not yet tackled Day 18, but rather than get in a mad rush to dash off some semi-optimized grid-based cellular automaton evolver and let it rip, I think I will pause and reflect and take this as an opportunity to learn more about

spoiler...

Bill Gosper's Hashlife algorithm. Because I've just been doing some reading on how it represents cellular spacetime, and a whole bunch of half-baked ideas about content-addressable data and non-cellular spacetime and how we personally encounter it that have been swirling around in my head for decades now have just got a tiny bit browner.

Hashlife is one of those things I'd run across a while ago and thought "huh, looks interesting, should check that out" but now I have, and let me tell you, this shit is seriously cool.

Elevator pitch: consider representing any given region of a spacetime as a tree of nodes, where the information recorded in each node consists of multiple links to nodes representing non-overlapping equal-sized sub-regions of the given region's present, plus one link to a node representing a region of that same reduced size in its future.

The links specify node identities. A node's identity, in turn, is constructed according to the present content of the region of spacetime it describes.

The bigger the region any given node represents, the further into its future will be the node its future link identifies. That future node represents the most remote region in the given node's future that is the same size as each of its present sub-regions and whose content can be determined completely from its present content via the spacetime's causal rules; the future region is therefore outside the light-cone of any location that's also outside the present region.

Pointers into the future, man. Let's see Rust deal safely with those.

posted by flabdablet at 7:32 AM on December 19, 2018

Day 19 part 2 was pretty fun to figure out.
posted by figurant at 11:29 AM on December 19, 2018

In the "I hate when that happens" department, my day 19 part 1 runs nicely on the test data but gets "too high" on the real data. What else could I test it on?
posted by Obscure Reference at 11:35 AM on December 19, 2018

I ran into something similar. Are you sure you're interpreting the #ip declaration correctly?
posted by figurant at 11:55 AM on December 19, 2018

I only hit the first one, then it goes into a long loop of some sort until it terminates. It interprets the example one just fine (I duplicate their output).
posted by Obscure Reference at 12:58 PM on December 19, 2018

The sample has the instruction pointer declared to be zero, which is sort of the degenerate case. I initially misinterpreted my input with #ip 3 as "set register zero, the instruction register, to value 3 when starting the program", when it should really mean "the instruction register for the following program is register 3"
posted by figurant at 1:09 PM on December 19, 2018

My code should be able to handle it even if they change register bindings in the middle of running. (though not if that occurs in a loop) I initialize to "unbound" until it reaches a #ip statement (making sure not to count it as an actual instruction) and it has the same register values, ips and instructions as they give for the sample case. My program input seems to set up a loop to be executed until some counter reaches 997 when it exits the loop, but it tells me my register 0 is too large. And all I have is their say so which makes it impossible to debug.
posted by Obscure Reference at 1:24 PM on December 19, 2018

You don't have more than one #ip X declaration in your input file, do you? I'm pretty sure it's not meant to be an instruction in the program, just a fixed setting for how your "machine" works. The program instructions on the following lines should be indexed starting at 0 and executed in the order that the instruction register indicates as you increment it and the program modifies it.
posted by figurant at 1:38 PM on December 19, 2018

I only have the one at the start but I could handle it were it so.
posted by Obscure Reference at 1:49 PM on December 19, 2018

I initially misinterpreted my input with #ip 3 as "set register zero, the instruction register, to value 3 when starting the program", when it should really mean "the instruction register for the following program is register 3"

Clearly not an 1802 coder.

Meanwhile back in the land of lag, I've just finished a bash script that emitted correct answers for both parts of Day 18.
posted by flabdablet at 2:22 PM on December 19, 2018

I used AWK for one of these.
posted by Obscure Reference at 2:30 PM on December 19, 2018

I didn't like day 19 part 2 at all.

spoiler

I can see how the solution relates to the way you'd optimize the problem in real life, but it kind of feels like not-what-I-signed-up-for.

figurant, I'm glad you liked it - that makes me feel less grouchy about it in general and more like it's just not my thing.
posted by pocams at 4:59 PM on December 19, 2018

I may have taken a more pleasant approach.

spoiler

I gave up quickly on tracing my input program and just looked at the contents of registers at various breakpoints. Once you spot the patterns that end up in register 0, it's fairly straightforward to get to your own solution.

posted by figurant at 5:12 PM on December 19, 2018

Day 19: I got bored while waiting some of the five and a half minutes it eventually took 1.bash to churn out part 1's result for me, and used the time to perform a

spoiler.

static analysis that allowed me to complete part 2 by hand.

posted by flabdablet at 8:24 PM on December 19, 2018

I've been having loads of fun since discovering Golly in the course of researching ways to go about tackling Day 18, and have just employed it to backfill Day 17 as well.
posted by flabdablet at 7:18 AM on December 21, 2018 [1 favorite]

Day 20 clearly called for recursion so I refused to use any.
posted by flabdablet at 10:59 AM on December 21, 2018 [1 favorite]

Day 21 done. All caught up at last.
posted by flabdablet at 2:20 PM on December 21, 2018

The wording of day 21 pt. 2 had me scratching my head for a while.

I finally churned through day 15. The only optimizations I can see are maybe caching the paths between map squares, but since the state of the map changes constantly you'd have to keep invalidating the caches and rebuilding them, and I'm not sure how much overall improvement there would be.
posted by figurant at 4:32 PM on December 21, 2018

My Day 15 pathfinder runs in O(p²) time, where p is the length of the path to the closest target square, on a completely open map; less on a map with obstacles. It does very little work inside the inner loops. It needs to be run once per movement decision, regardless of how many available target squares exist.

It's really simple-minded, but on maps this small it works very well. My urge to scratch the optimization itch tends to stop when time to solution drops below about 30ms, and my Day 15 code achieves 10ms for part 1 and 20ms for part 2. It's good enough.
posted by flabdablet at 1:13 AM on December 22, 2018

That's annoying. My solution for the sample on day 22 pt. 2 gets the number of steps correct but takes a different path, and I'm trying to figure out if there's more than one valid path in the same number of steps or if my solver is subtly broken. The fact that my answer to the actual puzzle is wrong suggests the latter.

Also, I figured this was going to be another "massively increase the size of the solution space in pt. 2 to force you to find the shortcut" problem and spent a lot of time thinking about how to cram a very large pre-calculated set of computations into memory, or at least some kind of fast storage. That didn't pay off.
posted by figurant at 8:12 PM on December 22, 2018

Well, if you're feeling bad about not having a part 2 that requires a massive solution space in the absence of a shortcut, Day 23 should make you feel better...
posted by Upton O'Good at 11:15 PM on December 22, 2018 [2 favorites]

I'm trying to figure out if there's more than one valid path in the same number of steps or if my solver is subtly broken. The fact that my answer to the actual puzzle is wrong suggests the latter.

Currently in much the same boat. Though what it's worth, the explanatory text does explicitly state that the 45 minute time for the sample is "tied with other routes".
posted by flabdablet at 3:54 AM on December 23, 2018

Still stuck on day 22.

I'm using a tweaked flood-fill to do the search, and as initially implemented it returned a time of 46 for the sample caves instead of the stated 45.

Noticing that if the target was in fact on the very first search region at 0,0 my code would return 1, I decided that this was just a simple off-by-one on the time accumulator and altered its initial value from 0 to -1. So now I had code that returned a reasonable result for the degenerate search, and agreed with the stated result for the sample.

Ran it against the given puzzle input and it generated an unacceptable answer. Fixed bugs, did it again, still unacceptable. Got to the point where I absolutely could not see anything wrong with it any more; still unacceptable.

Eventually I went to the reddit solutions megathread, downloaded the first solution published there and saved it as cheat.py. Runing cheat.py against my puzzle input produced a result that AoC accepted as correct. And it was 1 greater than the solution my own code had generated.

So now I have cheat.py that generates correct results for the degenerate case (target at 0,0) and for the sample case (depth 510, target 10,10) and for my puzzle input (depth 5913, target 8,701); and my own code, which agrees with cheat.py on the degenerate and sample cases but claims to have found a better-by-1 solution to the puzzle input case (972, where cheat.py and AoC both agree that the answer should be 973).

This is really annoying. It will be super duper extra annoying if my better-by-1 solution actually turns out to exist.
posted by flabdablet at 10:51 AM on December 23, 2018

I think 23 pt. 2 will have to be my stopping place for now. I have a working code that does things in (I thought) an efficient manner with a

Spoiler

branch-and-bound algorithm, with best-first search in a priority queue, splitting the whole region into 8 subregions (2 divisions per axis) at each branch step and bounding coarsely the number in range by checking for intersections with a region and a [x+/-range,y+/-range, z+/-range] box. I don't have an idea for a finer-grained bound that still can be guaranteed to be an upper bound.

This is the best I've come up with that doesn't take until the heat death of the universe, and still it's far too slow--doesn't complete when run for hours. I must be missing an additional clever trick, but it's not coming to me. Doesn't look like I'll be able to do better before holiday travel starts.
posted by Upton O'Good at 8:34 PM on December 23, 2018

Part 23b nearly stopped me. I tried four different approaches and finally got it to work but I"m still not sure it's a general solution or just worked for my input set. It was right up there with 17 that had so, so many edge cases. For what it's worth, if you push through it 24 is a lot of fun.

Also, it helps to have an incredibly supportive wife who is okay with me sitting up late on the holidays muttering about elves and Santa.
posted by flyingfox at 12:06 PM on December 25, 2018

Finally finished after having to take a break around Christmas. My solutions in all their gory detail are here.

Thanks for posting this, waninggibbon. It was a lot of fun!
posted by figurant at 5:02 PM on December 29, 2018 [1 favorite]