On the suggestion of my Flatiron classmates David and Andrew, I started trying out Project Euler recently. For the uninitiated, Project Euler is a series of math problems aptly named after the famed mathemetician Leonhard Euler, known for such learned things like fluid dynamics, number theory and calculus. Project Euler is effectively a database of math problems that are intended to be solved using code (any language can be used; I’m using Ruby). The questions test your logical thinking skills, and while they’re named after a mathemetician, the actual math necessary is more along the lines of high school math (e.g., prime numbers, factoring, etc.). This is not to diminish the difficulty of these problems - some of them are quite challenging - but rather to distinguish between the problem solving skills, which Project Euler helps build, versus pure math skill, which is more the province of a graduate school program. I’ve also throw my efforts to solve these problems on Github if you want to check them out.
I’ve only completed about 5 problems, but I’m already an advocate of trying them out. I like Project Euler because the problems are challenging enough where they really force you to build a clear, logical problem solving process yet not so obscure that you need to break out your AP Calculus book. Don’t be turned away from the problems because of the math - the biggest challenge is taking the large problem and breaking it down small-step-by-small-step.
Here’s an example problem:
1 2 3 |
|
As you can see, the problems are challenging but manageable. The prompt typically has an example pattern and then asks you to extrapolate that pattern to some large number (in this case, 1000). Here are the main reasons why I think its great to try a few Project Euler problems:
1) Great mental exercise
I’m trying to average a problem a day as a form of mental exercise. While doing Project Euler problems probably won’t directly make you a better Rails programmer, it will boost your overall problem solving process. And what else is coding at its core but implementing a clear process to solving problems via technology? Just as going for a 6-mile run today may not keep you from getting a cold tomorrow, doing Project Euler problems won’t help you solve that nasty bug in your code today, but having a consistent habit of problem solving exercise will make your mind healthier in the long run.
2) Learning core Ruby
Having to solve Project Euler problems has forced me back into the core Ruby documentation to try and find creative solutions. For example, I don’t typically use Ruby’s ‘inject’ method in my day-to-day coding. Inject is a pretty high-level Ruby function that allows you to specify an initial value and apply a code block to an Enumerable (e.g., an array), the result of which becomes the initial value in the following iteration. Most of the code I’ve written rely on the less abstract ‘collect’ or ‘map’ methods in Ruby. However, I’ve rediscovered the utility of the inject method since Project Euler problems tend to include some sort of iterative sum or product. I won’t go into the details of the inject method here, but you can find more information about it in this blog post if you’re interested.
3) Refactoring practice
Refactoring is the near-constant process of changing code without affecting what the user sees. Its the middle part of the “make it work, make it right, make it fast” adage. Recognizing patterns and understanding the tradeoffs included in applying certain methods or approaching a problem in a certain way are critical to skillful refactoring. Project Euler problems really help hammer in the practice of always looking over your code and finding ways to refactor it.
I’ve started taking a three-pronged approach to solving Project Euler problems. First, I’ll try and solve the problem for a smaller number (e.g., less than 100) with whatever code works. Second, I’ll solve the problem for the large number stated in the Project Euler prompt. Finally, I’ll refactor the code into an object-oriented manner, either by creating my own class or monkey-patching an existing Ruby class (often, the Integer class). This three-step process has helped me practice raw problem-solving and get into the habit of breaking down complex problems into small, simple tasks. Refactoring is a universal coding skill, so I’m hopeful that Project Euler will help me develop a better sense for patterns and make me a better problem solver.
4) Creative problem solving
This reason falls in line with the refactoring practice Project Euler provides. As the cliche goes, there’s often more than one way to skin a cat, and problem solving is no different. An example of this is the code below (warning: spoiler alert) that I wrote to solve Project Euler problem 8. The problem provides a 1000-digit number and you are required to find the greatest product of any five consecutive digits.
When I was thinking about this problem, I could see a few solutions. One way it could be done would be to go through the number in 5-digit chunks, basically creating sub-arrays out of the number, storing the value into a products array, then returning the maximum value. Another way to solve the problem would be to find the product of 5-digit chunks, store the result in a variable, then replace the value of that variable with subsequent products only if such product is larger. Yet another way to solve the problem would be to calculate the product of a 5-digit chunk, then iteratively check whether the next number is larger than the first number in the 5-digit array (i.e., the next product calculation). If so, then calculate the product. Otherwise, move onto the next number to add.
I think this last process is the most efficient, because each product that is actually calculated is guaranteed to be larger than the previous max product, since all else equal, replacing one number in a 5-digit product with a larger number will result in a larger number. This saves computation time and moves the determination of whether to calculate the product to a less computationally intensive task (comparing two numbers versus multiplication. At least, I think this is the case. I’m not super well versed in algorithm efficiency, but this makes sense to me at least.
The code I ended up implementing takes the most from the middle process. I could have extended the code further to make it more efficient, but I focused instead on making the code more object-oriented. My below code shows the three-step process I’m taking toward these problems - first, make it work with a smaller number, then make it work with the actual number, then refactor into an object.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 |
|
As I mentioned above, don’t be intimidated by the math parts of Project Euler. In retrospect, I wish I had started doing these problems earlier on in the semester, but its never too late to get some good mental exercise in.