egg-dropping.js

/**
 * Egg-dropping problem.
 * You have limited number of (crystal) eggs and limited number of throws,
 * and want to check some tower, determining highest floor where egg
 * will not break when thrown from there.
 *
 * This function will tell the max height of the building which could be tested
 * with the given number of eggs and throws.
 *
 * @param n int Number of eggs
 * @param m int Number of throws
 * @return int Max storeys in the building you can test with n eggs and m throws.
 */

// Non-optimal, will break on high n, m values:
function h(n, m) {
  if (n < 1 || m < 1) return 0;
  if (n === 1) return m;
  if (m === 1) return 1;
  if (n === m) return Math.pow(2, n) - 1;
  return 1 + h(n-1, m-1) + h(n, m-1);
}

// Combinatorics power!
function C(n, k) {
  if (k < 1) return 1;
  return (n - k + 1) / k * C(n, k - 1);
}
// Rewrite.
// Basically, sum of Pascal triangle m-th line numbers from 1 to n
function h(n, m) {
  let res = 0;
  for (let k = 1; k <= n; k++) {
    res += C(m, k);
  }
  return res;
}


/* 
  Inverse application example.
  Classic "2 eggs, 100 storeys" problem:

  > Suppose you have two eggs and you want to determine from which floors in a one hundred floor building you can drop an egg such that is doesn't break.
  > You are to determine the minimum number of attempts you need in order to find the critical floor in the worst case while using the best strategy.
*/
const floors = 100;
for (let i = 1; i < floors / 2; i++) {
  if ( h(2, i) >= floors ) {
    console.log(i);
    break;
  }
}
// Answer is 14.
// Of course, direct solution is much faster:
// Math.ceil( (Math.sqrt(8 * floors + 1) - 1) / 2 )