Two Egg Problem

Looking at the average number of drops needed for different strategies.

by asemahle

HTML

<script src="https://unpkg.com/vue"></script>
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0/css/bootstrap.min.css" integrity="sha384-Gn5384xqQ1aoWXA+058RXPxPg6fy4IWvTNh0E263XmFcJlSAwiGgFAW/dAiS6JXm" crossorigin="anonymous">

<div id="app">
  <h1>Two Egg Problem</h1>
  <p>Watch a video description of the problem <a href="https://www.youtube.com/watch?v=NGtt7GJ1uiM">HERE</a>.</p>
  <p>This program will calculate the average number of egg drops needed to find the best egg.</p>
  <p>Enter the number of floors that you will ascend at each step when testing the first egg. The video provides a solution of '14,13,12,11,10,9,8,7,6,5,4', which results in an average of 10.366 floors. Can you do better?</p>
  
  <p><sub>asemahle's conjecture: you can do no better than 10.356435643564357</sub></p>

  <div class="form-group">
    <label><b>Increments:</b></label>
    <input v-model="inp" class="form-control" placeholder="Enter increments">
  </div>
  
  <b>Average Drops:</b> 
  <p>{{ avgDrops }} {{msg}}</p>
  
  <b>High Scores:</b>
  <p v-if="Object.keys(highScores).length == 0">You have not beaten the video score</p>
  <ul v-else>
    <li v-for="(score, key) in highScores">{{ score }} - {{ key }}</li>
  </ul>
  
  <b>Breakdown (how many drops are needed if the egg breaks on the N<sup>th</sup> floor?):</b>
  <table class="table">
    <thead>
      <tr>
        <th scope="col">Floor</th>
        <th scope="col">1<sup>rst</sup> Egg Drops</th>
        <th scope="col">2<sup>nd</sup> Egg Drops</th>
        <th scope="col">Total Drops</th>
      </tr>
    </thead>
    <tbody>
      <tr v-for="(floor, idx) in dropsPerFloor">
        <td>{{ idx == dropsPerFloor.length - 1 ? 'Egg Never Breaks' : idx + 1 }}</td>
        <td>{{ floor[0] }} (floor {{ floorsForFirstEgg[floor[0]-1]||'N/A' }})</td>
        <td>{{ floor[1] }}</td>
        <td>{{ floor[0] + floor[1] }}</td>
      </tr>
    </tbody>
  </table>
  
</div>

JavaScript

const NUM_FLOORS = 100;

new Vue({
  el: '#app',
  data: {
    inp: '14,13,12,11,10,9,8,7,6,5,4',
    vidAvg: 10.366336633663366,
    highScores: {}
  },
  watch: {
  	avgDrops() {
      let strVal = this.avgDrops.toString();
    	if (this.avgDrops < this.vidAvg && !this.highScores[strVal]) {
      	this.$set(this.highScores, strVal, this.inp);
        console.log(this.highScores);
      }
    }
  },
  computed: {
  	msg() {
      let result = this.avgDrops == this.vidAvg ? 
        'equal to' : this.avgDrops < this.vidAvg ? 
        'better than' : 'worse than';
      return "(this is " + result + " the video solution)";
    },
  	increments() {
      return this.inp.replace(/[^\d,]/g, '') // strip non-digit & non-comma
      	.split(',') // turn into array on comma
        .filter(e => e != '') // remove empty values
        .map(e => parseInt(e)); // convert values to numbers
    },
    floorsForFirstEgg() {
    	let floors = [];
      let currentFloor = 0;
      for (let i of this.increments) {
      	currentFloor += i;
        floors.push(currentFloor);
      }
      return floors;
    },
    dropsPerFloor() {
    	dropsPerFloor = [];
      for (let breakFloor = 1; breakFloor <= NUM_FLOORS + 1; breakFloor++) {
      	let egg1Drops = 0;
        let egg2Drops = 0
        let lowerBound = -1;
        let upperBound = NUM_FLOORS + 1;
      	// simulate dropping first egg
        for (let floor of this.floorsForFirstEgg) {
        	if (upperBound - lowerBound === 2) break;
          egg1Drops++;
          if (floor < breakFloor) lowerBound = Math.max(lowerBound, floor-1);
          else { upperBound = Math.min(upperBound, floor); break; }
        }
        //simulate dropping second egg
        for (let floor = lowerBound + 2; floor < upperBound; floor++) {
        	if (upperBound - lowerBound === 2) break; 
          egg2Drops++;
          if (floor < breakFloor) lowerBound = Math.max(lowerBound, floor-1);
          else upperBound = Math.min(upperBound,...