Saturday, July 13, 2013

Problem 42


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 + 12;
    }

    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 = ((intcapitalized64;
        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");
    }
}

No comments:

Post a Comment