﻿ Degrees of Liberty

## Degree of liberty:

This question revolves around a Go board, and involves calculating the liberty of a given chain of go pieces.

From wikipedia, each chain has a degree of liberty the liberty of a chain is determined by the number of immediately adjacent empty squares. Diagonals are ignored.

These are the only rules needed to solve the question.

### Given a board, and an X,Y coordinate, calculate the available liberty of the piece or chain identified by that coordinate.

Approach 1:

Gather up the connected coordinates of the chain into a collection, and count the available neighbors for each. The downside being that certain free squares that were bordered by two or more peices of the chain would be counted more than once.

This problem could be elimnated by gathering all the available neighbors into a hashset, and then counting the number of members, but the interviewer asking the question insisted I solve the problem in a single pass.

My instincts were all overkill. In the end, the solution is easy to fit on a whiteboard.

I left out the Coordinate class definition. The interviewer suggested that, for time purposes, I didn't bother defining needed classes or types, unless they were especially complex. Coordinate in this case is just a container for an X,Y pair.

Click anywhere on the grid to choose a starting point, then step through the processing, or simply hit "PLAY"

uninitialized:not defined
uninitialized:null
uninitialized:null
uninitialized:null
uninitialized:null
uninitialized:null
uninitialized:not defined
uninitialized:null
```public int getLiberty(int xPos, int yPos, int[,] board)
{
int retValue = 0;
//bounds check:
if (board == null || xPos < 0 || yPos < 0
|| xPos >= board.GetLength(0) || yPos >= board.GetLength(1))
{
return -1;
//-1 signifies an invalid request, since 0 is a valid answer
}
int CurrentColor = board[xPos,yPos];
if (CurrentColor == 0)
{
return -1;//-1 signifies an invalid request, since 0 is a valid answer
}
bool[,] visited = new bool[board.GetLength(0), board.GetLength(1)];
Stack<Coordinate> stack = new Stack<Coordinate>();
stack.Push( new Coordinate(xPos, yPos));
Coordinate coords;
while (stack.Count > 0)
{
coords = stack.Pop();
if(!visited[coords.x, coords.y])
{
if (board[coords.x,coords.y] == 0)
{
retValue++;
}
else if (board[coords.x,coords.y] == CurrentColor)
{
//add all the neighbors to the party.
if ((coords.x - 1) >= 0
&& !visited[coords.x - 1, coords.y])
{
stack.Push( new Coordinate( coords.x - 1, coords.y ));
}
if ((coords.x + 1) < board.GetLength(0)
&& !visited[coords.x + 1, coords.y])
{
stack.Push(new Coordinate(coords.x + 1, coords.y));
}
if ((coords.y - 1) >= 0
&& !visited[coords.x, coords.y - 1])
{
stack.Push(new Coordinate(coords.x , coords.y - 1));
}
if ((coords.y + 1) < board.GetLength(1)
&& !visited[coords.x, coords.y + 1])
{
stack.Push(new Coordinate(coords.x , coords.y + 1));
}
}
//mark current position as evaluated
visited[coords.x, coords.y] = true;
}
}
return retValue;
}
```