Starting Euler
Feeling like I need to do something besides $work with my perl, I have decided recently to start working through the ProjectEuler.net problems. One of the ideas I'm looking to explore is building a framework of sorts that will host all the problems and will provide access to many common items both for use in solving the problems as well as in easing the development of the solutions.
I sort of jumped right in the other day and knocked out Problem 001 and Problem 003 while also starting to build the framework around it. I didn't start the git repository until after that but I suspect some of that will change anyway as it was real quick and dirty.
The basic setup of the framework will be a base class, Euler.pm, that will handle the profiling, running, and common math operations. The problems will each be housed in their own Moose role under Euler/001.pm, Euler/002.pm, etc. The app that will run will take a problem, or problems, as args, load the moose role at runtime, and then call some kind of _solve on each role that it has loaded. The base class will handle all the information and anything else that is needed and the idea of the 001.pm would be to have only the method _solve and that method returns only the correct answer. One item I would like to incorporate is creating things like 001a.pm and 001b.pm and then have the option to choose the "correct" (most efficient) one to run or to run them all. I am not sure if marking the "correct" one would be a manual process (renaming the "correct" to XXXa.pm) or if that is something I will want to build into the framework (store the profiling results each time and then pull out the best one).
I have some other ideas also but mostly I just want to play with some new(ish) perl stuff and get my brain thinking about math again. Just wanted to post an intro blog to also get me up on this new fan-dangled blog. Also, a big thanks to the fine folks who set up blogs.perl.org. ¡Mucho Mahalo!
Follow along at home: http://github.com/wtgee/Euler
I blog about Perl.
http://github.com/Abigail/ProjectEuler
I started doing the Project Euler problems a little while ago, but quickly grew frustrated. The first few are easy enough, but after that, each one seems to rely on some obscure bit of mathematical trivia necessary to avoid brute-forcing it. Not being a math guy, I found the "easy" ones beyond the first few completely impenetrable. I just don't have the brain for that kind of stuff, and don't know how to get it, and find it frustrating to the point of emotional distress. :(
Mike: I think the point of Project Euler is that it's a math challenge, not a trivial program challenge. Each time I solved a problem using brute force, it felt like cheating.
Yes, I have flipped through some of the later ones but never really applied any mental energy to them so we will see how it goes. I could easily understand getting to that frustration point. Part of my idea was to help me get back into math, so I suppose maybe it is good to go that route, although really esoteric math trivia might not be the best way to get "back into math."
Abigail: Thanks for the link to the github, now I can also double-check my findings easier. ;)
First a note about project Euler. The problems are chosen so that they can finish in a minute in a wide variety of programming languages. Some are meant to be solved by brute force. If a brute force solution works in the desired time, there is no need to feel bad about it.
That said, I really want to insist that there are fewer tricks in Project Euler problems than most people think. There are some - for instance without knowing about continued fractions and Pell's equation you're going to have no luck with problem 66. It is also true that many Project Euler problems you haven't figured out seem obscure, even after you see the solution given.
However most of the "tricks" are fairly straightforward techniques that you are probably unfamiliar with. They are good to have in your repertoire.
For example mNY of the problems are amenable to solution by dynamic programming techniques. For a random example look at problem 215. Brute force won't work since there are roughly 800 trillion solutions. However dynamic programming can work in 2 different ways, and both can solve it in reasonable time.
One solution is to calculate all possible rows, and then use dynamic programming to solve W(32, 1), W(32, 2), ... , W(32, 10).
The other solution is to work across looking at the exposed pattern made by a vertical cut. In a solution at position 2 you can only have the patterns 0101010101 and 1010101010. And ditto at position 30. Now how does that pattern change as you move over 1 horizontally? Well every number decreases by 1 except 0s which can turn into a 1 or a 2. (If you put a 3x1 brick then move over 1, you have 2 more squares exposed.)
Now you look at the function paths_to($n, $pattern) representing "the number of ways to get to position n and end up at pattern $pattern." This is a recurrence relation with several thousand variables, a known starting condition at $n == 2 (there is 1 way to get to 2 possibilities and none to any other), and the answer you want is paths_to(30, "0101010101") + paths_to(30, "1010101010").
Anyways the ins and outs of this particular problem aren't that important. What is important is that if you internalize the ideas of dynamic programming, you'll be able to solve a lot of PE problems. And conversely if you look at solutions to PE problems you won't just say, "That's a clever trick" but instead you'll just notice it is a standard DP problem and know how to do it.
Now how obscure is dynamic programming? It depends on what you do. If you're just throwing together web pages, you'll be unlikely to run into any DP problems in practice. But if your job involves a lot of optimization problems, you'll just think of it as a standard programming technique that everyone should know.
http://github.com/notbenh/euler_bench -- add your solutions in perl 5 or perl 6 and help the parrot developers track their progress on improving performance!