I am always looking for fun and interesting problems to practice my programming and/or math. The problem is they are hard to find on the internet in my opinion. Here is a list that will continue to grow as I find more.
1. Project Euler - I love this page! The problems scale, so as you learn about and solve the problems, they tend to get harder as you go. A great way to practice any programming language and learn a little math in the process.
2. Coding Bat - Actually written for Java or Python. Geared towards beginners, if you are interested in learning either of those languages.
3. Six Revisions - Their own comprehensive list of links to problems.
4. TopCoder - These problems are more geared towards intermediate and advanced level programmers. A very active community and tons of practice problems here for C++, C#, Python, and Java mostly.
5. Ruby Quiz - Another large list of problems, but without much activity in their community. Still a great resource for problems to be solved.
Showing posts with label euler. Show all posts
Showing posts with label euler. Show all posts
Thursday, August 11, 2011
Project Euler #4 in Ruby
Project Euler #4
Another great example here!
What happens here is very straightforward, because he is asking for two, three-digit numbers multiplied together, it immediately tells us the constraints of our two for loops, and thereby the maximum possible value we could have: 999x999 or 998001. What we need to do then is just compare the value we get from multiplying them together, and then the reverse of that, thereby checking to see if it is palindromic. It's super easy in Ruby as well, you just have to convert both to strings using the '.to_s' operator and then the '.reverse' on one of them. In line 5 the first conditional 'k.to_s == k.to_s.reverse' checks to see if it is palindromic and the second if it is greater than the last palindrome that we found, because there will be many. If it is, the line 6 states that we save it.
This code runs in just over a second for me, satisfying the 1 minute guideline set forth by the project Euler team.
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 
99. Find the largest palindrome made from the product of two 3-digit numbers.
99. Find the largest palindrome made from the product of two 3-digit numbers.Another great example here!
- success = 0
- for i in (100..999)
- for j in (100..999)
- k = i * j
- if (k.to_s == k.to_s.reverse && k > success)
- success = k
- end
- end
- end
- puts success
What happens here is very straightforward, because he is asking for two, three-digit numbers multiplied together, it immediately tells us the constraints of our two for loops, and thereby the maximum possible value we could have: 999x999 or 998001. What we need to do then is just compare the value we get from multiplying them together, and then the reverse of that, thereby checking to see if it is palindromic. It's super easy in Ruby as well, you just have to convert both to strings using the '.to_s' operator and then the '.reverse' on one of them. In line 5 the first conditional 'k.to_s == k.to_s.reverse' checks to see if it is palindromic and the second if it is greater than the last palindrome that we found, because there will be many. If it is, the line 6 states that we save it.
This code runs in just over a second for me, satisfying the 1 minute guideline set forth by the project Euler team.
Project Euler #3 in Ruby
Project Euler #3
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
Here is my solution in Ruby:
This is a great example for defining methods (or functions if you are a 'C' guy or gal). You will notice in line 1 the 'def lPrimeFactor(n)'. 'def' is the keyword for 'define', as in 'define function'. Whenever you define a function you also have to end that definition, as you will notice in line 15. The declaration of our function here to find the largest prime factor is written in camel-case, while the standard is to write it in all lower-case. You may write it however you like, if you use NetBeans though it might get grumpy at you.
In explanation of the code I have written here, all it does is check to see if 'i' is a factor of n, if so it will divide it and then continue to do so until it is not (like in the case of 8, it would divide by 2, three times), and then continues on to the next number working its way up until i is smaller than n, keeping track of the factors and returning the last one it divides successfully. Pretty straightforward.
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?
Here is my solution in Ruby:
- def lPrimeFactor(n)
- i = 2
- largest = 0
- while (i <= n)
- if (n % i == 0)
- while (n % i == 0 )
- n = n / i
- largest = i
- i += 1
- end
- end
- i += 1
- end
- return largest
- end
- puts lPrimeFactor(600851475143)
This is a great example for defining methods (or functions if you are a 'C' guy or gal). You will notice in line 1 the 'def lPrimeFactor(n)'. 'def' is the keyword for 'define', as in 'define function'. Whenever you define a function you also have to end that definition, as you will notice in line 15. The declaration of our function here to find the largest prime factor is written in camel-case, while the standard is to write it in all lower-case. You may write it however you like, if you use NetBeans though it might get grumpy at you.
In explanation of the code I have written here, all it does is check to see if 'i' is a factor of n, if so it will divide it and then continue to do so until it is not (like in the case of 8, it would divide by 2, three times), and then continues on to the next number working its way up until i is smaller than n, keeping track of the factors and returning the last one it divides successfully. Pretty straightforward.
Project Euler #2 in Ruby
Project Euler #2
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
Here is my solution:
You will notice the '_' symbol where the commas would be (or periods if you don't live in the States), for reference in keeping track of how many zeroes we have if we were writing '4,000,000' out by hand. Coding up '4_000_000', is basically the same, the compiler will ignore the underscores. It is just so we can keep track of how many zeroes there are.
I wanted to illustrate something handy in this tutorial, called 'parallel assignment'. Nothing earth shattering, but it could cut down on the number of times you have to press the enter and equals key.
Ruby allows you to assign variables to values, lined up one after the other, on a single line of code. If you will notice we combined lines 1 through 3 above into a single line (1) below. The same is true for lines 5 and 6 above into a single line 3 below. Line 4 below is still on its own line as Ruby won't let you do arithmetic while doing parallel assignment.
This isn't the most clever way of solving this problem, but certainly the easiest to understand. We simply do what the question asks for: Add up each even term of the Fibonacci sequence below 4,000,000.
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.Here is my solution:
- one = 1
- two = 1
- sum = 0
- while (two <= 4_000_000)
- temp = one
- one = two
- two = one + temp
- if (two % 2 == 0)
- sum += two
- end
- end
- puts sum
You will notice the '_' symbol where the commas would be (or periods if you don't live in the States), for reference in keeping track of how many zeroes we have if we were writing '4,000,000' out by hand. Coding up '4_000_000', is basically the same, the compiler will ignore the underscores. It is just so we can keep track of how many zeroes there are.
I wanted to illustrate something handy in this tutorial, called 'parallel assignment'. Nothing earth shattering, but it could cut down on the number of times you have to press the enter and equals key.
Ruby allows you to assign variables to values, lined up one after the other, on a single line of code. If you will notice we combined lines 1 through 3 above into a single line (1) below. The same is true for lines 5 and 6 above into a single line 3 below. Line 4 below is still on its own line as Ruby won't let you do arithmetic while doing parallel assignment.
- one, two, sum = 1, 1, 0
- while (two <= 4_000_000)
- temp, one = one, two
- two = one + temp
- if (two % 2 == 0)
- sum += two
- end
- end
- puts sum
This isn't the most clever way of solving this problem, but certainly the easiest to understand. We simply do what the question asks for: Add up each even term of the Fibonacci sequence below 4,000,000.
Wednesday, August 10, 2011
Project Euler #1 in Ruby
Project Euler #1
1. This is the declaration of a variable in Ruby, and you will notice you do not have to declare its type. It is inferred from what the variable is set equal to when it is declared. Handy! This is what is meant by being a "dynamically typed language", other programming languages like C require you to declare the variable's type at declaration and forever afterward it is of that type. This is referred to as a "statically typed language".
2. See line 1.
3. While loops in Ruby are very similar to those seen in Java or C++, the difference being we don't use brackets, instead we get a great deal of use out of 'end' statements. You will notice that everything within the while loop is tabbed out once (at least). If you use NetBeans, or Notepad++, or some such fancy editor, it will automatically do this and help you see where your blocks of code are located.
What you need to know for 'while' loops, is that you need the keyword 'while' then a conditional, and to close the 'while' block, you must include the 'end' keyword, just like I did on line 12.
For more information on while loops in Ruby, you may use Tutorials Point, or the slightly more concise Techotopia wiki.
4. This is our first look at 'if' statements. Again, very similar to C++, even in the modifiers '&&' or '||' which are 'AND' and 'OR' respectively, in how they modify logical statements.
In our case, line 4 says "if x modulus 3 is equal to 0 and if x modulus 5 is equal to 0 then...", and that is all there is to it! For those new to the game, modulus is just looking for the remainder after we divide.
For example: 6 % 5 = 1, because 6/5 = 1 R 1, where 'R' stands for 'remainder', and % stands for 'modulus' or 'mod' for short.
If you would like to learn more about the modulus, or the area of modular arithmetic in mathematics, you can look here, for a quick primer on the subject.
5. Line 5 is just what it looks like for anyone that has used C or Java, the "+=" operator takes the left hand side and simply adds to it the right hand side. For example:
6. An 'elsif' statement is just an "else" and "if" statement crammed together, and takes a conditional just like the 'if' statement in line 4.
10. We will skip to line 10, as lines 7 through 9 are explained previously. All there is to explain here is that when using 'if', you must also close the block with the 'end' keyword. This is not true for an 'else' or 'elsif' as these are part of a larger 'if' block or statement.
13. This is the last line in our code, and important if we want to know what the answer is! "puts" stands for "put string", and all you have to do to use it is put a string after it. Our sum happens to be of the 'Integer' class, but it has been written in such a way to know what to do when we use it in the 'puts' statement. More on this later!
As for what we are trying to accomplish in this project Euler problem, we want to sum up all of the multiples of 3 and 5 below 1000. Pretty straightforward. There are a few places where one can trip up though:
1. If you incorrectly sum up multiples of both 3 and 5. For example, 15 is a multiple of both 3 and 5, and if you write your code incorrectly you will get a sum that is too large, because you have added twice every multiple of both 3 and 15.
2. Another place is not noticing that the question states below 1000, not up to and including 1000. So just be wary of that.
If anyone has some other pitfalls to be wary of, please email me and I will be sure to include them here, for those that follow after! Good luck all, and happy coding!
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
The problem is fairly straightforward, and is the most correctly answered problem in the whole set. I will be explaining a little bit of Ruby in this solution I give.
Find the sum of all the multiples of 3 or 5 below 1000.
The problem is fairly straightforward, and is the most correctly answered problem in the whole set. I will be explaining a little bit of Ruby in this solution I give.
- x = 0
- sum = 0
- while (x < 1000)
- if (x % 3 == 0 && x % 5 == 0)
- sum += x
- elsif (x % 3 == 0)
- sum += x
- elsif (x % 5 == 0)
- sum += x
- end
- x += 1
- end
- puts sum
1. This is the declaration of a variable in Ruby, and you will notice you do not have to declare its type. It is inferred from what the variable is set equal to when it is declared. Handy! This is what is meant by being a "dynamically typed language", other programming languages like C require you to declare the variable's type at declaration and forever afterward it is of that type. This is referred to as a "statically typed language".
2. See line 1.
3. While loops in Ruby are very similar to those seen in Java or C++, the difference being we don't use brackets, instead we get a great deal of use out of 'end' statements. You will notice that everything within the while loop is tabbed out once (at least). If you use NetBeans, or Notepad++, or some such fancy editor, it will automatically do this and help you see where your blocks of code are located.
What you need to know for 'while' loops, is that you need the keyword 'while' then a conditional, and to close the 'while' block, you must include the 'end' keyword, just like I did on line 12.
For more information on while loops in Ruby, you may use Tutorials Point, or the slightly more concise Techotopia wiki.
4. This is our first look at 'if' statements. Again, very similar to C++, even in the modifiers '&&' or '||' which are 'AND' and 'OR' respectively, in how they modify logical statements.
In our case, line 4 says "if x modulus 3 is equal to 0 and if x modulus 5 is equal to 0 then...", and that is all there is to it! For those new to the game, modulus is just looking for the remainder after we divide.
For example: 6 % 5 = 1, because 6/5 = 1 R 1, where 'R' stands for 'remainder', and % stands for 'modulus' or 'mod' for short.
If you would like to learn more about the modulus, or the area of modular arithmetic in mathematics, you can look here, for a quick primer on the subject.
5. Line 5 is just what it looks like for anyone that has used C or Java, the "+=" operator takes the left hand side and simply adds to it the right hand side. For example:
- x = 0 #=> 0
- x += 3 #=> 3
- x += 39 #=> 42
6. An 'elsif' statement is just an "else" and "if" statement crammed together, and takes a conditional just like the 'if' statement in line 4.
10. We will skip to line 10, as lines 7 through 9 are explained previously. All there is to explain here is that when using 'if', you must also close the block with the 'end' keyword. This is not true for an 'else' or 'elsif' as these are part of a larger 'if' block or statement.
13. This is the last line in our code, and important if we want to know what the answer is! "puts" stands for "put string", and all you have to do to use it is put a string after it. Our sum happens to be of the 'Integer' class, but it has been written in such a way to know what to do when we use it in the 'puts' statement. More on this later!
As for what we are trying to accomplish in this project Euler problem, we want to sum up all of the multiples of 3 and 5 below 1000. Pretty straightforward. There are a few places where one can trip up though:
1. If you incorrectly sum up multiples of both 3 and 5. For example, 15 is a multiple of both 3 and 5, and if you write your code incorrectly you will get a sum that is too large, because you have added twice every multiple of both 3 and 15.
2. Another place is not noticing that the question states below 1000, not up to and including 1000. So just be wary of that.
If anyone has some other pitfalls to be wary of, please email me and I will be sure to include them here, for those that follow after! Good luck all, and happy coding!
Subscribe to:
Posts (Atom)