Reply to thread

Message: [QUOTE="Adam Shelly, post: 4495184"] Here's mine. I started out with very straightforward programming, but ended up making it muddier as I optimized. I also implemented a bunch of functions that I figured I could probably find alread written if I looked, but I figured they were good exercises : Integer#factors, Integer#divisors, Array#all_combinations.... I thought it was pretty fast, especially compared to my initial implementation. Then I timed Ryan's on my machine... Oh well. I enjoyed the challenge. -Adam --- class Integer def weird? (d =3D divisors).pop #remove self (which is always last) d.sum > self && !d.quick_find_subset_with_sum(self) && #weed out most !d.find_subset_with_sum(self) #confirm the rest end def divisors factors.all_combinations.uniq.inject([]){|result,combo| result << combo.product }.sort.uniq end def factors value, candidate =3D self, 3 factors =3D [1] while value % 2 =3D=3D 0 factors << 2 value /=3D 2 end while candidate <=3D Math.sqrt(value) while value % candidate =3D=3D 0 factors << candidate value /=3D candidate end candidate +=3D 2 end factors << value if value !=3D 1 factors end end class Array def product inject(1){|p,v| p*v} end def sum inject(0){|s,v| s+v} end def all_combinations ComboIndexGenerator.new(self.size).inject([]) {|result, index_set| result << values_at(*index_set) } end #this was my first attempt, which was straightforward, # but slow as heck for large sets def slow_find_subset_with_sum n return nil if sum < n all_combinations.each {|set| return set if set.sum =3D=3D n } nil end #this is my second attempt which is fast but misses some subsets. #but it is useful for quickly rejecting many non-weird numbers. def quick_find_subset_with_sum n a =3D self.sort.reverse sum,set =3D 0,[] a.each {|e| if (sum+e <=3D n) sum+=3De set<<e end return set if sum =3D=3D n } nil end #this one works pretty quickly... #it never tests subsets which are less than the sum, #and keeps track of sets it has already calculated def find_subset_with_sum n possibilities, seen =3D [self],{} until possibilities.empty? candidate =3D possibilities.pop diff =3D candidate.sum - n return candidate if diff =3D=3D 0 break if diff < 0 candidate.each_with_index{|e,i| break if e > diff new_cand =3D (candidate.dup) new_cand.delete_at(i) return new_cand if e =3D=3D diff possibilities << new_cand if !seen[new_cand] seen[new_cand]=3Dtrue } end nil end end #this class generates an all the possible combinations of n items #it returns an array with the next combination every time you call #next class ComboIndexGenerator include Enumerable def initialize nitems @n =3D nitems @max =3D 2**@n @val=3D0 end def to_a return nil if @val=3D=3D@max (0..@n).inject([]){|a,bit| a<<bit if @val[bit]=3D=3D1; a} end def next @val+=3D1 if @val<@max to_a end def each &b yield to_a while (n=3Dself.next) yield n end end end if $0 =3D=3D __FILE__ if ARGV.length < 1 puts "Usage: #$0 <upper limit>" exit(1) end puts "Weird numbers up to and including #{ARGV[0]}:" 70.upto(ARGV[0].to_i) do |i| puts i if i.weird? end end [/QUOTE]

Verification