/***************************************************************************
 * Copyright (c) 2005, Northwest Summit. All Rights Reserved.
 * 
 * This software is the proprietary information of Northwest Summit.
 * Use is subject to license terms.
 ***************************************************************************/

package com.nwsummit.games.minesweeper;

import java.util.Arrays;
import java.util.List;
import java.util.LinkedList;
import java.util.Random;

import com.nwsummit.util.IOUtil;

/**
 * Class holding the logic of the minesweeper game.
 */
public final class Minefield {

  /** Empty cell. */
  public static final int M_NONE = 0;

  /** Cell with a bomb. */
  public static final int M_BOMB = -1;

  /** Cell flagged as having a bomb. */
  public static final int M_FLAG = -2;

  /** Cell with a question mark. */
  public static final int M_DOUBT = -3;

  /** A covered cell. */
  public static final int M_COVER = -5;

  /** Wrongly flagged as bomb. */
  public static final int M_WRONG = -8;

  /** Exploded bomb. */
  public static final int M_BAD = -9;

  /** An empty list */
  public static final LinkedList EMPTY_LIST = new LinkedList();

  private int[][] _map; // internal map of the bombs
  private int[][] _grid; // bombs grid as seen externally
  private int _bombs, _flags;
  private int _rows, _cols;
  private int _remainCells;
  private boolean _questionMark;

  /**
   * Construct a minefield grid with the specified dimension, containing
   * the specified number of bombs.
   * <p>
   * @param rows number of rows in the grid
   * @param cols number of columns in the grid
   * @param bombs number of bombs
   */
  public Minefield(int rows, int cols, int bombs)
  {
    _bombs = bombs;
    _rows = rows;
    _cols = cols;
    _map = new int[_rows][_cols];
    _grid = new int[_rows][_cols];

    reset();
  }

  /** Return the number of bombs. */
  public int getBombs() {
    return _bombs;
  }

  /** Return the number of marked flags. */
  public int getFlags() {
    return _flags;
  }

  /** Return the number of rows. */
  public int getRows() {
    return _rows;
  }

  /** Return the number of columns. */
  public int getColumns() {
    return _cols;
  }

  /**
   * Return the number of remaining cells to open to complete sweeping.
   * A zero value means all bombs have been correctly identified.
   */
  public int getRemainingCells() {
    return _remainCells;
  }

  /** Return this minefield grid (as seen externally). */
  public int[][] getGrid() {
    return _grid;
  }

  /** Return the internal map of bombs. */
  public int[][] getMap() {
    return _map;
  }

  /** Return <code>true</code> if all bombs have been correctly identified. */
  public boolean isDone() {
    return (_remainCells == 0);
  }

  /** Whether to do question mark. */
  public boolean doQuestionMark() {
    return _questionMark;
  }

  /** Set whether to do question mark. */
  public void doQuestionMark(boolean b) {
    _questionMark = b;
  }

  /** Reset this minefield with new bombs location. */
  public void reset()
  {
    _flags = 0;
    _remainCells = (_rows * _cols) - _bombs;

    // clear internal map and external grid
    for (int i=0; i<_rows; i++) {
      Arrays.fill(_map[i], M_NONE);
      Arrays.fill(_grid[i], M_COVER);
    }

    // plant new bombs
    Random random = new Random(System.currentTimeMillis());
    for (int i=0; i<_bombs; i++) {
      while (true) {
        int r = Math.abs(random.nextInt() % _rows);
        int c = Math.abs(random.nextInt() % _cols);
        if (_map[r][c] != -1) {
          _map[r][c] = M_BOMB;
          updateBombCount(r, c);
          break;
        }
      }
    }
  }

  /**
   * Update the bombs count of the neighboring cells to the specified bomb's
   * location.
   * <p>
   * @param r zero-based row index of the bomb location.
   * @param c zero-based column index of the bomb location.
   */
  private void updateBombCount(int r, int c)
  {
    int r1 = Math.max(r-1, 0);
    int r2 = Math.min(r+1, _rows-1);
    int c1 = Math.max(c-1, 0);
    int c2 = Math.min(c+1, _cols-1);

    for (int i=r1; i<=r2; i++) {
      for (int j=c1; j<=c2; j++) {
        if (_map[i][j] != M_BOMB)
          _map[i][j] += 1;
      }
    }
  }

  /**
   * Flag the specified cell as having a bomb. The following logic takes
   * place:
   * <ul>
   * <li>If there is no flag on the cell, it is set with M_FLAG.
   * <li>If the cell is flagged, it is set with M_DOUBT.
   * <li>If the cell is set with M_DOUBT, it is set with M_COVER.
   * </ul>
   * @param r zero-based row index of the cell.
   * @param c zero-based column index of cell.
   * @return the new value of the specified cell.
   */
  public int flag(int r, int c)
  {
    int marking = _grid[r][c];
    if (marking == M_COVER) {
      _grid[r][c] = M_FLAG;
      _flags += 1;
    }
    else if (marking ==  M_FLAG) {
      _grid[r][c] = _questionMark? M_DOUBT : M_COVER;
      _flags -= 1;
    }
    else if (marking == M_DOUBT)
      _grid[r][c] = M_COVER;

    return _grid[r][c];
  }

  /**
   * Open the specified cell. If the specified cell is empty, then all
   * neighboring are open as well. The process takes place recursively
   * if one of the neighboring cell is also empty.
   * <p>
   * @param r zero-based row index of the cell.
   * @param c zero-based column index of the cell.
   * @return <code>null</code> if the cell open is a bomb; a list of cells
   * open otherwise, each element being a <code>Minefield.Cell</code> object.
   */
  public List open(int r, int c)
  {
    // do nothing if the cell has been open
    if (_grid[r][c] != M_COVER && _grid[r][c] != M_DOUBT)
      return EMPTY_LIST;

    int val = _map[r][c];

    // open a bomb = game over
    if (val == M_BOMB) {
      _grid[r][c] = M_BAD;
      return null;
    }

    LinkedList openCells = new LinkedList();
    _grid[r][c] = val;
    if (val == M_NONE)
      openSpaces(r, c, openCells); // empty cell: open all adjacent blank cells
    else {
      _remainCells -= 1;
      openCells.add(new Cell(r, c));
    }

    return openCells;
  }

  /**
   * Recursively open empty cells in the grid, starting with the specified
   * cell. This method also updates the specified openCells list and the
   * count of remaining cells to open.
   */
  private void openSpaces(int r, int c, List openCells)
  {
    _remainCells -= 1;
    openCells.add(new Cell(r, c));

    int r1 = Math.max(r-1, 0);
    int r2 = Math.min(r+1, _rows-1);
    int c1 = Math.max(c-1, 0);
    int c2 = Math.min(c+1, _cols-1);
    for (int i=r1; i<=r2; i++) {
      for (int j=c1; j<=c2; j++) {
        int val = _map[i][j];
        if (_grid[i][j] == M_COVER && val != M_BOMB) {
          _grid[i][j] = val;
          if (val == M_NONE)
            openSpaces(i, j, openCells);
          else {
            _remainCells -= 1;
            openCells.add(new Cell(i, j));
          }
        }
      } // for j
    } // for i
  }

  /**
   * Open the remaining cells around the specified numbered cell. The action
   * takes place if and only if the specified cell
   * <ul>
   * <li>is already open
   * <li>is adjacent to one or more bomb
   * <li>has all of its bomb(s) flagged
   * </ul>
   * @param r zero-based row index of the cell.
   * @param c zero-based column index of the cell.
   * @return <code>null</code> if a bomb is open by this action (i.e. bombs
   * have been previously incorrectly flagged around the specified cell);
   * the list of cells open otherwise, each element being a
   * <code>Minefield.Cell</code> object.
   */
  public List openRemaining(int r, int c)
  {
    // no action if the cell is not open, nor is adjacent to a bomb
    if (_grid[r][c] == M_COVER || _grid[r][c] < 1 || _grid[r][c] > 8)
      return EMPTY_LIST;

    int r1 = Math.max(r-1, 0);
    int r2 = Math.min(r+1, _rows-1);
    int c1 = Math.max(c-1, 0);
    int c2 = Math.min(c+1, _cols-1);

    // check whether the right number of bombs around it has been flagged
    int flaggedBombs = 0;
    for (int i=r1; i<=r2; i++) {
      for (int j=c1; j<=c2; j++) {
        if (_grid[i][j] == M_FLAG)
          flaggedBombs += 1;
      }
    }
    if (flaggedBombs != _grid[r][c])
      return EMPTY_LIST; // no action

    LinkedList openCells = new LinkedList();
    for (int i=r1; i<=r2; i++) {
      for (int j=c1; j<=c2; j++) {
        if (_grid[i][j] == M_COVER || _grid[i][j] == M_DOUBT) {
          int val = _map[i][j];
          _grid[i][j] = val;

          if (val == M_BOMB) { // we die here!
            _grid[i][j] = M_BAD;
            return null;
          }
          else if (val == M_NONE)
            openSpaces(i, j, openCells);
          else {
            _remainCells -= 1;
            openCells.add(new Cell(i, j));
          }
        }
      } // for j
    } // for i
    return openCells;
  }

  /**
   * Update in the external grid the value of the bomb cells.
   * <p>
   * @param showFlag <code>true</code> to update not yet open bomb cells with
   * M_FLAG; <code>false</code> to update them with M_BOMB.
   * @return the list of bomb cells and cells wrongly flagged, if any; each
   * element being a <code>Minefield.Cell</code> object.
   */
  public List makeFinalSolution(boolean showFlag)
  {
    LinkedList list = new LinkedList();
    for (int i=0; i<_rows; i++) {
      for (int j=0; j<_cols; j++) {
        if (_map[i][j] == M_BOMB) {
          list.add(new Cell(i, j));
          if (_grid[i][j] == M_COVER)
            _grid[i][j] = (showFlag? M_FLAG : M_BOMB);
        }
        else if (_grid[i][j] == M_FLAG) {
          list.add(new Cell(i, j));
          _grid[i][j] = M_WRONG;
        }
      }
    }
    return list;
  }

  /** Return the string representing the parameters of this minefield. */
  public String toString()
  {
    StringBuffer sb = new StringBuffer("{");
    sb.append("rows=").append(_rows);
    sb.append("; cols=").append(_cols);
    sb.append("; bombs=").append(_bombs);
    sb.append("; remain=").append(_remainCells);
    sb.append("}");
    return sb.toString();
  }

  //--------------------------------------------------------------| Inner class

  /**
   * Class representing the coordinate of a cell in the minefield grid.
   */
  public class Cell {
    int _x, _y;
    Cell(int x, int y) {
      _x = x;
      _y = y;
    }

    /** Index of the cell's row. */
    public int getX() { return _x; }

    /** Index of the cell's column. */
    public int getY() { return _y; }
  }

  //---------------------------------------------------------------------------

  /**
   * Minesweeper game in text mode!
   */
  public static class Game {

    /**
     * Return the string representation of the specified grid.
     */
    public static String toString(int[][] grid)
    {
      StringBuffer sb = new StringBuffer();
      for (int r=0; r<grid.length; r++) {
        for (int c=0; c<grid[r].length; c++) {
          int val = grid[r][c];
          sb.append('[');
          switch (val) {
            case M_COVER:
              sb.append(' '); break;
            case M_BOMB:
              sb.append('*'); break;
            case M_FLAG:
              sb.append('o'); break;
            case M_DOUBT:
              sb.append('?'); break;
            case M_NONE:
              sb.append('.'); break;
            case M_BAD:
              sb.append('x'); break;
            default:
              sb.append(val);
          }
          sb.append(']');
        }
        sb.append('\n');
      }
      return sb.toString();
    }

    public static void main(String[] args) throws Exception
    {
      Minefield mfield = new Minefield(9, 9, 10);
      boolean isOk = true;
      do {
        System.out.println(toString(mfield.getMap()));
        System.out.println(toString(mfield.getGrid()));

        System.out.print("action (1=open|2=mark|3=remain|.=quit): ");
        String action = IOUtil.readLine(System.in);
        if (".".equals(action))
          System.exit(0);

        System.out.print("row: ");
        int r = Integer.parseInt(IOUtil.readLine(System.in)) - 1;

        System.out.print("col: ");
        int c = Integer.parseInt(IOUtil.readLine(System.in)) - 1;

        if ("1".equals(action))
          isOk = (mfield.open(r, c) != null);
        else if ("2".equals(action))
          mfield.flag(r, c);
        else if ("3".equals(action))
          isOk = (mfield.openRemaining(r, c) != null);

        System.out.println("remain=" + mfield.getRemainingCells());
        System.out.println("isDone=" + mfield.isDone());
      }
      while (isOk && !mfield.isDone());

      mfield.makeFinalSolution(isOk);
      System.out.println(toString(mfield.getGrid()));
    }
  }
}