❌ About FreshRSS

Normal view

There are new articles available, click to refresh the page.
Before yesterdayAda Forum - Latest topics

How does one override an operation with classwide types?

By: jere
28 December 2023 at 17:38

I didn’t think it was possible, but some annotations in the annotated RM seem to indicate it is possible. I’m working with subpools and I want to create some of my own for non heap objects. The problem is that in GNAT they use heap allocation in the function Set_Pool_of_Subpool, which is a required call, so if it is possible to override this, then I would like to so I can have it avoid heap allocation.

For reference from System.Storage_Pools.Subpools:

type Subpool_Handle is access all Root_Subpool'Class;
   for Subpool_Handle'Storage_Size use 0;

function Pool_of_Subpool (Subpool : not null Subpool_Handle)
      return access Root_Storage_Pool_With_Subpools'Class;

procedure Set_Pool_of_Subpool (
      Subpool : in not null Subpool_Handle;
      To : in out Root_Storage_Pool_With_Subpools'Class)
         with Global => overriding in out Subpool;

And the RM annotation (Ada22 annotated RM 20.a/3):

Discussion: Pool_of_Subpool and Set_Pool_of_Subpool are provided by the Ada 
implementation and typically will not be overridden by the pool implementer. 

There is uses the phrasing “typically” which would imply that they could be overridden by an implementer for some cases.

The only way I could come up to override it was to create a derived type of the handle but then the compiler complains when I use “new” with the derived subpool handle type that the handle type isn’t the standard one, so I don’t think that is what the discussion point was referring to (as it would be pointless to override in this way).

To my knowledge you can’t override operations with classwide types. Anyone have any insight into this?

Subpools reference: Storage Subpools

1 post - 1 participant

Read full topic

Running RecordFlux

28 December 2023 at 08:30

I’m writing a protocol parser and would like to use RecordFlux to generate a parser from a specification. I’ve been unable to get any recent version of RecordFlux working with the GNAT toolchain from Alire. The wheel on pypi expects a GNAT Studio install with gnatcoll in the path and compiling from source seems to require and even deeper tree of manually built dependencies.

I’m begging anyone at AdaCore to write an alire.toml file.

1 post - 1 participant

Read full topic

2023 Day 25: Snowverload

By: cantanima
26 December 2023 at 02:31

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

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

5 posts - 3 participants

Read full topic

2023 Day 23: A Long Walk

By: cantanima
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.

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

By: cantanima
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 :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

AEiC 2024 - Ada-Europe conference - grants for Open Access publication

21 December 2023 at 17:32

Season’s greetings from the organizers of the 28th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2024), to be held 11-14 June 2024, in Barcelona, Spain!

Accepted Journal Track papers will be published in the conference’s Special Issue of the Journal of Systems Architecture (JSA). Note that the Ada-Europe organization will waive the Open Access fees for the first four accepted papers, which do not already enjoy OA from other agreements with the Publisher.

www.ada-europe.org/conference2024/cfp.html#cfpjournal

#AEiC2024 #AdaEurope #AdaProgramming

1 post - 1 participant

Read full topic

2023 Day 20: Pulse Propagation

By: cantanima
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

Read full topic

2023 Day 19: Aplenty

By: cantanima
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

Read full topic

2023 Day 18: Lavaduct Lagoon

By: cantanima
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

Read full topic

2023 Day 17: Clumsy Crucible

By: cantanima
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 :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

Question about vector initialization

By: cunger
18 December 2023 at 06:38

Yesterday, I was trying to do something with an array of vectors and stumbled a bit. So I’d like to ask some clarification questions about initialization…

With arrays (as with most other types), a variable is uninitialized until it’s explicitly set to a value.

My_List : array (1 .. 10) of Boolean;   -- uninitialized
My_List := [1 => True, other => False];

With vectors it’s slightly different. The reference manual says:

If an object of type Vector is not otherwise initialized, it is initialized to the same value as Empty_Vector.

So if I have:

package Boolean_Vectors is Ada.Containers.Vectors (
  Index_Type   => Positive,
  Element_Type => Boolean
);

subtype Boolean_Vector is Boolean_Vectors.Vector;

I can actually do:

My_Vector : Boolean_Vector; -- Implicitly initialized here?
My_Vector.Append (True);    -- Or here?
My_Vector.Append (False);

Although I’m not sure when exactly initialization happens (and why it was designed to happen implicitly).

Now, Empty_Vector is a constant, so I cannot use it if I want to initialize an empty vector explicitly.
So, what do I do when I want to have an array of vectors?

My_Vector_List : array (1 .. 10) of Boolean_Vector;
My_Vector_List := [others => ??]; -- How do I put an empty vector here
                                  -- that can grow later?

Or do I have to do it like this?

My_Vector_1, My_Vector_2 : Boolean_Vector;

My_Vector_List (1) := My_Vector_1;
My_Vector_List (2) := My_Vector_2;
...

9 posts - 7 participants

Read full topic

Ada package for dates prior to 1900?

18 December 2023 at 03:11

Hi;

How does one do calendar, date and time, calculations in Ada if the dates are prior to 1900? I’m sure that this is a real problem that has been encountered previously. I’ve never seen anything that does this. Do people just make a foreign call to Perl or UNIX cal program?

Thanks,
Ken Wolcott

5 posts - 3 participants

Read full topic

2023 Day 16: The Floor Will Be Lava

By: cantanima
16 December 2023 at 14:48

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

By: cantanima
13 December 2023 at 04:55

: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

❌
❌