Project Euler describes itself as a
The obvious difference between these problems and the brainteasers is that you are required to use some math (not advanced math, but math nonetheless). You end up looking up cool stuff on the wikipedia. A problem on prime numbers may have you reacquainting yourself with the Sieve of Eratosthenes as a fast way of generating prime numbers, and delving into the details of the Miller Rabin Primality Test for the first time. When I say "delving into the details" what I really mean is that you learn enough to be able to implement it in code. This isn't super deep but deeper than most of us would go if weren't focused on solving a concrete problem.
The problems that I like best follow a specific pattern: the setting involves a game or a process that can be easily simulated in a few lines of code. One is asked to compute some function, which again can be easily coded. But the kicker is that one has to provide the answer to the function for some gargantuan input like \(10^{12}\) and the nifty lines of code one has written so far would have to run for eternity to arrive at the answer. It is the process of rethinking one's approach so that the answer is computable in about a minute's worth of running time is what is most fun and rewarding about Project Euler.
An example of this (and one that I would rate as moderately hard on the "Euler Scale") is Problem 469, which concerns itself with knights sitting around a table. We have a round table with $n$ seats and Knights enter the room sequentially. The first knight picks any chair and blocks the seats to his immediate left and right. Then the next knight enters and picks one of the available seats uniformly at random. This goes on until a Knight cannot be seated. The question concerns the average fraction of seats that remain empty. Now for a small value of $n$ (say $1000$), this is not hard to compute. One simulates the knight seating process and estimates the average. But the problem asks to compute the answer for $10^{18}$ and it wants the answer to be correct to many significant digits. Well, what to do now? That is the typical kind of dilemma I face when attempting Euler problems.
When you do solve a problem correctly you get access to a terrific forum in which people post their code. I am constantly amazed at the range of approaches people from all over the world use in their solutions.
Bottom line, start solving these problems if you like math, brainteasers and have a basic knowledge of programming. You will lean a lot and have fun doing it!
series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.I've worked my through about 150 of the approximately 500 problems over the last few months, and it's been a lot of fun!
The obvious difference between these problems and the brainteasers is that you are required to use some math (not advanced math, but math nonetheless). You end up looking up cool stuff on the wikipedia. A problem on prime numbers may have you reacquainting yourself with the Sieve of Eratosthenes as a fast way of generating prime numbers, and delving into the details of the Miller Rabin Primality Test for the first time. When I say "delving into the details" what I really mean is that you learn enough to be able to implement it in code. This isn't super deep but deeper than most of us would go if weren't focused on solving a concrete problem.
The problems that I like best follow a specific pattern: the setting involves a game or a process that can be easily simulated in a few lines of code. One is asked to compute some function, which again can be easily coded. But the kicker is that one has to provide the answer to the function for some gargantuan input like \(10^{12}\) and the nifty lines of code one has written so far would have to run for eternity to arrive at the answer. It is the process of rethinking one's approach so that the answer is computable in about a minute's worth of running time is what is most fun and rewarding about Project Euler.
An example of this (and one that I would rate as moderately hard on the "Euler Scale") is Problem 469, which concerns itself with knights sitting around a table. We have a round table with $n$ seats and Knights enter the room sequentially. The first knight picks any chair and blocks the seats to his immediate left and right. Then the next knight enters and picks one of the available seats uniformly at random. This goes on until a Knight cannot be seated. The question concerns the average fraction of seats that remain empty. Now for a small value of $n$ (say $1000$), this is not hard to compute. One simulates the knight seating process and estimates the average. But the problem asks to compute the answer for $10^{18}$ and it wants the answer to be correct to many significant digits. Well, what to do now? That is the typical kind of dilemma I face when attempting Euler problems.
When you do solve a problem correctly you get access to a terrific forum in which people post their code. I am constantly amazed at the range of approaches people from all over the world use in their solutions.
Bottom line, start solving these problems if you like math, brainteasers and have a basic knowledge of programming. You will lean a lot and have fun doing it!
No comments:
Post a Comment