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

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?

Posted by Kristian

8 comments

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
        }

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

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)

You can pre-calculate the table for triangle numbers if you want. Something like this:

max_triagle_index = int(
    math.floor(math.sqrt(max(map(len, word_list)) * 26 * 2)) + 1
)
triangle_numbers = {
    (n + 1) * n / 2
    for n in range(1, max_triagle_index + 1)
}

I don’t know if this is likely to speed things up for you or not, but you calculate one square root for the whole set, and instead get a set lookup into n items.

Carl Appellof

I always hate using floating point functions when solving integer problems unless it really speeds things up. In C++ to test for a triangle number, I just used the brute force method, adding another row of billiard balls to the total until the total is greater than or equal to the test number.

bool IsTriangular(int num)
{
int total = 1;
for (int i = 2; total < num; ++i)
{
total += i;
}
return (num == total);
}

Sure, I could have pre-calculated an array of triangle numbers "big enough", but for such small numbers, I think brute force is good enough.

Took 0.08 ms on my system after reading the entire words file into memory.

Jean-Marie Hachey

Our list of common English words contains 162 triangle words…
The smallest triangle word is A … what is the biggest one in that list ?

Triangular number
https://en.wikipedia.org/wiki/Triangular_number

Nombre triangulaire
https://fr.wikipedia.org/wiki/Nombre_triangulaire

OEIS triangular numbers
Triangular numbers: a(n) = binomial(n+1,2) = n(n+1)/2 = 0 + 1 + 2 + … + n.
https://oeis.org/A000217

Jean-Marie Hachey

Biggest triangle word in our list: CONSTRUCTION, t(n) =171
I found the word with word processing and basic functions in a spreadsheet.
(Word and Excel)

Leave a Reply