3
\$\begingroup\$

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(:*)   
\$\endgroup\$
2
\$\begingroup\$

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?))

Make your steps logical
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?)) 
    
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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>' \$\endgroup\$ – TCSGrad Apr 26 '14 at 20:47
  • \$\begingroup\$ 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? \$\endgroup\$ – TCSGrad Apr 26 '14 at 20:48
  • \$\begingroup\$ 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! \$\endgroup\$ – TCSGrad Apr 26 '14 at 21:01
  • \$\begingroup\$ @TCSGrad - yeah, sorry for the confusion - I added some more options so you could keep using named variables instead of an array... \$\endgroup\$ – Uri Agassi Apr 27 '14 at 7:59
1
\$\begingroup\$

(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

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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"]
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.