Project Euler Problem 24
Used the algorithm on Wikipedia at http://en.wikipedia.org/wiki/Permutation#Lexicographical_order_generation. It’s a generic method that takes any arbitrary list and the desired permutation number k.
Problem Statement
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
require "fixnum.rb" # Fixnum.factorial
def permutation(k, list)
size = list.size
factorial = (size-1).factorial
result = []
while result.size != size
x = k / factorial
x -= 1 if (k % factorial).zero?
result << list.delete_at(x)
k = k % factorial
factorial = (list.size - 1).factorial
end
result
end
puts permutation(1000000, [0,1,2,3,4,5,6,7,8,9]).join
Project Euler Problem 23
This problem required generating all “abundant” numbers below the specified limit, and then canceling out those that could not be reached by adding up any two abundant numbers from the generated list.
A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
Solution in Ruby:
require "mathn"
require "set"
require "fixnum.rb" # for Fixnum.factor?
require "array.rb" # for Array.sum
abundant = []
all = (1..max).to_set
sum_of_abundant_numbers = Set.new
max = 28123
# find all abundant numbers
(1..max).each do |n|
factors = Set.new
(1..Math.sqrt(n)).each do |f|
if n.factor?(f)
factors << f
factors << (n/f) unless f == 1
end
end
abundant << n if factors.to_a.sum > n
end
# find sum of all abundant number pairs
abundant.each do |a|
abundant.each do |b|
break if a + b > max
sum_of_abundant_numbers << a + b
end
end
all = all - sum_of_abundant_numbers
puts all.to_a.sum
One liner for Project Euler problem 20
I was needlessly worrying about about the capabilities of Bignum in being able to handle this factorial which has 158 digits in its result. Wasn’t an issue at all though.
Ruby certainly brings conciseness to the code. It maybe possible in a lot lesser characters in J or other functional languages, but this is good enough for me for the time being.
The problem statement is
Find the sum of the digits in the number 100!
Solution in Ruby
puts (1..100).to_a.inject{|prod, n| prod * n}.to_s.split(//).map{|d| d.to_i}.inject{|sum, n| sum + n}
Edit: even shorter with the reduce method in Ruby 1.9
(1..100).reduce(:*).to_s.split(//).map{|d| d.to_i}.reduce(:+)
Project Euler Problem 17
This is a good way to learn Ruby by solving some problems from Project Euler. Here’s my solution to problem 17. Link to the problem - http://projecteuler.net/index.php?section=problems&id=17 and the problem text and solution are below:
If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.
words = {
0 => '',
1 => 'one',
2 => 'two',
3 => 'three',
4 => 'four',
5 => 'five',
6 => 'six',
7 => 'seven',
8 => 'eight',
9 => 'nine',
10 => 'ten',
11 => 'eleven',
12 => 'twelve',
13 => 'thirteen',
14 => 'fourteen',
15 => 'fifteen',
16 => 'sixteen',
17 => 'seventeen',
18 => 'eighteen',
19 => 'nineteen',
20 => 'twenty',
30 => 'thirty',
40 => 'forty',
50 => 'fifty',
60 => 'sixty',
70 => 'seventy',
80 => 'eighty',
90 => 'ninety',
100 => 'hundred',
1000 => 'thousand'
}
total_letters = 0
(1..1000).each do |number|
zero_padded_number = "%04d" % number
digits = zero_padded_number.split(//).collect { |d| d.to_i }
last_two_digits = digits[-2, 2].join.to_i
thousands = words[digits[0]] + words[1000] if digits[0] != 0
hundreds = words[digits[1]] + words[100] if digits[1] != 0
_and_ = 'and' if (last_two_digits != 0 and number > 100)
tens = last_two_digits >= 20 ? words[digits[2] * 10] + words[digits[3]] : words[last_two_digits]
string = "#{thousands}#{hundreds}#{_and_}#{tens}"
total_letters += string.length
end
puts total_letters
