*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

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); } } }

## No comments:

## Post a Comment