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?
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