# Curious fractions in functional Ruby

Problem 33 in Project Euler asks:

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by canceling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

This is the code I came up with, which solves the problem pretty handily. But, I'm concerned that this is messy and unreadable, even with the comments - and I simply hate using magic numbers/indices littered throughout the code. Also, I do not want a procedural ("C" style) solution - I'm learning how to write idiomatic (read "functional") programming with Ruby, and I'd like to learn how to write cleaner functional code.

a = 10.upto(99).to_a.map(&:to_s)  # Create array of integers 10 - 99
puts a.product(a)                 # Form cartesion product [a,b] for all 2 digit numbers a,b
.reject{|x| x.any? {|y| y.chars.include? '0'}}     # Numbers inlcuding '0' are the trivial matches
.reject{|x| x.first == x.last ||                   # Reject pairs where a = b
x.first.to_f/x.last.to_f > 1  ||       # Reject fractions greater than 1
(x.first.chars & x.last.chars).size != 1} # Reject pairs in which no digits are common
.map{|x| [x.first.to_f / x.last.to_f, x.first.chars, x.last.chars, x.first.chars & x.last.chars]} # Ex: [0.5, ["4", "9"], ["9", "8"], ["9"]]
.map{|x| [x.first, x[1] - x.last, x[2] - x.last, x[1], x[2]]}   # Ex: [0.5, ["4"], ["8"],  ["4", "9"], ["9", "8"]]
.select{|x| x.length == 5 && x.first == x[1].join.to_f/x[2].join.to_f} # Select only the tuples which match the condition
.map{|x| Rational(x[-2].join.to_i, x[-1].join.to_i)}  # Convert each such tuple to rational numbers
.reduce(:*)


Array multiple assignment
You pass arrays around, and you find yourself calling for x[1] and x.last - this is very unreadable, and brittle.
Ruby allows you to implicitely assign elements of the array to parameters in your block according to its location, so you could write the same "maps" like this:

  .map do|numerator, denominator|
[numerator.to_f / denominator.to_f, numerator.chars, denominator.chars,
numerator.chars & denominator.chars]
end.map do |result, numerator_digits, denominator_digits, mutual_digit|
[result, numerator_digits - mutual_digit, denominator_digits - mutual_digit,
numerator_digits, denominator_digits]
end.select do|result, new_numerator_digits, new_denominator_digits|
result == new_numerator_digits.join.to_f/new_denominator_digits.join.to_f
end.map do |_, _, _, numerator_digits, denominator_digits|
Rational(numerator_digits.join.to_i, denominator_digits.join.to_i)
end.reduce(:*)


Note that unneeded array elements at the end of the array are truncated, so you don't have to write them. For the unneeded elements at the beginning of the array I've used the _ idiom which tells the method that I expect these parameters, but I won't need them.

If it deserves a comment - it deserves a method
Instead of commenting your code, consider refactoring it into methods. Each method will do one thing, and, given the proper name, will be descriptive when used, and easily read in itself:

def trivial?(pair)
pair.any? {|y| y.chars.include? '0'}
end

def identical?(numerator, denominator)
numerator == denominator
end

def larger_than_one?(numerator, denominator)
numerator.to_i > numerator.to_i
end

def has_common_digits?(numerator, denominator)
(numerator.chars & numerator.chars).size > 0
end

a = 10.upto(99).to_a.map(&:to_s)
puts a.product(a)
.reject(&method(:trivial?))
.reject(&method(:identical?))
.reject(&method(:larger_than_one?))
.select(&method(:has_common_digits?))


The last few steps you take look like they are held out with gum, and that you made some acrobatics to stay one-line and "idiomatic". It is better to make your methods do something you can explain, than simply adding and removing temp-variables:

def reduced_fraction(numerator, denominator)
mutual_digit = numerator.chars & denominator.chars
(numerator.chars - mutual_digit).join.to_f / (denominator.chars - mutual_digit).join.to_f
end

a = 10.upto(99).to_a.map(&:to_s)
puts a.product(a)
.reject(&method(:trivial?))
.reject(&method(:identical?))
.reject(&method(:larger_than_one?))
.select(&method(:has_common_digits?))
.select do |numerator, denominator|
numerator.to_f / denominator.to_f == reduced_fraction(numerator, denominator)
end.map { |fraction| Rational(*fraction) }
.reduce(:*)


Update
Yes, it seems that using &method(:something) in map and multiple assignment are mutually exclusive... :(

I can suggest a few strategies where you don't have to fall back to using pair.first, pair.last:

1. Use multiple assignment in the first line of your method:

def identical?(pair)
numerator, denominator = pair
...
end

2. Use a hash to hold your values, and use keyword arguments in your method

def identical?(numerator: nil, denominator: nil)
numerator == denominator
end

a = 10.upto(99).to_a.map(&:to_s)
puts a.product(a)
.reject(&method(:trivial?))
.map { |numerator, denominator| {numerator: numerator, denominator: denominator } }
.reject(&method(:identical?))

• Are you sure that works? I'm using Ruby 2.0, and I'm seeing identical errors as below: 033.rb:9:in larger_than_one?': wrong number of arguments (1 for 2) (ArgumentError) from 033.rb:26:in reject' from 033.rb:26:in <main>' Apr 26, 2014 at 20:47
• This is because it is expecting 2 arguments instead of one that is being sent - I replaced (num,denum) with (pair) and then used pair.first, pair.last to make it work - what am I missing here? Apr 26, 2014 at 20:48
• I've been able to refactor my code and get rid of the syntax errors - Thanks a lot for teaching me about the &method syntax! Apr 26, 2014 at 21:01
• @TCSGrad - yeah, sorry for the confusion - I added some more options so you could keep using named variables instead of an array... Apr 27, 2014 at 7:59

(This is less a review of the code itself, and more a suggestion for an alternative approach.)

In my opinion, the most idiomatic thing you can do in Ruby is to keep it readable :)

So if being strictly functional interferes with that, well, don't be strictly functional. Ruby can indeed be very functional, and more power to you for learning it - but Ruby can also be a lot of other things. No reason to disregard that on purpose (sort of relevant quote here).

That being said, the int-to-string-to-float-to-int conversion seems sketchy to me, and seems to play a big part in complicating your code.

That got me thinking that it'd be easier to start with the digits 1-9 rather than the numbers 10-99.

We know that neither numerator or denominator can contain a zero, so we only have to look at 1-9. Furthermore, we can start by looking at the "simplified" fractions with single-digit components, and discarding those that are >= 1. That leaves 36 fractions.

From there, we need only mix in an extra digit in both numerator and denominator; i.e. 4 "expanded" fractions to check per extra digit.

First pass, I get this, if I try to keep chaining things

# this'll be useful - could even be a constant
digits = (1...10).to_a

# n and d are numerator and denominator, respectively I've pared
# them down here to keep the line-lengths down a bit.
result = digits.product(digits)           # 2-digit combinations of numbers 1-9
.reject { |n, d| n >= d }  # skip those where the numerator >= denominator
.map do |n, d|
fraction = Rational(n, d) # our 1-digit fraction
digits.map do |digit|     # add in another digit top and bottom
numerators   = [n, digit].permutation(2).map { |a, b| 10 * a + b }
denominators = [d, digit].permutation(2).map { |a, b| 10 * a + b }
numerators.product(denominators)
.map { |n, d| fraction if Rational(n, d) == fraction }
end
end.flatten.compact.inject(&:*).denominator

p result # => 100


I'm sure this can be cleaned up further.

The chaining feels forced. I'd probably do less chaining and use more local variables

digits = (1...10).to_a

# a helper
def numbers_for_digits(a, b)
[a, b].permutation(2).map { |a, b| 10 * a + b }
end

fractions = digits.product(digits).map do |numerator, denominator|
next if numerator >= denominator
fraction = Rational(numerator, denominator)
digits.map do |digit|
numerators   = numbers_for_digits(numerator, digit)
denominators = numbers_for_digits(denominator, digit)
fractions    = numerators.product(denominators)
fractions.map do |numerator, denominator|
fraction if Rational(numerator, denominator) == fraction
end
end
end

result = fractions.flatten.compact.inject(&:*).denominator


p.s. For those curious:

16 / 64 == 1 / 4 == 0.25
19 / 95 == 1 / 5 == 0.2
26 / 65 == 2 / 5 == 0.4
49 / 98 == 4 / 8 == 0.5

As others have said, use logical groupings and aim for readability. I also suggest to use the standard library as much as possible. In Ruby there's a class Rational which has a wonderful feature of reducing any fraction. For example, if r=Rational(4,10), then r.numerator is equal to 2, and r.denominator is equal to 5. Using this, we can plan our attack:

#params are 2-digit numerator and 2-digit denominator
def curious? n,d
rat = Rational(n,d)               #reduced fraction
return false if rat.numerator==n  #not reducible

n0, n1 = n/10, n%10   #split into tens and ones digits
d0, d1 = d/10, d%10
return false if ([n0, n1] & [d0, d1]).empty?   #no common digits

#we know at least one digit repeats; try all combinations
n0==d0 && !d1.zero? && Rational(n1,d1)==rat ||
n0==d1 && !d0.zero? && Rational(n1,d0)==rat ||
n1==d0 && !d1.zero? && Rational(n0,d1)==rat ||
n1==d1 && !d0.zero? && Rational(n0,d0)==rat
end

list=[]
(10..98).each {|n|
next if (n%10).zero?   #comment this line if you want "trivial" as well
(n+1..99).each {|d|
list<<"#{n}/#{d}" if curious?(n,d)
}
}
p list   #["16/64", "19/95", "26/65", "49/98"]
`