# Finds base 10 numbers whose digits don't repeat. Solution to Cedric's coding
 # challenge: http://beust.com/weblog/archives/000491.html

 # @author Bob Lee (crazybob@crazybob.org)
 # @converted to Ruby by ak_avenger - I'm not taking any credit for this
 
class FastBeustSequence

   #~ * Finds all numbers in sequence up to max.
   #~ *
   #~ * @param max maximum sequence value
   #~ * @param listener hears search results
  def self.findAll(max, listener)
    zero = Digit.new(nil, 0)
    one = zero.next
    length = 1
    while length <= 10
      return nil if (find(one, zero, length, 0, max, listener)) 
      length += 1
    end
  end

  #~ /**
   #~ * Called recursively for each digit from most to least significant.
   #~ *
   #~ * @param start digit to start with, used to skip 0 for most significant digit
   #~ * @param head of set
   #~ * @param remaining digit count
   #~ * @param value so far
   #~ * @param max value
   #~ * @param listener hears results
   #~ * @return true if we reached max, false otherwise
   #~ */
  def self.find(start, head, remaining, value, max, listener)
    current = start
    while current != nil
      newValue = value + current.value
      if (remaining == 1)
        return true if (newValue > max)
        listener.hear(newValue)
      else
        current.use
        newHead = (current == head) ? head.next : head
        if (find(newHead, newHead, remaining - 1, newValue * 10, max, listener))
          return true
        end
        current.yield
      end
      current = current.next
    end
    return false
  end

  #~ /** A digit, part of a doubly-linked set. */
  class Digit
    attr_accessor :previous, :next, :value

    #~ /** Constructs digit with given value as well as all subsequent digits. */
    def initialize(previous, value)
      @value = value
      @previous = previous

      #~ // Recursively construct subsequent digits.
      ( @next = Digit.new(self, value + 1) ) if (value < 9) 
    end

    #~ /** Removes digit from the set. */
    def use
      previous.next = @next if (previous != nil) 
      @next.previous = previous if (@next != nil) 
    end

    #~ /** Puts digit back into the set. */
    def yield
      previous.next = self if (previous != nil)
      @next.previous = self if (@next != nil) 
    end
  end
end

class Listener
  def initialize output
    @output = output
  end
  
  def hear thing
    @output.puts thing
  end
end

File.open( 'log.txt', 'w') do |log|
  start_time = Time.now
  FastBeustSequence.findAll(9_876_543_210, Listener.new(log))
  end_time = Time.now
  log.puts "Time: #{end_time - start_time}"
end