30:T6f0,state = { hopButton; let state = this || { currentHole: firstHoleToCheck, rabbitPosition: start, message: "Not started..." }; // state.possibleRabbitPositions[firstGuess] = 1; if (paused) return yield state; for (; state.currentHole < length; ++state.currentHole) { await Promises.delay(delay); // Did we find the bunny? if (state.rabbitPosition === state.currentHole) { state.message = `Found bunny at hole ${state.currentHole} ⛳🐰`; return yield state; } /* attempt to keep track of all possible rabbit positions but blows up as numbers become very large for (let i = 0; i < length; i++) { const rabbitsPossiblyAtPos = d3.range(state.possibleRabbitPositions[i]); if (i === 0) { for (const d of rabbitsPossiblyAtPos) { state.possibleRabbitPositions[1] += 1; } } else if (i === length - 1) { for (const d of rabbitsPossiblyAtPos) { state.possibleRabbitPositions[length - 2] += 1; } } else { for (const d of rabbitsPossiblyAtPos) { const hop = randomHop(); const nextHole = i + hop; state.possibleRabbitPositions[nextHole] += 1; } // count rabbit can be possibly be in this hole } }*/ // If not, bunny hops if (state.rabbitPosition === length - 1) { state.rabbitPosition -= 1; } else if (state.rabbitPosition === 0) { state.rabbitPosition += 1; } else { const hop = randomHop(); state.rabbitPosition += hop; } state.message = state.currentHole === length - 1 ? `Last hole (${state.currentHole}) and bunny not found 🐇` : `Bunny not found in hole ${state.currentHole} 🕳️`; yield state; } }31:[] 2e:{"title":"Rabbit in the Hole","cells":[{"id":0,"value":"# Rabbit in the Hole\n\nIn [Ben Awad's 'coding interview' with React Core team member Dan Abramov](https://www.youtube.com/watch?v=XEt09iK8IXs?t=1265) he posed Dan the following tricky coding interview question:\n\n> *There are 100 holes 🕳️ in a line, and there's a rabbit 🐰 hiding in one of the holes*\n>\n> *You can only look in one hole at a time, and every time you look in a hole, the rabbit jumps to an adjacent hole.*\n> ***Find the rabbit***\n\n> *A good solution finds the right algorithm with the best ${tex`\\mathcal{O}`}, bonus points for providing the exact number of worst case searches for 100 holes*","pinned":false,"hidden":false,"mode":"md"},{"id":814,"value":"If we move through the holes by checking them sequentially from the first hole (`[0]`), the rabbit could jump back when we check the hole next to it, thereby slipping past us.\nThis is determined by whether the rabbit starts at an even or odd position (assuming we start checking at `[0]`.\n\nNow, we start checking at hole ${firstHoleToCheck} which is **${firstCheckParity}**, the rabbit's starts at hole ${start} which is **${rabbitStartParity}**. ${firstCheckParity === rabbitStartParity ? `Both are *${firstCheckParity}*, so we'll find the rabbit.` : \"They're not both even or odd, __so we won't find the rabbit__ by checking all holes sequentially.\" }","pinned":false,"hidden":false,"mode":"md"},{"id":663,"value":"## ${state.message}","pinned":false,"hidden":false,"mode":"md"},{"id":712,"value":"viewof paused = Inputs.toggle({ label: \"Pause ⏸️\", value: false }) // thanks Mike, https://observablehq.com/@mbostock/pause-a-generator","pinned":false,"hidden":false,"mode":"ojs"},{"id":1036,"value":"viewof firstHoleToCheck = Inputs.radio([0, 1], {\n label: \"First hole to check\",\n value: 1\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":8,"value":"viewof start = Inputs.range([0, length - 1], {\n step: 1,\n label: \"Start position of rabbit🐰\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":144,"value":"viewof length = Inputs.range([5, 250], {\n step: 5,\n value: 100,\n label: \"Number of holes\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":616,"value":"viewof delay = Inputs.range([50, 1500], {\n step: 50,\n value: 250,\n label: \"Delay (ms)\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":134,"value":"html`

\n${holes.map(\n (h, i) =>\n `

${h ? \"🐰\" : \"🕳\"}

${i}

`\n)}\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":190,"value":"viewof hopButton = Inputs.button(\"Restart hopping 🐰🐇\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":743,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":751,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":847,"value":"randomHop = () => (Math.random() > 0.5 ? 1 : -1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":5,"value":"holes = {\n const newHoles = Array.from({ length }).fill(false);\n newHoles[state.rabbitPosition] = true;\n\n return newHoles;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":648,"value":"getBorderStyle = (h, i) =>\n h && state.currentHole === i\n ? \"3px solid hotpink\"\n : h\n ? \"2px solid crimson\"\n : state.currentHole === i\n ? \"2px solid black\"\n : \"1px solid hsl(0, 0%, 90%)\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":899,"value":"rabbitStartParity = checkParity(start)","pinned":true,"hidden":false,"mode":"ojs"},{"id":896,"value":"firstCheckParity = checkParity(firstHoleToCheck)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1042,"value":"checkParity = (number) => (number % 2 ? \"odd\" : \"even\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}