On 1/29/07, George Ogata <george.ogata / gmail.com> wrote:
> On 1/29/07, Sander Land <sander.land / gmail.com> wrote:
> > Here is my solution, a simple brute force + cache.
> > http://pastie.caboo.se/36232
> >
> > class Fixnum
> >   def divisors
> >     @d ||= (2..self/2).select{|i| self % i == 0 }
>
>       You've probably already realized this, but this would be a lot faster:
>
>       @d ||= (2..Math.sqrt(self)).select{|i| self % i == 0 }
>
> >   end
> > end
> >
> > best_mul = Hash.new{|h,k|
> >   pos_mul = k.divisors.map{|d| h[d] + 'x ' + h[k/d] }
> >   h[k] = (pos_mul << '|'*k).sort_by{|tp|tp.length}.first
> > }
> >
> > best_plus = Hash.new{|h,k|
> >   pos_plus = (k/2...k).map{|p| best_mul[p] + '+ ' + h[k-p] }
>
>     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.

>
> >   h[k] = (pos_plus << best_mul[k]).sort_by{|tp|tp.length}.first
> > }.merge(1=>'|')
> >
> > puts best_plus[ARGV[0].to_i].gsub(' ','').sub(/^$/,'Hug a Tree')
>
> Sweet solution, though.  :-)

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 |||||||||||.

This helped:

 #in best_plus
 h[k] = (pos_plus << best_mul[k]).sort_by{|tp|tp.length +
tp.split(/[x\+]/).length - 1}.first

>
>