CodeEval - Chardonnay or Cabernet - Easy

import sys

test_cases = open(sys.argv[1], 'r')
for test in test_cases:
    test=test.split(" | ")
    word=test[1]
    word_char=[0]*26
    for x in word.lower():
        if x.isalpha():
            word_char[ord(x)-ord('a')] += 1
    wine_list=test[0].split()
    sol_list=[]
    for wine in wine_list:
        wine_chars=[0]*26
        for x in wine.lower():
            if x.isalpha():
                wine_chars[ord(x)-ord('a')] += 1
        listed=True
        for i in range(len(wine_chars)):
            if wine_chars[i] < word_char[i]:
                listed=False
                break
        if listed:
            sol_list.append(wine)
    sol=""
    for i in range(len(sol_list)):
        if i>0 :
            sol += " "
        sol += sol_list[i]
    if sol:
        print sol
    else:
        print False

test_cases.close()

CodeEval - Play with DNA - Hard

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws FileNotFoundException, IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb=new StringBuffer();
        String line;
        while ((line = in.readLine()) != null) {
            StringTokenizer st=new StringTokenizer(line);
            String pattern=st.nextToken();
            int allowedMiss=Integer.parseInt(st.nextToken());
            String str=st.nextToken();
            LinkedList<Pattern> list=new LinkedList<Pattern>();
            StringBuilder strb=new StringBuilder();
            for(int i=0;i<pattern.length()-1;i++){
                strb.append(str.charAt(i));
            }
            for(int i=pattern.length()-1;i<str.length();i++){
                 strb.append(str.charAt(i));
                 int dist=levenshteinDistance(pattern, strb.toString());
                 if(dist<=allowedMiss){
                     list.add(new Pattern(dist, strb.toString()));
                 }
                 strb.deleteCharAt(0);
            }
            Collections.sort(list);
            boolean first=true;
            while(!list.isEmpty()){
                if(!first){
                    sb.append(' ');
                }
                sb.append(list.remove().getPattern());
                first=false;
            }
            if(first){
                sb.append("No match");
            }
            sb.append('\n');
        }
       
        System.out.print(sb);
    }
   
    private static int minimum(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    public static int levenshteinDistance(String str1,String str2) {
        int[][] distance = new int[str1.length() + 1][str2.length() + 1];

        for (int i = 0; i <= str1.length(); i++)
            distance[i][0] = i;
        for (int j = 1; j <= str2.length(); j++)
            distance[0][j] = j;

        for (int i = 1; i <= str1.length(); i++)
            for (int j = 1; j <= str2.length(); j++)
                distance[i][j] = minimum(
                        distance[i - 1][j] + 1,
                        distance[i][j - 1] + 1,
                        distance[i - 1][j - 1]+ ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1));

        return distance[str1.length()][str2.length()];   
    }

}
class Pattern implements Comparable<Pattern> {
    int score;
    String pattern;

    public Pattern(int score, String pattern) {
        this.score = score;
        this.pattern = pattern;
    }
   

    public String getPattern() {
        return pattern;
    }

    public int getScore() {
        return score;
    }

    public void setPattern(String pattern) {
        this.pattern = pattern;
    }

    public void setScore(int score) {
        this.score = score;
    }

    @Override
    public int compareTo(Pattern o) {
        if(this.score<o.getScore())
            return -1;
        if(this.score>o.getScore())
            return 1;
        return this.pattern.compareTo(o.getPattern());
    }
   
   
}

CodeEval - String Searching - Hard

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws FileNotFoundException, IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        String line;
        while ((line = in.readLine()) != null) {
            StringTokenizer st=new StringTokenizer(line,",");
            String str=st.nextToken();
            String temp=st.nextToken();
            StringBuilder stb=new StringBuilder();
            LinkedList<String> list=new LinkedList<String>();
            for(int i=0;i<temp.length();i++){
                char c=temp.charAt(i);
                if(i==0){
                    if(c!='*'){
                        stb.append(c);
                    }
                    if(i<temp.length()-1){
                        if(c=='\\'&&temp.charAt(i+1)=='*'){
                            stb.deleteCharAt(stb.length()-1);
                        }
                    }
                }else if(i== temp.length()-1){
                    if(c=='*'){
                        if(temp.charAt(i-1)=='\\'){
                           stb.append(c);
                        }
                    }else{
                        stb.append(c);
                    }
                }else{
                    if(c=='*'){
                        if(temp.charAt(i-1)=='\\'){
                           stb.append(c);
                        }else{
                            list.add(stb.toString());
                            stb=new StringBuilder();
                        }
                    }else if(c=='\\'){
                        if(temp.charAt(i+1)!='*'){
                           stb.append(c);
                        }
                    }else{
                        stb.append(c);
                    }
                }
            }
            if(stb.length()!=0){
                list.add(stb.toString());
            }
            sb.append(findThesePatterns(str, list)).append('\n');
        }
        System.out.print(sb);
    }
   
    static boolean findThesePatterns(String Str,LinkedList<String> pattern){
        LinkedList<LinkedList<Integer>> list=new LinkedList<LinkedList<Integer>>();
        LinkedList<Integer> length=new LinkedList<Integer>();
        while(!pattern.isEmpty()){
            String val=pattern.remove();
            list.add(searchForPattrern(Str,val));
            length.add(val.length());
        }
        return canBeAfter(0, -1, list, length);
    }
   
    static boolean canBeAfter(int j,int index,LinkedList<LinkedList<Integer>> list,LinkedList<Integer> length){
        if(j==length.size()){
            return true;
        }
        LinkedList<Integer> less=list.get(j);
        int lengthL=length.get(j);
        for(int val:less){
            if(val>index){
               boolean res=canBeAfter(j+1,val+lengthL,list, length);
               if(res){
                   return true;
               }
            }
        }
        return false;
    }
   
     static LinkedList<Integer> searchForPattrern(String val,String pattern){
         LinkedList<Integer> index=new LinkedList<Integer>();
         for(int i=0;i<val.length()-pattern.length()+1;i++){
             int counter=0;
             for(int j=0;j<pattern.length();j++){
                 if(val.charAt(i+j)!=pattern.charAt(j)){
                     break;
                 }
                 counter++;
             }
             if(counter==pattern.length()){
                 index.add(i);
             }
         }
         return index;
     }
}

UVA - 671 - Spell checker

//Don't USE Edit Distance .. It will give you TLE ... :)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        String m = "";
        int cases=Integer.parseInt(br.readLine());
        for(int i=0;i<cases;i++){
            if(i>0)
                sb.append("\n");
            br.readLine();
            HashMap<String,Integer> hm=new HashMap<String,Integer>();
            int ind=1;
            while(true){
                m=br.readLine();
                hm.put(m,ind);
                ind++;
            }
          
            while(true){
                m=br.readLine();
                if(m.equals("#")){
                    break;
                }
                if(hm.containsKey(m)){
                   sb.append(m).append(" is correct\n");
                }else{
                    sb.append(m).append(":");
                    HashSet<String> added=new HashSet<String>();
                    LinkedList<Word> list=new LinkedList<Word>();
                    //delete one character
                    for(int j=0;j<m.length();j++){
                       StringBuilder temp=new StringBuilder();
                       for(int z=0;z<m.length();z++){
                           if(z!=j)
                            temp.append(m.charAt(z));
                        }
                       String wanted=temp.toString();
                       if(!added.contains(wanted)){
                           if(hm.containsKey(wanted)){
                               list.add(new Word(wanted, hm.get(wanted)));
                               added.add(wanted);
                           }
                       }
                    }
                    //replacing one character
                    for(int j=0;j<m.length();j++){
                       StringBuilder temp=new StringBuilder();
                       for(int z=0;z<m.length();z++){
                           if(z!=j)
                                temp.append(m.charAt(z));
                        }
                        for (int l = 0; l < 27; l++) {
                            StringBuilder temp2=new StringBuilder(temp.toString());
                            temp2.insert(j, (char)('a'+l));
                            String wanted = temp2.toString();
                            if (!added.contains(wanted)) {
                                if (hm.containsKey(wanted)) {
                                    list.add(new Word(wanted, hm.get(wanted)));
                                    added.add(wanted);
                                }
                            }
                       }
                     
                    }
                    //inserting one character
                    for(int j=0;j<m.length()+1;j++){
                       StringBuilder temp=new StringBuilder(m);
                       for (int l = 0; l < 27; l++) {
                            StringBuilder temp2=new StringBuilder(temp.toString());
                            temp2.insert(j, (char)('a'+l));
                            String wanted = temp2.toString();
                            if (!added.contains(wanted)) {
                                if (hm.containsKey(wanted)) {
                                    list.add(new Word(wanted, hm.get(wanted)));
                                    added.add(wanted);
                                }
                            }
                       }
                     
                    }
                    Collections.sort(list);
                    while(!list.isEmpty()){
                        sb.append(" ").append(list.remove().getWord());
                    }
                    sb.append("\n");
                }
            }
          
        }
        System.out.print(sb);
    }
  
}class Word implements Comparable<Word>{
    String word;
    int index;

    public Word(String word, int index) {
        this.word = word;
        this.index = index;
    }

    public int getIndex() {
        return index;
    }

    public String getWord() {
        return word;
    }
  
  
    @Override
    public int compareTo(Word o) {
        if(this.index>o.getIndex()){
            return 1;
        }
        return -1;
    }
  
}

UVA - 644 - Immediate Decodability

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer("");
        String m = "";
        LinkedList<String> list=new LinkedList<String>();
        int cases=1;
        while((m=br.readLine())!=null){
            while(!m.equals("9")){
                list.add(m);
                m=br.readLine();
            }
            String[]arr=new String[list.size()];
            for(int i=0;i<arr.length;i++){
                arr[i]=list.remove();
            }
            boolean pre=false;
            for(int i=0;i<arr.length-1;i++){
                for(int j=i+1;j<arr.length;j++){
                    if(isPrefix(arr[i],arr[j])){
                        pre=true;
                        break;
                    }
                }
                if(pre)
                    break;
            }
            if(pre){
                sb.append("Set ").append(cases).append(" is not immediately decodable\n");
            }
            else{
                sb.append("Set ").append(cases).append(" is immediately decodable\n");
            }
            cases++;
        }
        System.out.print(sb);
    }
   
    static boolean isPrefix(String x,String y){
        for(int i=0,j=0;i<Math.min(x.length(), y.length());i++){
            if(x.charAt(i)!=y.charAt(i)){
                return false;
            }
        }
        return true;
    }
}