Skip to content

Instantly share code, notes, and snippets.

@krishicks
Forked from anonymous/gist:20005
Created March 2, 2010 01:54
Show Gist options
  • Save krishicks/319040 to your computer and use it in GitHub Desktop.
Save krishicks/319040 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment