From: George Ogata <george.ogata@...>
Date: 2007-01-30T20:35:56+09:00
Subject: Re: Counting Toothpicks (#111)

On 1/30/07, David Chelimsky <dchelimsky@gmail.com> wrote:
> On 1/29/07, George Ogata <george.ogata@gmail.com> wrote:
> > On 1/29/07, Sander Land <sander.land@gmail.com> wrote:
> >     The speedup here would be negligable, but hey:
> >
> >     pos_plus = (1..k/2).map{|p| best_mul[p] + '+ ' + h[k-p] }
>
> I get a stack overflow w/ this.

Darn, it does too.  Calling best_mul[] on the larger addend (like
Sander's original algo) helps:

        pos_plus = (1..k/2).map{|p| best_mul[k-p] + '+ ' + h[p] }

It wasn't so obvious to me that it's still correct that way, actually,
but I'm convinced it is.

> I think so too, though I did find that the toothpicks weren't being
> counted correctly because it counted characters in each expression,
> but not the extra toothpicks for + and x. So 11 was getting |||x|||+||
> instead of |||||||||||.

Hmm, I didn't get that behavior.

Note that he adds '+ ' (plus-space) and 'x ' (x-space) in the strings,
so I believe the string length does actually represent the toothpick
count correctly.  Perhaps the spaces somehow disappeared when you
copied it?