Project Euler

Problem 42: Coded Triangle Numbers

The n^th term of the sequence of triangle numbers is given by, t_n = 0.5n(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 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

The Catch

How to check if a number is a triangle numbers.
How to find the value of a word.

The Light

Since a triangle number t is formulated by t_n = 0.5n(n+1), any number that satisfies the inverse of this equation is a triangle number.

t = 0.5*n(n + 1)
0 = 0.5*n(n + 1) - t
0 = n(n + 1) - 2t
0 = n² + n - 2t

Use quadratic formula to solve for n:
n = (-1 + sqrt(1 + 8t))/2
n = (-1 - sqrt(1 + 8t))/2
Since n > 0 (given), the second solution is eliminated. A number t is a triangle number if it makes the first solution an integer.

Use the discussion in Problem 22 to find the value of a word based on their letters' position on the alphabet. Also, use Java's Scanner class to read input from words.txt file.

The Code

import java.util.*;
import java.io.*;

public class Problem42
{
  public static void main(String[] args) throws FileNotFoundException
  {
    Scanner scan = new Scanner(new File("words.txt"));
    int count = 0;

    String input = scan.nextLine();
    String[] s = input.split(",");

    for(int i = 0; i < s.length; i++)
    {
      String word = s[i].substring(1, s[i].length() -1);
      int t = value(word);
      double n = (Math.sqrt(1 + 8 * t) - 1) / 2.0;
      if( n == (int)n )
        count++;
    }

    System.out.println("Total number of triangle words : " + count);    
  }

  public static int value(String word)
  {
    int result = 0;
    int A = (int)'A';
    char[] c = word.toCharArray();

    for(int i = 0; i < c.length; i++)
    {
      int position = (int)c[i] - A + 1;
      result += position;
    }
    return result;
  }
}