While playing
Final Fantasy XIII-2, I came across an interesting puzzle. The puzzle is as follows.
Given n-numbers in a circle that form numbers similar to the ones in a clock. Like a clock, it has two pointers (e.g. the hour and the minute) that move to the left and to the right. Initially both pointers are pointing to the same number and we are allowed to choose any number to begin with. For any number that we pick, the two pointers will move x steps to the left and x steps to the right where x is the value shown in the number that we pick. For each number that we pick, the number will disappear and we cannot pick that number again. The next step is to pick any number that the left or right pointer is pointing to. The win this puzzle, we need to perform n-moves that will eliminate all the numbers in the clock. If both pointers are pointing to the numbers that have disappeared and there are still numbers that have not disappeared, we are lost.
Example:
2
3 1
3 3
2 2
2
We pick 2 (north). Number 2 (north) will disappear. The left pointer will move 2 steps to the left and pointing to 3 (west). The right pointer will move to 2 steps to the right and pointing to 3 (east)
We pick 3 (west). Number 3 (west) will disappear. The left pointer will move 3 steps to the left and pointing to 2 (southeast). The right pointer will move 3 steps to the right pointing to 1 (northeast)
We pick 2 (southeast). Number 2 (southeast) will disappear. The left pointer wil move 2 steps to the left and pointing to 1 (northeast). The right pointer will move 2 steps to the right pointing to 2 (southwest)
We keep picking a number that either a left or right pointer is pointing to and we need to make sure that if there are still some numbers in the clock, both left and right pointers must not point to the numbers that have disappeared. Once all the numbers have disappeared, we have won the puzzle
One possible solution.
1. Init --> 2
2. Left --> 3
3. Left --> 2
4. Left --> 1
5. Right --> 3
6. Right --> 2
7. Right --> 3
8. Left --> 2
My solution in Java.
import java.util.ArrayList;
import java.util.List;
public class ClockPuzzle {
private static class Number implements Cloneable {
private boolean marked;
private final int value;
public Number(int value) {
this.value = value;
}
public Number(int value, boolean marked) {
this.value = value;
this.marked = marked;
}
@Override
protected Object clone() {
return new Number(value, marked);
}
}
private static enum Direction {
INIT("Init "),
LEFT("Left "),
RIGHT("Right");
private String str;
private Direction(String str) {
this.str = str;
}
@Override
public String toString() {
return str;
}
}
private final Number[] numbers;
private final int size;
public ClockPuzzle(int... values) {
numbers = new Number[values.length];
for (int i = 0; i < values.length; i++) {
numbers[i] = new Number(values[i]);
}
size = values.length;
}
public void solve(int index) {
List<String> result = new ArrayList<>();
Number[] newNumbers = copy(numbers);
result.add(createResult(Direction.INIT, index, newNumbers[index].value));
solve(newNumbers, index, result);
}
private void solve(Number[] numbers, int index, List<String> result) {
Number e = numbers[index];
if (e.marked) {
return;
}
e.marked = true;
if (allMarked(numbers)) {
printResult(result);
} else {
// the left pointer
int leftIndex = getActualIndex(index-e.value, numbers.length);
solve(leftIndex, Direction.LEFT, numbers, result);
// the right pointer
int rightIndex = getActualIndex(index+e.value, numbers.length);
solve(rightIndex, Direction.RIGHT, numbers, result);
}
}
private void solve(int index, Direction direction, Number[] numbers, List<String> result) {
Number[] newNumbers = copy(numbers);
List<String> newResult = copy(result);
newResult.add(createResult(direction, index, newNumbers[index].value));
solve(newNumbers, index, newResult);
}
private Number[] copy(Number[] numbers) {
Number[] newNumbers = new Number[numbers.length];
for (int i = 0; i < newNumbers.length; i++) {
newNumbers[i] = (Number) numbers[i].clone();
}
return newNumbers;
}
private String createResult(Direction direction, int index, int value) {
return direction.toString() + " --> " + value + " (index: " + index + ")";
}
private List<String> copy(List<String> list) {
List<String> newList = new ArrayList<>();
for (String s : list) {
newList.add(s);
}
return newList;
}
private void printHeader() {
for (int i = 0; i < 50; i++) {
System.out.print("=");
}
System.out.println();
}
private void printResult(List<String> result) {
printHeader();
int i = 1;
for (String r : result) {
if (i < 10) {
System.out.println(" " + i++ + " " + r);
} else {
System.out.println(i++ + " " + r);
}
}
printHeader();
}
private boolean allMarked(Number[] numbers) {
for (Number n : numbers) {
if (!n.marked) {
return false;
}
}
return true;
}
private int getActualIndex(int i, int arraySize) {
if (i >= arraySize) {
return i - arraySize;
}
if (i < 0) {
return arraySize + i;
}
return i;
}
public static void main(String[] args) {
ClockPuzzle clockPuzzle = new ClockPuzzle(2, 1, 3, 2, 2, 2, 3, 3);
for (int i = 0; i < clockPuzzle.size; i++) {
clockPuzzle.solve(i);
}
}
}
