02 Kata [ruby] - sum of even fibonacci numbers

Here is the first tentative using brute force.

class SecondKata
  def sum(limit)
    sum = 0
 
    limit.to_i.times do |i|
   fibN = fib(i)
   
   sum += fibN if fibN % 2 == 0
   
   break if fibN > limit
 end
 
 sum
  end
  
  def fib(n)
    n < 2 ? n : fib(n - 1) + fib(n - 2)
  end
end

And here is the second tentative using a little big of math magic.

class SecondKata
  def sum(limit)
    sum = 0
 n = ((Math.log(limit.to_i * (Math.sqrt 5)) * 2) + 1.618).round
 
    (6..n).each do |i|
   fibN = (4 * fib(i - 3)) + fib(i - 6)
   
   sum += fibN if fibN % 2 == 0
   
   break if fibN > limit
 end
 
 sum + 2
  end
  
  def fib(n)
    n < 2 ? n : fib(n - 1) + fib(n - 2)
  end
end

02 Kata [scala] - sum of even fibonacci numbers

Here is the first tentative using brute force.

class SecondKata {
  var sum:Long = 0;

  def sum(limit: Long): Long = {
    var sum: Long = 0

    (for (i: Long <- 0l to 40l; j = fib(i); if (j < limit) && isEven(j)) yield j).foreach(sum += _)

    sum
  }

  def isEven(n: Long): Boolean = {
    return (n % 2) == 0
  }

  def fib(n: Long): Long = {
    if ((n < 2)) n else fib(n - 1) + fib(n - 2)
  }
}

And here is the second tentative using a little big of math magic.

class SecondKata {
  def sum(limit: Long): Long = {
    val n: Long = round(((log(limit * sqrt(5))) * 2) + 1.618)

    var sum: Long = 0

    (for (i: Long <- 6l to 40l;
          j = (4 * fib(i - 3)) + fib(i - 6);
          if (j < limit) && isEven(j)
    ) yield j).foreach(sum += _)

    sum + 2
  }

  def isEven(n: Long): Boolean = {
    return (n % 2) == 0
  }

  def fib(n: Long): Long = {
    if ((n < 2)) n else fib(n - 1) + fib(n - 2)
  }
}

02 Kata [java] - sum of even fibonacci numbers

Here is the first tentative using brute force.

public long sum() {
 long sum = 0;

 for (int i = 1; i < 1000000; i++) {
  long fibNum = fib(i);

  if (fibNum > 4000000) {
   break;
  }

  if (isEven(fibNum)) {
   sum += fibNum;
  }
 }
 
 return sum;
}

private boolean isEven(long n) {
 return (n % 2) == 0;
}

private long fib(long n) {
 return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}

And here is the second tentative using a little big of math magic.

public long sum(double limit) {
 long n = Math.round(((Math.log(limit * Math.sqrt(5))) * 2) + 1.618);
 long sum = 0;

 for (long i = 6; i < n; i++) {
  long fib = (4 * fib(i - 3)) + fib(i - 6);

  if (fib % 2 == 0)
   sum += fib;
 }

 return sum + 2;
}

private long fib(long n) {
 return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}

02 Kata [reason] - sum of even fibonacci numbers

In this second kata, we are going to explore another problem from Project Euler.

Let's check it out:
"By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms"

I have been working on two possible solutions. In the first solution, I use a little bit of brute force, meaning that, I have to calculate every fibonacci number until tje result exceeds four million. For every generetade fibonacci number, I will test whether it's even or not and then, if it's even I sum it up. And, then, after all that, I will return the sum.

This first solution is the easiest way to solve the problem, meaning that we don't have to think hard to come up with it. And I see two positive outcomes when using this solution. We can use it to learn a language that we don't master yet and we can also use it as a start point to think about more fancy solutions.

In the second solution, I made use of a little math to optimize the algorithm.

We first find the index of the last fibonacci number that we need to compute in order to get the correct solution.
To find the index we use the following formula:

• round ((log limit * (sqrt 5)) * 2) + 1.618)

1.618 is the golden ratio.

So, no we have the fib(n) that will generate a fibonnaci number that is less than the limit.

But we can use a little more math to make things a little bit faster.

Since every third fibonacci number is even, we don't need to compute the fibonacci number for all indexes in the sequence.
We can use de following formula and calculate only the ones that we know are even.

(4 * fib(i - 3)) + fib(i - 6)

In this version, we don't compute the fib(3), so we have to add 2 to the final result in order to get the correct answer.

So, let's take a look at the solutions

01 Kata [haskell] - sum of multiples of 3 or 5 less than 1000

And at last but not at least, the haskell solution.

module FirstKata (
  fkSum
) where

fkSum = foldl (+) 0 (filter (\x -> (mod x 3 == 0) 
        || (mod x 5 == 0)) [1,2..999])

testFkSum = TestCase $ assertEqual 233168 fkSum

This first solution is the same as the java one, only it sintax is very different. Short story is, we have a function to compute all multiples of 3 or 5 less than 1000.
The function does exactly and only this.

fkSum :: Int -> Int
fkSum a = foldl (+) 0 (filter (\x -> (mod x 3 == 0) 
          || (mod x 5 == 0)) [1..a])

testFkSum = TestCase $ assertEqual 233168 (fkSum 999)

A little refactor latter and we have a little more generic function.
It now takes a number (upperLimit) function parameter.

fkSum :: Int -> [Int] -> Int
fkSum a [] = 0
fkSum a (b) = foldl (+) 0 (filter (\x -> isMultiple x b) [1..a])

isMultiple :: Int -> [Int] -> Bool
isMultiple a [] = False
iisMultiple a (x:xs) = 
        if (mod a x == 0) then True else isMultiple a xs

testFkSumFirst = TestCase $ assertEqual 23 (fkSum 9 [3,5])
testFkSumSecond = TestCase $ assertEqual 233168 (fkSum 999 [3,5])

suite = TestList [ testFkSumFirst, testFkSumSecond ]

And now we have the most generic function in haskell as well.

After some tips, we can improve our solution.

The good thing about this new solution is that it executes in constant time no matter how big is the upper limit.
But, it comes with a price and it's that we don't have the most generic solution that can handle the universe. What we have now is a solution that
can find the sum of any pair of multiples for any given upper limit.

The theory behing the solution.

We had to apply the inclusion exclusion principle. This principle states that the number of elements in the union of two set is the elements of the first set plus the elements of the second set minus the elements that are in both.

So, given the above, we have

• sumOfMultiples of 3 or 5 less than 1000 = f 1000 3 + f 1000 5 - f 1000 15

Now we know what is the sum of the multiples of 3 or 5 less than 1000 but, wait... What is the sum of the multiples of 3 less than 1000? and the sum of multiples of 5 less than 1000?

To find out the sum of the individual multiples we have to use the first principle of finite induction that states that n * ( n + 1 ) / 2 to any given number n.

In this case, n is the number of multiples that we have to sum up. We find it by dividing the upper limit by the multiple

• 1000 / 3
• 1000 / 5

And by the latter we have:

• f 1000 3 = ( n * ( n + 1 ) / 2 ) * 3
• f 1000 5 = ( n * ( n + 1 ) / 2 ) * 5

By applying this function, we'll find out the value of the sum of any individual multiples.

So, add all together and see what's look like.

Java

public long sum(long upperLimit, 
                                         int firstMultiple, 
                                         int secondMultiple) {
        return sumMultiples(upperLimit, firstMultiple)
                + sumMultiples(upperLimit, secondMultiple)
                - sumMultiples(upperLimit, 
                               firstMultiple * secondMultiple);
    }
 
    public long sumMultiples(long upperLimit, int multiple) {
        long n = upperLimit / multiple;
        return (n * (n + 1) / 2) * multiple;
    }

Ruby

def sum(upper_limit, first_multiple, second_multiple)
    first_sum = sum_multiples(upper_limit, first_multiple)
    second_sum = sum_multiples(upper_limit, second_multiple)
    third_sum = sum_multiples(upper_limit, 
                              first_multiple * second_multiple)

    first_sum + second_sum - third_sum
  end

  def sum_multiples(upper_limit, multiple)
    n = upper_limit / multiple

    j = (n * (n + 1) / 2) * multiple
  end

Scala

def sum(upperLimit: Long, fm: Int, sm: Int): Long = {
    return (sumMultiples(upperLimit, fm)
      + sumMultiples(upperLimit, sm)
      - sumMultiples(upperLimit, fm * sm  }

  def sumMultiples(upperLimit: Long, multiple: Int): Long = {
    val n: Long = upperLimit / multiple
    return (n * (n + 1) / 2) * multiple
  }

Haskell

module FirstKata (
  fkSum
) where

fkSum u x y = f x + f y - f (x * y)
 where f d = let n = u `div` d in (n * (n + 1) `div` 2) * d

I hope you have enjoyed the reading.

01 Kata [scala] - sum of multiples of 3 or 5 less than 1000

Now, lets take a look at the scala solution.

class FirstKata {
  def sum: Int = {
    var sum = 0;

    for (i <- 1 until 1000) {
      if (i % 3 == 0 || i % 5 == 0)
        sum = sum + i
    }

    sum
  }
}

class FirstKataTest extends Assertions {
  @Test
  def sum() {
    val kata = new FirstKata

    assertEquals(kata.sum, 233168)
  }
}

This solution is very similar to the java one except for the fact that was written in scala.
Lets perform a serie of little refactoring in order to get the more generic solution we are capable of.

class FirstKata {
  def sum(upperLimit: Int): Int = {
    var sum: Int = 0;

    for (i <- 1 until upperLimit) {
      if (i % 3 == 0 || i % 5 == 0)
        sum = sum + i
    }

    sum
  }
}

class FirstKataTest extends Assertions {
  @Test
  def sum() {
    val kata = new FirstKata

    assertEquals(kata sum 10, 23)
    assertEquals(kata sum 1000, 233168)
  }
}

The first refactoring added the upperLimit parameter.

class FirstKata {
  def sum(upperLimit: Int, multiples: Seq[Int]): Int = {
    var sum: Int = 0;

    for (i <- 1 until upperLimit) {
      if (isMultiple(i, multiples))
        sum = sum + i
    }

    sum
  }

  def isMultiple(upperLimit: Int, multiples: Seq[Int]): Boolean = {
    for (multiple <- multiples) {
      if (upperLimit % multiple == 0)
        return true
    }

    return false
  }
}

class FirstKataTest extends Assertions {
  @Test
  def sum() {
    val kata = new FirstKata

    assertEquals(kata.sum(10, 3::5::Nil), 23)
    assertEquals(kata.sum(1000, 3::5::Nil), 233168)
  }
}

The second refactoring add the multiples parameter as a Seq[Int].

class FirstKata {
  def sum(upperLimit: Int, multiples: Seq[Int]): Int = {
    var sum: Int = 0;

    for (i <- 1 until upperLimit if isMultiple(i, multiples))
    yield sum = sum + i

    sum
  }

  def isMultiple(upperLimit: Int, multiples: Seq[Int]): Boolean = {
    if (multiples.filter(upperLimit % _ == 0).isEmpty) 
      false 
    else 
      true
  }
}

In this refactoring we made use of for comprehension to get a more concise solution

class FirstKata {
  def sum(upperLimit: Int, mult: Seq[Int]): Int = upperLimit match {
    case 0 => 0
    case x =>
      if (isMultiple(x, mult))
        (x + sum((x - 1), mult))
      else
        sum((x - 1), mult)
  }

  def isMultiple(upperLimit: Int, multiples: Seq[Int]): Boolean = {
    if (multiples.filter(upperLimit % _ == 0).isEmpty)
      false 
    else 
      true
  }
}

Now using pattern matching. It illustrates the what one can get using FP.
And at last but not least.

class FirstKata {
  def sum(upperLimit: Int, multiples: Seq[Int]): Int = {
    List.range(1, upperLimit)
       .filter(isMultiple(_, multiples)).foldLeft(0)(_ + _)
  }

  def isMultiple(upperLimit: Int, multiples: Seq[Int]): Boolean = {
    if (multiples.filter(upperLimit % _ == 0).isEmpty)
      false 
    else 
      true
  }
}

A more concise solution.

01 Kata [ruby] - sum of multiples of 3 or 5 less than 1000

Lets take a look at the ruby solution now.

class FirstKata
  def sum()
    sum = 0

    1000.to_i.times {
        |i| sum += i if (i % 3 == 0 || i % 5 == 0)
    }

    sum
  end
end

class FirstKataTest < Test::Unit::TestCase
  def test_sim
    assert_equal(233168, FirstKata.new.sum)
  end
end

This is the very same solution of the first one in java except that this one is in ruby.
So, lets make it a little bit more generic adding a parameter to the sum method.

class FirstKata
  def sum(upper_limit)
    sum = 0

    upper_limit.to_i.times {
        |i| sum += i if (i % 3 == 0 || i % 5 == 0)
    }

    sum
  end
end

class FirstKataTest < Test::Unit::TestCase
  def test_sum
    assert_equal(23, FirstKata.new.sum(10))
    assert_equal(233168, FirstKata.new.sum(1000))
  end
end

Lets make it even more generic adding a multiple parameter.

class FirstKata
  def sum(upper_limit, multiple)
    sum = 0

    upper_limit.to_i.times do |i|
      sum += i if (i % multiple == 0)
    end

    sum
  end
end

class FirstKataTest < Test::Unit::TestCase
  def test_sum
    assert_equal(18, FirstKata.new.sum(10, 3))
  end
end

This parameter is a number. So, we indeed have a more generic solution, but it only works for 1 multiple at a time.
Lets fix this.

class FirstKata
  def sum(upper_limit, multiples)
    sum = 0

    upper_limit.to_i.times do |i|
      sum += i if is_multiple?(i, multiples)
    end

    sum
  end

  def is_multiple?(number, multiples)
    multiple = false

    multiples.each do |j|
      if (number % j == 0)
        multiple = true
      end
    end

    multiple
  end
end

class FirstKataTest < Test::Unit::TestCase
  def test_sum
    assert_equal(23, FirstKata.new.sum(10, [3,5]))
    assert_equal(233168, FirstKata.new.sum(1000, [3,5]))
  end
end

Now we can receive a list of multiples and thus our solution is a generic one.
But can we still improve our code?

I think so...

class FirstKata
  def sum(upper_limit, multiples)
    sum = 0

    upper_limit.to_i.times do |i|
      sum += i if is_multiple?(i, multiples)
    end

    sum
  end

  def is_multiple?(number, multiples)
    multiples.each do |j|
      return true if (number % j == 0)
    end

    false
  end
end

class FirstKataTest < Test::Unit::TestCase
  def test_is_multiple?
    assert_equal(true, FirstKata.new.is_multiple?(2, [2]))
    assert_equal(true, FirstKata.new.is_multiple?(6, [3]))
    assert_equal(true, FirstKata.new.is_multiple?(6, [3, 2]))
    assert_equal(true, FirstKata.new.is_multiple?(15, [3, 5]))
  end

  def test_sum
    assert_equal(23, FirstKata.new.sum(10, [3, 5]))
    assert_equal(233168, FirstKata.new.sum(1000, [3, 5]))
  end
end

And we now have a more concise version of the generic solution.