On solving Project Euler - Part 1

For those of you who have never heard about it, Project Euler is a website publishing almost every week new programming and mathematical challenges. It has been almost one year since I discovered it, and I must tell that I have really become addicted to it.
I would recommend it to any programmer who do not hate mathematics, as it can be used for several purposes: challenging your mathematical and programming skills, learning new mathematics concepts, and it is especially a good practice for learning a new programming language. Of course, it won't help you to become better at designing software, but it might help help you to improve your algorithm writing skills.

As I said, both mathematical and programming skills are needed to solve Project Euler problems. While some of them might be solved with just a simple brute force algorithm, or on the opposite, with a clever formula, most of the problems will require to use both your mathematical and algorithm implementation skills.

On the listing page, the problems are ordered by publishing date. Usually, trying to solve them in this order is better, as concepts introduced in older problems are often reused in newer problems, and it will make them easier to solve than just starting from zero.
The listing can also be sorted by the difficulty of the problems (you will need to register), which is determined by the number of people who solved them: indeed, once you solved a problem, you can input your answer in a form and verify if it is correct. In the case it is, you will then be able to access the forum thread of this problem, where people usually post their solution. This is a very interesting feature of Project Euler, because you can see what are the other algorithms that can be used, in several programming languages.

We could also classify the problems in different categories based on how they can be solved, and what are the most efficient languages to solved them.

A first category could be the one of problems which can be solved by implementing the obvious algorithm transcribed from the problem itself. An important point that I didn't mention before is that all the problems have been designed according to a "one-minute rule", meaning that there always exist an algorithm that can solve the problem in less that one minute even on modest hardware. Although this rule will usually lead you to rethink your first (slow) brute-force algorithm in order to make your solution comply to it, some problems can just be brute-forced as I said before.

The problem 1 is a nice and simple example from this category:

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.

An obvious brute-force algorithm in Ruby could be:

This simple algorithm comply with the one-minute rule, but might not scale well for bigger values, for which we might need a better algorithm or formula. In same same naive way, the following Clojure code gives the answer to the problem 6:

This problem can also be solved with the following Factor code:

We will see in the next posts the other categories of challenges available on Project Euler, and the way to solve them efficiently. Indeed, implementing brute-force algorithms is not the real fun of Project Euler, and is really not what you need to improve your problem solving skills!

As an exercise, you can try to solve the problem 187, which seem simple to solve with a naive brute-force algorithm, but there is little chance that it complies with the one-minute rule!
A more clever algorithm can solve this problem in seconds, and a more advanced one can solve it in an instant...

Takeshi's Komanechi University Mathematics

I suppose some of you might already know Takeshi Kitano as a filmmaker, who shot great movies like Sonatine and Kikujiro.

Here in Japan, he is very famous, but not for his movies. More that a filmmaker, he is popular as a comedian and appears a lot on TV, know as Beat Takeshi.

But what you might not know, even living in Japan, is the Math Kitano the mathematician. Indeed, during his childhood, Takeshi's mother was very strict concerning education. He went to the renown Meiji University and usually says that he would have liked to become a mathematician if he didn't become a comedian.

This passion for mathematics gave birth in 2006 to the TV program "Takeshi's Komanechi University Mathematics" (たけしのコマネチ大学数学科).
Aired every Thursday between 25:15 and 25:45 on Fuji Television, this program aims at showing the charm of mathematics while being as well an entertainment program.
Every week, three teams are trying to solve a problem (of university entry level): Takeshi, aka "Math Kitano", two pretty student girls from Tokyo University, and a a group of four comedians.

Surprisingly, Math Kitano performs very well and sometimes outperforms Tokyo University students, especially in geometry related problems, which must be one of the reasons why the way he shots his movies is so geometric.
On the other side, the team of four comedians always use very weird but funny ways to solve problems, and it is quite enjoying to watch, even from a mathematician point of view.

After discovering this TV program, I just became addicted, and found myself solving these problems every week. I think this is one good way to keep one's mathematics abilities, and I would recommend it to any people living in Japan.

To give you a taste of it, here is a link the some problems on my Picasa galleries:

たけしのコマネチ大学数学科

And here's a link to a YouTube search results page.

I hope I will find some time solve problems in the next posts.

Think twice before naming your new programming language

Smart people invent new programming languages, with powerful features, that perform really well. What else do we need?

When you want to learn and use these new programming languages, you might want to buy books or to search for tutorials, code examples, blog articles, etc.

There comes the name: you might have plenty of good reasons for choosing a certain name for your programming language, but before deciding on it please think about people who are willing to use it.

I am one of those: recently, I am learning the Factor and J programming languages, or I should say "I am trying to learn". I suppose that you can imagine my frustration when I try to search for information using Google, or for books using Amazon.

Just think about what kind of results you will get when looking for something related to Factor on Google...

Of course you could tell me that there is the Factor documentation. But I don't want to limit myself to the official documentation: I want to read books if they exist, I want to read code snippets shared by other people, I want to read blog posts, search on GitHub (Factor is not registered yet), and the reality is that I just can't. This is so frustrating, especially for language such as J, which are even more difficult to search for, and I don't need to explain you why...

Some work have been done to make C and C++ easy to search on the internet, but nothing yet for J yet. I think the same goes for R, and if I read this wiki page, it seems that I could quote almost the whole alphabet!

So please, I beg you, the next time you create a great programming language such as Factor or J, think carefully about a name that will be easy to search for on the internet. Do not use a one-character or two-character name, only use characters from the Latin alphabet, do not use a common word, and just make it as unique as possible.