[Solved] People Dancing Algorithm

Current answer

The previous answer assumed that the movement of people to their new positions would be sequential, i.e. people would start moving together within the same sequence.

The answer below assumes that the movement within the same sequence is instantaneous. It uses two arrays to map people from their old positions to their new positions, and continues running the sequence as long as there is a reduction in the total number of spaces occupied.

public static void main(String[] args) {
    int numberOfPeople = 4;
    int[] moves = new int[]{3, 2, 1, 3};
    int[] positions = new int[numberOfPeople];

    Arrays.fill(positions, 1);

    int positionsOccupied;

    do {
        positionsOccupied = positionsOccupied(positions);
        positions = dance(positions, moves);

    } while (positionsOccupied(positions) < positionsOccupied);

    System.out.println("Result: " + positionsOccupied(positions));
}

public static int[] dance(int[] oldPositions, int[] moves) {
    int[] newPositions = new int[oldPositions.length];

    for (int i = 0; i < oldPositions.length; i++) {
        newPositions[moves[i] - 1] += oldPositions[i];
    }

    return newPositions;
}

public static int positionsOccupied(int[] positions) {
    int result = 0;

    for (int i = 0; i < positions.length; i++) {
        if (positions[i] > 0) {
            result++;
        }
    }

    return result;
}

Previous answer

You actually only need one array to hold the positions, and an additional array to hold a snapshot of the previous state.

After every iteration, the snapshot is compared with the current positions, and if they’re equal this means that subsequent invocations of the dance sequence will have no further impact on the positions and that you can calculate a final result:

public static void main(String[] args) {
    int numberOfPeople = 4;
    int[] moves = new int[]{3, 2, 1, 3};
    int[] positions = new int[numberOfPeople];

    Arrays.fill(positions, 1);

    int[] snapshot;

    do {
        snapshot = Arrays.copyOf(positions, positions.length);

        dance(positions, moves);
    } while (!Arrays.equals(positions, snapshot));

    System.out.println("Result: " + positionsOccupied(positions));
}

public static void dance(int[] positions, int[] moves) {
    for (int i = 0; i < positions.length; i++) {
        int currentNumber = positions[i];
        positions[i] = 0;
        positions[moves[i] - 1] += currentNumber;
    }
}

public static int positionsOccupied(int[] positions) {
    int result = 0;

    for (int i = 0; i < positions.length; i++) {
        if (positions[i] > 0) {
            result++;
        }
    }


    return result;
}