Rule of Three Substitution

README.md

Build and run instructions:

>javac Substitution.java

>java Substitution < input.txt
Rules:
AA AB
AB BB
B AA
Steps: 4
From: AB
To: AAAB
2 1 AB->BB
3 1 BB->AAB
1 1 AAB->ABB
3 2 ABB->AAAB

input.txt

AA AB
AB BB
B AA
4 AB AAAB

Substitution.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Substitution {
    private static class Rule {
        private String from;
        private String to;

        public Rule(String from, String to) {
            this.from = from;
            this.to = to;
        }

        public String getFrom() {
            return from;
        }

        public String getTo() {
            return to;
        }

        public String toString() {
            return from + " " + to;
        }
    }

    private static class Step {
        private int ruleIndex;
        private int substitutionIndex;
        private String from;
        private String to;
        
        public Step(int ruleIndex, int substitutionIndex, String from, String to) {
            this.ruleIndex = ruleIndex;
            this.substitutionIndex = substitutionIndex;
            this.from = from;
            this.to = to;
        }

        public String toString() {
            return (ruleIndex + 1) + " " + (substitutionIndex + 1) + " " + from + "->" + to;
        }
    }

    public static List<Step> solve(List<Rule> rules, int numSteps, String current, String to, List<Step> pastSteps) {
        // solve for how to use rules to get from current to to in numSteps steps
        // return a list of steps
        // if no solution, return an empty list
        // if there are multiple solutions, return any one of them
        // pastSteps is a list of steps that have been taken to get to current
        
        // If current is already to, return pastSteps
        if (current.equals(to)) {
            return pastSteps;
        }

        // If numSteps is 0, return an empty list
        if (numSteps == 0) {
            return Collections.emptyList();
        }

        // For each rule
        for (int i = 0; i < rules.size(); i++) {
            Rule rule = rules.get(i);
            // For each possible substitution
            for (int j = 0; j < current.length(); j++) {
                // If the rule can be applied
                if (current.startsWith(rule.getFrom(), j)) {


                    // Create a new string
                    String newCurrent = current.substring(0, j) + rule.getTo() + current.substring(j + rule.getFrom().length());

                    // Create a new list of steps
                    List<Step> steps = new ArrayList<>(pastSteps);
                    // Create a new step
                    Step step = new Step(i, j, current, newCurrent);
                    // Add the new step to the list
                    steps.add(step);

                    // Solve for the new string
                    List<Step> newSteps = solve(rules, numSteps - 1, newCurrent, to, steps);
                    // If the new string can be solved, return the new steps
                    if (!newSteps.isEmpty()) {
                        return newSteps;
                    }

                }
            }
        }

        return Collections.emptyList();
    }

    public static void main(String[] args) {
        // Read from System.in
        Scanner scanner = new Scanner(System.in);
        // Read 3 linse of rules from scanner
        List<Rule> rules = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            String line = scanner.nextLine();
            String[] parts = line.split(" ");
            rules.add(new Rule(parts[0].trim(), parts[1].trim()));
        }
        // Read the string to be substituted
        String s = scanner.nextLine();
        // Parse the first part of s as int as number of steps
        int numSteps = Integer.parseInt(s.substring(0, s.indexOf(' ')));
        // Parse the second part of s as string as the string to be substituted
        String from = s.split(" ")[1];
        // Parse the third part of s as string as the string to be substituted to
        String to = s.split(" ")[2];

        // Print the parsed input for debugging
        System.out.println("Rules:");
        for (Rule rule : rules) {
            System.out.println(rule);
        }
        System.out.println("Steps: " + numSteps);
        System.out.println("From: " + from);
        System.out.println("To: " + to);

        List<Step> solution = solve(rules, numSteps, from, to, Collections.emptyList());
        // print out solution
        if (solution.isEmpty()) {
            System.out.println("No solution");
        } else {
            for (Step step : solution) {
                System.out.println(step);
            }
        }
    }
}