cielux
10/24/2018 - 6:27 AM

Find Rotation Point

const words = [ 'ptolemaic', 'retrograde', 'supplant', 'undulate', 'xenoepist', 'asymptote', // <-- rotates here! 'babka', 'banoffee', 'engender', 'karpatka', 'othellolagkage', ];

Write a function for finding the index of the "rotation point," which is where I started working from the beginning of the dictionary. This array is huge (there are lots of words I don't know) so we want to be efficient here.

findRotationPoint.js
content_copyfile_download
function findRotationPoint(words) {
  // Find the rotation point in the vector
  let firstWord = words[0];
  let start = 0;
  let end = words.length-1;
  while (start < end) {
    const halfway = Math.floor((end - start)/2);
    const guessIndex = start + halfway;
    const guessPoint = words[guessIndex];
    if (guessPoint >= firstWord) {
      start = guessIndex;
    } else {
      end = guessIndex;
    }
    if (start + 1 === end) {
      break;
    }
  }
  return end;
}

// Tests

let desc = 'small array';
let actual = findRotationPoint(['cape', 'cake']);
let expected = 1;
assertEquals(actual, expected, desc);

desc = 'medium array';
actual = findRotationPoint(['grape', 'orange', 'plum', 'radish', 'apple']);
expected = 4;
assertEquals(actual, expected, desc);

desc = 'large array';
actual = findRotationPoint(['ptolemaic', 'retrograde', 'supplant',
  'undulate', 'xenoepist', 'asymptote',
  'babka', 'banoffee', 'engender',
  'karpatka', 'othellolagkage']);
expected = 5;
assertEquals(actual, expected, desc);

function assertEquals(a, b, desc) {
  if (a === b) {
    console.log(`${desc} ... PASS`);
  } else {
    console.log(`${desc} ... FAIL: ${a} != ${b}`);
  }
}