Skip to content

Instantly share code, notes, and snippets.

@bknarendra
Created June 5, 2012 15:49
Show Gist options
  • Save bknarendra/2875863 to your computer and use it in GitHub Desktop.
Save bknarendra/2875863 to your computer and use it in GitHub Desktop.
AddAGram
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment