Project Euler 42: How many triangle words does the list of common English words contain?

Written by on 15 May 2011

Topics: Project Euler

Problem 42 of Project Euler presents us with a new string manipulation problem. The problem asks us the following

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

The actual input file can be found in the problem description at the Project Euler Website.

The input file has the same structure as found in Problem 22 and we also need to sum up each word, which we also did in Problem 22 so the bread and butter of the problem is already solved. The new part of this problem is to check if it is a triangle number.

To solve that part we can use inverse functions. So lets find the inverse function of t = f(n) = n(n+1) / 2.

This is a quadratic function on the form

with a = 1, b = 1 and c = -2t

with the discriminant

This gives us the two solutions

Since we know that t , n > 0 we can disregard one solution which means that in order to check if a word is a triangle number we need to check

is an integer and t is the word value.

That can be done with the following bit of C# code

int result = 0;
string[] words = readInput(filename);

for(int i = 0; i < words.Length; i++){
    double wordsum = (Math.Sqrt(1+8*sum(words[i])) - 1.0) / 2.0;
        if (wordsum == ((int)wordsum)) {
            result++;
        }
}

which gives the result

There are 162 triangle words
Solution took 1 ms

Wrapping up

The problem was rather easy to solve as most of the code was already written in an earlier solution. I think I will just finish this post with a link to the source code for the problem.

Did you solve the problem differently?

3 Comments For This Post I'd Love to Hear Yours!

  1. David A says:

    This is what I had. I got the solution in 6ms – fast, but 6 times slower than your algorithm. By the way, the only reason why I am using lambda expressions is because I’m trying to get used to using it (Is there any performance downgrade?).

    [STAThread]
            static void Main(string[] args) {
                #region Timing and Displaying
                Stopwatch stopwatch = Stopwatch.StartNew();
                #endregion Timing and Displaying
                string s = File.ReadAllText(@"C:\Users\David\Downloads\words.txt");
                s = s.Substring(1, s.Length - 2);
                string[] names = s.Split(new string[] { "\",\"" }, StringSplitOptions.RemoveEmptyEntries);
                List<int> list = Enumerable.Range(0, 26).ToList();
                list.ForEach(x => list[x] = x == 0 ? 1 : x + 1 + list[x - 1]);
                int[] triangleNumbers = list.ToArray();
                Func<int, string> ValueOfString = x => {
                    int sum = 0;
                    foreach(char c in x)
                        sum += c - 64;
                    return sum;
                };
                Func<bool, int> IsTriangleNumber = x => Array.BinarySearch(triangleNumbers, x) >= 0;
                int count = 0;
                foreach (var name in names)
                    if (IsTriangleNumber(ValueOfString(name)))
                        count++;
                var answer = count;
                #region Timing and Displaying
                stopwatch.Stop();
                Clipboard.SetText(answer.ToString());
                Console.WriteLine(answer.ToString() + " in " + stopwatch.ElapsedMilliseconds + " ms.");
                Console.ReadKey(true);
                #endregion Timing and Displaying
            }
  2. Kristian says:

    Hi David

    I have been looking at your code and on my computer it runs in 2ms vs. 1ms on for my own algorithm, and I don’t think anything can be said about one being fast when we are in such small timings.

    I can see the majority of the time is being spent reading the input file and outputting the result, and there is nothing we can do about that.

    The only thing I could recommend was to add a little more white space here and there, I think that would increase the readability of the code.

    /Kristian

  3. Darren says:

    One way to test whether a number n is a triangle number without solving the quadratic equation is to see whether

    2*n = int(sqrt(2*n)) * (int(sqrt(2*n))+1)
    

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.