gistfile1.rbx

class FastBeustSequence
  class << self
    def find_all(max)
      @listener = []
      zero      = Digit.new(nil, 0)
      one       = zero.next
      start     = Time.now
    
      (1..10).each {|length| find(one, zero, length, 0, max, @listener)}
    
      finish    = Time.now
      puts "Time: #{finish-start}"
      puts "Integers in list: #{@listener.length}"
    end

    def find(start, head, remaining, value, max, listener)
      current = start
      while current
        new_value = value + current.value
        if remaining == 1
          return true if new_value > max
          #listener << new_value
        else
          current.use
          new_head = (current == head) ? head.next : head
          if find(new_head, new_head, remaining - 1, new_value * 10, max, listener)
            return true
          end
          current.yield
        end
        current = current.next
      end
    end
  end
end

class Digit
  attr_accessor :next, :value, :previous
  
	def initialize(previous, value)
	  @previous = previous
	  @value = value
	  @next = Digit.new(self, @value+1) if @value < 9
	end
	
	def use
	  @previous.next = @next if @previous
	  @next.previous = @previous if @next
	end
	
	def yield
	  @previous.next = self if @previous
	  @next.previous = self if @next
	end
end

if __FILE__ == $0
  FastBeustSequence.find_all(ARGV[0].to_i)
end