31:[] 2f:{"title":"Three-Pile Nim","cells":[{"id":0,"value":"md`# Three-Pile Nim`","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"md`\n[Nim](https://en.wikipedia.org/wiki/Nim) is a simple mathematical strategy game for 2 players. The game starts with 3 piles of tokens. Two players take turns; on each turn, a player must remove one or more tokens from a single chosen pile. Nim is usually played as a “misère” game, where the player who removes the last token from the game loses. But the plot below shows the “normal play” game, where the player who removes the last token wins.\n\nIn the plot below, we color each square based on the size of third pile for which the current player will lose, if the other two piles have the sizes indicated by the row and column (assuming perfect play from both players). For any other size of third pile, the current player has a winning strategy.\n\nThis picture is generated using brute force over an *N* by *N* by *N* grid, which gets bogged down for larger sizes. The result can be proven equivalent to a simple bitwise xor operation, which would be a much faster method for generating a larger picture.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":127,"value":"viewof N = {\n var transform = x => Math.log2(x);\n transform.invert = x => 2 ** Math.floor(x)\n return Inputs.range([2, 128], {value: 16, transform, label: 'Size'})\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":45,"value":"Plot.cell(plotgrid, {\n x: 'x', y: 'y', fill: 'z', inset: -1,\n}).plot({\n width: 810, height: 800,\n x: {round: 0, axis: 'top', ticks},\n y: {round: 0, axis: 'left', ticks}\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":93,"value":"misère = false","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"grid = {\n let grid = [];\n for (let i = 0; i < N; i++) {\n grid[i] = [];\n for (let j = 0; j < N; j++) {\n grid[i][j] = [];\n for (let k = 0; k < N; k++) {\n grid[i][j][k] = +!test(i, j, k, grid);\n }\n }\n }\n return grid\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":22,"value":"test = (I, J, K, grid) => {\n if (misère && I + J + K === 0) return 1;\n let losses = 0;\n for (let i = 0; i < I; ++i) losses += grid[i][J][K];\n for (let j = 0; j < J; ++j) losses += grid[I][j][K];\n for (let k = 0; k < K; ++k) losses += grid[I][J][k];\n return losses;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":236,"value":"ticks = [0, 1, 2, 4, 8, 16, 32, 64, N-1].filter(x => x < N)","pinned":true,"hidden":false,"mode":"ojs"},{"id":37,"value":"plotgrid = {\n let plotgrid = [];\n for (let i = 0; i < N; i++) {\n for (let j = 0; j < N; j++) {\n for (let k = 0; k < N; k++) {\n if (grid[i][j][k]) plotgrid.push({x: i, y: j, z: k});\n }\n }\n }\n return plotgrid\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}