## mark a section (Learn more)

# 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

This paste will be private.