Thread: Speeding Up This Program

I'm just messing around with one of those Online Submission Sites, and I need help speeding up my code because I'm running into their 1 second Run-Time wall (just barely).

The program reads two input files. 1 input file is a dictionary file of about 5000 words. The second input file is the input given by the "grader".

Here is the full description of the program:

Among the large Wisconsin cattle ranchers, it is customary to brand cows with serial numbers to please the Accounting Department. The cow hands don't appreciate the advantage of this filing system, though, and wish to call the members of their herd by a pleasing name rather than saying, "C'mon, #4734, get along."

Help the poor cowhands out by writing a program that will translate the brand serial number of a cow into possible names uniquely associated with that serial number. Since the cow hands all have cellular saddle phones these days, use the standard Touch-Tone(R) telephone keypad mapping to get from numbers to letters (except for "Q" and "Z"):

2: A,B,C 5: J,K,L 8: T,U,V
3: D,E,F 6: M,N,O 9: W,X,Y
4: G,H,I 7: P,R,S

Acceptable names for cattle are provided to you in a file named "dict.txt", which contains a list of fewer than 5,000 acceptable cattle names (all letters capitalized). Take a cow's brand number and report which of all the possible words to which that number maps are in the given dictionary which is supplied as dict.txt in the grading environment (and is sorted into ascending order).

For instance, the brand number 4734 produces all the following names:

GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI
GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI
GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI
HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI
HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI
IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI
ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI

As it happens, the only one of these 81 names that is in the list of valid names is "GREG".

Write a program that is given the brand number of a cow and prints all the valid names that can be generated from that brand number or ``NONE'' if there are no valid names. Serial numbers can be as many as a dozen digits long.

PROGRAM NAME: namenum
INPUT FORMAT
A single line with a number from 1 through 12 digits in length.
SAMPLE INPUT (file namenum.in)
4734

OUTPUT FORMAT
A list of valid names that can be generated from the input, one per line, in ascending alphabetical order.
SAMPLE OUTPUT (file namenum.out)
GREG

I can get through their first 8 Tests without any problems, but when I run the 9th Test (Input: 26678268463) I get the timeout error from the website. It sometimes happens to the 3rd Test, but usually not. What can I do to increase speed? I've already made a few changes, but I'm out of ideas.

import java.io.*;
import java.util.ArrayList;
 
 
public class namenum
{
	static ArrayList<String> dictList = new ArrayList<String>();
 
	static Reference[] index = new Reference[10];
 
    public static void main(String args[]) throws Exception
    {
    	FileReader reader = new FileReader("namenum.in");
		BufferedReader in = new BufferedReader(reader);
		FileReader reader2 = new FileReader("dict.txt");
		BufferedReader dict = new BufferedReader(reader2);
		FileWriter writer = new FileWriter("namenum.out");
		PrintWriter out = new PrintWriter(writer);
 
		index[2] = new Reference("A","B","C");
		index[3] = new Reference("D","E","F");
        index[4] = new Reference("G","H","I");
		index[5] = new Reference("J","K","L");
		index[6] = new Reference("M","N","O");
		index[7] = new Reference("P","R","S");
		index[8] = new Reference("T","U","V");
		index[9] = new Reference("W","X","Y");
 
		boolean any = false;
 
		String line = in.readLine();
		String[] letters = new String[line.length()];
		for(int i=0;i<line.length();i++)
		{
			letters[i] = line.substring(i,i+1);
		}
 
		String lineDict = dict.readLine();
		while(lineDict!=null)
		{
			if(lineDict.length() == letters.length)
				dictList.add(lineDict);
			lineDict = dict.readLine();
		}
 
		int results = (int)Math.pow(3,line.length());
 
		int[] spots = new int[letters.length];
		for(int i=0;i<spots.length;i++)
		{
			spots[i] = 0;
		}
 
		for(int i=0;i<results;i++)
		{
			String val = "";
			for(int x=0;x<letters.length;x++)
			{
				Reference ref = index[Integer.parseInt(letters[x])];
				String letter1 = ref.let1;
				String letter2 = ref.let2;
				String letter3 = ref.let3;
 
				if(spots[x]==0)
					val += letter1;
				else if(spots[x]==1)
					val += letter2;
				else if(spots[x]==2)
					val += letter3;
			}
			for(int x=0;x<dictList.size();x++)
			{
				String v = dictList.get(x);
				if(v.equals(val))
				{
					any = true;
					out.println(val);
				}
			}
			spots[spots.length-1]++;
			for(int x=spots.length-1;x>-1;x--)
			{
				if(spots[x]>=3 && x>0)
				{
					spots[x-1]++;
					spots[x]=0;
				}
			}
		}
		if(!any)
			out.println("NONE");
 
		out.close();
    }
 
    public static class Reference
    {
    	String let1;
    	String let2;
    	String let3;
 
    	public Reference(String v1, String v2, String v3)
    	{
    		let1 = v1;
    		let2 = v2;
    		let3 = v3;
    	}
    }
 
 
}

With respect to simply speeding the code up (don't have time right now to read the full problem): but you can speed it up a bit by using Set instead of ArrayList for dictList. How much it speeds it up depends upon the size of the dictList of course. Its always best to profile your code and print out the time it takes for the calculations, finding the bottleneck and working with that.

Originally Posted by helloworld922

What website is this? I'm interesting in giving it a go

USACO Training Program Gateway

My teacher last year introduced us to this to prepare us for a High School Programming Contest.