Question

Imagine you have a rotary combination lock with many dials. Each dial has the digits 0 - 9. At any point in time, one digit from each dial is visible.

Each dial can be rotated up or down. For some dial, if a 4 is currently visible then rotating the dial up would make 5 visible; rotating the dial down would make 3 visible. When 0 is the visible digit then rotating down would make 9 visible. Similarly, when 9 is visible then rotating up would make 0 visible.

We have devised a robotic finger to manipulate such combination systems. The robotic finger takes as input a String that indicates the operations to be performed. An L moves the finger one dial to the left, an R moves the finger one dial to the right, and a + rotates the dial that the finger is at up and a - rotates the dial that the finger is at down.

The robotic finger always starts at the leftmost dial.

Task 1: Basic Operations

Valid Sequence

Given a String that consists of (only) the characters L, R, + and -, determine if this String represents a valid sequence of operations.

A valid sequence of operations would not move the finger to the left of the leftmost dial or to the right of the rightmost dial.

public boolean validOperation(String ops, int numDials) {

Rotations

Given a sequence of operations in String form, as well as an initial arrangement of the dials, determine the digits that will be visible after the operations have been performed.

public int[] rotate(int[] initialState, String ops) {

Task 2: Finding Rotation Sequences

Given an initial state of the dials and a final state, return a String that represents a sequence of operations of shortest length that transforms the initial state to the final state.

public String getRotationSequence(int[] initialState, int[] newState) {

TEST CASE

@Test
public void testValidOp1() {
    RoboticFinger rf = new RoboticFinger();
    assertTrue(rf.validOperation("R++L++-RRR", 4));
}

@Test
public void testValidOp2() {
    RoboticFinger rf = new RoboticFinger();
    assertTrue(!rf.validOperation("R++L++-RRR", 3));
}

@Test
public void testValidOp3() {
    RoboticFinger rf = new RoboticFinger();
    assertTrue(!rf.validOperation("L-+R++RR", 10));
}

@Test
public void testValidOp4() {
    RoboticFinger rf = new RoboticFinger();
    assertTrue(!rf.validOperation("RRR+-R+R+LL", 4));
}

@Test
public void testValidOp5() {
    RoboticFinger rf = new RoboticFinger();
    assertTrue(rf.validOperation("RRR+-R+R+LL", 6));
}

@Test
public void testRotate1() {
    RoboticFinger rf = new RoboticFinger();
    int[] initialState = {1, 2, 4, 4, 5};
    String ops = "R++R-";
    int[] expectedState = {1, 4, 3, 4, 5};
    assertArrayEquals(expectedState, rf.rotate(initialState, ops));
}

@Test
public void testRotate2() {
    RoboticFinger rf = new RoboticFinger();
    int[] initialState = {1, 2, 4, 4, 5};
    String ops = "R++R-R-L++";
    int[] expectedState = {1, 4, 5, 3, 5};
    assertArrayEquals(expectedState, rf.rotate(initialState, ops));
}

@Test
public void testRotate3() {
    RoboticFinger rf = new RoboticFinger();
    int[] initialState = {7, 0, 2, 9, 1, 5, 6};
    String ops = "R-R++R+++R+RR--";
    int[] expectedState = {7, 9, 4, 2, 2, 5, 4};
    assertArrayEquals(expectedState, rf.rotate(initialState, ops));
}

@Test
public void testGetRotationSequence1() {
    RoboticFinger rf = new RoboticFinger();
    int[] initialState = {1, 2, 4, 4, 4, 7};
    int[] finalState = {2, 7, 3, 4, 8, 9};
    int expectedLength = "+R+++++R-RR++++R++".length();
    String ops = rf.getRotationSequence(initialState, finalState);
    assertArrayEquals(finalState, rf.rotate(initialState, ops));
    assertEquals(expectedLength, ops.length());
}

@Test
public void testGetRotationSequence2() {
    RoboticFinger rf = new RoboticFinger();
    int[] initialState = {9, 9, 9, 9, 9, 9, 1};
    int[] finalState = {2, 7, 3, 4, 8, 9, 2};
    int expectedLength = 22;
    String ops = rf.getRotationSequence(initialState, finalState);
    assertArrayEquals(finalState, rf.rotate(initialState, ops));
    assertEquals(expectedLength, ops.length());
}

@Test
public void testGetRotationSequence3() {
    RoboticFinger rf = new RoboticFinger();
    int[] initialState = {5};
    int[] finalState = {7};
    int expectedLength = 2;
    String ops = rf.getRotationSequence(initialState, finalState);
    assertArrayEquals(finalState, rf.rotate(initialState, ops));
    assertEquals(expectedLength, ops.length());
}

Answer 1

Main.java:

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {

        // object to run tests on
        Robot robot = new Robot();

        // task 1
        {
            int[] initialState = {7, 0, 2, 9, 1, 5, 6};
            String ops = "R-R++R+++R+RR--";
            int[] expectedState = {7, 9, 4, 2, 2, 5, 4};
            int[] finalState = robot.rotate(initialState, ops);
            assert Arrays.equals(expectedState, finalState) : "task 1 failed";
        }

        // task 2
        {
            int[] initialState = {1, 2, 4, 4, 4, 7};
            int[] finalState = {2, 7, 3, 4, 8, 9};
            int expectedLength = "+R+++++R-RR++++R++".length();
            String rotationSequence = robot.getRotationSequence(initialState, finalState);
            assert expectedLength == rotationSequence.length() : "task 2 failed";
        }
    }
}
Robot.java:

public class Robot {
    /**
     * Determine the digits that will be visible after the operations have been performed
     *
     * @param initialState represents the state of the combination dials and {@code 0 <= initialState[i] <= 9} for all {@code 0 <= i < initialState.length}.
     * @param ops          represents the operations to perform and only contains the characters 'L', 'R', '+' and '-' or {@code ops} is empty
     * @return the new state
     */
    public int[] rotate(int[] initialState, String ops) {

        int[] finalState = initialState.clone(); // copy of initialState that will be modified and returned

        int stateID = 0; // position of robotic finger

        for(int opsID = 0; opsID < ops.length(); ++opsID) {

            char character = ops.charAt(opsID);

            switch(character) {
                case 'L':
                    --stateID; // moving left
                    break;
                case 'R':
                    ++stateID; // moving right
                    break;
                case '+':
                    finalState[stateID] = (finalState[stateID] + 1) % 10; // dialing up
                    break;
                case '-':
                    finalState[stateID] = (finalState[stateID] + 9) % 10; // dialing down
            }
        }

        return finalState;
    }

    /**
     * Transform the initial state to a given new state using the shortest sequence of operations
     *
     * @param initialState represents the initial state of the dials, and {@code 0 < initialState.length <= 10}, and {@code 0 <= initialState[i] <= 9} for all {@code 0 <= i < initialState.length}.
     * @param newState     represents the new (desired) state of the dials, and {@code 0 < initialState.length <= 10}, and {@code 0 <= initialState[i] <= 9} for all {@code 0 <= i < initialState.length}. Also {@code newState.length() == initialState.length()}.
     * @return a representation of a shortest operation sequence that ensures that the initial state is transformed to the new state.
     */
    public String getRotationSequence(int[] initialState, int[] newState) {

        StringBuilder rotationSequence = new StringBuilder(); // to store the rotation sequence

        for(int stateID = 0; stateID < initialState.length; ++stateID) {

            int initialValue = initialState[stateID];
            int newValue = newState[stateID];

            int dialUpDistance = (newValue < initialValue ? newValue + 10 : newValue) - initialValue; // number of dial ups needed at this position
            int dialDownDistance = initialValue - (newValue > initialValue ? newValue - 10 : newValue); // number of dial downs needed at this position

            // appending the moves with the minimum length
            if(dialUpDistance <= dialDownDistance) {
                rotationSequence.append(new String(new char[dialUpDistance]).replace("\0", "+"));
            } else {
                rotationSequence.append(new String(new char[dialDownDistance]).replace("\0", "-"));
            }

            // moves right
            rotationSequence.append('R');
        }

        // removing "R"s from the end if any
        while(rotationSequence.length() > 0 && rotationSequence.charAt(rotationSequence.length() - 1) == 'R') {
            rotationSequence.deleteCharAt(rotationSequence.length() - 1);
        }

        return rotationSequence.toString();
    }
}

THUMBS UP IF YOU LIKE IT !