ICPC2017E.java

import java.util.*;

public class Main {
    Scanner sc = new Scanner(System.in);

    String[] terminal = {
            "0",
            "1",
            "a",
            "b",
            "c",
            "d"
    };

    String exp;

    ArrayList<String> generate(int len) {
//        debug(len);
        ArrayList<String> list = new ArrayList<>();
        if (len > 16) {
            return list;
        }
        // I am E
        for (String t : terminal) {
//            debug("¥tatom", t);
            list.add(t);
        }
        // -E
        ArrayList<String> minus = generate(len + 2);
        for (String t : minus) {
            if (t.charAt(0) == '-') {
                continue;
            }
//            debug("¥tminus", t);
            list.add("-" + t);
        }
        ArrayList<String> left = generate(len + 5);
        ArrayList<String> right = generate(len + 5);
//        debug("left & right", left.size(), right.size());
        // (E^E)
        for (String t : left) {
            for (String s : right) {
                if (t.charAt(0) == '0') {
                    continue;
                }
                if (s.charAt(0) == '0') {
                    continue;
                }
                if (s.charAt(0) == t.charAt(0)) {
                    continue;
                }
//                if (flag)
//                    debug("¥t^", t, s);
//                StringBuilder sb = new StringBuilder();
//                sb.append('(');
//                sb.append(t);
//                sb.append('^');
//                sb.append(s);
//                sb.append(')');
                list.add("(" + t + "^" + s + ")");
            }
        }
//        debug("left & right 2", left.size(), right.size());
        // (E*E)
        for (String t : left) {
            for (String s : right) {
                if (t.charAt(0) == '1') {
                    continue;
                }
                if (s.charAt(0) == '1') {
                    continue;
                }
                if (s.charAt(0) == t.charAt(0)) {
                    continue;
                }
//                debug("¥t*", t, s);
//                StringBuilder sb = new StringBuilder();
//                sb.append('(');
//                sb.append(t);
//                sb.append('*');
//                sb.append(s);
//                sb.append(')');
//                list.add(sb.toString());
                list.add("(" + t + "*" + s + ")");
            }
        }
//        debug("list size", list.size());
        return list;
    }

    class Node {
        int type;
        Node left;
        Node right;
        int index;
        int v;

        int value(int[] variable) {
//            debug(type, left, right, index, v, variable);
            if (type < 4) {
                return variable[type];
            }
            if (type == 7) {
                return v;
            }
            if (type == 4) {
                int v = left.value(variable);
                return 1 - v;
            }
            int l = left.value(variable);
            int r = right.value(variable);
            if (type == 5) {
                return l ^ r;
            }
            assert type == 6;
            return l * r;
        }
    }

    Node kaiseki(int index) {
//        debug(exp, index);
        char c = exp.charAt(index);
        if (varmap.containsKey(c)) {
            Node node = new Node();
            node.index = index + 1;
            node.type = varmap.get(c);
            return node;
        }
        if (teisuu.contains(c)) {
            Node node = new Node();
            node.index = index + 1;
            node.type = 7;
            node.v = c - '0';
            return node;
        }
        if (c == '-') {
            Node node = new Node();
            Node left = kaiseki(index + 1);
            node.left = left;
            node.index = left.index;
            node.type = 4;
            return node;
        }
        Node node = new Node();
        assert c == '(';
        Node left = kaiseki(index + 1);
        node.left = left;
        char d = exp.charAt(left.index);
        if (d == '^') {
            node.type = 5;
        } else {
            assert d == '*';
            node.type = 6;
        }
        Node right = kaiseki(left.index + 1);
        node.right = right;
        assert exp.charAt(right.index) == ')';
        node.index = right.index + 1;
        return node;
    }

    HashMap<Character, Integer> varmap = new HashMap<>(10);
    HashSet<Character> teisuu = new HashSet<>(10);

    void run() {
        varmap.put('a', 0);
        varmap.put('b', 1);
        varmap.put('c', 2);
        varmap.put('d', 3);
        teisuu.add('0');
        teisuu.add('1');
        debug("hajimari");
        ArrayList<String> list = generate(1);
        debug("owari");
        for (int turn = 0; ; ++turn) {
            debug(turn);
            exp = sc.next();
            if (exp.charAt(0) == '.') {
                break;
            }
            Node atom = kaiseki(0);
            ArrayList<Integer> ans = new ArrayList<>();
            for (int a = 0; a < 2; ++a) {
                for (int b = 0; b < 2; ++b) {
                    for (int c = 0; c < 2; ++c) {
                        for (int d = 0; d < 2; ++d) {
                            int[] v = new int[]{a, b, c, d};
                            int w = atom.value(v);
                            ans.add(w);
                        }
                    }
                }
            }
            int min = exp.length();
            for (String str : list) {
                exp = str;
                Node root = kaiseki(0);
                ArrayList<Integer> arr = new ArrayList<>();
                for (int a = 0; a < 2; ++a) {
                    for (int b = 0; b < 2; ++b) {
                        for (int c = 0; c < 2; ++c) {
                            for (int d = 0; d < 2; ++d) {
                                int[] v = new int[]{a, b, c, d};
                                int w = root.value(v);
                                arr.add(w);
                            }
                        }
                    }
                }
                if (ans.equals(arr)) {
                    min = Math.min(min, str.length());
                }
            }
            System.out.println(min);
        }
    }

    int ni() {
        return sc.nextInt();
    }

    public static void main(String[] args) {
        new Main().run();
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }
}