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] }

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