❌ About FreshRSS

Reading view

There are new articles available, click to refresh the page.

2023 Day 25: Snowverload

Finally

:snowflake: :snowflake: :snowflake:

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 :wink: 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!”

:stopwatch: :hourglass: :rage:

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.

:hourglass: :stopwatch: :face_with_symbols_over_mouth:

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.

:hourglass_flowing_sand: :hourglass: :sob:

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.

:star2: :star_struck:

It ain’t pretty, but I’ll take the :star2:! 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 :pray: and :sleeping_bed: 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 :eye: or two today.

Merry Christmas, even if belated.

5 posts - 2 participants

Read full topic

2023 Day 24: Don't Tell Me The Odds

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 :fearful: in me.

5 posts - 3 participants

Read full topic

2023 Day 23: A Long Walk

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.

Added in later: Found my answer spoiler

So, spoiler in the worst-case scenario is oldsymbol{O(b^d)} because that’s the worst-case size of the frontier.

So, the worst-case space complexity of spoiler is oldsymbol{O(bd)}.

Added in much later: I take that back. spoiler

4 posts - 2 participants

Read full topic

2023 Day 21: Step Counter

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 :tm:, 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

Read full topic

2023 Day 20: Pulse Propagation

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

Read full topic

2023 Day 19: Aplenty

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

Read full topic

2023 Day 18: Lavaduct Lagoon

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

Read full topic

2023 Day 17: Clumsy Crucible

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 :bulb: 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.

visualization_1

visualization_2

2 posts - 2 participants

Read full topic

2023 Day 16: The Floor Will Be Lava

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

AoC2023_day15

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

Read full topic

2023 Day 12: Hot Springs

:scream:

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., :face_with_symbols_over_mouth:) 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 :heart: 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 moding. 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

Read full topic

2023 Day 11: Cosmic Expansion

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

Read full topic

Day 5: If You Give A Seed A Fertilizer

@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

Read full topic

Initializing a discriminated record

(If it matters, alr tells me that this is gnat_external=12.3.1; notice the pragma)

I was recently in a situation along these lines:

pragma Ada_2022;

   --  ...

   type Enum is (A, B, C);

   type Disc_Rec (Kind : Enum) is record
      case Kind is
         when A => Field : Natural;
         when others => null;
      end case;
   end record;

   --  ... in what follows, `Thing` is of type `constant Enum` and `Value` is of type 

         D : Disc_Rec := (
            case Thing is
               when A => Disc_Rec'(Kind => A, Field => Value),
               when B | C => Disc_Rec'(Kind => Thing)               --  LINE 37
         );

gnat tells me:

test_enum.adb:37:48: error: no single variant is associated with all values of the subtype of discriminant value "Kind"

Column 47 lands on Thing.

I understand the message, but I’d have thought it clear that since Thing has the type B or C in line 37, Thing has all values of the subtype that matter in this branch. Indeed, if Disc_Rec does not have the case statement that defines Field, and I remove the assignment to Field in line 36, the compiler sings happily. So the problem doesn’t seem to be Thing so much as that the optional Field… which isn’t needed in this branch.

Is there a way to make something like this work? My current workaround handles the branches explicitly (when A => ... , when B => ..., when C => ...), but In a practical case, Kind could have a lot of variants.

7 posts - 3 participants

Read full topic

Two SPARK questions

To help learn me some SPARK, I decided to try implementing the Euclidean Algorithm. With a generic type. Basically (simplified from what I actually have, which includes contracts):

generic

   type Ring_Element is private;

   Zero : Ring_Element;

   with function "=" (Left, Right : Ring_Element) return Boolean is <>;
   with function Size (Value : Ring_Element) return Natural;
   with function "-" ( Left, Right : Ring_Element ) return Ring_Element is <>;
   with function "rem"
     (Dividend, Divisor : Ring_Element) return Ring_Element is <>;
package Euclidean is ...

And the body Euclidean:

    function Gcd ( A, B : Ring_Element ) return Ring_Element is

       M: Ring_Element := A;
       N: Ring_Element := B;

    begin

       while N /= Zero loop

          declare
             R : constant Ring_Element := M rem N;
          begin
             M := N;
             N := R;
          end;

       end loop;

    end Gcd;

The algorithm has several nice properties. One is a loop invariant that r divides a - b.

I’ve struggled with getting SPARK to accept a contract to that effect. My latest iteration has this:

   if R /= Zero then ( A rem R ) - ( B rem R ) = Zero

…but when I instantiate Ring_Element => Integer it reports

   euclidean.adb:26:41: medium: loop invariant might fail in first iteration, cannot prove (A rem R ) - ( B rem R ) = Zero, in instantiation at main.adb:32 (e.g. when A = -2 and B = 1 and M = 1 and R = 3)[#0]

That… makes no sense. It’s not possible for the algorithm to start with those inputs and end up with R = 3.

  1. Am I misreading the error report?
  2. How does SPARK come up with this value of R?
  3. Any advice on writing a contract for this condition? I’ve generally had trouble with guaranteeing arithmetic expressions like A + B and A - B; I understand why, but am not sure how to handle them. Using rem R was something I thought might help here, it did get me past the under/overflow, and it is also true.

10 posts - 3 participants

Read full topic

Gnatdoc and generic package parameters

gnatdoc doesn’t seem to document generic parameters to a package. Does that sound right?

In case my meaning isn’t clear, the following specification should do the trick. Ask away if not.

-- @summary this commentary appears (as long as there's no space between it and "generic" keyword)
generic
   type T is <>;
   -- commentary on T does not appear
   function "=" ( Left, Right: T ) return Boolean is <>;
   -- commentary on "=" does not appear
package P is
   -- commentary in here appears

7 posts - 3 participants

Read full topic

❌