tag:blogger.com,1999:blog-6950637025522526042023-06-20T06:23:47.921-07:00kata coderto seek perfection, one must practice...ggarciahttp://www.blogger.com/profile/14422001652591906627noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-695063702552252604.post-72654543212701419042011-05-16T07:01:00.000-07:002011-05-16T07:01:34.358-07:0002 Kata [ruby] - sum of even fibonacci numbersHere is the first tentative using brute force.<br />
<br />
<pre class="prettyprint">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
</pre>
And here is the second tentative using a little big of math magic.
<pre class="prettyprint">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
</pre>ggarciahttp://www.blogger.com/profile/14422001652591906627noreply@blogger.com0tag:blogger.com,1999:blog-695063702552252604.post-62804268304413048532011-05-12T12:28:00.000-07:002011-05-13T13:29:46.248-07:0002 Kata [scala] - sum of even fibonacci numbersHere is the first tentative using brute force.<br />
<br />
<pre class="prettyprint">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)
}
}
</pre>
And here is the second tentative using a little big of math magic.
<pre class="prettyprint">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)
}
}
</pre>ggarciahttp://www.blogger.com/profile/14422001652591906627noreply@blogger.com0tag:blogger.com,1999:blog-695063702552252604.post-28981953631175335572011-05-12T12:27:00.000-07:002011-05-13T13:29:46.332-07:0002 Kata [java] - sum of even fibonacci numbersHere is the first tentative using brute force.<br />
<br />
<pre class="prettyprint">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);
}
</pre>
And here is the second tentative using a little big of math magic.
<pre class="prettyprint">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);
}
</pre>ggarciahttp://www.blogger.com/profile/14422001652591906627noreply@blogger.com0tag:blogger.com,1999:blog-695063702552252604.post-78647747611020523962011-05-12T12:26:00.000-07:002011-05-13T13:29:46.294-07:0002 Kata [reason] - sum of even fibonacci numbersIn this second kata, we are going to explore another problem from Project Euler.<br />
<br />
Let's check it out:<br />
"By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms"<br />
<br />
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.<br />
<br />
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.<br />
<br />
In the second solution, I made use of a little math to optimize the algorithm.<br />
<br />
We first find the index of the last fibonacci number that we need to compute in order to get the correct solution.<br />
To find the index we use the following formula:<br />
<br />
<ul> <li>round ((log limit * (sqrt 5)) * 2) + 1.618)</li>
</ul><br />
1.618 is the golden ratio.<br />
<br />
So, no we have the fib(n) that will generate a fibonnaci number that is less than the limit.<br />
<br />
But we can use a little more math to make things a little bit faster.<br />
<br />
Since every third fibonacci number is even, we don't need to compute the fibonacci number for all indexes in the sequence.<br />
We can use de following formula and calculate only the ones that we know are even.<br />
<br />
(4 * fib(i - 3)) + fib(i - 6)<br />
<br />
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.<br />
<br />
So, let's take a look at the solutionsggarciahttp://www.blogger.com/profile/14422001652591906627noreply@blogger.com0tag:blogger.com,1999:blog-695063702552252604.post-10873230248344439472011-05-05T19:08:00.000-07:002011-05-05T19:08:45.135-07:0001 Kata [haskell] - sum of multiples of 3 or 5 less than 1000And at last but not at least, the haskell solution.<br />
<br />
<pre class="prettyprint">module FirstKata (
fkSum
) where
fkSum = foldl (+) 0 (filter (\x -> (mod x 3 == 0)
|| (mod x 5 == 0)) [1,2..999])
</pre><br />
<pre class="prettyprint">testFkSum = TestCase $ assertEqual 233168 fkSum
</pre><br />
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.<br />
The function does exactly and only this.<br />
<br />
<pre class="prettyprint">fkSum :: Int -> Int
fkSum a = foldl (+) 0 (filter (\x -> (mod x 3 == 0)
|| (mod x 5 == 0)) [1..a])
</pre><br />
<pre class="prettyprint">testFkSum = TestCase $ assertEqual 233168 (fkSum 999)
</pre><br />
A little refactor latter and we have a little more generic function.<br />
It now takes a number (upperLimit) function parameter.<br />
<br />
<pre class="prettyprint">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
</pre><br />
<pre class="prettyprint">testFkSumFirst = TestCase $ assertEqual 23 (fkSum 9 [3,5])
testFkSumSecond = TestCase $ assertEqual 233168 (fkSum 999 [3,5])
suite = TestList [ testFkSumFirst, testFkSumSecond ]
</pre><br />
And now we have the most generic function in haskell as well.<br />
<br />
After some tips, we can improve our solution.<br />
<br />
The good thing about this new solution is that it executes in constant time no matter how big is the upper limit.<br />
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<br />
can find the sum of any pair of multiples for any given upper limit.<br />
<br />
<b>The theory behing the solution.</b><br />
<br />
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.<br />
<br />
So, given the above, we have <br />
<br />
<ul><li>sumOfMultiples of 3 or 5 less than 1000 = f 1000 3 + f 1000 5 - f 1000 15</li>
</ul><br />
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?<br />
<br />
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.<br />
<br />
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<br />
<br />
<ul><li>1000 / 3</li>
<li>1000 / 5</li>
</ul><br />
And by the latter we have:<br />
<br />
<ul><li>f 1000 3 = ( n * ( n + 1 ) / 2 ) * 3</li>
<li>f 1000 5 = ( n * ( n + 1 ) / 2 ) * 5</li>
</ul><br />
By applying this function, we'll find out the value of the sum of any individual multiples.<br />
<br />
<b>So, add all together and see what's look like.</b><br />
<br />
<b>Java</b><br />
<pre class="prettyprint">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;
}
</pre><br />
<b>Ruby</b><br />
<pre class="prettyprint">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
</pre><br />
<b>Scala</b><br />
<pre class="prettyprint">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
}
</pre><br />
<b>Haskell</b><br />
<pre class="prettyprint">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
</pre><br />
I hope you have enjoyed the reading.ggarciahttp://www.blogger.com/profile/14422001652591906627noreply@blogger.com0tag:blogger.com,1999:blog-695063702552252604.post-63097476049061645292011-05-05T19:06:00.001-07:002011-05-05T19:06:57.195-07:0001 Kata [scala] - sum of multiples of 3 or 5 less than 1000Now, lets take a look at the scala solution.<br />
<br />
<pre class="prettyprint">class FirstKata {
def sum: Int = {
var sum = 0;
for (i <- 1 until 1000) {
if (i % 3 == 0 || i % 5 == 0)
sum = sum + i
}
sum
}
}
</pre><br />
<pre class="prettyprint">class FirstKataTest extends Assertions {
@Test
def sum() {
val kata = new FirstKata
assertEquals(kata.sum, 233168)
}
}
</pre><br />
This solution is very similar to the java one except for the fact that was written in scala.<br />
Lets perform a serie of little refactoring in order to get the more generic solution we are capable of.<br />
<br />
<pre class="prettyprint">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
}
}
</pre><br />
<pre class="prettyprint">class FirstKataTest extends Assertions {
@Test
def sum() {
val kata = new FirstKata
assertEquals(kata sum 10, 23)
assertEquals(kata sum 1000, 233168)
}
}
</pre><br />
The first refactoring added the upperLimit parameter.<br />
<br />
<pre class="prettyprint">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
}
}
</pre><br />
<pre class="prettyprint">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)
}
}
</pre><br />
The second refactoring add the multiples parameter as a Seq[Int].<br />
<br />
<pre class="prettyprint">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
}
}
</pre><br />
In this refactoring we made use of for comprehension to get a more concise solution<br />
<br />
<pre class="prettyprint">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
}
}
</pre><br />
Now using pattern matching. It illustrates the what one can get using FP.<br />
And at last but not least.<br />
<br />
<pre class="prettyprint">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
}
}
</pre><br />
A more concise solution.ggarciahttp://www.blogger.com/profile/14422001652591906627noreply@blogger.com0tag:blogger.com,1999:blog-695063702552252604.post-27780644790554271182011-05-05T19:05:00.000-07:002011-05-05T19:05:46.377-07:0001 Kata [ruby] - sum of multiples of 3 or 5 less than 1000Lets take a look at the ruby solution now.<br />
<br />
<pre class="prettyprint">class FirstKata
def sum()
sum = 0
1000.to_i.times {
|i| sum += i if (i % 3 == 0 || i % 5 == 0)
}
sum
end
end
</pre><br />
<pre class="prettyprint">class FirstKataTest < Test::Unit::TestCase
def test_sim
assert_equal(233168, FirstKata.new.sum)
end
end
</pre><br />
This is the very same solution of the first one in java except that this one is in ruby.<br />
So, lets make it a little bit more generic adding a parameter to the sum method.<br />
<br />
<pre class="prettyprint">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
</pre><br />
<pre class="prettyprint">class FirstKataTest < Test::Unit::TestCase
def test_sum
assert_equal(23, FirstKata.new.sum(10))
assert_equal(233168, FirstKata.new.sum(1000))
end
end
</pre><br />
Lets make it even more generic adding a multiple parameter.<br />
<br />
<pre class="prettyprint">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
</pre><br />
<pre class="prettyprint">class FirstKataTest < Test::Unit::TestCase
def test_sum
assert_equal(18, FirstKata.new.sum(10, 3))
end
end
</pre><br />
This parameter is a number. So, we indeed have a more generic solution, but it only works for 1 multiple at a time.<br />
Lets fix this.<br />
<br />
<pre class="prettyprint">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
</pre><br />
<pre class="prettyprint">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
</pre><br />
Now we can receive a list of multiples and thus our solution is a generic one.<br />
But can we still improve our code?<br />
<br />
I think so...<br />
<br />
<pre class="prettyprint">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
</pre><br />
<pre class="prettyprint">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
</pre><br />
And we now have a more concise version of the generic solution.ggarciahttp://www.blogger.com/profile/14422001652591906627noreply@blogger.com0tag:blogger.com,1999:blog-695063702552252604.post-43939968584850422772011-05-05T19:03:00.000-07:002011-05-05T19:03:28.032-07:0001 Kata [java] - sum of multiples of 3 or 5 less than 1000<pre class="prettyprint">public int sum() {
int sum = 0;
for (int i = 0; i < 1000; i++) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i;
}
}
return sum;
}
</pre><br />
<pre class="prettyprint">public class FirstKataTest {
@Test
public void testSum() {
FirstKata kata = new FirstKata();
assertEquals(
kata.sum(),
233168
);
}
}
</pre><br />
This is the first shot to solve the problem and we should notice that it is a very specific method that works in this case only.<br />
But what if want to find the sum of multiples for any given number? Well, we'll need to perform a little refactoring.<br />
<br />
<pre class="prettyprint">public class FirstKata {
public int sum(int upperLimit) {
int sum = 0;
for (int i = 0; i < upperLimit; i++) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i;
}
}
return sum;
}
}
</pre><br />
<pre class="prettyprint">@Test
public void testSum() {
FirstKata kata = new FirstKata();
assertEquals(
kata.sum(1000),
233168
);
assertEquals(
kata.sum(10),
23
);
}
</pre><br />
As one can see, we add the parameter upperLimit to the sum method and now, we can compute the sum of multiples of any number we feel it's right.<br />
But this solution is not generic enough, since it computes only the multiples of 3 or 5. So, let's perform another refactoring and make the method more generic.<br />
<br />
<pre class="prettyprint">public class FirstKata {
public int sum(int upperLimit, List<Integer> multiples) {
int sum = 0;
for (int i = 0; i < upperLimit; i++) {
if (isMultiple(i, multiples)) {
sum += i;
}
}
return sum;
}
public boolean isMultiple(int number, List<Integer> multiples) {
for (int multiple : multiples) {
if (number % multiple == 0) {
return true;
}
}
return false;
}
}
</pre><br />
<pre class="prettyprint">@Test
public void testSum() {
List<Integer> multiples = new ArrayList<Integer>();
multiples.add(3);
multiples.add(5);
FirstKata kata = new FirstKata();
assertEquals(
kata.sum(1000, multiples),
233168
);
assertEquals(
kata.sum(10, multiples),
23
);
}
@Test
public void testIsMultiple() {
FirstKata kata = new FirstKata();
List<Integer> multiples = new ArrayList<Integer>();
multiples.add(3);
multiples.add(5);
assertTrue(kata.isMultiple(6, multiples));
assertTrue(kata.isMultiple(10, multiples));
}
</pre><br />
Fair enough. Now we can compute the sum of any multiples for any number.<br />
And that's all for the java solution.ggarciahttp://www.blogger.com/profile/14422001652591906627noreply@blogger.com0tag:blogger.com,1999:blog-695063702552252604.post-18031671160225707992011-03-29T20:37:00.000-07:002011-05-05T18:51:51.468-07:0001 Kata [reason] - sum of multiples of 3 or 5 less than 1000The purpose of this first kata is to solve a small problem from Project Euler site in the following programming languages: Java, Scala, Ruby and Haskell.<br />
Also, we should provide different solution within a given language.<br />
<br />
<b>Why is that?</b><br />
Well, the main goal here is:<br />
<ul><li>to practice in different languages in order to see the problem from different perspectives</li>
<li>when trying to find different solutions for the same problem within a give language we are forced to deep our knowledge of that given language.</li>
</ul><br />
I will split the solutions in various posts separated by languages to make it easier to follow.<br />
<br />
So, let's get things done here.<br />
<br />
<b>The codes are available at github.</b><br />
git://github.com/colt44/kata-coder.git<br />
<br />
<b>The problem:</b><br />
Find the sum of all numbers multiple of 3 or 5 less than 1000<br />
<br />
<b>The enviroment</b><br />
Java<br />
openjdk 64 bits - version "1.6.0_18"<br />
testNG - version 5.6<br />
ruby - version 1.8<br />
haskell - version 6.12.1ggarciahttp://www.blogger.com/profile/14422001652591906627noreply@blogger.com0