Advent of Code, Day 19

Advent of Code, Day 19

[Gautier Write-Only Address]

Nice puzzle, with plenty of recursion!
First time I see two independent tails in a recursion.
A good opportunity to use the LISP-esque features of Ada: unconstrained arrays, 'First and 'Last, for 1-dimensional arrays: built-in concatenation with "&", slices.
Or perhaps there is a different way?

Re: Advent of Code, Day 19

[John Perry]

On Saturday, December 19, 2020 at 7:43:16 AM UTC-6, gautier...@hotmail.com wrote:
> Nice puzzle, with plenty of recursion! 
> First time I see two independent tails in a recursion. 
> A good opportunity to use the LISP-esque features of Ada: unconstrained arrays, 'First and 'Last, for 1-dimensional arrays: built-in concatenation with "&", slices. 
> Or perhaps there is a different way?

I've totally botched today's puzzle. I got the first part, but not yet the second, and I'm traveling over the next couple of days, so I probably won't finish this for a while, if ever. I'll try hard not to peek at your solution. ;-)

Re: Advent of Code, Day 19

[Gautier Write-Only Address]

For me the first part was the tough one. I've tried for too long to structure the rules verification like this
procedure Verify_Rule (...) is
  ...
  procedure Verify_Rule_List (...) is
  ...
  begin
    loop on the list, call recursively Verify_Rule
  end;
end;
But a loop cannot be used here, each subrule can consume a variable range of characters in the string and there are multiple tails of the string for the next subrule for the loop.
So the solution in that case was to delegate everything further to recursion.

Part two was (in my case) a matter of applying the indicated rules modification.
    if part = 2 then
      rule (8)  := (is_terminal => False, max => 3, alt => 2, sub => (42, 42,  8, -1, -1));
      rule (11) := (is_terminal => False, max => 5, alt => 3, sub => (42, 31, 42, 11, 31));
    end if;

Re: Advent of Code, Day 19

[Jeffrey R. Carter]

On 12/21/20 8:48 PM, Gautier Write-Only Address wrote:
> For me the first part was the tough one. I've tried for too long to structure the rules verification like this
> procedure Verify_Rule (...) is
>    ...
>    procedure Verify_Rule_List (...) is
>    ...
>    begin
>      loop on the list, call recursively Verify_Rule
>    end;
> end;
> But a loop cannot be used here, each subrule can consume a variable range of characters in the string and there are multiple tails of the string for the next subrule for the loop.
 > So the solution in that case was to delegate everything further to recursion.

I initially thought of it as similar to a regular expression, since a single 
rule could end up matching many characters. I therefore reviewed 
PragmARC.Matching.Regular_Expression to see how it might be modified for this 
problem. That led me down the wrong path, as these are more recursive rewriting 
rules than regular expressions.

Once I realized that I soon found a simple recursive solution probably similar 
to yours.

>      if part = 2 then
>        rule (8)  := (is_terminal => False, max => 3, alt => 2, sub => (42, 42,  8, -1, -1));
>        rule (11) := (is_terminal => False, max => 5, alt => 3, sub => (42, 31, 42, 11, 31));
>      end if;

I copied and modified the input file, and modified the program to allow a rule 
list to have up to 3 rules.

My structure for a rule was somewhat more complex than yours, following a 
semi-formal description of the structure of the data.

-- 
Jeff Carter
"It has been my great privilege, many years ago,
whilst traveling through the mountains of Paraguay,
to find the Yack'Wee Indians drinking the juice of
the cacti."
The Old Fashioned Way
152

Re: Advent of Code, Day 19

[John Perry]

On Monday, December 21, 2020 at 2:48:17 PM UTC-5, gautier...@hotmail.com wrote:
> For me the first part was the tough one.

I spent a while on the first one, partly because of that "Get" issue I referenced in another thread, but mostly because my brain wasn't working Saturday.

> But a loop cannot be used here, each subrule can consume a variable range of characters in the string and there are multiple tails of the string for the next subrule for the loop. 

I used recursion from the beginning, but passing to the matching function the position of the last successful check, and returning the position of the "next" successful check. (With recursion, I mean "next recursive call", not "next linear rule". I hope you follow. This strategy worked just fine once I stomped out the bugs introduced for the aforementioned brain failures.

What hung me up on the second part was that I handled the rule options incorrectly. I didn't think to check all the options; if one of them worked, I figured it was true, so returned only the position of the first successful option!

That fails once the loop is introduced: "8: 42 | 8 42" may succeed at evaluating rule 8 with option "42", but that position fails with rule 11 (from "0: 8 11"). The code wasn't checking "8 42", because "8" had worked. I rather embarrassingly reasoned myself into knots trying to figure this out. I did eventually work out a complicated fix, but didn't implement that one.

Peeking at your solution broke the logjam: check "42", then "8 42". I was still stuck because of the double positions (you have a different approach I believe; you return True or False) and finally I realized I could return all the positions that work. Correctness of the entire string comes from one of the returned positions being S'Length + 1. I was rather pleased when it finally worked out.

I've looked at Part 1 of Day 20 & that doesn't seem nearly as hard; hopefully I don't regret saying this!

john perry

Re: Advent of Code, Day 19

[Maxim Reznik]

For Day 19 I tried to make something like "A Pike VM" [1]
It even works with the example, but doesn't find any solution for Part I. 
It's hard to debug why, so I give up :) Don't want to spend much time on it...

[1] https://www.codeproject.com/Articles/5256833/Regex-as-a-Tiny-Threaded-Virtual-Machine

Re: Advent of Code, Day 19

[John Perry]

On Tuesday, December 22, 2020 at 11:43:54 AM UTC-5, Maxim Reznik wrote:
> For Day 19 I tried to make something like "A Pike VM" [1] 
> It even works with the example, but doesn't find any solution for Part I. 
> It's hard to debug why, so I give up :) Don't want to spend much time on it... 
> 
> [1] https://www.codeproject.com/Articles/5256833/Regex-as-a-Tiny-Threaded-Virtual-Machine

I have noticed that the last couple of days, the examples are good to get the idea across, but not necessarily to develop code that works on your actual input. :-(

Re: Advent of Code, Day 19

[Maxim Reznik]

I've fixed my solution for day 19. Now it works and looks not bad, (while a rather long, however) :)
https://github.com/reznikmm/ada-howto/blob/advent-2020/md/19/19.md

I also uploaded a few others.