import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Day21 {

//    public static final String INPUT = "abcdefgh";
    public static final String INPUT = "fbgdceah";
    public static final Pattern SWAP_IDX = Pattern.compile("swap position (\\d+) with position (\\d+)");
    public static final Pattern SWAP_LETTER = Pattern.compile("swap letter (\\w) with letter (\\w)");
    public static final Pattern ROTATE_INT = Pattern.compile("rotate (left|right) (\\d+) steps?");
    public static final Pattern ROTATE_LETTER = Pattern.compile("rotate based on position of letter (\\w)");
    public static final Pattern REVERSE_RANGE = Pattern.compile("reverse positions (\\d+) through (\\d+)");
    public static final Pattern MOVE_IDX = Pattern.compile("move position (\\d+) to position (\\d+)");
    public static final boolean REVERSE = false;
    
    public static List<String> permute(String str) { 
        final List<String> permutations = new ArrayList<>();
        Day21.permute(permutations, "", str); 
        return permutations;
    }

    private static void permute(List<String> permutations, String prefix, String str) {
        final int n;
        
        if ((n = str.length()) == 0) {
            permutations.add(prefix);
            return;
        }
        
        for (int i = 0; i < n; i++) {
            Day21.permute(permutations, prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
        }
    }
    
    public static void main(String[] args) {
//        final List<Character> string = new ArrayList<>();
//        
//        for (char c : Day21.INPUT.toCharArray()) {
//            string.add(Character.valueOf(c));
//        }
//        
//        Day21.run(string);
//        System.out.println(string.stream().reduce("", (s, c) -> s += c.charValue(), String::concat));
        
        Day21.bogo(Day21.INPUT);
    }
    
    public static void bogo(String find) {
        /*
         * Not my original solution for part 2
         * This solution attemps every permutation of the string to be found as input to part 1's logic
         * Doing this would have greatly reduced the time spent reversing the logic of the "rotate based on position of letter \w" command
         * For strings of length N, there are N! permutations, 8! = 40320, so this is very feasible to "brute force" in this way
         */
        
        final List<String> commands = new ArrayList<>();
        System.out.println("input:");
        
        for (String input; (input = Day0.readline()) != null && !"end".equals(input); ) {
            commands.add(input);
        }
        
        final List<Character> start = new ArrayList<>();
        final List<Character> result = new ArrayList<>();
        final List<String> permutations = Day21.permute(find);
        
        for (String permutation : permutations) {
            start.clear();
            
            for (char c : permutation.toCharArray()) {
                start.add(Character.valueOf(c));
            }
            
            result.clear();
            result.addAll(start);
            Day21.run(result, commands);
            
            if (result.stream().reduce("", (s, c) -> s += c.charValue(), String::concat).equals(find)) {
                System.out.println("Input '" + permutation + "' generates '" + find + "'");
            }
        }
    }
    
    public static void run(List<Character> string) {
        final List<String> commands = new ArrayList<>();
        System.out.println("input:");
        
        for (String input; (input = Day0.readline()) != null && !"end".equals(input); ) {
            commands.add(input);
        }
        
        if (Day21.REVERSE) {
            Collections.reverse(commands);
        }
        
        for (String input : commands) {
            final Matcher matcher;
            
            if (input.startsWith("swap position ")) {
                (matcher = Day21.SWAP_IDX.matcher(input)).matches();
                Collections.swap(string, Integer.parseInt(matcher.group(1)), Integer.parseInt(matcher.group(2)));
            } else if (input.startsWith("swap letter ")) {
                (matcher = Day21.SWAP_LETTER.matcher(input)).matches();
                final char x = matcher.group(1).charAt(0), y = matcher.group(2).charAt(0);
                
                for (int i = 0; i < string.size(); i++) {
                    final char at = string.get(i).charValue();
                    
                    if (at == x) {
                        string.set(i, Character.valueOf(y));
                    } else if (at == y) {
                        string.set(i, Character.valueOf(x));
                    }
                }
            } else if (input.startsWith("reverse positions ")) {
                (matcher = Day21.REVERSE_RANGE.matcher(input)).matches();
                Collections.reverse(string.subList(Integer.parseInt(matcher.group(1)), 1 + Integer.parseInt(matcher.group(2))));
            } else if (input.startsWith("move position ")) {
                (matcher = Day21.MOVE_IDX.matcher(input)).matches();
                
                final int remidx, insidx;
                
                if (Day21.REVERSE) {
                    remidx = Integer.parseInt(matcher.group(2));
                    insidx = Integer.parseInt(matcher.group(1));
                } else {
                    remidx = Integer.parseInt(matcher.group(1));
                    insidx = Integer.parseInt(matcher.group(2));
                }
                
                final Character rem = string.remove(remidx);
                string.add(insidx, rem);
            } else if (input.startsWith("rotate based ")) {
                (matcher = Day21.ROTATE_LETTER.matcher(input)).matches();
                
                if (Day21.REVERSE) {
                    final char find = matcher.group(1).charAt(0);
                    final int len = Day21.INPUT.length();
                    final List<Character> copy = new ArrayList<>(string);
                    boolean found = false;
                    
                    for (int i = 0; i < len; i++) {
                        Collections.rotate(copy, -1);
                        
                        int rotate = copy.indexOf(Character.valueOf(find));
                        
                        if (rotate >= 4) {
                            rotate++;
                        }
                        
                        final List<Character> check = new ArrayList<>(copy);
                        Collections.rotate(check, ++rotate);
                        
                        if (string.equals(check)) {
                            string.clear();
                            string.addAll(copy);
                            found = true;
                            break;
                        }
                    }
                    
                    if (!found) {
                        System.err.println("Failed to reverse rotation by letter!");
                        return;
                    }
                } else {
                    int rotate = string.indexOf(Character.valueOf(matcher.group(1).charAt(0)));
                    
                    if (rotate >= 4) {
                        rotate++;
                    }
                    
                    Collections.rotate(string, ++rotate);
                }
            } else if (input.startsWith("rotate ")) {
                (matcher = Day21.ROTATE_INT.matcher(input)).matches();
                Collections.rotate(string, (matcher.group(1).equalsIgnoreCase("left") ? -1 : 1) * Integer.parseInt(matcher.group(2)) * (Day21.REVERSE ? -1 : 1));
            } else {
                System.err.println("Unrecognized command: " + input);
                return;
            }
        }
    }
    
    public static void run(List<Character> string, List<String> commands) {
        if (Day21.REVERSE) {
            Collections.reverse(commands);
        }
        
        for (String input : commands) {
            final Matcher matcher;
            
            if (input.startsWith("swap position ")) {
                (matcher = Day21.SWAP_IDX.matcher(input)).matches();
                Collections.swap(string, Integer.parseInt(matcher.group(1)), Integer.parseInt(matcher.group(2)));
            } else if (input.startsWith("swap letter ")) {
                (matcher = Day21.SWAP_LETTER.matcher(input)).matches();
                final char x = matcher.group(1).charAt(0), y = matcher.group(2).charAt(0);
                
                for (int i = 0; i < string.size(); i++) {
                    final char at = string.get(i).charValue();
                    
                    if (at == x) {
                        string.set(i, Character.valueOf(y));
                    } else if (at == y) {
                        string.set(i, Character.valueOf(x));
                    }
                }
            } else if (input.startsWith("reverse positions ")) {
                (matcher = Day21.REVERSE_RANGE.matcher(input)).matches();
                Collections.reverse(string.subList(Integer.parseInt(matcher.group(1)), 1 + Integer.parseInt(matcher.group(2))));
            } else if (input.startsWith("move position ")) {
                (matcher = Day21.MOVE_IDX.matcher(input)).matches();
                
                final int remidx, insidx;
                
                if (Day21.REVERSE) {
                    remidx = Integer.parseInt(matcher.group(2));
                    insidx = Integer.parseInt(matcher.group(1));
                } else {
                    remidx = Integer.parseInt(matcher.group(1));
                    insidx = Integer.parseInt(matcher.group(2));
                }
                
                final Character rem = string.remove(remidx);
                string.add(insidx, rem);
            } else if (input.startsWith("rotate based ")) {
                (matcher = Day21.ROTATE_LETTER.matcher(input)).matches();
                
                if (Day21.REVERSE) {
                    final char find = matcher.group(1).charAt(0);
                    final int len = Day21.INPUT.length();
                    final List<Character> copy = new ArrayList<>(string);
                    boolean found = false;
                    
                    for (int i = 0; i < len; i++) {
                        Collections.rotate(copy, -1);
                        
                        int rotate = copy.indexOf(Character.valueOf(find));
                        
                        if (rotate >= 4) {
                            rotate++;
                        }
                        
                        final List<Character> check = new ArrayList<>(copy);
                        Collections.rotate(check, ++rotate);
                        
                        if (string.equals(check)) {
                            string.clear();
                            string.addAll(copy);
                            found = true;
                            break;
                        }
                    }
                    
                    if (!found) {
                        System.err.println("Failed to reverse rotation by letter!");
                        return;
                    }
                } else {
                    int rotate = string.indexOf(Character.valueOf(matcher.group(1).charAt(0)));
                    
                    if (rotate >= 4) {
                        rotate++;
                    }
                    
                    Collections.rotate(string, ++rotate);
                }
            } else if (input.startsWith("rotate ")) {
                (matcher = Day21.ROTATE_INT.matcher(input)).matches();
                Collections.rotate(string, (matcher.group(1).equalsIgnoreCase("left") ? -1 : 1) * Integer.parseInt(matcher.group(2)) * (Day21.REVERSE ? -1 : 1));
            } else {
                System.err.println("Unrecognized command: " + input);
                return;
            }
        }
    }
}