# Normal view

Before yesterdayNews from the Ada programming language world

26 December 2023 at 02:31

Finally

Day 25 strikes me as much harder than most Day 25’s, and I ain’t the only one. I mean, come on, 2020 was the year where you basically played a tribute to Zork. (Or maybe it was 2019, and 2020 was the relatively easy discrete log puzzle.)

But today’s puzzle? Part 1 alone should count as a two- or even three-part problem. I won’t even bother covering up the “spoilers”, as I bet revealing them won’t spoil much at all.

The moment I read the problem, I knew it was a graph theory problem. I don’t know much graph theory – I’m not that kind of mathematician; I did real math with nonlinear polynomials and stuff; see my solution to Day 24 or whatever – so I immediately went to look up stuff on graph connectivity, which I’d heard and read something. That led me to “min cuts”, a new idea to me, then to Karger’s algorithm, and that looked both appealing and tractable, so I said, “aha! let me implement this!”

Three hours and a boatload of annoyance later, I was still struggling to implement Karger’s algorithm. I think I was close, and I may yet get it working, but at this point it was time to spend time with my family, so I did.

When I came to look at it, a stroke of divine inspiration hit – ok, maybe not divine, but it is Christmas so what do I know – and I had the idea to generate a bunch of random paths through the graph and count the edges used. It stood to reason that the edges used most were the load-bearing ones that guaranteed connectivity.

A couple of hours and some deep frustration later, I was still struggling to get that working, inasmuch as my top 3 hits consistently disagreed with the example’s 3 edges to remove. I finally surrendered to the temptation to peruse Reddit. Per Reddit, or at least the Reddit solutions I could be bothered to read, most people employ one of two approaches.

1. Karger’s algorithm to find the min cut of graph.
2. A Monte Carlo method that picks two random points a fair number of times, on each turn finds a shortest path (shortest seems to be important, which prompted me to switch from using DFS to BFS – the one time I start with DFS it turns out to be counterproductive!), and keeps a running tally of which edges are used most often. The 3 edges that show up most are, with extremely high probability, the edges you want.

Notice anything familiar? Me, too. I asked myself whether I should feel elated or depressed that most other people were taking one of these two approaches, too – elated that, hey, that’s what the experts were doing; depressed that, yeah, I can’t seem to cut it.

I downloadeded Conscious-Money-7663’s Python solution to use as a sanity check against my code. Its top 3 hits agree with the example’s counsel, so I guess something’s wrong with my code.

After an hour or two of fruitless searching for a bug, I said “What the heck” and tried my code on the input.

It worked.

It ain’t pretty, but I’ll take the ! From there it was spectacularly easy to finish the puzzle (very easy, same as every Day 25 I’ve done, which now covers 2018…2023).

At some point I’ll go back & try to figure out (a) why my Karger’s Algorithm doesn’t work, and (b) why my Monte Carlo method doesn’t work on the example. But for now I can go and now, hope my wife doesn’t divorce me, my parents don’t disown me, and my kids haven’t uploaded too many videos complaining that I was spending Christmas trying to solve a stupid puzzle instead of… well, there wasn’t anything else to do, as far as I know, or I’d have done it. But I still got an evil or two today.

Merry Christmas, even if belated.

5 posts - 2 participants

• 26 December 2023 at 02:31

# 2023 Day 24: Don't Tell Me The Odds

25 December 2023 at 04:01

On Day 18 I wrote:

I don’t suppose he’ll ever supply a puzzle that relies on my old research topics…

Careful what you wish for!

If you’re as stuck on Part 2 as most people were (took roughly an hour for the first 100 people to solve it), take consolation in the fact that quite a few people posting solutions expressed their unhappiness with the puzzle. The most common technique was to reformulate the problem in a way that they then plug it into the Z3 theorem prover.

A few others took a more mathematical approach, sometimes making assumptions on the input. I’m a bit sick, so had trouble either following the explanations, or even looking at their code and making sense of it. I did translate one Python solution to Ada, and thought I’d call it a day after it gave me the right answer.

Unfortunately – or, depending on one’s point of view, fortunately – the discussion had given me another idea, based on the research I conducted in a previous life. The fancy name is “Groebner basis”, but essentially you’re looking at slightly non-linear polynomials. The trick is to make them linear, seeing everything as a nail, I used Groebner bases, but at least one person at Reddit used a different approach.

The only assumption this approach needs is that you can find at least three hailstones that intersect in the x, y plane. Part 1 has you count how often that happens, so that’s a good sign. Call them `h_1`, `h_2`, `h_3`. You’re looking for a position (`x`,`y`,`z`) and velocities `dx`, `dy`, `dz` along with times `t_1`, `t_2`, `t_3` such that for each `i`

…and similarly for `y` and `z`. Rewrite them with everything on one side and you have nine equations in nine variables. Unfortunately, `t_i` and `dx` etc. are unknown, which makes the products `t_i dx` etc. nonlinear (a couple of Reddit commenters’ claims notwithstanding).

So a matrix won’t work… yet. To fix that, take 6 pairs of equations and multiply strategically in order to cancel the non-linear terms; this is an active research field in the general case, but here’s an example of how it works in this case:

let:

…and `r_i` is now linear in the variables `x`, `y`, `dx`, and `dy`. Similar work gives you linear equations for `x`, `z`, `dx`, `dz` and for `y`, `z`, `dy`, `dz`.

You need two of each of the three sets of variables: that gives you 6 linear equations in 6 variables, which is “easily” solved using a two-dimensional array in Ada. I write “easily” in scare quotes because I did have to swap rows at least once.

I’m reasonably sure that’s not what the puzzle master intended; I suspect it’s closer to the Python solution I translated. Oh, look: spoiler

PS: oh, this is also ironic. usually the 3-d puzzles inspire in me.

5 posts - 3 participants

• 25 December 2023 at 04:01

# 2023 Day 23: A Long Walk

24 December 2023 at 04:06

Took me a while to get around to this one, because Day 21 set me back one day. Day 22 was straightforward (more or less) and while I got Day 23, it took a good long while.

Part 1 is straightforward, I think.

For Part 2, spoiler That gives me the right answer, but it still takes too long (several minutes! with several million paths queued up!), so I went to look at Reddit commentary and there everyone is basically doing what I’m doing, but using spoiler instead.

I really have to brush up on the advantages of each, since I don’t quite understand why that approach takes them milliseconds, whereas my approach takes minutes.

So, spoiler in the worst-case scenario is because that’s the worst-case size of the frontier.

So, the worst-case space complexity of spoiler is .

Added in much later: I take that back. spoiler

4 posts - 2 participants

• 24 December 2023 at 04:06

# 2023 Day 21: Step Counter

22 December 2023 at 04:06

I’ve only finished Part 1 so far, but here are some thoughts on Part 2. While it’s not implemented yet, it should be the right track: when testing it by hand on a much smaller example, I come too close to the brute-force answer to make me think the mistakes are anything other than due to hand computation / numbers-slightly-off / etc.

Sorry if this seems far too long, too detailed, or too annoying with blurred spoilers-which-perhaps-aren’t, but if anyone sees an invalid assumption, I would be grateful!

• Once the elf visits a plot, he cannot visit it again except on multiples of 2, on account of the limited number of directions available. That is, if he first visits the plot in row 5, column 12 on step 7, then he will only visit that plot on odd-numbered steps.
• In my input, and I suspect in all inputs, the number of steps is 65 + x * 131, where x is a Very Large Number , 131 is the dimension of the square, and 65 is the number of steps it takes to get from the starting point, which is in the middle, to the end of the square.
• Unlike the example – and this is a big deal!spoiler
• As the elf explores, you get spoiler
• You can thus consider separately squares spoiler
• Rspoiler the number of squares visited in the cardinal directions, but they’re not all full: spoiler We’ll return to this speed bump in a moment.
• In each column not in a cardinal direction (e.g., the column with squares `G`, `E`, and `C`; or, the column with just `G` and `E`), spoiler
• So it’s relatively easy to count the number of full squares, spoiler That product gives the number of plots the elf can visit in all the full squares. spoiler
• Likewise, it should be relatively easy to brute-force count the number of plots the elf visits in squares that aren’t full, because you know the shortest number of steps it takes to arrive there, and you can explore from that entrace position. Again, the fact that movement is limited to the cardinal directions helps you here: in a box to the northwest of A, for instance, the earliest entrance is in a southeast corner, so explore from there for the number of steps remaining.
• Add the values in these last two steps and you should have the answer.

I suspect the reason my hand computation is wrong is that I’m slightly off on the next-to-last step. I’ll look at it more later…

5 posts - 2 participants

• 22 December 2023 at 04:06

# 2023 Day 20: Pulse Propagation

20 December 2023 at 17:46

I usually look at the general leaderboard for each problem to get an impression of how difficult the “experts” find it. It surprises me that the general leaderboard for day 20 suggests that this has been the hardest problem so far: nearly 49 minutes for the first 100 participants to complete it! The only one that came close to this relative difficulty was day 10, with 36 minutes before the first 100 participants completed it.

Day 20 didn’t seem that complicated to me. So long as you read the problem carefully, and I do mean carefully, part 1 is possibly the most straightforward problem yet. The only thing that makes part 2 challenging is that the answer is a “ludicrous size” number, so you don’t want to wait around for it. But the technique to make it work has already been used with other problems: spoiler

1 post - 1 participant

• 20 December 2023 at 17:46

# 2023 Day 19: Aplenty

19 December 2023 at 20:31

Today’s puzzle is cute:

``````To start, each part is rated in each of four categories:

* `x`: E*x*tremely cool looking
* `m`: *M*usical (it makes a noise when you hit it)
* `a`: *A*erodynamic
* `s`: *S*hiny
``````

Kind of embarrassed how I didn’t notice what the categories “spelled out” at first.

I solved it in a manner similar to Day 5: spoiler

Using the original example:

• Start at `in` with intervals (1,4000),(1,4000),(1,4000),(1,4000).
• The rule `s < 1351` applies, so spoiler

…and so forth. When a group visits `A`, add the group’s number of intervals to the running total; when a group visits `R`, spoiler.

6 posts - 3 participants

• 19 December 2023 at 20:31

# 2023 Day 18: Lavaduct Lagoon

19 December 2023 at 07:44

Part 1 was pretty straightforward.

After several hours of looking at Part 2, it looks as if I had two really good ideas, but gave up on them too early. (Short on time lately.)

My favorite idea was to (spoiler). But when I applied it to the example, I realized, to my horror, that it depended on an unspoken assumption: spoiler. After starting at it a while and watching an hour or so go by, I despaired and gave up. I still like the idea (and apparently someone else did do it this way!), so I hope to return to it eventually.

Then I thought about trying a spoiler I still like that idea, but just as I was on the verge of implementing it I got cold feet. (From what I read, at least one person did something to this effect, too.)

As the hour drew very, very late, I visited the Reddit page and learned that most people seem to be solving it using spoiler… neither of which I’ve ever heard of. (I’d be embarrassed, since I have a PhD in mathematics, but someone else commented that he has a PhD in computational geometry, and he hadn’t heard of it either, so there.) But even that isn’t trivial; you can’t just copy & paste the formulas from Wikipedia. And since the same approach was useful on Day 10, these formulas may prove useful a third time.

I don’t suppose he’ll ever supply a puzzle that relies on my old research topics…

LOL, one person on the Reddit page says, “Finally, a relaxing day again…” That’s what I thought of the entire previous week between days 10 and 17…

4 posts - 2 participants

• 19 December 2023 at 07:44

# 2023 Day 17: Clumsy Crucible

18 December 2023 at 07:08

I should have finished this much earlier, but my spoiler Nothing was helping me figure that out, not even comparing to known solutions! Then I noticed that there was a large gap between my previously-considered level of heat loss (1043 or so) and the reported result (1060) and the proverbial went off.

I might add more later, but for now, here’s a quick 'n dirty visualization of parts 1 and 2. Brighter shades indicate more heat loss. I’d be curious to know if other participants likewise see a “bulge” in their data, or if there’s a different pattern.

2 posts - 2 participants

• 18 December 2023 at 07:08

# 2023 Day 16: The Floor Will Be Lava

16 December 2023 at 14:48

First: this is pretty cool. I don’t remember the animations starting before the end of the competition.

Today’s puzzle would have wrecked me when I first started doing AoC puzzles, back in 2020. I must be learning something, as I managed it in relatively short time (less than two hours, all told), without having to run my code on the example.

I used the following tools, and I’m pretty sure that each, or some variant of each, is necessary.

• A beam can end up in an infinite loop. (I haven’t verified this, but I’m pretty sure it’s true.)
• To prevent this, we need a way to verify the beam isn’t repeating previous steps; i.e., a beam tracker. But it’s not enough to spoiler, then it should keep moving.
• When you get to Part 2, don’t forget to spoiler
• Splitting leads to new beams; my maximum number of beams was 65. Since we are spoiler

I’ll see if I can come up with a visualization of Part 2’s solution later. I did create a visualization for Day 14, but it wasn’t very helpful, and the forum rejected it as being too large an image, so I shrugged it off.

5 posts - 3 participants

• 16 December 2023 at 14:48

# 2023 Day 14: Parabolic Reflector Dish

14 December 2023 at 14:32

Fake spoiler: it didn’t require the use of the quadratic formula.

Not too difficult; I had more trouble with part 1 than with part 2. For part 2, spoiler

3 posts - 2 participants

• 14 December 2023 at 14:32

# 2023 Day 13: Point of Incidence

14 December 2023 at 05:56

Correct loop termination bedeviled me. A spoiler which isn’t really a spoiler is that I’m pretty sure parts 1 and 2 can call the same subprograms, but testing for different things. I didn’t implement it that way, though.

3 posts - 2 participants

• 14 December 2023 at 05:56

# 2023 Day 12: Hot Springs

13 December 2023 at 04:55

just kidding. but this one took me a long time. We seem to have entered the fiendishly difficult phase. Fortunately, difficult problems are usually followed by not-so-difficult ones. Usually.

• I first completed part 1 using a recursive algorithm that pruned failing branches. No problem, though it was a bit slow, so I knew what was coming next.
• Yup, Part 2 inflates the input to an insane size. The first record completed quickly, to my surprise but I quit the program after it dawdled on the second record for several minutes.
• I stared at it a while.
• Finally, I visited the Reddit solutions page. People were mentioning spoiler. What the heck is spoiler, thinks I, feeling a little humiliated at not knowing. Scrolling down a little, I see that someone else has the wherewithal to ask. It means spoiler. Oh yeah, says I, albeit a little more colorfully. (i.e., ) I remember something about that from my Algorithms class. But… how?
• Reading a bit more, I see what people say they are doing. Unfortunately, they are writing in languages like C++, D, Python, Rust. Excerpts range from illegible to incomprehensible out of their context. Probably doesn’t help that’s it’s 2am. Oooookayyyyy… time for a nap.

Thinking about it this evening, I realized that I could do the following.

1. For each line, iterate over the contiguous groups from left to right. So, start with the leftmost.
2. Assume the group records n damaged springs,
• Determine spoiler.
• For each i in 0 … spoiler A picture is probably worth 1000 words here: if n is 3, and spoiler, look at spoiler It is easy to tell whether this matches `.#?#?`.***
• If it matches, take the next contiguous group and recurse (step 2) with an appropriate starting index for the next string. (Have I mentioned how I Ada’s custom indexing?.)
• This is a key point. If you don’t want to wait forever, spoiler

A couple of additional complications I encountered:

• The result in part 2 is larger than `Natural'Last` on my input, so you’ll likely need something larger.
• If you use a hashed map for the spoiler, be prepared for some `mod`ing. I do wonder if I’d have done better with an ordered map.

There was more, but I can’t remember it now.

***I don’t recall reading this detail anywhere in the Reddit discussion of solutions, but then again, I don’t think so well at 2am. Either way, I’m pleased as punch that it seemed different.

3 posts - 2 participants

• 13 December 2023 at 04:55

# 2023 Day 11: Cosmic Expansion

11 December 2023 at 12:57

What a relief after yesterday’s puzzle!

• Kind of amusing how the puzzle master attempted to disguise spoiler. I recently completed the 2018 puzzles, and he made no attempt to disguise that.
• It amuses me that I guessed Part 2’s task while completing Part 1, so I went ahead and solved Part 1 with an approach that made it easy to complete Part 2 in about 5 minutes. The puzzle master’s love of throwing huge numbers into puzzles, which blocks a lot of obvious approaches, really helped foresee where this was going.
• That 5 minutes for Part 2 includes the minute I spent figuring out why my initial answer was wrong… spoiler

1 post - 1 participant

• 11 December 2023 at 12:57

# 2023 Day 10: Pipe Maze

10 December 2023 at 17:20

4 posts - 3 participants

• 10 December 2023 at 17:20

# 2023 Day 8: Haunted Wasteland

8 December 2023 at 12:05

Relatively straightforward. I suspected, correctly, that spoiler. Unfortunately, I incremented my step counter at the wrong time, so that I didn’t see spoiler.

4 posts - 2 participants

• 8 December 2023 at 12:05

# 2023 Day 7: Camel Cards

8 December 2023 at 01:54

I relied on enumerations. In both parts spoiler For part 2, I used spoiler
That, and a rewrite of the ordering in part 1, did the trick.

2 posts - 2 participants

• 8 December 2023 at 01:54

# 2023 Day 6: Wait For It

6 December 2023 at 22:39

Didn’t see a thread for this yet, so figured I would start one. I’ve only worked on part 1. I did like that I could come up with various methods of doing this right off the bat. I decided on spoiler.

5 posts - 3 participants

• 6 December 2023 at 22:39

# Day 5: If You Give A Seed A Fertilizer

5 December 2023 at 16:39

@JeremyGrosser hasn’t posted on today’s puzzle yet; I hope he won’t mind if I do.

There’s always at least one puzzle with ginormous numbers, though I don’t recall their appearance in as early as Day 5!

The first speed bump I encountered is that gnat defaults (?) to 32-bit integers for `Natural`, so my machine choked, though nearly 12 hours later I can’t remember whether it choked on the input proper or during the tracing. Very well, then: spoiler

Is 32-bits a fixed standard for Ada’s `Natural`? Since 64-bit numbers are not uncommon in these puzzles (at least 2 or 3 puzzles will go there), should I by default define a numeric type and use that? (Isn’t that arguably the Ada way anyway? I’ve always wished the puzzle master would be more specific about the data we might encounter in these puzzles.)

The second speed bump is that solving Part 2 the natural, “brute-force” way takes the computer while, and I mean a while. It is doable! It took my machine “only” about 15 minutes. (I’ve paid for those gigahertz; might as well use them, right?)

So, while I was able to solve Part 2 via brute force – not usually possible when we start to see 6-digit numbers, let alone 9-digit ones! – I decided to spoiler.

My solution is here. I’d be interested to know if anyone took a different approach.

17 posts - 5 participants

• 5 December 2023 at 16:39

# 2023 Day 4: Scratchcards

4 December 2023 at 05:53

I got stuck on silly parsing bugs in part 1 and am too tired for part 2 tonight. Looks like it’s gonna be spoiler

9 posts - 5 participants