🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of remcopeereboom

remcopeereboom's solution

to Sum Of Multiples in the Ruby Track

Published at Jul 13 2018 · 6 comments
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

Given a number, find the sum of all the unique multiples of particular numbers up to but not including that number.

If we list all the natural numbers below 20 that are multiples of 3 or 5, we get 3, 5, 6, 9, 10, 12, 15, and 18.

The sum of these multiples is 78.


For installation and learning resources, refer to the exercism help page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

gem install minitest

If you would like color output, you can require 'minitest/pride' in the test file, or note the alternative instruction, below, for running the test file.

Run the tests from the exercise directory using the following command:

ruby sum_of_multiples_test.rb

To include color from the command line:

ruby -r minitest/pride sum_of_multiples_test.rb

Source

A variation on Problem 1 at Project Euler http://projecteuler.net/problem=1

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

sum_of_multiples_test.rb

require 'minitest/autorun'
require_relative 'sum_of_multiples'

# Common test data version: 1.1.0 df076b2
class SumOfMultiplesTest < Minitest::Test
  def test_multiples_of_3_or_5_up_to_1
    # skip
    assert_equal 0, SumOfMultiples.new(3, 5).to(1)
  end

  def test_multiples_of_3_or_5_up_to_4
    skip
    assert_equal 3, SumOfMultiples.new(3, 5).to(4)
  end

  def test_multiples_of_3_up_to_7
    skip
    assert_equal 9, SumOfMultiples.new(3).to(7)
  end

  def test_multiples_of_3_or_5_up_to_10
    skip
    assert_equal 23, SumOfMultiples.new(3, 5).to(10)
  end

  def test_multiples_of_3_or_5_up_to_100
    skip
    assert_equal 2_318, SumOfMultiples.new(3, 5).to(100)
  end

  def test_multiples_of_3_or_5_up_to_1000
    skip
    assert_equal 233_168, SumOfMultiples.new(3, 5).to(1000)
  end

  def test_multiples_of_7_13_or_17_up_to_20
    skip
    assert_equal 51, SumOfMultiples.new(7, 13, 17).to(20)
  end

  def test_multiples_of_4_or_6_up_to_15
    skip
    assert_equal 30, SumOfMultiples.new(4, 6).to(15)
  end

  def test_multiples_of_5_6_or_8_up_to_150
    skip
    assert_equal 4_419, SumOfMultiples.new(5, 6, 8).to(150)
  end

  def test_multiples_of_5_or_25_up_to_51
    skip
    assert_equal 275, SumOfMultiples.new(5, 25).to(51)
  end

  def test_multiples_of_43_or_47_up_to_10000
    skip
    assert_equal 2_203_160, SumOfMultiples.new(43, 47).to(10000)
  end

  def test_multiples_of_1_up_to_100
    skip
    assert_equal 4_950, SumOfMultiples.new(1).to(100)
  end

  def test_multiples_of_an_empty_list_up_to_10000
    skip
    assert_equal 0, SumOfMultiples.new().to(10000)
  end

  # Problems in exercism evolve over time, as we find better ways to ask
  # questions.
  # The version number refers to the version of the problem you solved,
  # not your solution.
  #
  # Define a constant named VERSION inside of the top level BookKeeping
  # module, which may be placed near the end of your file.
  #
  # In your file, it will look like this:
  #
  # module BookKeeping
  #   VERSION = 1 # Where the version number matches the one in the test.
  # end
  #
  # If you are curious, read more about constants on RubyDoc:
  # http://ruby-doc.org/docs/ruby-doc-bundle/UsersGuide/rg/constants.html

  def test_bookkeeping
    skip
    assert_equal 2, BookKeeping::VERSION
  end
end
class SumOfMultiples
  def self.to(n)
    new(3, 5).to(n)
  end

  def initialize(*factors)
    @factors = factors
  end

  def to(n)
    (0...n).select { |x| multiple? x }.inject(:+)
  end

  private

  attr_reader :factors

  def multiple?(x)
    factors.any? { |f| x % f == 0 }
  end
end

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of bcgoss

Using select and then inject like this will create two loops. First, hit every number from 0 to n and pick out the multiples. Then, hit each multiple and add it to the result. In the worst case, looking for multiples of 1, you will double the run time.

Avatar of remcopeereboom

Using select and then inject like this will create two loops. First, hit every number from 0 to n and pick out the multiples. Then, hit each multiple and add it to the result. In the worst case, looking for multiples of 1, you will double the run time.

Thanks for the feedback @bcgoss. You haven't made any explicit comments stating whether or not you think my code is inefficient, but I think that is what you were trying to get at. You seem to be suggesting that going over all elements of a set twice is necessarily more inefficient than doing so once. That certainly sounds reasonable doesn't it? You might be surprised to learn than, that turns out not to be the case.

It's actually a common fallacy - and a particularly unfortunate one. In order to explain why things are not as bad as they seem we need to be a bit more precise, so I'm going to be a bit overly verbose, but bare with me.

Using select and then inject like this will create two loops.

Yes, it definitely will. But not firstly that the two loops are not necessarily the same size. This already suggest that we have to be careful about comparing them to a single loop. You are - you note that if we are looking for multiples of 1, the loops will be the same size...

Okay, but is this extra work? If we had a single loop, than we would be doing the both actual work parts, but now are only doing half the work in each loop, so we do exactly the same amount of work overal. Here is a pseudo code example:

Single loop version

This does n * (a + b) work

(1..n).times do step_a step_b end

Double loop version

This does n * a + n * b work, but that's == n * (a + b)

(1..n).times { step_a } (1..n).times { step_b }

Notice how the total amount of work done stays the same. Now if you were to measure the performance of this, than the second version would be slightly slower. In particular if n, step_a, and step_b are all small, than the first version would be much faster, but of course if that's the case we don't really care about performance anyway. If that's not the case, than the second version will be about as fast as the first version. You might think that there is a lot of overhead because you need to update the loop counter and such, but modern processors are highly vectorized, use branch prediction, and can often update these things in a single instruction concurrently, so you might not even notice the loop "part" itself if this were a language like C/C++.

Note finally that even if we double the running time, that we don't care. Unless we are doing some really cutting edge programming, a constant time difference is not something we optimize for. If we need better performance, than we are almost always better off choosing an algorithm with better asymptotic performance, improving things like read/write times (especially across HDD's or over a network) or just buying a computer that is twice as fast.

The upshot of all of this combined is that if we can make an algorithm more readable by separating the steps than this we should always do this. Only if after profiling we find that a particular piece of code is a bottleneck should we avoid this.

Avatar of bcgoss

Thanks for your thoughtful reply. I see what you mean, when you frame it as the Distributive Principle it makes a lot of sense. I thought I had profiled but there were some flaws in my approach. I recreated your method, and my method and put a counter inside the block of each one. I read the block out after the method finished with puts. In my implementation, the select block was hidden as a guard statement so I forgot to count it too. Other people might have ignored me, but you took a minute to carefully explain this idea, which I really appreciate!

Avatar of remcopeereboom

Cheers @bcgoss, that may be the nicest reply I've ever had :)

Avatar of pikislabis

Starting the range from the smallest number of factors is more efficient than starting from 0.

Taking the below test as an example: def test_multiples_of_43_or_47_up_to_10000 assert_equal 2_203_160, SumOfMultiples.new(43, 47).to(10000) end

In your solution you are going to check from 0 to 42 if any of these numbers are multiple of the factors, when you have the security it isn't.

Avatar of remcopeereboom

@pikislabis commented:

Starting the range from the smallest number of factors is more efficient than starting from 0.

Taking the below test as an example: def test_multiples_of_43_or_47_up_to_10000 assert_equal 2_203_160, SumOfMultiples.new(43, 47).to(10000) end

In your solution you are going to check from 0 to 42 if any of these numbers are multiple of the factors, when you have the security it isn't.

Nice catch! That's indeed an important optimization if the smallest factor is very large. It's maybe not so much of a concern if the smallest factor is 42 and we are generating multiples up to 10_000, but there are certainly situations where it might matter.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?