Google Code Jam 2011 Qualifier Round - Problem B, Magicka

Magicka.java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Magicka {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new File("B-large.in"));
        int cases = sc.nextInt();

        for(int c=1; c<=cases; c++) {
            Map<Set<Character>, Character> combineMap = new HashMap<Set<Character>, Character>();
            Map<Character, List<Character>> clashMap = new HashMap<Character, List<Character>>();

            int combines = sc.nextInt();
            for(int i=0; i<combines; i++) {
                String combination = sc.next();
                Set<Character> ingredients = new HashSet<Character>();
                ingredients.add(combination.charAt(0));
                ingredients.add(combination.charAt(1));
                combineMap.put(ingredients, combination.charAt(2));
            }

            int clashes = sc.nextInt();
            for(int i=0; i<clashes; i++) {
                String clash = sc.next();
                char a = clash.charAt(0);
                char b = clash.charAt(1);

                List<Character> charsA = clashMap.containsKey(a) ? clashMap.get(a) : new ArrayList<Character>();
                charsA.add(b);
                clashMap.put(a, charsA);

                List<Character> charsB = clashMap.containsKey(b) ? clashMap.get(b) : new ArrayList<Character>();
                charsB.add(a);
                clashMap.put(b, charsB);
            }

            int inputLength = sc.nextInt();
            String input = sc.next();
            List<Character> res = new ArrayList<Character>();

            for(int i=0; i<inputLength; i++) {
                res.add(input.charAt(i));
                List<Character> newRes = fold(res, combineMap, clashMap);
                List<Character> nextRes = fold(newRes, combineMap, clashMap);
                while (!newRes.equals(nextRes)) {
                    newRes = nextRes;
                    nextRes = fold(nextRes, combineMap, clashMap);
                }
                res = nextRes;
            }
        }
    }

    public static List<Character> fold(List<Character> elements, Map<Set<Character>, Character> combineMap, Map<Character, List<Character>> clashMap) {
        List<Character> res = new ArrayList<Character>();
        for(char c : elements) res.add(c);

        if (res.size() >= 2) {
            Set<Character> s = new HashSet<Character>();
            s.add(res.get(res.size()-2));
            s.add(res.get(res.size()-1));
            if (combineMap.containsKey(s)) {
                res.remove(res.size()-1);
                res.remove(res.size()-1);
                res.add(combineMap.get(s));
            } else if (clashMap.containsKey(res.get(res.size()-1))) {
                for(int i=0; i<res.size()-1; i++)
                    if (clashMap.get(res.get(res.size()-1)).contains(res.get(i))) res.clear();
            }
        }
        return res;
    }
}