Chutes & Ladders Board Generator (June 2016 Community Challenge)

Question

This is an "entry" I made for the June 2016 Community Challenge to make a Chutes and Ladders generator. It generates a random number of chutes and ladders with a total delta of -50 and displays their start points, endpoints, and deltas.

Some notes:

• The number of chutes must be at least 2, and the number of ladders at least 1.
• The total delta from chutes must be (-)100 and the total delta from ladders must be 50. This is how I balanced the board to a total delta of -50 while ensuring that there were a decent amount of chutes and ladders.
• I have attempted to use the MVP pattern.

ChutesAndLaddersBoardGenerator

using System;
using System.Windows.Forms;

namespace ChutesAndLaddersBoardGenerator
{
    internal static class ChutesAndLaddersBoardGenerator
    {
        private const int BoardSize = 10;

        [STAThread]
        private static void Main()
        {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            var model = new Generator(BoardSize);
            var view = new ChutesAndLaddersBoardGeneratorView();
            new ChutesAndLaddersBoardGeneratorPresenter(view, model);
            Application.Run(view);
        }
    }
}

ChutesAndLaddersBoardGeneratorView

using System;
using System.Collections.Generic;
using System.Windows.Forms;

namespace ChutesAndLaddersBoardGenerator
{
    internal partial class ChutesAndLaddersBoardGeneratorView : Form,
        IChutesAndLaddersBoardGeneratorView
    {
        public ChutesAndLaddersBoardGeneratorView()
        {
            InitializeComponent();
            BindComponent();
        }

        private void BindComponent()
        {
            generateBoardButton.Click += OnGenerateBoardButtonClick;
        }

        public event Action GenerateBoard;

        private void OnGenerateBoardButtonClick(object sender, EventArgs e)
        {
            GenerateBoard?.Invoke();
        }

        public void LoadChutesAndLadders(
            List<ChuteOrLadder> chutesAndLadders)
        {
            chutesAndLaddersDisplay.DataSource = chutesAndLadders;
            int totalDelta = 0;
            foreach (var chuteOrLadder in chutesAndLadders)
            {
                totalDelta += chuteOrLadder.Delta;
            }
            totalDeltaLabel.Text = "Total Delta: " + totalDelta;
        }
    }
}

IChutesAndLaddersBoardGeneratorView

using System;
using System.Collections.Generic;

namespace ChutesAndLaddersBoardGenerator
{
    internal interface IChutesAndLaddersBoardGeneratorView
    {
        event Action GenerateBoard;

        void LoadChutesAndLadders(List<ChuteOrLadder> chutesAndLadders);
    }
}

ChutesAndLaddersBoardGeneratorPresenter

namespace ChutesAndLaddersBoardGenerator
{
    internal class ChutesAndLaddersBoardGeneratorPresenter
    {
        private readonly IChutesAndLaddersBoardGeneratorView view;
        private readonly Generator generator;

        internal ChutesAndLaddersBoardGeneratorPresenter(
            IChutesAndLaddersBoardGeneratorView view,
            Generator generator)
        {
            this.view = view;
            this.generator = generator;
            this.view.GenerateBoard += OnGenerateBoard;
        }

        internal void OnGenerateBoard()
        {
            view.LoadChutesAndLadders(generator.GenerateChutesAndLadders());
        }
    }
}

Generator

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ChutesAndLaddersBoardGenerator
{
    internal class BoardSquare
    {
        internal Tuple<int, int> Coordinates { get; set; }
        internal bool HasChuteOrLadder { get; set; }
        internal int SquareNumber { get; set; }

        public override string ToString()
        {
            return Coordinates.ToString() + " " + SquareNumber;
        }
    }

    internal class Generator
    {
        private const int TotalChutesDelta = -100;
        private const int TotalDelta = -50;
        private const int TotalLaddersDelta = 50;
        private static Random random;
        private int size;

        internal Generator(int size)
        {
            if (size % 2 != 0)
            {
                throw new Exception("Board size must be even!");
            }
            else if (size < 2)
            {
                throw new Exception("Board size must be positive!");
            }
            this.size = size;
            random = new Random();
        }

        internal List<ChuteOrLadder> GenerateChutesAndLadders()
        {
            var board = GenerateBoard();
            var chutesAndLadders = new List<ChuteOrLadder>();
            chutesAndLadders.AddRange(GenerateChutes(board));
            chutesAndLadders.AddRange(GenerateLadders(board));
            return chutesAndLadders;
        }

        private BoardSquare[,] GenerateBoard()
        {
            BoardSquare[,] board = new BoardSquare[size, size];
            int squareNumber = size * size;
            for (int i = 0; i < size; i += 2)
            {
                for (int j = 0; j < size; j++)
                {
                    board[i, j] = new BoardSquare
                    {
                        Coordinates = new Tuple<int, int>(i, j),
                        SquareNumber = squareNumber--,
                        HasChuteOrLadder = false
                    };
                }
                for (int j = size - 1; j >= 0; j--)
                {
                    board[i + 1, j] = new BoardSquare
                    {
                        Coordinates = new Tuple<int, int>(i, j),
                        SquareNumber = squareNumber--,
                        HasChuteOrLadder = false
                    };
                }
            }
            return board;
        }

        private List<ChuteOrLadder> GenerateChutes(BoardSquare[,] board)
        {
            var chutes = new List<ChuteOrLadder>();
            var numberOfChutes = random.Next(2, board.GetLength(0));
            int[] deltas = new int[numberOfChutes + 1];
            deltas[0] = 0;
            deltas[1] = 0 - TotalChutesDelta;
            for (var i = 2; i < deltas.Length; i++)
            {
                int nextDelta = random.Next(1, (0 - TotalChutesDelta) - 1);
                if (deltas.Contains(nextDelta))
                {
                    i--;
                    continue;
                }
                deltas[i] = nextDelta;
                Debug.WriteLine(deltas[i]);
            }

            Array.Sort(deltas);
            for (var i = 0; i < numberOfChutes; i++)
            {
                deltas[i] = deltas[i + 1] - deltas[i];
            }

            for (var i = 0; i < numberOfChutes; i++)
            {
                var startSquareNumber =
                    random.Next(1 + deltas[i], (size * size));
                var startSquare = GetSquare(board, startSquareNumber);
                var endSquare =
                    GetSquare(board, startSquareNumber - deltas[i]);
                if (!startSquare.HasChuteOrLadder &&
                    !endSquare.HasChuteOrLadder)
                {
                    chutes.Add(new ChuteOrLadder
                    {
                        StartSquareNumber = startSquareNumber,
                        EndSquareNumber = startSquareNumber - deltas[i]
                    });
                    board[startSquare.Coordinates.Item1,
                        startSquare.Coordinates.Item2].HasChuteOrLadder = true;
                    board[endSquare.Coordinates.Item1,
                        endSquare.Coordinates.Item2].HasChuteOrLadder = true;
                }
                else
                {
                    i--;
                }
            }
            return chutes;
        }

        private List<ChuteOrLadder> GenerateLadders(BoardSquare[,] board)
        {
            var ladders = new List<ChuteOrLadder>();
            var numberOfLadders = random.Next(1, board.GetLength(0));
            int[] deltas = new int[numberOfLadders + 1];
            deltas[0] = 0;
            deltas[1] = TotalLaddersDelta;
            for (var i = 2; i < deltas.Length; i++)
            {
                int nextDelta = random.Next(1, TotalLaddersDelta);
                if (deltas.Contains(nextDelta))
                {
                    i--;
                    continue;
                }
                deltas[i] = nextDelta;
            }

            Array.Sort(deltas);
            for (var i = 0; i < numberOfLadders; i++)
            {
                deltas[i] = deltas[i + 1] - deltas[i];
            }

            for (var i = 0; i < numberOfLadders; i++)
            {
                var startSquareNumber =
                    random.Next(2, (size * size) - (deltas[i] + 1));
                var startSquare = GetSquare(board, startSquareNumber);
                var endSquare =
                    GetSquare(board, startSquareNumber + deltas[i]);
                if (!startSquare.HasChuteOrLadder &&
                    !endSquare.HasChuteOrLadder)
                {
                    ladders.Add(new ChuteOrLadder
                    {
                        StartSquareNumber = startSquareNumber,
                        EndSquareNumber = startSquareNumber + deltas[i]
                    });
                    board[startSquare.Coordinates.Item1,
                        startSquare.Coordinates.Item2].HasChuteOrLadder = true;
                    board[endSquare.Coordinates.Item1,
                        endSquare.Coordinates.Item2].HasChuteOrLadder = true;
                }
                else
                {
                    i--;
                }
            }
            return ladders;
        }

        private BoardSquare GetSquare(BoardSquare[,] board, int squareNumber)
        {
            int row = (board.GetLength(0) * board.GetLength(0) - squareNumber)
                / board.GetLength(0);
            int column = 0;
            if (row % 2 == 0)
            {
                column = (board.GetLength(0) -
                    (squareNumber % board.GetLength(0))) % board.GetLength(0);
            }
            else
            {
                column = (squareNumber - 1) % board.GetLength(0);
            }
            return board[row, column];
        }

        private void PrintBoard(BoardSquare[,] board)
        {
            for (int i = 0; i < board.GetLength(0); i++)
            {
                for (int j = 0; j < board.GetLength(1); j++)
                {
                    Debug.Write(board[i, j] + "\t");
                }
                Debug.WriteLine("");
            }
        }
    }
}

ChuteOrLadder

namespace ChutesAndLaddersBoardGenerator
{
    internal class ChuteOrLadder
    {
        internal int Delta
        {
            get
            {
                return EndSquareNumber - StartSquareNumber;
            }
        }

        internal int EndSquareNumber { get; set; }
        internal int StartSquareNumber { get; set; }

        public override string ToString()
        {
            return StartSquareNumber + "\t" + EndSquareNumber + "\t" + Delta;
        }
    }
}

Answer 1

class Generator

internal Generator(int size)
  {
      if (size % 2 != 0)
      {
          throw new Exception("Board size must be even!");
      }
      else if (size < 2)
      {
          throw new Exception("Board size must be positive!");
      }
      this.size = size;
      random = new Random();
  }  

The correct exception would be an ArgumentOutOfRangeException instead of an Exception. You should always throw the most suitable exception.

In addition you won't need an else if just two if will do.

---

The List<ChuteOrLadder> GenerateChutes is doing too much. You should extract the generation of the deltas to a separate method. It will be more readable and easier to maintain and will remove the code duplication happening in GenerateLadders() and GenerateChutes().

I don't like the manipulation of the looping variable either. Try to find a way to do it differently.

Both points can be done like so

private int[] GenerateDelta(int deltaUpperLimit, int secondDeltaValue, int maxRandomValue)
{
    int[] deltas = new int[deltaUpperLimit + 1];
    deltas[0] = 0;
    deltas[1] = secondDeltaValue;

    for (var i = 2; i < deltas.Length; i++)
    {
        int nextDelta = random.Next(1, maxRandomValue);
        while (deltas.Contains(nextDelta))
        {
            nextDelta = random.Next(1, maxRandomValue);
        }
        deltas[i] = nextDelta;
    }

    Array.Sort(deltas);

    for (var i = 0; i < deltaUpperLimit; i++)
    {
        deltas[i] = deltas[i + 1] - deltas[i];
    }
    return deltas;
}  

Some more code duplication in the methods generating ladders and chutes

for (var i = 0; i < numberOfLadders; i++)
{
    var startSquareNumber =
        random.Next(2, (size * size) - (deltas[i] + 1));
    var startSquare = GetSquare(board, startSquareNumber);
    var endSquare =
        GetSquare(board, startSquareNumber + deltas[i]);
    if (!startSquare.HasChuteOrLadder &&
        !endSquare.HasChuteOrLadder)
    {
        ladders.Add(new ChuteOrLadder
        {
            StartSquareNumber = startSquareNumber,
            EndSquareNumber = startSquareNumber + deltas[i]
        });
        board[startSquare.Coordinates.Item1,
            startSquare.Coordinates.Item2].HasChuteOrLadder = true;
        board[endSquare.Coordinates.Item1,
            endSquare.Coordinates.Item2].HasChuteOrLadder = true;
    }
    else
    {
        i--;
    }
}  

which can be removed by having an (badly named) AddItem() method like so

private bool AddItem(int startSquareNumber, int delta)
{
    var startSquare = GetSquare(board, startSquareNumber);
    if (startSquare.HasChuteOrLadder)
    { 
        return false;
    }

    var endSquare = GetSquare(board, startSquareNumber + delta);
    if (endSquare.HasChuteOrLadder)
    {
        return false;
    }

    ladders.Add(new ChuteOrLadder
    {
        StartSquareNumber = startSquareNumber,
        EndSquareNumber = startSquareNumber + delta
    });
    board[startSquare.Coordinates.Item1,
        startSquare.Coordinates.Item2].HasChuteOrLadder = true;
    board[endSquare.Coordinates.Item1,
        endSquare.Coordinates.Item2].HasChuteOrLadder = true;

    return true;
}  

Implementing these changes will lead to

private List<ChuteOrLadder> GenerateChutes(BoardSquare[,] board)
{
    var chutes = new List<ChuteOrLadder>();
    var numberOfChutes = random.Next(2, board.GetLength(0));

    int[] deltas = GenerateDelta(numberOfChutes, 0 - TotalChutesDelta, (0 - TotalChutesDelta) - 1);

    int sizeSquared = size * size;
    for (var i = 0; i < numberOfChutes; i++)
    {
        var randomMinValue = 1 + deltas[i];
        var startSquareNumber =
            random.Next(randomMinValue, sizeSquared);

        while (!AddItem(startSquareNumber, deltas[i]))
        {
            startSquareNumber =
            random.Next(randomMinValue, sizeSquared);
        }
    }
}

private List<ChuteOrLadder> GenerateLadders(BoardSquare[,] board)
{
    var ladders = new List<ChuteOrLadder>();
    var numberOfLadders = random.Next(1, board.GetLength(0));

    int[] deltas = GenerateDelta(numberOfLadders, TotalLaddersDelta, TotalLaddersDelta);

    int sizeSquared = size * size;
    for (var i = 0; i < numberOfLadders; i++)
    {
        var randomMaxValue = sizeSquared - deltas[i] + 1;
        var startSquareNumber = random.Next(2, randomMaxValue);

        while (!AddItem(startSquareNumber, deltas[i]))
        {
            startSquareNumber =
            random.Next(2, randomMaxValue);
        }
    }
}

---

Why do you use a Tuple<int, int> which is hard to read if accessing the values instead of having a simple small struct/class Position/Coordinate having only Row, Col or X,Y as variables/properties ? This would improve the readability of e.g

board[startSquare.Coordinates.Item1, startSquare.Coordinates.Item2].HasChuteOrLadder = true;
board[endSquare.Coordinates.Item1, endSquare.Coordinates.Item2].HasChuteOrLadder = true;  

---

internal class ChuteOrLadder

Seeing an Or inside a class name usually indicates that that class has too many responsibilities which isn't the case here. I would suggest to rename this class to something else and then have

internal class Chute : RenamedChuteOrLadder
{

}
internal class Ladder : RenamedChuteOrLadder
{

}  

to make it more clear with what you are dealing. This would involve some bigger refactoring but it will be worth it if you need to understand the code in 6 months.

---

Answer 2

Your algorithm for getting a collection of random deltas could be improved. It checks for collisions each number it adds, which is O(n) each time, and it keeps creating a new random number until there isn't a collision, which could go on forever. Here is an algorithm that is O(n):

static class RandomExtensions
{
    public static void Shuffle<T>(this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1)
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

This:

public void LoadChutesAndLadders(
    List<ChuteOrLadder> chutesAndLadders)
{
    chutesAndLaddersDisplay.DataSource = chutesAndLadders;
    int totalDelta = 0;
    foreach (var chuteOrLadder in chutesAndLadders)
    {
        totalDelta += chuteOrLadder.Delta;
    }
    totalDeltaLabel.Text = "Total Delta: " + totalDelta;
}

Can be written more concisely using LINQ:

public void LoadChutesAndLadders(
    List<ChuteOrLadder> chutesAndLadders)
{
    chutesAndLaddersDisplay.DataSource = chutesAndLadders;
    int totalDelta = chutesAndLadders.Sum(x => x.Delta);
    totalDeltaLabel.Text = "Total Delta: " + totalDelta;
}