AddAGram

gistfile1.java

import java.util.*;
import java.io.*;
public class AddAGram{
	public static Vector<String>dic[];
	public static Stack<String>s;
	public static HashSet<String>vis=new HashSet<String>();
	public static boolean check(char []l,char []s){
		int i,j,len=l.length;
		for(i=0;i<s.length;i++)
			for(j=0;j<l.length;j++)
				if(s[i]==l[j]&&l[j]!=0) {s[i]=0;l[j]=0;len--;}
		if(len==1) return true;
		return false;
	}
	static void addAll(String str){
		int l=str.length()-1,tot=dic[l].size();
		String other="";
		for(int i=0;i<tot;i++){
			other=dic[l].elementAt(i);
			if(check(str.toCharArray(),other.toCharArray())&&!vis.contains(other))
				s.push(other);
		}
	}
	static char diff(String small,String large){
		StringBuffer sb=new StringBuffer(large);
		for(int i=0;i<small.length();i++)
			sb=sb.deleteCharAt(sb.indexOf(String.valueOf(small.charAt(i))));
		return sb.charAt(0);
	}
	public static void generateOriginal(String start,String end){
		LinkedList<String>list=new LinkedList<String>();
		for(String a:vis) list.add(a);
		String next="",prev=start;
		list.remove(start);
		int k,j=end.length();
		for(int i=4;i<=j;){
			for(k=0;k<list.size();k++){
				if(list.get(k).length()==i){
					if(check(list.get(k).toCharArray(),prev.toCharArray())){
						next=list.remove(k);i++;
						System.out.println(prev+"+"+diff(prev,next)+"="+next);
						prev=next;break;
					}
				}
			}
		}
	}
	public static void main(String args[]) throws Exception{
		dic=new Vector[30];
		String str;int i,j,k;
		for(i=0;i<30;i++) dic[i]=new Vector<String>();
		InputReader sc=new InputReader(new FileInputStream("WORD.LST"));
		long init=System.currentTimeMillis();
		while(!sc.isExhausted()){
			str=sc.readLine();dic[str.length()].add(str);
		}
		int z=0;
		String word="",tmp="";Vector<String>v;
		for(i=29;i>2;i--){
			v=dic[i];
			for(z=0;z<v.size();z++){
				word=v.elementAt(z);
				s=new Stack<String>();
				vis.clear();
				s.push(word);
				while(!s.empty()){
					tmp=s.pop();
					addAll(tmp);
					vis.add(tmp);
					if(tmp.length()==3) {
						generateOriginal(tmp,word);
						System.out.println("Time taken : "+(System.currentTimeMillis()-init));
						return;
					}
				}
			}
		}
	}
}

class InputReader{
	private boolean finished = false;
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int peek() {
		if (numChars == -1)
			return -1;
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				return -1;
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar];
	}

	public static boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private String readLine0() {
		StringBuffer buf = new StringBuffer();
		int c = read();
		while (c != '\n' && c != -1) {
			if (c != '\r')
				buf.appendCodePoint(c);
			c = read();
		}
		return buf.toString();
	}

	public String readLine() {
		String s = readLine0();
		while (s.trim().length() == 0)
			s = readLine0();
		return s;
	}

	public String readLine(boolean ignoreEmptyLines) {
		if (ignoreEmptyLines)
			return readLine();
		else
			return readLine0();
	}

	public boolean isExhausted() {
		int value;
		while (isSpaceChar(value = peek()) && value != -1)
			read();
		return value == -1;
	}
}