The Josephus Problem

alert(getJosephus(getOrdinalsUpTo(getCount(1, 100))));

function getJosephus(queue) {
  let lastRemoved;
  while (queue.length > 0) {
    queue.push(queue.shift());
    lastRemoved = queue.shift();
  }
  return lastRemoved;
}

function getOrdinalsUpTo(n) {
  const ordinals = [];
  for (let ordinal = 1; ordinal <= n; ordinal++) {
    ordinals.push(ordinal);
  }
  return ordinals;
}

function getCount(lower, upper) {
  const p = "Enter a positive integer greater than " +
    lower - 1 + " and less than " + upper + ".";
  let value;
  while (!Number.isInteger(value) || value < lower || value >= upper) {
    response = prompt(p);
    if (response === null) return 0;
    value = parseFloat(response);
  }
  return value;
}

Exercises

1. The program shown above is defective. Fix it.
2. Replace getCount with getRandomCount.
3. In getOrdinalsUpTo, replace [] with new Queue.
   1. Implement Queue using linked nodes.
   2. Implement Queue using a fixed-length array. (Do not use methods of Array.)
4. Implement getJosephus by manipulating the bits of the base two representation of the input value. (See Finding Josephus.)
5. Implement and use getRebels instead of getOrdinalsUpTo.
   1. Have getRebels return a list of names. (Use getRandomName?)
      • A list of popular first names.
      • Lists of popular surnames.
   2. Have getRebels return a list of Rebel objects. (Use getRandomRebel?)
6. Replace getJosephus with getJosephusSequence.
7. Repeat these exercises using other programming languages.