CodeReview_Rainfall.cs

// CodeReview_Rainfall.cs
// 2016-08-21
//
// see http://codereview.stackexchange.com/questions/38500/rainfall-challenge

#if !LINQPAD
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
#endif

class Rainfall
{
    const string TEST_FILE = "d:/dev/cpp/cc/LINQPad/queries/CodeReview/rainfall/"
        + /**/ "sample-3-input.txt" /*/ "rainfall-example-4.txt" /**/;

    static void Main (string[] args)
    {
        var filename = args != null && args.Length > 0 ? args[0] : TEST_FILE;

        using (var sr = new StreamReader(filename))
            process_file(sr);
    }

    static void process_file (StreamReader sr)
    {
        var s = sr.ReadLine().Trim().Split().Select(int.Parse).ToArray();
        int row_count = s[0], col_count = s.Length > 1 ? s[1] : row_count;
        var dsf = Enumerable.Repeat(-1, row_count * col_count).ToArray();
        var dummy = Enumerable.Repeat(ushort.MaxValue, 1 + row_count + 1).ToArray();
        ushort[] prev_row = dummy, curr_row = dummy;

        for (int row = 0; row <= row_count; ++row)
        {
            var next_row = dummy;

            if (row < row_count)
                next_row = ("65535 " + sr.ReadLine().Trim() + " 65535").Split()
                    .Select(ushort.Parse)
                    .ToArray();

            if (row > 0)
            {
                for (int col = 1; col <= col_count; ++col)
                {
                    var n_w = Math.Min(prev_row[col], curr_row[col - 1]);
                    var s_e = Math.Min(next_row[col], curr_row[col + 1]);
                    var min = Math.Min(n_w, s_e);

                    if (curr_row[col] > min)
                    {
                        int curr = (row - 1) * col_count + (col - 1), sink = curr;

                        if (min == prev_row[col])
                            sink -= col_count;
                        else if (min == next_row[col])
                            sink += col_count;
                        else if (min == curr_row[col - 1])
                            sink -= 1;
                        else
                            sink += 1;

                        join(dsf, curr, sink);
                    }
                }
            }

            prev_row = curr_row;
            curr_row = next_row;
        }

        var basins = new HashSet<int>(Enumerable.Range(0, dsf.Length).Select(i => root(dsf, i)));
        var counts = basins.Select(sink => -dsf[sink]).OrderBy(x => -x);

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

    static int root (int[] a, int i)
    {
        int j = a[i];

        if (j >= 0)
            for (int k; (k = a[i = j]) >= 0; j = k)
                a[i] = k;

        return i;
    }

    static void join (int[] a, int i, int j)
    {
        if ((i = root(a, i)) != (j = root(a, j)))
        {
            if (a[i] <= a[j])  // |set(i)| >= |set(j)| (membership counts are negative)
            {
                a[i] += a[j];
                a[j] = i;
            }
            else
            {
                a[j] += a[i];
                a[i] = j;
            }
        }
    }
}