Skip to content

Instantly share code, notes, and snippets.

@alecklandgraf
Last active January 13, 2020 16:05
Show Gist options
  • Save alecklandgraf/8097ff66da18a0ce9d86a1ea870c43a2 to your computer and use it in GitHub Desktop.
Save alecklandgraf/8097ff66da18a0ce9d86a1ea870c43a2 to your computer and use it in GitHub Desktop.
/*
* 100 million simulations reveal of 63.1% chance of winning First Orchard.
*/
const GREEN_APPLES = "green apples";
const RED_APPLES = "red apples";
const PLUMBS = "plumbs";
const PEARS = "pears";
const BASKET = "basket";
const RAVEN = "raven";
const STRATEGY = "best";
function generateState() {
return {
[RAVEN]: 5,
[GREEN_APPLES]: 4,
[RED_APPLES]: 4,
[PLUMBS]: 4,
[PEARS]: 4
};
}
const die = [GREEN_APPLES, RED_APPLES, PLUMBS, PEARS, BASKET, RAVEN];
function rollDie() {
return die[Math.floor(Math.random() * 6)];
}
function findMax(state) {
let max = state[RED_APPLES];
let basket = RED_APPLES;
if (state[GREEN_APPLES] > max) {
basket = GREEN_APPLES;
max = state[GREEN_APPLES];
}
if (state[PLUMBS] > max) {
basket = PLUMBS;
max = state[PLUMBS];
}
if (state[PEARS] > max) {
basket = PEARS;
}
return basket;
}
function simulate() {
const state = generateState();
while (
state[RAVEN] !== 0 &&
[state[GREEN_APPLES], state[RED_APPLES], state[PLUMBS], state[PEARS]].some(
Boolean
)
) {
let roll = rollDie();
// worst strategy would be random or picking a tree with less fruit than another
if (roll === BASKET && STRATEGY === "best") {
roll = findMax(state);
}
if (state[roll] > 0) {
state[roll] -= 1;
}
}
return state[RAVEN] === 0 ? "lost" : "won";
}
module.exports = simulate;
@alecklandgraf
Copy link
Author

for perf, an interesting data structure could be something like

orchard = { 
  4: [ PEARS, GREEN_APPLES, RED_APPLES, PLUMBS ],
  3: [],
  2: [],
  1: [],
  0: [],
}

// when a fruit is picked, we move it, e.g.
4: [ PEARS, GREEN_APPLES, RED_APPLES ],
3: [ PLUMBS ],

// then the find max fruit algorithm can be
orchard[4][0] || orchard[3][0] || orchard[2][0] || orchard[1][0]

// double accounting would lower the cost of moving a fruit from 4 -3, 3-2, 2-1, and 1-0
if (state[roll] > 0) {
  removeElement(orchard[state[roll]], roll)
  orchard[state[roll] - 1].push(roll)
  state[roll] -= 1;
}

// N.B. a random strategy could be represented
validTrees = [4, 3, 2, 1].filter(fruitLeft => orchard[fruitLeft].length > 0)
basketSelected = orchard[validTrees[Math.floor(Math.random() * validTrees.length)]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment