Skip to content

Instantly share code, notes, and snippets.

@DavidGoussev
Created December 19, 2015 07:51
Show Gist options
  • Select an option

  • Save DavidGoussev/38d2d0ebaf782ff259d0 to your computer and use it in GitHub Desktop.

Select an option

Save DavidGoussev/38d2d0ebaf782ff259d0 to your computer and use it in GitHub Desktop.
Dont Eat the Last Cake!
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
@Vicente3Rafael
Copy link
Copy Markdown

how did you arrive at division by 4?

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