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.
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?
/**
*
* @author Umang
* started at : 13/07/2013 09:01 PM
* completed at : 9:26 PM
*/
import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Problem42
{
private static HashMap<Integer, Long> triangleValues;
private static int countedTill = 0;
static
{
triangleValues = new HashMap<>();
}
private static long calcuateTriangleNumber(int no)
{
return no * (no + 1) / 2;
}
public static long getTriangleNumber(int no)
{
long triangleNumber = 0;
if (no >= countedTill)
{
int i = 0;
for (i = countedTill; i <= no; i++)
{
triangleNumber = calcuateTriangleNumber(no);
triangleValues.put(no, triangleNumber);
}
countedTill = i;
}
else
{
triangleNumber = triangleValues.get(no);
}
return triangleNumber;
}
private static boolean isTriangleNumber(long no)
{
boolean isTriangleNumber = false;
long triangleNumber = 0;
int i = 0;
do
{
triangleNumber = getTriangleNumber(i);
if (triangleNumber == no)
{
isTriangleNumber = true;
break;
}
i++;
}
while (no >= triangleNumber);
return isTriangleNumber;
}
private static String getFileContent()
{
StringBuilder content = new StringBuilder("");
File aFile = new File("D:/words.txt");
Scanner aScanner = null;
try
{
aScanner = new Scanner(aFile);
}
catch (FileNotFoundException ex)
{
System.out.println("File could not be readed");
ex.printStackTrace();
System.exit(0);
}
while (aScanner.hasNextLine())
{
content = content.append(aScanner.nextLine());
}
return content.toString();
}
private static LinkedList<String> getWordList()
{
LinkedList<String> result = new LinkedList<>();
String content = getFileContent();
StringTokenizer lineTokenizer = new StringTokenizer(content, ",\"");
while (lineTokenizer.hasMoreTokens())
{
result.add(lineTokenizer.nextToken());
}
return result;
}
private static int getCharNo(char character)
{
int charNo = 0;
char capitalized = Character.toUpperCase(character);
charNo = ((int) capitalized) - 64;
return charNo;
}
private static long getValueFromString(String str)
{
long count = 0;
for (int i = 0; i < str.length(); i++)
{
count += getCharNo(str.charAt(i));
}
return count;
}
public static void main(String args[])
{
int triangleNumberCount = 0;
LinkedList<String> wordList = getWordList();
for (String word : wordList)
{
if (isTriangleNumber(getValueFromString(word)))
{
triangleNumberCount++;
}
}
System.out.println("There are " + triangleNumberCount + " triangle numbers");
}
}
|
