> > I do worry about the memory used by your solution, since you need to
> > have half of the whole tree in memory at once.
>
> I know a lot of people mentioned this as a possible issue with solutions
> in general here, but this really doesn't seem like an issue to me. The
> whole tree for say 1000 rows is only something like around 250,250
> digits here, (n(n+1)/2)/2 (as stored in the Hashes). I'm not sure of the
> size of the digits in actual RAM but that doesn't really seem like a
> lot. I'm guessing not more than maybe 5M total, counting the keys
> (another digit for each). Seems like a pretty minor cost to me for what
> I might do to fix it. Personally, I'd rather have code that is easier to
> read or finish faster than take up a chunk of memory. But this is maybe
> just my preference.

I don't think people are examining the memory issue because of this
particular problem; you're right, this triangle could probably grow
pretty damn large before anyone really noticed.

I think people look at the memory issues more as an exercise.  If this
problem were such that we needed around 1,000,000 rows or more, or
perhaps this problem were on an embedded device with 64K RAM (ignore
the Ruby libs/exe), then you'll have issues with a solution that just
allocates the whole triangle. Some folks are curious (self-included)
as to how they might solve the problem with that consideration.
(You'll also see people here going the opposite route, to make it as
fast as possible no holds bars...  both are optimization problems.)

As they say, the root of all evil is "vi"...  I mean, premature
optimization.  But if it's just an exercise to see how to do it, I
say, let them use emacs...  err, optimize.