Problem B. Magicka - Qualification Round 2011 - Google Code Jam

Dashboard - Qualification Round 2011 - Google Code Jam

Introduction

Magicka™ is an action-adventure game developed by Arrowhead Game Studios. In Magicka you play a wizard, invoking and combining elements to create Magicks. This problem has a similar idea, but it does not assume that you have played Magicka.
Note: "invoke" means "call on." For this problem, it is a technical term and you don't need to know its normal English meaning.

Problem

As a wizard, you can invoke eight elements, which are the "base" elements. Each base element is a single character from {Q, W, E, R, A, S, D, F}. When you invoke an element, it gets appended to your element list. For example: if you invoke W and then invoke A, (we'll call that "invoking WA" for short) then your element list will be [W, A].
We will specify pairs of base elements that combine to form non-base elements (the other 18 capital letters). For example, Q and F might combine to form T. If the two elements from a pair appear at the end of the element list, then both elements of the pair will be immediately removed, and they will be replaced by the element they form. In the example above, if the element list looks like [A, Q, F] or [A, F, Q] at any point, it will become [A, T].
We will specify pairs of base elements that are opposed to each other. After you invoke an element, if it isn't immediately combined to form another element, and it is opposed to something in your element list, then your whole element list will be cleared.
For example, suppose Q and F combine to make T. R and F are opposed to each other. Then invoking the following things (in order, from left to right) will have the following results:

• QF → [T] (Q and F combine to form T)
• QEF → [Q, E, F] (Q and F can't combine because they were never at the end of the element list together)
• RFE → [E] (F and R are opposed, so the list is cleared; then E is invoked)
• REF → [] (F and R are opposed, so the list is cleared)
• RQF → [R, T] (QF combine to make T, so the list is not cleared)
• RFQ → [Q] (F and R are opposed, so the list is cleared)

Given a list of elements to invoke, what will be in the element list when you're done?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line, containing the following space-separated elements in order:
First an integer C, followed by C strings, each containing three characters: two base elements followed by a non-base element. This indicates that the two base elements combine to form the non-base element. Next will come an integer D, followed by D strings, each containing two characters: two base elements that are opposed to each other. Finally there will be an integer N, followed by a single string containing N characters: the series of base elements you are to invoke. You will invoke them in the order they appear in the string (leftmost character first, and so on), one at a time.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is a list in the format "[e₀, e₁, ...]" where e_i is the i^th element of the final element list. Please see the sample output for examples.
Input

Output
 5
0 0 2 EA
1 QRI 0 4 RRQR
1 QFT 1 QF 7 FAQFDFQ
1 EEZ 1 QE 7 QEEEERA
0 1 QW 2 QWCase #1: [E, A]
Case #2: [R, I, R]
Case #3: [F, D, T]
Case #4: [Z, E, R, A]
Case #5: []

Official analysis: https://code.google.com/codejam/contest/975485/dashboard#s=a&a=1

This problem can be solved with a simulation. First, we have to remember what elements combine to make other elements. A map of some sort, like a hash map, is a great way of doing this. Next we have to track the opposed elements, remembering that one element can be opposed to multiple other elements; a set of pairs, while not particularly efficient for this purpose, will do the trick.

Finally, the simulation itself. For each character, first we check to see if it combines with the last item on the element list, and combine it if so. If it doesn't combine, then we iterate through the elements already in the list and see if it's opposed to any of them -- if so, we clear the list. Finally, if neither of those conditions was met, we append it to the list.

	void run() throws Exception { final int t = Integer.valueOf(reader.readLine());
	Map<String, Character> cm;
	Set<CharPair> ds;
	String line;
	String chunks[];
	int c;
	int d;
	int n;
	for (int i = 1; i <= t; i++) {
	line = reader.readLine();
	chunks = line.split(" ");
	c = Integer.valueOf(chunks[0]);
	d = Integer.valueOf(chunks[c + 1]);
	n = Integer.valueOf(chunks[c + d + 2]);
	cm = new HashMap<String, Character>(2 * c);
	char[] combs;
	for (int j = 1; j <= c; j++) {
	combs = chunks[j].toCharArray();
	cm.put(combs[0] + "" + combs[1], combs[2]);
	cm.put(combs[1] + "" + combs[0], combs[2]);
	}
	ds = new HashSet<CharPair>(d);
	for (int j = c + 2; j <= c + d + 1; j++) {
	ds.add(new CharPair(chunks[j].charAt(0), chunks[j].charAt(1)));
	}
	solve(i, cm, ds, n, chunks[c + d + 3].toCharArray());
	}
	}
	void solve(int t, Map<String, Character> cm, Set<CharPair> ds, int n, char[] letters) {
	stack = new ArrayDeque<Character>(n);
	prev = 0;
	Character combine;
	boolean del;
	for (char letter : letters) {
	if (prev != 0) {
	combine = cm.get(prev + "" + letter);
	if (combine == null) {
	push(letter);
	del = false;
	for (CharPair p : ds) {
	if (stack.contains(p.a) && stack.contains(p.b)) {
	del = true;
	break;
	}
	}
	if (del) {
	clear();
	}
	} else {
	pop();
	push(combine);
	}
	} else {
	push(letter);
	}
	}
	out.println("Case #" + t + ": " + stack.toString());
	}
	private void push(char e) {
	stack.add(e);
	prev = e;
	}
	private void pop() {
	stack.removeLast();
	}
	private void clear() {
	stack.clear();
	prev = 0;
	}

Read full article from Dashboard - Qualification Round 2011 - Google Code Jam