3
\$\begingroup\$

I have a class which takes a string representing a grid from Conway's game of life (along with its size, only accepting square grids) and returns the next grid in string format. Can it be improved?

Please note that this purely does the computation, and none of the displaying or editing. Also, it is internal so it will not have detection or prevention for errors.

The code:

public class GameOfLifeComputer
{
    #region Fields

    private int _up;
    private int _down;
    private int _left;
    private int _right;
    private int _currentIndex;
    private int _cellCount;
    private string _outputGrid;

    #endregion

    #region Methods

    /// <summary>
    /// Returns a string for the next grid state.
    /// </summary>
    /// <param name="inputGrid">The current grid state.</param>
    /// <param name="gridSize">Side length of the grid in cells.</param>
    /// <returns>The next grid state.</returns>
    public string CalculateNextGrid(string inputGrid, int gridSize)
    {
        _outputGrid = "";
        _currentIndex = 0;

        foreach (char currentCell in inputGrid)
        {
            _cellCount = CountCells(_currentIndex, inputGrid, gridSize);


            if (currentCell == '1')
            {
                if (_cellCount < 2 || _cellCount > 3)
                {
                    _outputGrid += "0";
                }
                else
                {
                    _outputGrid += "1";
                }
            }
            else
            {
                if (_cellCount == 3)
                {
                    _outputGrid += "1";
                }
                else
                {
                    _outputGrid += "0";
                }
            }
        }

        return _outputGrid;
    }

    /// <summary>
    /// Returns how many adjacent cells are alive.
    /// </summary>
    /// <param name="currentIndex">Position of the cell.</param>
    /// <param name="inputGrid">State of the grid as a string.</param>
    /// <param name="gridSize">Side length of the grid in cells.</param>
    /// <returns></returns>
    private int CountCells(int currentIndex, string inputGrid, int gridSize)
    {
        var count = 0;

        // Define where the adjacent cells are in terms of relative index position.
        _up = -gridSize;
        _down = gridSize;

        // Up and down must cycle to the top or bottom of the grid if the cell is on the edge.
        if (currentIndex < gridSize)
        {
            _up = inputGrid.Length - gridSize;
        }
        else if (currentIndex > inputGrid.Length - gridSize)
        {
            _down = gridSize - inputGrid.Length;
        }

        // Left and right must cycle to the opposite side on the same row if the cell is on the edge.
        if (currentIndex % gridSize == 0)
        {
            _left = gridSize - 1;
            _right = 1;
        }
        else
        {
            _left = -1;
            _right = 1 - gridSize;
        }

        // Count how many adjacent cells are alive.
        if (inputGrid[currentIndex + _up    + _right]   == '1') { count += 1; }
        if (inputGrid[currentIndex + _up            ]   == '1') { count += 1; }
        if (inputGrid[currentIndex + _up    + _left ]   == '1') { count += 1; }
        if (inputGrid[currentIndex + _left          ]   == '1') { count += 1; }
        if (inputGrid[currentIndex + _down  + _left ]   == '1') { count += 1; }
        if (inputGrid[currentIndex + _down          ]   == '1') { count += 1; }
        if (inputGrid[currentIndex + _down  + _right]   == '1') { count += 1; }
        if (inputGrid[currentIndex + _right         ]   == '1') { count += 1; }

        return count;
    }

    #endregion
}
\$\endgroup\$
  • \$\begingroup\$ AH! I just tested it by giving it a 4x4 grid with a glider on it, and it gave me back a 4x4 grid with nothing in it!!! \$\endgroup\$ – Aric Aug 10 '17 at 19:04
4
\$\begingroup\$

The first bad thing you do is a lot of string concatenations like

_outputGrid += "1";

which cause many memory reallocations. Since during one game grid size is a constant number you can save it at the constructor, and then just create array for result and set its elements by index.

_outputGrid = new char[_gridSize * _gridSize];
...
_outputGrid[currentIndex] = '0';

At the end of the CalculateNextGrid method convert this array to string and return it:

return new string(_outputGrid);

I suggest to use array of bool's as internal storage for result instead of a string. In my opinion true and false represent the state of a cell (alive or dead) more clearly. You can even use array of enum values like:

public enum CellState
{
    Alive,
    Dead
}

_outputGrid[currentIndex] = CellState.Alive;

You can go further and create method like:

private void ReviveCell(int index) => _outputGrid[index] = CellState.Alive;

It would be better to extract magic conditions to some methods like:

private static bool ShouldBeDeadByUnderpopulation(int count) => count < 2;

private static bool ShouldBeDeadByOverpopulation(int count) => count > 3;

and so on.

And instead of condition like

if (inputGrid[currentIndex + _up    + _right]   == '1')

use methods too

if (IsAlive(value))

With all these changes your code will look like a story where all is clear :)

if (IsAlive(currentCell))
{
    if (ShouldBeDeadByUnderpopulation(_cellCount ) ||
        ShouldBeDeadByOverpopulation(_cellCount))
    {
        KillCell(currentIndex);
    }
    else
    {
        // Note that this code is redundant since cell is alive at the moment
        ReviveCell(currentIndex);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for that! Really helpful. Were my calculations for the directions correct? \$\endgroup\$ – Aric Aug 11 '17 at 6:54
  • \$\begingroup\$ I've checked some of them and they were correct. But I would use two dimensional array for internal implementation of the game and operate by two indices (x and y) instead of single one. \$\endgroup\$ – Maxim Aug 11 '17 at 11:31
  • \$\begingroup\$ It might make things simpler. I'll work on what you've said and produce a second revision. \$\endgroup\$ – Aric Aug 11 '17 at 12:20
1
\$\begingroup\$

It's not a good idea to change state of the class the way you do it here only to return the field as a result:

private int _currentIndex;
private string _outputGrid;

public string CalculateNextGrid(string inputGrid, int gridSize)
{
    _outputGrid = "";
    _currentIndex = 0;

    ...

    return _outputGrid;
}

This is not thread safe. Should you ever want to use a single instance of it with multiple threads they will overwirte each other's work. Most of the fields could be local to the functions making them pure ones and thus much easier to use and to maintain.

[..] a pure function has two useful characteristics:

  • It has no side effects. The function does not change any variables or the data of any type outside of the function.

  • It is consistent. Given the same set of input data, it will always return the same output value.

\$\endgroup\$
  • \$\begingroup\$ Thanks! My program will only ever have one object running though and it waits for a result before giving it the next input \$\endgroup\$ – Aric Aug 11 '17 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.