Problem 42 in Project Euler provides a list of some 2000 English words and requires us to find the number of triangle words. I went about in a simple straight forward way attempting this one. A class TriangleNumbers keeps a sorted list of all the triangle numbers. A static method in EnglishWord class returns the word value for the given word. This number is checked for validity.
Obviously, new triangle numbers are only computed when the word value is greater than the last known triangle number. An implementation in Java is provided below:
The EnglishWord class:
package pba.text;
/**
* A class which allows manipulations with the English Words
*
* @author AnuvratSingh
*/
public class EnglishWord {
/**
* Returns the numerical value of a word which is found by summing the alphabetical position of each character in
* the word. For example, the word value for SKY is 19 + 11 + 25 = 55
*
* @param word the word whose numerical value is required
* @return the numerical value of the given word
*/
public static int getNumericalValue(String word) {
String lowerCaseWord = word.toLowerCase();
int sum = 0;
for (int i = 0; i < lowerCaseWord.length(); i++)
sum += lowerCaseWord.charAt(i) - 'a' + 1;
return sum;
}
}
The TriangleNumbers class:
package pba.number;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* The n^(th) term of the sequence of triangle numbers is given by, t_(n) = ½n(n+1); so the first ten triangle numbers
* are: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
*
* @author AnuvratSingh
*/
public class TriangleNumbers {
/**
* The list of all triangle numbers in ascending order. The order is not enforced, but required at certain places.
*/
private List<Integer> m_triangleNumbers;
/**
* The last number which has been added to the list.
*/
private int m_lastNumber;
/**
* The index of the last number which has been inserted.
*/
private int m_lastIndex;
public TriangleNumbers() {
m_triangleNumbers = new ArrayList<Integer>();
m_lastIndex = 0;
m_lastNumber = 0;
}
/**
* Builds the list of triangle numbers
*
* @param looseUpperBound The upper bound to which the list is to be created. Loose implies that the last number to
* be inserted into the list will be equal to or just greater than the upper bound specified
* @return true if the upper bound is a triangle number itself, false otherwise
*/
private boolean buildTriangleNumbers(int looseUpperBound) {
while (m_lastNumber < looseUpperBound) {
m_lastNumber += ++m_lastIndex;
m_triangleNumbers.add(m_lastNumber);
}
return m_lastNumber == looseUpperBound ? true : false;
}
/**
* Check if the given number is a triangle number or not.
*
* @param number The number for which the condition needs to be verified
* @return true if the given number is a triangle number, false otherwise
*/
public boolean checkForTriangularNumberProperty(int number) {
if (number > m_lastNumber)
return buildTriangleNumbers(number);
return Collections.binarySearch(m_triangleNumbers, number) >= 0 ? true : false;
}
}
The main method:
package problems_40_50;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import pba.number.TriangleNumbers;
import pba.text.EnglishWord;
public class Problem_42 {
private static final String fileName = "problem_42.in";
public static void main(String[] args) throws IOException {
TriangleNumbers tn = new TriangleNumbers();
// Read all the words into a String array
BufferedReader bufferedReader = new BufferedReader(new FileReader(Problem_42.fileName));
String[] words = bufferedReader.readLine().split("\",\"");
// Correct the first and the last word which have "
int numberOfTriangleWords = 0;
words[0] = words[0].substring(1);
int numberOfWords = words.length;
String lastWord = words[numberOfWords - 1];
words[numberOfWords - 1] = lastWord.substring(0, lastWord.length() - 1);
// Check the condition for each word
for (String word : words)
if (tn.checkForTriangularNumberProperty(EnglishWord.getNumericalValue(word)))
numberOfTriangleWords++;
System.out.println(numberOfTriangleWords);
}
}
Popularity: 11% [?]
Related posts:
