Weekly Code Puzzle #3 Results "Don't Eat the Last Cake"

Happy belated Thanksgiving everyone. In honor of the holiday we had a puzzle related to eating. Don't Eat the Last Cake.

The fun part of this puzzle is that it involves writing code to play a game against an AI opponent. This is good practice for when the robot uprising inevitably happens.

Here's how it turned out:

The "Come With Me if You Want to Live" award:

This award goes to Brian Bugh for walking through every step of his thought process in his code comments.

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  

“The only way to win is not to play” award:

This award goes to Matthew Maxwell who discovered that you can cheat death by always returning zero in the JavaScript solution. This tricks the computer into eventually eating itself to death and you don't have to play the game at all.

Matthew Maxwell

function Player(){}

Player.prototype.firstmove = function () {  
  return false;
};

Array.prototype.indexOf =  Player.prototype.move = function stupify() {  
  return 0;
};

Extra bonus for the Harry Potter reference.

Next Time on Weekly Code Puzzle

This week's puzzle is Connect Four: Who Won?

Given a multidimensional array representing a Connect Four board, your task is to create a function which can determine who won the game.

Please follow these instructions to get the link to your solution and email that link to weeklypuzzle@bloc.io or tweet it at @BlocPuzzle. Submit by Friday December 11 9am PST to be included.