第3回 オフラインリアルタイムどう書く: Java解答（スタック迷走編）

TripY2.java

import static org.junit.Assert.assertEquals;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

/**
 * 問題: http://nabetani.sakura.ne.jp/hena/ord3ynode/
 */
public class TripY2 {

	Map<String, Character> rdic;
	Map<String, Character> ldic;

	public TripY2() {
		rdic = new HashMap<>();
		rdic.put("BA", 'C');
		rdic.put("AB", 'E');
		rdic.put("AC", 'B');
		rdic.put("CA", 'D');
		rdic.put("AD", 'F');
		rdic.put("DA", 'B');
		rdic.put("BC", 'F');
		rdic.put("CB", 'A');
		rdic.put("BE", 'D');
		rdic.put("EB", 'C');
		rdic.put("DE", 'F');
		rdic.put("ED", 'A');
		rdic.put("CF", 'E');
		rdic.put("FC", 'A');
		rdic.put("DF", 'C');
		rdic.put("FD", 'E');
		rdic.put("EF", 'D');
		rdic.put("FE", 'B');

		ldic = new HashMap<>();
		ldic.put("FD", 'A');
		ldic.put("EF", 'C');
		ldic.put("FE", 'D');
		ldic.put("BA", 'D');
		ldic.put("AB", 'C');
		ldic.put("AC", 'F');
		ldic.put("CA", 'B');
		ldic.put("AD", 'E');
		ldic.put("DA", 'C');
		ldic.put("BC", 'A');
		ldic.put("ED", 'F');
		ldic.put("DE", 'B');
		ldic.put("EB", 'A');
		ldic.put("CB", 'E');
		ldic.put("BE", 'F');
		ldic.put("CF", 'D');
		ldic.put("DF", 'E');
		ldic.put("FC", 'B');
	}

	protected String execute(String input) {
		Deque<Character> current = new ArrayDeque<>();
		current.push('A');

		Deque<Character> pre = new ArrayDeque<>();
		pre.push('B');

		for (int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);
			Character posi = current.peek();
			if (c == 'b') {
				current.push(pre.pop());
				pre.push(posi);
			} else if (c == 'r') {
				String key = String.valueOf(pre.pop()) + String.valueOf(posi);
				current.push(rdic.get(key));
				pre.push(posi);
			} else if (c == 'l') {
				String key = String.valueOf(pre.pop()) + String.valueOf(posi);
				current.push(ldic.get(key));
				pre.push(posi);
			}
		}

		String result = "";
		int counter = current.size();
		for (int i = 0; i < counter; i++) {
			result += current.removeLast();
		}
		return result;
	}

	public static void main(String[] args) {
		TripY trip = new TripY();
		System.out.println(trip.execute("rrrrbllrlrbrbrr")); // ACBACABCFDEDADFC
	}

	@Test
	public void testExecute() throws Exception {
		TripY2 trip = new TripY2();

		String[][] answers = {
		/* 0 */{ "b", "AB" },
		/* 1 */{ "l", "AD" },
		/* 2 */{ "r", "AC" },
		/* 3 */{ "bbb", "ABAB" },
		/* 4 */{ "rrr", "ACBA" },
		/* 5 */{ "blll", "ABCAB" },
		/* 6 */{ "llll", "ADEBA" },
		/* 7 */{ "rbrl", "ACADE" },
		/* 8 */{ "brrrr", "ABEDAB" },
		/* 9 */{ "llrrr", "ADEFDE" },
		/* 10 */{ "lrlll", "ADFEDF" },
		/* 11 */{ "lrrrr", "ADFCAD" },
		/* 12 */{ "rllll", "ACFDAC" },
		/* 13 */{ "blrrrr", "ABCFEBC" },
		/* 14 */{ "brllll", "ABEFCBE" },
		/* 15 */{ "bbrllrrr", "ABACFDEFD" },
		/* 16 */{ "rrrrblll", "ACBACABCA" },
		/* 17 */{ "llrlrrbrb", "ADEFCADABA" },
		/* 18 */{ "rrrbrllrr", "ACBABEFCAD" },
		/* 19 */{ "llrllblrll", "ADEFCBCADEB" },
		/* 20 */{ "lrrlllrbrl", "ADFCBEFDFCB" },
		/* 21 */{ "lllrbrrlbrl", "ADEBCBACFCAB" },
		/* 22 */{ "rrrrrrlrbrl", "ACBACBADFDEB" },
		/* 23 */{ "lbrbbrbrbbrr", "ADABABEBCBCFE" },
		/* 24 */{ "rrrrlbrblllr", "ACBACFCACFDAB" },
		/* 25 */{ "lbbrblrlrlbll", "ADADFDABCFDFED" },
		/* 26 */{ "rrbbrlrlrblrl", "ACBCBADFEBEFDA" },
		/* 27 */{ "blrllblbrrrrll", "ABCFDADEDABEDFE" },
		/* 28 */{ "blrllrlbllrrbr", "ABCFDABCBEFDEDA" },
		/* 29 */{ "lbrbbrllllrblrr", "ADABABEFCBEDEBCF" },
		/* 30 */{ "rrrrbllrlrbrbrr", "ACBACABCFDEDADFC" }, };

		for (int i = 0; i < 30; i++) {
			assertEquals(answers[i][1], trip.execute(answers[i][0]));
			// System.out.println(i);
		}
	}
}