A complete solver for "Calculator: The Game"

CalculatorGameSolver.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.regex.Pattern;

public class CalculatorGameSolver {
    // Given a single action input (e.x. "1=>5"), returns the appropriate action for that input
    public static Action parseAction(String input) {
        if (input.matches("\\d+")) {
            // e.x.: 12
            return new InsertAction(input);
        }

        // Switch based on the Action operator
        switch (input.replaceAll("\\d", "").toLowerCase()) {
            case "+": // e.x.: +2 or +15
            case "-": // e.x.: -7 or -12
                return new AddAction(input);

            case "x": // e.x.: x3 or x10
            case "*": // e.x.: *3 or *10
            case "x-": // e.x.: x-3 or x-10
            case "*-": // e.x.: *-3 or *-10
                return new MultiplyAction(input);

            case "/": // e.x.: /5 or /10
                return new DivideAction(input);

            case "<<": // e.x.: <<
                return new DeleteAction(input);

            case "=>": // e.x.: 4=>12 or 3=>2
                return new ReplaceAction(input);

            case "x^": // e.x.: x^2 or x^3
                return new PowerAction(input);

            case "+/-": // e.x.: +/-
            case "+-": // e.x.: +-
                return new FlipSignAction(input);

            case "reverse": // e.x.: Reverse or reverse
            case "r": // e.x.: R or r
                return new ReverseAction(input);

            case "sum": // e.x.: Sum or sum
            case "s": // e.x.: S or s
                return new SumAction(input);

            case "shift<": // e.x.: Shift< or shift<
            case "s<": // e.x.: S< or s<
            case "<": // e.x.: <
            case "shift>": // e.x.: Shift> or shift>
            case "s>": // e.x.: S> or s>
            case ">": // e.x.: >
                return new ShiftAction(input);

            case "mirror": // e.x. Mirror or mirror
            case "m": // e.x. M or m
                return new MirrorAction(input);

            case "[+]": // e.x. [+]1
                return new AddModifierAction(input);

            case "store":
                return new SetStoreAction(input);

            case "load":
                return new LoadStoreAction(input);

            case "inv10":
            case "inv":
            case "i":
                return new InverseAction(input);

            default:
                throw new IllegalArgumentException("Unknown Action: " + input);
        }
    }

    // Parse actions separated by a comma or space
    public static Action[] getActionsFromString(String actionStr) {
        final String[] actionStrings = actionStr.split("[,\\s]");
        final int totalActions = actionStrings.length;
        final List<Action> actions = new ArrayList<>(totalActions + 1);

        boolean storeAction = false;
        boolean loadAction = false;
        for (String s : actionStrings) {
            Action a = parseAction(s);
            actions.add(a);

            storeAction |= a instanceof SetStoreAction;
            loadAction |= a instanceof LoadStoreAction;
        }

        // store action always need a corresponding load action if none is specified
        if (storeAction && !loadAction) {
            actions.add(parseAction("load"));
        }

        return actions.toArray(new Action[0]);
    }

    // Creates all combinations of possible moves from a list of actions and the number of moves
    public static Action[][] getAllCombinations(Action[] actions, int numMoves) {
        final int combinations = (int)Math.pow(actions.length, numMoves);

        // TODO: Optimization candidate
        final Action[][] allActions = new Action[combinations][numMoves];
        for (int i = 0; i < combinations; i++) {
            int c = i;
            for (int a = 0; a < numMoves; a++) {
                allActions[i][a] = actions[c % actions.length];
                c /= actions.length;
            }
        }

        return allActions;
    }

    // Tests each set of actions in allActions to find which combination of actions take the player from startValue to goal
    // Returns a reference to the action array for the winning solution
    // If there are multiple solutions, it'll prefer the first solution it finds, which is also the shortest solution
    // Throws an IllegalArgumentException if no solution can be found
    public static Action[] searchCombinations(final Action[][] allActions, final int startValue, final int goal) {
        // TODO: Optimization candidate
        GameContext context = new GameContext(startValue);
        for (int i = 0; i < allActions.length; i++) {
            int j = 0;

            while (j < allActions[i].length && context.getValue() != goal && context.isValid()) {
                allActions[i][j++].apply(context);
            }

            if (context.getValue() == goal && context.isValid()) {
                return allActions[i];
            }

            context.reset();
        }

        /*
            If the solver reaches this point, that can mean one of two things:
              1. either there's no combination of moves that wins; or
              2. an action is implemented incorrectly
        */
        throw new IllegalArgumentException("No solution possible");
    }

    // Takes an array of actions returns a comma-with-space separated string of its elements
    public static String actionArrayToString(Action[] arr) {
        final StringBuilder sb = new StringBuilder();
        if (arr.length != 0) {
            sb.append(arr[0]);
        }

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] instanceof LoadStoreAction) continue;
            sb.append(", ").append(arr[i]);
        }

        return sb.toString();
    }

    // Takes an array of actions, a start value, and returns a comma-with-space separated string of its elements
    // This function takes into account what the actions should be at each step of the game
    public static String printSolution(Action[] arr, int startValue) {
        final StringBuilder sb = new StringBuilder();
        GameContext context = new GameContext(startValue);
        if (arr.length != 0) {
            sb.append(arr[0].toString(context));
            arr[0].apply(context);
        }

        for (int i = 1; i < arr.length; i++) {
            sb.append(", ").append(arr[i].toString(context));
            arr[i].apply(context);
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        System.out.println("Enter Actions:");
        final Action[] actions = getActionsFromString(in.nextLine());

        System.out.print("Enter Max Moves: ");
        final int numMoves = in.nextInt();

        System.out.print("Enter Goal: ");
        final int goal = in.nextInt();

        System.out.print("Start Value: ");
        final int startValue = in.nextInt();

        // Print level state for custom parsing
        //System.out.println(actionArrayToString(actions).replaceAll(" ", "") + ";" + numMoves + "," + goal + "," + startValue);

        final Action[][] allActions = getAllCombinations(actions, numMoves);
        final Action[] solution = searchCombinations(allActions, startValue, goal);

        System.out.println("Combinations: " + allActions.length);
        System.out.println("Solution:\n" + printSolution(solution, startValue));
    }

    public static class GameContext {
        final int startValue;
        float value;
        float modifier = 0.0f;
        int store = 9999999; // If this is loaded without storing first, the value becomes invalid

        public GameContext(int startValue) {
            this.startValue = startValue;
            value = startValue;
        }

        public void reset() {
            value = startValue;
            modifier = 0.0f;
            store = 9999999;
        }

        public boolean isValid() {
            return (int)value <= 999999
                && Math.floor(value) == value
                && Math.floor(modifier) == modifier;
        }

        public int getValue() {
            return (int)value;
        }

        public int getModifier() {
            return (int)modifier;
        }
    }

    public static abstract class Action {
        final String stringValue;

        public Action(String value) {
            stringValue = value;
        }

        public abstract void apply(GameContext context);

        @Override
        public int hashCode() {
            return stringValue.hashCode();
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Action action = (Action) o;
            return stringValue.equals(action.stringValue);
        }

        @Override
        public String toString() {
            return stringValue;
        }

        public String toString(GameContext context) {
            return stringValue;
        }
    }

    public static class DeleteAction extends Action {
        public DeleteAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            context.value = context.getValue() / 10;
        }
    }

    public static class FlipSignAction extends Action {
        public FlipSignAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            context.value *= -1;
        }
    }

    public static class ReverseAction extends Action {
        public ReverseAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            int value = context.getValue();
            final int sign = value < 0 ? -1 : 1;
            value *= sign;

            int returnVal = 0;
            while (value != 0) {
                returnVal = (returnVal * 10) + (value % 10);
                value /= 10;
            }

            context.value = sign * returnVal;
        }
    }

    public static class SumAction extends Action {
        public SumAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            int value = context.getValue();
            final int sign = value < 0 ? -1 : 1;
            value *= sign;

            int returnVal = 0;
            while (value != 0) {
                returnVal += (value % 10);
                value /= 10;
            }

            context.value = sign * returnVal;
        }
    }

    public static class ShiftAction extends Action {
        private final boolean shiftLeft;

        public ShiftAction(String value) {
            super(value);
            shiftLeft = value.contains("<");
        }

        @Override
        public void apply(GameContext context) {
            int value = context.getValue();
            final int sign = value < 0 ? -1 : 1; // Keep track of the sign as this math does not work on negative numbers
            value *= sign; // If negative, value becomes positive

            final int power10 = (int)Math.pow(10, (value == 0 ? 1 : (int)Math.log10(value)));
            if (shiftLeft) {
                final int msd = value / power10; // Most significant digit
                // Removes the most significant digit, shifts all digits left, then adds the most significant digit
                value = (value - msd * power10) * 10 + msd;
            } else {
                final int lsd = value % 10; // Least significant digit
                // Shifts all digits right,then adds the least significant digit to the most significant position
                value = (value / 10) + (lsd * power10);
            }

            // Set new value with its original sign
            context.value = sign * value;
        }
    }

    public static class MirrorAction extends Action {
        public MirrorAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            int value = context.getValue();
            final int power10 = (int)Math.pow(10, (value == 0 ? 1 : (int)Math.log10(value)) + 1);
            final int sign = value < 0 ? -1 : 1;
            value *= sign;

            int reversed = 0;
            while (value != 0) {
                reversed = (reversed * 10) + (value % 10);
                value /= 10;
            }

            context.value = sign * (context.getValue() * power10 + reversed);
        }
    }

    public static class InverseAction extends Action {
        public InverseAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            int value = context.getValue();
            final int sign = value < 0 ? -1 : 1;
            value *= sign;

            int inversed = 0;
            int pow10 = 1;
            while (value != 0) {
                inversed += ((10 - (value % 10)) % 10) * pow10;
                pow10 *= 10;
                value /= 10;
            }

            context.value = sign * inversed;
        }
    }

    public static abstract class IntegerAction extends Action {
        final int intValue;

        public IntegerAction(String value) {
            super(value);
            intValue = Integer.parseInt(value.replaceAll("[^\\d\\-]*(-?\\d+).*", "$1"));
        }

        @Override
        public String toString(GameContext context) {
            return toString().replaceFirst(Integer.toString(intValue), Integer.toString(intValue + context.getModifier() * (intValue < 0 ? -1 : 1)));
        }
    }

    public static class AddAction extends IntegerAction {
        public AddAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            context.value = context.getValue() + intValue + context.getModifier() * (intValue < 0 ? -1 : 1);
        }
    }

    public static class MultiplyAction extends IntegerAction {
        public MultiplyAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            context.value = context.getValue() * (intValue + context.getModifier() * (intValue < 0 ? -1 : 1));
        }
    }

    public static class PowerAction extends IntegerAction {
        public PowerAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            context.value = (float)Math.pow(context.getValue(), intValue);
        }
    }

    public static class DivideAction extends IntegerAction {
        public DivideAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            context.value = context.value / (intValue + context.getModifier() * (intValue < 0 ? -1 : 1));
        }
    }

    public static class InsertAction extends IntegerAction {
        public InsertAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            final int powerOf10 = (intValue + context.getModifier()) == 0 ? 10 : (int)Math.pow(10, (int)Math.log10(intValue + context.getModifier()) + 1);
            context.value = context.getValue() * powerOf10 + ((intValue + context.getModifier()) * (context.getValue() < 0 ? -1 : 1));
        }
    }

    public static class ReplaceAction extends IntegerAction {
        final Pattern replacePattern;
        final String replaceWith;

        public ReplaceAction(String value) {
            super(value);
            replacePattern = Pattern.compile(Integer.toString(intValue));
            replaceWith = value.replaceAll("[^=]+=>(-?\\d+)", "$1");
        }

        // TODO: Optimization candidate
        // TODO: Modifier?
        @Override
        public void apply(GameContext context) {
            context.value = Integer.parseInt(replacePattern.matcher(Integer.toString(context.getValue())).replaceAll(replaceWith));
        }
    }

    public static abstract class ModifierAction extends IntegerAction {
        public ModifierAction(String value) {
            super(value);
        }
    }

    public static class AddModifierAction extends ModifierAction {
        public AddModifierAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            context.modifier += intValue;
        }
    }

    public static abstract class StoreAction extends Action {
        public StoreAction(String value) {
            super(value);
        }
    }

    public static class SetStoreAction extends StoreAction {
        public SetStoreAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            context.store = context.getValue();
        }

        @Override
        public String toString(GameContext context) {
            return stringValue + " " + ((int)context.value);
        }
    }

    public static class LoadStoreAction extends StoreAction {
        public LoadStoreAction(String value) {
            super(value);
        }

        @Override
        public void apply(GameContext context) {
            final int powerOf10 = (context.store + context.getModifier()) == 0 ? 10 : (int)Math.pow(10, (int)Math.log10(context.store + context.getModifier()) + 1);
            context.value = context.getValue() * powerOf10 + ((context.store + context.getModifier()) * (context.getValue() < 0 ? -1 : 1));
        }

        @Override
        public String toString(GameContext context) {
            return stringValue + " " + context.store;
        }
    }
}