Learning D With Project Euler

D is a systems programming language. Its focus is on combining the power and high performance of C and C++ with the programmer productivity of modern languages like Ruby and Python. Special attention is given to the needs of quality assurance, documentation, management, portability and reliability.

Project Euler is a website dedicated to a series of math problems intended to be solved with computer programs. Each problem has been designed according to a "one-minute rule", which means that an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

In this article, I pick some problems and show you how to solve them with D.

• I choose only easiest ones because published solution could spoil the problem.
  
• The purpose is to demonstrate the feature and power of D, so the codes below may not be the best way to solve those problems.

Before We Start

First, we need a D compiler.
All the examples below use dmd 2.0.32, you can download it from the official website.
Extract the compiler from the zip file and try compiling the "Hello World" program:

//helloworld.d import std.stdio; void main() { writeln("Hello, world!"); }

If you are using Windows, simply run something like this:

C:\dmd2\windows\bin\dmd.exe helloworld.d
helloworld.exe

Problem 1

Let's start with Problem 1

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.

It's very easy, and the answer is:

$\sum _{i=1}^{\left\lfloor {\frac {999}{3}}\right\rfloor }3i+\sum _{i=1}^{\left\lfloor {\frac {999}{5}}\right\rfloor }5i-\sum _{i=1}^{\left\lfloor {\frac {999}{15}}\right\rfloor }15i$

This equation can be solved with a pencil and paper. Eh... wait a minute. We are talking about the programming language here, aren't we?
Maybe it's better to start with a common method that everybody uses at his first attempt:

//problem1_a.d import std.stdio; void main() { int sum = 0; for (int i = 1; i < 1000; ++i) { if (i % 3 == 0 || i % 5 == 0){ sum += i; } } writeln(sum); }

Yes, this is exactly what I did when I solved the first problem.
If I were more familiar with D at that time, it would look like:

//problem1_b.d import std.stdio; void main() { int sum; foreach (i; 1..1000) { if (i % 3 == 0 || i % 5 == 0){ sum += i; } } writeln(sum); }

There are 2 differences from the first version:

1. The foreach statement, it is not only terser, but also faster.

   The speed is negligible here, but you will find it saves about 10% time when tested with 1×10⁸ instead of 1000

2. In D, int sum is initialized with 0 by default.

   In case you really, really don't want it be initialized, use int sum = void;

D2's standard library, Probos, also provide a powerful algorithm module that make it possible to do it with one-liner.

//problem1_c.d import std.stdio, std.algorithm, std.range; void main() { writeln( reduce!("a + b")(0, filter!("a % 3 == 0 || a % 5 == 0")(iota(1, 1000, 1))) ); }

It's not as fast as the second version (problem1_b.d), but it's faster than the corresponding program written in other language like python or haskell.
If you have no idea what these functions mean, here is a brief explanation:

• !( ... )

  Template argument are enclosed with !(...) instead of <...>. Foo!(int) in D is equal to Foo<int> in C++.

• reduce!("a + b")(0, range);

  sum the elements in the range and return a number.

• filter!("a % 3 == 0 || a % 5 == 0")(range);

  find all elements in the range that meet the requirements and return a new range.

• iota(begin, end, step);

  construct a range that goes through the numbers begin, begin + step, begin + 2 * step, ..., up to and excluding end.

Give alias to these functions will make the code more readable.

auto numbers = iota(1, 1000, 1); alias filter!("a % 3 == 0 || a % 5 == 0", typeof(numbers)) filter1; alias reduce!("a + b") sum; writeln( sum(0, filter1(numbers)) );

Check these pages at official website for more information.
algorithm, template, template comparison between D and C++

Problem 2

Problem 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:
    1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.

This one-liner functional solution is split into several lines so I can write some comments in it:

//problem2_a.d import std.stdio; import std.algorithm; import std.range; void main() { writeln( reduce!("a + b")( // the sum of all filter!("(a&1) == 0")( // the even-valued terms until!("a >= 4000000")( // which do not exceed four million recurrence!("a[n-1] + a[n-2]")(1, 2) // a Fibonacci sequence starting with 1 and 2 ) ) ) ); }

It's a bad practice to calculate the fibonacci sequence with straight recursion, and it's even worse when recursion is also used to sum the sequence.

//problem2_b.d import std.stdio; int fib(int n) { if (n < 3) { return n; } else { return fib(n - 2) + fib(n - 1); } } int sumFib(int bound, int n = 1) { if (fib(n) > bound) { return 0; } else if (fib(n) & 1) { return sumFib(bound, n + 1); } else { return sumFib(bound, n + 1) + fib(n); } } void main() { writeln(sumFib(4_000_000)); }

If you run this program, fib() will be called 35563510 times before it gets the result.
This number is totally unacceptable because there are only 32 elements in the sequence below 4,000,000.

But it's amazing to see the program can be improved greatly when changed to template recursion.

//problem2_c.d import std.stdio; import std.metastrings; template fib(int n) { static if (n < 3) { const fib = n; } else { const fib = fib!(n - 2) + fib!(n - 1); } } template sumFib(int bound, int n = 1) { static if (fib!(n) > bound) { const sumFib = 0; } else static if (fib!(n) & 1) { const sumFib = sumFib!(bound, n + 1); } else { const sumFib = sumFib!(bound, n + 1) + fib!(n); } } pragma (msg, ToString!( sumFib!(4_000_000) )); void main(){}

The algorithm is exactly the same. But theses changes make everything done during compilation.

• if -> static if
• return -> const
• writeln(...) -> pragma (msg, ...)

It's much better than the original version because the compiler compile each fib!(n) only once (1 ≤ n ≤ 33).
The compiler output the result directly and there is no need to run the program at all.

Problem 22

Problem 22 is chosen because it's the first problem that requires file and string operations:

Using names.txt, a 46K text file containing over five-thousand first names, 
begin by sorting it into alphabetical order. Then working out the alphabetical 
value for each name, multiply this value by its alphabetical position in the 
list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is 
worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list.
So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

import std.stdio, std.string, std.algorithm; void main() { string input = cast(string)std.file.read("names.txt"); auto words = split(input, ","); sort(words); int score(string s) { // a nested function return reduce!("a + b - 64")(0, s[1..length-1]); // remove quotation marks and calculate the alphabetical value } long sum; foreach (i; 0..words.length) { sum += (i + 1) * score(words[i]); } writeln(sum); }