Advent of Code

[davelodwig]

I spend all day writing code and solving problems.

As much as I try to do AoC I just can't get the energy up to do it in the evenings after work.

[Greenbank]

I do it in the morning before work usually. My daughter leaves for school around 7.15 and so I've got ~2 hours before I start work. Usually I'd either go for a swim/bike/run in this time, or just start work early and then have a longer lunch or knock off early, but in December it's generally AoC time.

For the trickier days doing AoC may bleed over into lunchtime or the evening, but I find that subconscious thought (while I'm doing my day job) helps get me to the solution without taking too much time sat actively staring at it. Reading elsewhere (the AoC subreddit mostly) it seems I'm lucky that I'm able to put an AoC problem down once I need to focus on something else (e.g. what I get paid for) and it doesn't bother me to do so.

The weekends (or holidays) I just have to find the time whenever outside family life.

Going back and redoing all of the previous years in Go is becoming a bit of a slog, especially now that I've picked off most of the easy ones from each year, but the plan is to tackle 1-3 days at a time in the new year and I'll get through them all in a few months. Already having a solution (albeit in C/perl/?) helps. Also going back and looking at my old code is a useful exercise to see how long it takes me to understand it and whether there are any useful comments/etc.

[Greenbank]

Spoiler day 20

(click to show/hide)

Got lucky and did part 2 within about 10 minutes of finishing part 1.

Another spoiler just in case you didn't want to see the magic of Day 20 part 2.

(click to show/hide)

Hacked my code from part 1 to stop when it met the condition for part 2, saw it just kept running so knew something was up and killed it.
Looked at what fed into the `rt` module, saw it was a single conjunction module.
Looked at what fed into that module, saw there were just 4 inputs to this conjunction module.
Knowing that all 4 of the inputs had to be high at the same time for this node to output a high I adapted my part2 break code from above to output the button count when each of those 4 inputs sent a high pulse.
Got 4 numbers somewhere around 4000. Also saw they were repeating on exact multiples of those numbers, so knew CRT wasn't going to be required.
Ran `factor` on the command line and saw they were all prime, so no need to do LCM. Even better.
Multiplied them together and submitted them as my answer and, lo and behold, it was correct.

Only then did I go digging as to why, and worked out what was going on and why the above worked.

[Greenbank]

Spoiler Day 21 part 2

(click to show/hide)

Another unsatisfactory one (IMHO). Again I got lucky with my guesses.

Real spoiler below.

(click to show/hide)

The way the numbers looked (both in terms of answer from just 64 steps and the required number after 26501365 steps) told me it was impossible to bother trying to brute force so I switched into pattern spotting mode.

AoC Spidey sense tingled at:
* Map was an odd size (literally) - usually they have even lengths
* No rocks in same row or column as Start
* No rocks in diagonals between centres of each edge, so no rocks in the area with a Manhattan distance of ~65 from the start
* And the start was exactly centred in the map at 65,65.
* 65
* Answer required at 26501365 steps.
* 26501365 mod 131 = 65 (I'm guessing he picked that number on purpose so that the trailing 65 was more obvious)
* Guessing we can compute a few terms and extrapolate
* Adjust code to handle an infinite grid but keep track of real points
* Compute answer for 65, 65+131, 65+131+131 steps
* Check 1st order differences between the 3 answers, not equal, so assume it's quadratic and compute 2nd order difference (heh, back at Day 9 and Lagrange Interpolation)
* Calculate answer using 1st order and 2nd order differences
* ???
* Profit (with a second star)

[EDIT] Reworked part1 to be a single BFS to 65+131+131 steps and counting newly visited grid squares on odd and even step numbers separately. (A cell visited on an even step cannot be visited on any odd numbered step and vice versa.) Part 1 runs in 3.4ms and then Part 2 is done in 66.8ms (cumulative).

[Greenbank]

2023 Day 21 Part 2 mild spoiler from the AoC Creator

(click to show/hide)

I said:

26501365 mod 131 = 65 (I'm guessing he picked that number on purpose so that the trailing 65 was more obvious)

Not only that, it was an even better coincidence:-

Source: https://www.reddit.com/r/adventofcode/comments/18nx8de/comment/kedjwqd/?utm_source=reddit&utm_medium=web2x&context=3

topaz2078 1 hr. ago (AoC creator)

From my Perl code:

Code: [Select]

my $goal_dist = 65 + 131*202300;
Very good find!

[vorsprung]

a mixture of shell, C and predominantly perl. Now most of my professional coding is in Go

Same here

[vorsprung]

Wot Greenbank sed.

For me, over the years I've used AoC to improve my skills in Java, Elm, JavaScript and C++ as well as general data structures and algorithm competence. I also use it with students (from first year undergraduates to PhDs) to help them develop their algorithmic thinking, reasoning and communication. I didn't do a Comp Sci or Maths degree so AoC has been useful learning tool for me (and mostly fun).

I don't have any students.  At the moment I am only mentoring one person, maybe I should teach them how to program properly.  Hmmm

[jwo]

Day 23

A little easier than the last few days, but struggled to get computing Part 2 to anything faster than around 10 seconds.

(click to show/hide)

Beyond the obvious contraction of the graph representation to store only junctions (with edge weights as he steps between them), not sure what further optimisations are possible as generally longest path calculations on a graph are NP hard..

[Greenbank]

Got there in the end as I was busy/pissed most of 24th/25th/26th.

Have to redo/optimise days 22, 23, 24, 25. Plus revisit a few days (12, 14, 16, 17, 20) that are taking a bit more than they should but it can go on the backlog for now until my brain is ready for them.

[Pickled Onion]

Had a bit of a break, so only on day 19.

Bah. And Grr.

Spent ages working out what would happen if the ranges on different paths overlapped, and what if a path had a disjoint range, then a bit of time coding up the range flattening... Only to find that it had been crafted so that no ranges overlapped and the simple sum of combinations for each route gave the answer.

My final code cut simply down to

(click to show/hide)

    public long Part2()
    {
        return Workflows.Values.SelectMany(RangesFor).Sum(x => x.Combinations);
    }

Where RangesFor(workflow) worked back from every 'A' to 'in'

[Pickled Onion]

a mixture of shell, C and predominantly perl. Now most of my professional coding is in Go

Same here

I'd done* many of the previous years in Perl. A lot of the problems seemed to be geared towards languages like Perl and Python. One year I tried to solve them in regular expressions, which worked for the first several days at least.

I've learnt a huge amount by solving them in C# LINQ this year. I'll be giving a talk on LINQ Best Practice in a couple of weeks to the internal C# group, 100+ developers. It's become apparent that 90% of them are "doing it wrong", and most of the other 10% are simply following received wisdom (including me up to now). There's a paucity of good guidance or documentation on what is one of the sharpest tools in the C# box. In fact it's a lot like Perl in that it's easy to write something that works, but you need a deeper understanding to write something that Works Well and is clear/maintainable.


* not finished though