12
\$\begingroup\$

My solution for the Rainfall Challenge (August 2016 Community Challenge).

Error handling was intentionally ignored.


Cell.cs

public class Cell
{
    private readonly int myRowIndex;
    private readonly int myColIndex;
    private readonly int myValue;

    public Cell(int value, int rowIndex, int colIndex)
    {
        myRowIndex = rowIndex;
        myColIndex = colIndex;
        myValue = value;
    }

    public int RowIndex => myRowIndex;
    public int ColIndex => myColIndex;
    public int Value => myValue;
    public bool IsSink { get; set; }
    public Cell Top { get; set; }
    public Cell Right { get; set; }
    public Cell Bottom { get; set; }
    public Cell Left { get; set; }
    public Cell Next { get; set; }
}

Program.cs

Main

static void Main(string[] args)
{
    var data = ReadData();

    var cells = CreateCells(data).ToArray();

    ConnectCells(cells, data.GetLength(0));

    SetIsSink(cells);

    SetNext(cells);

    var basins = GetBasins(cells);

    Console.WriteLine(string.Join(" ", basins));
}

ReadData

private static int[,] ReadData()
{
    var size = int.Parse(Console.ReadLine());
    var result = new int[size, size];
    for (int row = 0; row < size; row++)
    {
        var rowData = Console.ReadLine().Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries).ToArray();
        for (int col = 0; col < size; col++)
            result[row, col] = int.Parse(rowData[col]);
    }
    return result;
}

CreateCells

private static IEnumerable<Cell> CreateCells(int[,] data)
{
    for (int row = 0; row < data.GetLength(0); row++)
        for (int col = 0; col < data.GetLength(1); col++)
            yield return new Cell(data[row, col], row, col);
}

ConnectCells

private static void ConnectCells(Cell[] cells, int size)
{
    foreach (var cell in cells)
    {
        var indexLeft = GetIndexLeft(cell, size);
        var indexRight = GetIndexRight(cell, size);
        var indexTop = GetIndexTop(cell, size);
        var indexBottom = GetIndexBottom(cell, size);

        if (indexLeft > -1) cell.Left = cells[indexLeft];
        if (indexRight > -1) cell.Right = cells[indexRight];
        if (indexTop > -1) cell.Top = cells[indexTop];
        if (indexBottom > -1) cell.Bottom = cells[indexBottom];
    }
}

private static int GetIndexTop(Cell cell, int size)
{
    if (cell.RowIndex == 0)
        return -1;
    return (cell.RowIndex - 1) * size + cell.ColIndex;
}

private static int GetIndexRight(Cell cell, int size)
{
    if (cell.ColIndex + 1 == size)
        return -1;
    return cell.RowIndex * size + cell.ColIndex + 1;
}

private static int GetIndexLeft(Cell cell, int size)
{
    if (cell.ColIndex == 0)
        return -1;
    return cell.RowIndex * size + cell.ColIndex - 1;
}

private static int GetIndexBottom(Cell cell, int size)
{
    if (cell.RowIndex + 1 == size)
        return -1;
    return (cell.RowIndex + 1) * size + cell.ColIndex;
}

SetIsSink

private static void SetIsSink(Cell[] cells)
{
    foreach (var cell in cells)
        cell.IsSink = (cell.Left == null || cell.Left.Value > cell.Value) &&
                        (cell.Right == null || cell.Right.Value > cell.Value) &&
                        (cell.Top == null || cell.Top.Value > cell.Value) &&
                        (cell.Bottom == null || cell.Bottom.Value > cell.Value);
}

SetNext

private static void SetNext(Cell[] cells)
{
    foreach (var cell in cells.Where(c => !c.IsSink))
        cell.Next = GetNext(cell);
}

private static Cell GetNext(Cell cell)
{
    var cells = new[] {cell.Left, cell.Right, cell.Top, cell.Bottom};
    return cells.Where(c => c != null)
        .OrderBy(c => c.Value)
        .First();
}

GetBasins

private static IEnumerable<int> GetBasins(Cell[] cells)
{
    var visited = new HashSet<Cell>();
    var basin = cells.Where(c => c.IsSink).ToDictionary(c => c, c => 1);

    foreach (var cell in cells.Where(c => !c.IsSink))
    {
        var current = cell;
        int count = 0;
        while (!current.IsSink)
        {
            if (visited.Add(current)) count++;
            current = current.Next;
        }
        basin[current] += count;
    }

    return basin.Values.OrderByDescending(v => v);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ why the fancy yield return in CreateCells when the only caller's first action is to do a ToArray() on it. Just make CreateCells make an array \$\endgroup\$ – pm100 Aug 3 '16 at 21:26
  • 1
    \$\begingroup\$ yield has been introduced with C# 2.0 (2005)... so it's not fancy but a well-established language element ;). In general I prefer yield compared to introducing a local variable because it simplifies the code. However, the usage in method CreateCells is close to the edge... \$\endgroup\$ – JanDotNet Aug 4 '16 at 5:48
  • 1
    \$\begingroup\$ @pm100 I don't think it's fancy but rather a good habit. \$\endgroup\$ – t3chb0t Aug 4 '16 at 9:10
6
\$\begingroup\$

The most obvious changes are to put most of those static methods into the Cell class.

If you thought little bit more carefully you could Tell that IsSink and Next could be calculated properties, removing the need for the methods GetNext, SetNext and SetIsSink.

public Cell Next {
    get
    {
        var cells = new[] { Left, Right, Top, Bottom };
        return cells.Where(c => c != null)
                    .OrderBy(c => c.Value)
                    .First();
    } 
}

public bool IsSink { 
    get {
        return (Left == null || Left.Value > Value) &&
                (Right == null || Right.Value > Value) &&
                (Top == null || Top.Value > Value) &&
                (Bottom == null || Bottom.Value > Value);
    } 
}

The same goes for ConnectCell and all help methods used there.

private void ConnectCell(Cell[,] cells)
{
    Left = ColIndex > 0 ? cells[RowIndex, ColIndex - 1] : null;
    Right = ColIndex < cells.GetLength(1) -1 ? cells[RowIndex, ColIndex - 1] : null;
    Top = RowIndex > 0 ? cells[RowIndex - 1, ColIndex] : null;
    Bottom = RowIndex < cells.GetLength(0) -1 ? cells[RowIndex + 1, ColIndex] : null;
}

You don't need to create explicit backfields for the properties RowIndex, ColIndex and Value. Instead create private setters. Example for Value

public int Value{ get; private set; }

It's also worth mentioning that the prefix my is not adding any information to the name. In C# it's common the use of _ as a field prefix instead.

If you are willing to use jagged arrays, you can change ReadData to use more Linq.

private static int[][] ReadData()
{
    var size = int.Parse(Console.ReadLine());
    var result = new int[size][];
    for (int row = 0; row < size; row++)
    {
        var rowData = Console.ReadLine()
            .Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
            .ToArray()
            .Select(s => int.Parse(s))
            .ToArray();
        result[row] = rowData;
    }
    return result;
}
\$\endgroup\$
  • \$\begingroup\$ The ToArray after Split is not needed. \$\endgroup\$ – Bruno Costa Aug 4 '16 at 14:39
  • \$\begingroup\$ Thanks for the great review! Incredible that I didn't see that lots of the functions actually belong to the cell XD... However, I think I would prefere readonly backfields over private setters because it increases the part of immutable state. \$\endgroup\$ – JanDotNet Aug 15 '16 at 6: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.