/**
 *  Implements strategy for 4 by 7 Chomp
 */

public class Strategy
{
  /**
   *  Represents a few winning Chomp positions for the second player
   *  Each array is number of squares in row 0, 1, 2, 3
   *    (a missing element is 0)
   */
  private int winPositions[][] =
  {
    {1},
    {7,6}, {6,5}, {5,4}, {4,3}, {3,2}, {2,1},
    {7,7,4}, {7,5,2}, {6,4,2}, {4,2,2},
    {7,4,3}, {6,3,3}, {5,5,3},
    {4,1,1,1}, {3,1,1},
    {2,2,2,1},
    {2,2,1}, {3,3,1,1},
    {5,2,1,1},
  };

  public Position findBestMove(ChompGame game)
  {
    int rows = game.numRows(), cols = game.numCols();
    int i, r, wLength, bLength, cutRow, cutCol;
    int wSteps[], bSteps[];

    // Convert the current board position into the same form as
    // winPositions
    bSteps = new int[rows];
    for (r = 0; r < rows; r++)
      bSteps[r] = game.countInRow(r);

    for (i = 0; i < winPositions.length; i++)
    {
      wSteps = winPositions[i];
      cutRow = -1;
      cutCol = cols;

      // Check whether winPosition[i] can be reached from
      //   the current position in one move, if so save cutRow and cutCol
      //   -- the position of that move
      for (r = 0; r < rows; r++)
      {
        if (r < wSteps.length)
          wLength = wSteps[r];
        else
          wLength = 0;

        bLength = bSteps[r];

        if (cutRow < 0 && bLength != wLength)
        {
          cutRow = r;
          cutCol = wLength;
        }

        if (bLength > cutCol)
          bLength = cutCol;

        if (bLength != wLength)
          break;
      }

      if (r == rows && cutRow >= 0)
      {
        return new Position(cutRow, cutCol);
      }
    }
    return null;
  }

  /**
   *  Picks a move randomly from pieces on the border
   */
  public Position findRandomMove(ChompGame game)
  {
    int rows = game.numRows(), cols = game.numCols();
    Position list[] = new Position[rows + cols];
    int count = 0;
    int r, c;

    // Add all border squares to the list:
    for (r = 0; r < rows; r++)
    {
      for (c = 0; c < cols; c++)
      {
        if (r + c > 0 && !game.isEmpty(r, c) &&
                 (game.isEmpty(r + 1, c) || game.isEmpty(r, c + 1)))
          list[count++] = new Position(r, c);
      }
    }

    // Choose a random element from the list:
    if (count == 0)
    {
      return new Position(0, 0);
    }
    else
    {
      int n = (int)(count * Math.random());
      return list[n];
    }
  }
}