day 7

day 7

[Stephen Leake]

I'm a day behind, because I decided to use WisiToken, an Ada parsing
library I maintain, for this. And life intervened.

The main client for WisiToken is Emacs ada-mode, and that works nicely.

It turns out WisiToken is less friendly for uses like this puzzle, so I
had to fix some things. Once that was done, using the parser went quite
nicely; it made it very easy to handle the list of contained bags, for
example.

I also constructed a color map, giving integer ids to each color, to
simplify comparing them. On the other hand, that means I don't have the
actual color name handy for debug messages; I need the inverse map for
that.

One other design choice: I used a closure operation (in the Dragon book
sense
https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools,
not the "function closure" sense; apparently the Dragon book use of
"closure" is not well known?), rather than recursion to compute the bags
containing the target color. That was to avoid overflowing the stack.

However, for counting the contained bags I used function recursion,
which would overflow the stack if the first computation did. I could
have added more state info to allow accumulating the count in another
closure operation, but that seemed too hard.

I'm not clear what the puzzle statement about "topologically
impractical" is about; that might be hinting at overflowing the stack?
It can't mean a loop in the 'contains' relation, which would be a
problem; the rules don't allow expressing such a thing, since they only
talk about bag colors, not bag identity

-- 
-- Stephe

Re: day 7

[Jeffrey R. Carter]

On 12/9/20 2:35 AM, Stephen Leake wrote:
> 
> I'm not clear what the puzzle statement about "topologically
> impractical" is about; that might be hinting at overflowing the stack?

Clearly the day 7 problems came out of a meeting of the Society for Putting One 
Bag Inside Another Bag.

I took "topologically impractical" to mean the difficulty of having a bag that a 
person could carry contain that many bags.

Regarding recursion, on real-world problems I have never had a correct recursive 
solution overflow the stack on my typical desktop machine (usually a few years 
behind the latest and greatest).

-- 
Jeff Carter
"[T]he [Agile] idea that it's bad to spend an
appropriate time at the beginning of the project
to clarify the overall requirements and design
is nonsense."
Bertrand Meyer
149