[ruby-talk:12462] Re: ...and the challenge

On Mon, 12 Mar 2001, Benjamin J. Tilly wrote:

> >===== Original Message From Mathieu Bouchard <[e-mail]> =====
> >On Mon, 12 Mar 2001, Benjamin J. Tilly wrote:
> >> >(oh, btw. Ben's version takes over 3 times longer. i'm now testing with
> >> >n=10**30 and using >/dev/null)
> >> We have a winner.  If you want all of the Hamming numbers less
> >> than a fixed bound, this appears fastest.
> >
> >I believe there are faster ways than that, but I don't want to go that
> >far...
> 
> Well fastest of the submitted solutions. :-)
> 
> >> Theoretically the sort is k*log(k) where k is the number of
> >> elements.  Practically if you raise n large enough for that to
> >> matter, you will run out of memory on the machine. :-)
> >
> >the hamming function, where h(1)=1, is very close to
> >
> >proc{|k| 0.185*6.9893**(k**(1/3.0)) }
> >
> >which can be used as a reliable approximation for large values of k
> >(add 2% for safety)
> 
> Ah, I didn't know that.  Well with that fact you should be
> able to indeed do well.
> 
I was about to post that Ben was the winner since matju's solution didn't
adhere to my initial posting (the n first hamming numbers and not the
hamming numbers less than a fixed bound) but the above formula should turn
things around.

Thanks for all nice solutions, this was fun.

My solution is slower than yours but shorter when you've got
LazyArray's (It's simple to define them if you build on
MetaRuby; they're basically as the ProcAsArray example but allowing a
length of Infinity):

  def hamming_sequence(gens)
    hs = LazyArray.new([1]) {|i, me|
      # Having an explicit state is ugly; there's probably a nicer
solution
      unless me.state["inner"]
	me.state["inner"] = merge(gens.map{|gen| hs.map {|v| gen*v}})
      end
      me.state["inner"][i-1]
    }
  end

  # The n first
  hamming_sequence([2,3,5])[0...1000]

This solution is basically the same as the perl one pointed to by
Ben. Expressing it in Ruby makes things a fair amount cleaner though...

Regards,

Robert