Done puzzle 43
[project-euler.git] / euler24.rb
1 require 'logger'
2 $log = Logger.new(STDERR)
3 $log.level = Logger::WARN
4
5
6 class Integer
7 def to_factorial_radix
8 return [0] if self == 0
9 remainder = self
10 result = []
11 radix = 1
12 while remainder > 0
13 result << (remainder % radix)
14 remainder = remainder.div radix
15 radix += 1
16 end
17 result.reverse
18 end
19 end
20
21 class Array
22 def factorial_radix_to_i(current_radix = 0)
23 $log.info { "Calling factorial_radix_to_i with string #{self} and current_radix = #{current_radix}" }
24 return 0 if self.empty?
25 return 0 if self == [0]
26 value_of_rest = self[0..-2].factorial_radix_to_i(current_radix + 1)
27 $log.info { "Value of remainder = #{value_of_rest}" }
28 $log.info { "Returning #{self[-1] + value_of_rest}" }
29 self[-1] + (current_radix + 1) * value_of_rest
30 end
31
32 def prepad_with_zeros(length)
33 [0] * [length - self.length, 0].max + self
34 end
35
36 def permutation_from_factorial_radix_number(n)
37 $log.info { "Permuting #{self} with frn #{n}" }
38 return [] if n.empty?
39 return self if self.empty?
40 items_copy = self.dup
41 permutation = [items_copy.delete_at(n[0])]
42 permutation += items_copy.permutation_from_factorial_radix_number(n[1..-1])
43 end
44
45 def nth_permutation(n)
46 permutation_from_factorial_radix_number(n.to_factorial_radix.prepad_with_zeros(self.length))
47 end
48 end
49
50 if __FILE__==$0
51 puts (Array.new(10) {|i| i}).nth_permutation(10 ** 6 - 1).join('')
52 end
53
54 $log.close