Created
December 19, 2015 07:51
-
-
Save DavidGoussev/38d2d0ebaf782ff259d0 to your computer and use it in GitHub Desktop.
Dont Eat the Last Cake!
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Player | |
| def initialize(cakes) | |
| end | |
| # Decide who move first - player or opponent (return true if player) | |
| def firstmove(cakes) | |
| # games with < 2 cakes are unwinnable when going first because the starting player | |
| # can always be forced into a loss condition: | |
| # 1 cakes | |
| # - pick 1 (lose, they ate the cake!) | |
| # - pick 2/3 (invalid move) | |
| # | |
| # 2 cakes | |
| # - pick 1 (lose, they created stalemate) | |
| # - pick 2 (lose, they ate the cake) | |
| # - pick 3 (invalid move) | |
| # games with remainder of 2 are unwinnable when going first because player 1 | |
| # can always be forced into a loss condition: | |
| # e.g. 6 cakes | |
| # 1. p1 (5) -> c3 (2) -> (lose, stalemate) | |
| # 2. p2 (4) -> c3 (1) -> (lose, must eat cake) | |
| # 3. p3 (3) -> c2 (1) -> (lose, must eat cake) | |
| cakes > 2 && cakes % 4 != 2 | |
| end | |
| def move(cakes, last) | |
| # Last chosen position actually doesn't matter! Red herring! Only science matters! | |
| # Since we can start computer on a losing position because of first-movers advantage, | |
| # we can constantly force them back into a losing position in 1 or 2 turns. | |
| # p[cakes % 4 == 0] -> choose 3, computer must choose 2 or 1; if 1, they're in losing position, | |
| # if 2, then we pick 1 next round to put them in losing position | |
| # p[cakes % 4 == 1] -> choose 3, computer in losing position | |
| # p[cakes % 4 == 2] -> not possible because we avoid this losing position by first-players choice | |
| # p[cakes % 4 == 3] -> choose 1, computer in losing position | |
| # Therefore, the first move actually decides the game, as long as | |
| # the first player always uses their leverage. | |
| cakes % 4 < 3 ? 3 : 1 | |
| end | |
| end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
how did you arrive at division by 4?