b******g
发帖数: 1721 | 1 You are given a game board that contains a four by four (4x4) array of
pieces. The pieces can be one of six shapes and can be one of six colors
If the board contains 4 pieces of the same shape and same color, the board
contains a winning pattern.
public enum Color
{
Red,
Blue,
Green,
Yellow,
Black,
Purple
}
public enum Shape
{
Square,
Triangle,
Circle,
Star,
Pentagon,
Octagon
}
public class Piece
{
public Color color;
public Shape shape;
public bool Equals(Piece compareTo) {};
}
public class Board
{
public Piece[,] position = new Piece[4,4];
public void Board(){ /*completely builds the board*/};
public void MakeRandomBoard(){};
public piece GetPiece(int x) {};
public bool IsWinner() {};
}
Write the code to detect when a winning pattern is present in a board.
---_---------
my solution is to use hashtable to record pieces and counts, if anyone is 4,
return true. for hashtable, i did not give a hash fuction. any idea?
we can also use 6*6 array to record counts. | r*c
发帖数: 167 | 2 using System;
using System.Collections.Generic;
namespace WinningGame
{
class Program
{
static void Main(string[] args)
{
int nCount = 0;
int nTotalGames = 1000;
for (int i = 0; i < nTotalGames; i++)
{
Board bd = new Board();
//bd.PrintBoard();
bool bResult = bd.IsWinner();
if (bResult)
{
nCount++;
bd.PrintBoard();
}
Console.WriteLine(string.Format("Game is {0}", bResult ? "
won" : "lost"));
}
Console.WriteLine(string.Format("{0} Games out of {1} are
winning ones", nCount, nTotalGames));
return;
}
}
public enum Color{
UNKNOWN = -1, Red = 0, Blue, Green, Yellow, Black, Purple
}
public enum Shape{
UNKNOWN = -1, Square = 0, Triangle, Circle, Star, Pentagon, Octagon
}
public class Piece
{
public Color color;
public Shape shape;
public Piece(int c, int s) { color = (Color)c; shape = (Shape)s; }
public bool Equals(Piece rhs) { return this.color == rhs.color &&
this.shape == rhs.shape;}
public override string ToString(){
return string.Format("({0}|{1})", Enum.GetName(typeof(Color),
color), Enum.GetName(typeof(Shape), shape));
}
}
public class PiecePlus
{
public Piece Piece {get; set;}
public int Row {get; set;}
public int Col {get; set;}
public PiecePlus(int row, int col, Piece p) { Piece = p; Row = row;
Col = col; }
public bool Equals(PiecePlus rhs) { return this.Piece.Equals(rhs.
Piece) && this.Row == rhs.Row && this.Col == rhs.Col; }
public override string ToString(){
return string.Format("pattern: {0}", Piece.ToString());
}
}
public class Board
{
public static readonly int boardLength = 4;
public static readonly int nMatchCountForWin = 4;
public static readonly int nNumOfEleInColorEnum = Enum.GetNames(
typeof(Color)).Length - 1; // excluding UNKNOWN
public static readonly int nNumOfEleInShapeEnum = Enum.GetNames(
typeof(Shape)).Length - 1; // excluding UNKNOWN
public static readonly PiecePlus DefaultPiecePlus = new PiecePlus(-1
, -1, new Piece(-1, -1));
public Piece[,] position = new Piece[boardLength, boardLength];
public Board(){
MakeRandomBoard();
}
public void MakeRandomBoard(){
Random rdm = new Random((int)DateTime.Now.Ticks);
for(int i=0; i
for (int j = 0; j < boardLength; ++j){
position[i, j] = new Piece(rdm.Next() %
nNumOfEleInColorEnum, rdm.Next() % nNumOfEleInShapeEnum);
}
}
}
public void PrintBoard()
{
for (int i = 0; i < boardLength; ++i){
for (int j = 0; j < boardLength; ++j){
Console.Write(position[i, j].ToString());
if (j <= boardLength - 1)
Console.Write("\t");
}
Console.Write("\n");
}
}
private bool isWinningImpl(int row, int col, Piece p, int
nRequirdMatches, HashSet hs, out PiecePlus ppPattern)
{
PiecePlus temp = new PiecePlus(row, col, p);
if (hs.Contains(temp)){
ppPattern = temp;
return true;
}
int nCount = 0;
for(int j=col; j
if(p.Equals(position[row, j]))
nCount++;
}
if (nCount >= nRequirdMatches){
if (!hs.Contains(temp))
hs.Add(temp);
ppPattern = temp;
return true;
}
for (int i = row + 1; i < boardLength; ++i){ //avoid double
counting
if (p.Equals(position[i, col]))
nCount++;
}
if (nCount >= nRequirdMatches){
if (!hs.Contains(temp))
hs.Add(temp);
ppPattern = temp;
return true;
}
if (row < boardLength - 1 && col < boardLength - 1)
return isWinningImpl(row + 1, col + 1, p, nRequirdMatches -
nCount, hs, out ppPattern);
ppPattern = DefaultPiecePlus;
return false;
}
public bool IsWinner()
{
HashSet hs = new HashSet();
PiecePlus ppPattern;
for (int i = 0; i < boardLength; ++i){
for (int j = 0; j < boardLength; ++j){
if (isWinningImpl(0, 0, position[i, j],
nMatchCountForWin, hs, out ppPattern)){
Console.WriteLine(string.Format("winning pattern: {0
}", ppPattern.ToString()));
return true;
}
}
}
return false;
}
}
} |
|
