From the viking code school engineering principles prep course:
10 friends are sitting in a circle around a table and decide to play a new game. In it, they count up through the numbers from 1 to 100. The first person says "1", the second says "2" and so on... but with a few catches:
Whenever the number is divisible by 7, they switch directions. So person 6 will say "6", person 7 will say "7", then person 6 again will say "8". Whenever the number is divisible by 11, they skip the next person.
Pseudocode a program that will determine which player is the one to say "100". How does one begin figuring out the logic to this one?
Oftentimes in programming, choosing a suitable data structure can drastically simplify the algorithm for solving a particular problem. Your problem can be elegantly solved using a circular doubly-linked list. Since there are ten friends sitting in a circle, we'll put them into the linked list as follows:
next +-------+ next
+--------->| |----------+
| | 1 | |
| +--| |<--+ v
+-------+ | +-------+ | +-------+
| | | | | |
+-->| 10 |<--+ prev prev +--| 2 |---+
| | | | | |
next | +-------+ +-------+ | next
| | ^ v
+-------+ | prev prev | +-------+
| | | | | |
| 9 |<--+ +---| 3 |
| | | |
+-------+ +-------+
^ | ^ |
next | | prev prev | | next
| v | v
+-------+ +-------+
| | | |
| 8 |---+ +-->| 4 |
| | | | | |
+-------+ | prev prev | +-------+
^ v | |
next | +-------+ +-------+ | next
| | | | | |
+---| 7 |--+ prev prev +-->| 5 |<--+
| | | | | |
+-------+ | +-------+ | +-------+
^ +-->| |--+ |
| | 6 | |
+----------| |<---------+
next +-------+ next
For example, in JavaScript you could write it as:
var firstFriend = toList([1,2,3,4,5,6,7,8,9,10]);
function Node(prev, data, next) {
this.prev = prev;
this.data = data;
this.next = next;
}
function toList(array) {
var length = array.length;
if (length === 0) throw new Error("empty array");
var root = new Node(null, array[0], null), node = root, i = 1;
while (i < length) node = node.next = new Node(node, array[i++], null);
return (root.prev = node).next = root;
}
Now, we can solve the problem using two mutually recursive functions: one for the friends counting in the forward direction and one for the friends counting in the reverse direction:
var answer = forward(1, firstFriend);
function forward(count, friend) {
if (count === 100) return friend.data;
if (count % 7 === 0 &&
count % 11 === 0) return reverse(count + 1, friend.prev.prev);
if (count % 7 === 0) return reverse(count + 1, friend.prev);
if (count % 11 === 0) return forward(count + 1, friend.next.next);
return forward(count + 1, friend.next);
}
function reverse(count, friend) {
if (count === 100) return friend.data;
if (count % 7 === 0 &&
count % 11 === 0) return forward(count + 1, friend.next.next);
if (count % 7 === 0) return forward(count + 1, friend.next);
if (count % 11 === 0) return reverse(count + 1, friend.prev.prev);
return reverse(count + 1, friend.prev);
}
Putting it all together, the answer is 1:
var firstFriend = toList([1,2,3,4,5,6,7,8,9,10]);
var answer = forward(1, firstFriend);
alert(answer);
function Node(prev, data, next) {
this.prev = prev;
this.data = data;
this.next = next;
}
function toList(array) {
var length = array.length;
if (length === 0) throw new Error("empty array");
var root = new Node(null, array[0], null), node = root, i = 1;
while (i < length) node = node.next = new Node(node, array[i++], null);
return (root.prev = node).next = root;
}
function forward(count, friend) {
if (count === 100) return friend.data;
if (count % 7 === 0 &&
count % 11 === 0) return reverse(count + 1, friend.prev.prev);
if (count % 7 === 0) return reverse(count + 1, friend.prev);
if (count % 11 === 0) return forward(count + 1, friend.next.next);
return forward(count + 1, friend.next);
}
function reverse(count, friend) {
if (count === 100) return friend.data;
if (count % 7 === 0 &&
count % 11 === 0) return forward(count + 1, friend.next.next);
if (count % 7 === 0) return forward(count + 1, friend.next);
if (count % 11 === 0) return reverse(count + 1, friend.prev.prev);
return reverse(count + 1, friend.prev);
}Solving it manually to check for correctness:
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
+=====+=====+=====+=====+=====+=====+=====+=====+=====+=====+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 12 | | 11 | 10 | 9 | 8 | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | | 14 | 13 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | | | 15 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 16 | 17 | 18 | 19 | 20 | 21 | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 25 | 24 | 23 | | 22 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | 28 | 27 | 26 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | | 29 | 30 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 31 | 32 | 33 | | 34 | 35 | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 40 | 39 | 38 | 37 | 36 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | | 42 | 41 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | | | 43 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 44 | | 45 | 46 | 47 | 48 | 49 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 55 | 54 | 53 | 52 | 51 | 50 | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | | 56 | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | | | 57 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 58 | 59 | 60 | 61 | 62 | 63 | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 67 | | 66 | 65 | 64 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | 70 | 69 | 68 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | | 71 | 72 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 73 | 74 | 75 | 76 | 77 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 80 | 79 | 78 | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | 84 | 83 | 82 | 81 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | 85 | 86 | 87 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 88 | | 89 | 90 | 91 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 95 | 94 | 93 | 92 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | 98 | 97 | 96 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | | 99 | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 100 | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Although this solution is recursive, every recursive program can be converted into a non-recursive program using a stack. The pseudocode for this program is very simple. Hence, I'll leave it as an exercise for you to figure out.