Hackerrank: Gridland Metro

Question

Problem statement

The city of Gridland is represented as an n X m matrix where the rows are numbered from 1 to n and the columns are numbered from 1 to m.

Gridland has a network of train tracks that always run in straight horizontal lines along a row. In other words, the start and end points of a train track are (r, c₁) and (r, c₂), where r represents the row number, c₁ represents the starting column, and c₂ represents the ending column of the train track.

The mayor of Gridland is surveying the city to determine the number of locations where lampposts can be placed. A lamppost can be placed in any cell that is not occupied by a train track.

Given a map of Gridland and its k train tracks, find and print the number of cells where the mayor can place lampposts.

Note: A train track may (or may not) overlap other train tracks within the same row.

Input Format

The first line contains three space-separated integers describing the respective values of n(the number of rows), m (the number of columns), and k (the number of train tracks).

Each line i of the k subsequent lines contains three space-separated integers describing the respective values of r, c₁, and c₂ that define a train track.

Constraints

• 1 ≤ n, m ≤ 10⁹

• 0 ≤ k ≤ 1000

• 1 ≤ r ≤ n

• 1 ≤ c₁ ≤ c₂ ≤ m

Output Format

Print a single integer denoting the number of cells where the mayor can install lampposts.

Sample Input

4 4 3

2 2 3

3 1 4

4 4 4

Sample Output

9

Explanation

In the diagram above, the yellow cells denote the first train track, green denotes the second, and blue denotes the third. Lampposts can be placed in any of the nine red cells, so we print 9 as our answer.

My introduction of algorithm

The Gridland Metro is the medium level algorithm in the contest of Hackerrank World CodeSprint 7 in Sept. 2016. I did manage to solve the algorithm in the contest but I spend too many hours, problems are related to runtime error and timeout, the test cases I used in the code does not help to figure out the issue. Since n,m and k are with large value and I did not have good techniques to work on simulation of large test cases, I examined the code and remembered the coding guideline phrase "express the intent", and then change a for loop to one statement to get distinct rows with train tracks first, in the function CalculateNumberOfCellsTakenByTrainTracks, first statement:var distinctRowsOfTrainTracks = rowsOfTrainTracks.Distinct().ToArray().

Today I spent near 2 hours to review the C# algorithm, and put together the readable code, I have to relearn the algorithm and also write code with less smells, with some instructional notes.

The code passes all test cases on hackerrank.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GridlandMetro
{
    /*
     * problem statement:
     * https://www.hackerrank.com/contests/world-codesprint-7/challenges/gridland-metro
     */
    public class MyComparer : IComparer<Tuple<int, int>>
    {
        public int Compare(Tuple<int, int> x, Tuple<int, int> y)
        {
            return (x.Item1 - y.Item1);
        }
    }

    class Program
    {                    
        static void Main(string[] args)
        {
            //RunSampleTestcase(); 
            //RunSampleTestcase2();
            ProcessInput();
        }

        /*
         * Sample test case in the problem statement. 
         * The result should be 9 since 
         * 7 cells are taken by 3 train tracks.
         */
        private static void RunSampleTestcase()
        {          
            int k = 3;
            int rows = 4; 
            int columns = 4; 

            var map = new int[k];
            var rowsOfTrainTracks = new List<int>();
            var trainTrackColumns = new List<Tuple<int, int>>();

            var trainTracks = new int[3, 3]{
                {2,2,3},
                {3,1,4}, 
                {4,4,4}
            };

            for (int i = 0; i < k; i++)
            {
                int row = trainTracks[i, 0];
                int startColumn = trainTracks[i, 1];
                int endColumn   = trainTracks[i, 2];

                rowsOfTrainTracks.Add(row);
                trainTrackColumns.Add(new Tuple<int, int>(startColumn, endColumn));
            }

            long cellNumberTakenByTrainTracks = CalculateNumberOfCellsTakenByTrainTracks(rowsOfTrainTracks, trainTrackColumns);
            long cellsForLampposts = rows * columns - cellNumberTakenByTrainTracks;
            Debug.Assert(cellsForLampposts == 9); 
        }

        /*
         * Test case: 
         * Row No 2: 4 train tracks, 8 cells are taken by 4 train tracks.
         * 1 - 4 reserved for train track - merge two of [1,4],[2,3] 
         * 6 - 7 train track
         * 9 - 9 train track
         */
        private static void RunSampleTestcase2()
        {
            int k = 5;  // 5 train tracks

            int rows = 2;
            int columns = 10; 

            var map = new int[k];
            var rowsOfTrainTracks = new List<int>();
            var trainTrackColumns = new List<Tuple<int, int>>();

            var trainTracks = new int[5, 3]{
                {2,8,9},
                {2,2,3},
                {1,1,4}, 
                {2,1,4},
                {2,6,7}
            };

            for (int i = 0; i < k; i++)
            {
                int row = trainTracks[i, 0];
                int startColumn = trainTracks[i, 1];
                int endColumn = trainTracks[i, 2];

                rowsOfTrainTracks.Add(row);
                trainTrackColumns.Add(new Tuple<int, int>(startColumn, endColumn));
            }

            long cellNumberTakenByTrainTracks = CalculateNumberOfCellsTakenByTrainTracks(rowsOfTrainTracks, trainTrackColumns);
            long cellsForLampposts = rows * columns - cellNumberTakenByTrainTracks;
            Debug.Assert(cellsForLampposts == 8);
        }

        public static void ProcessInput()
        {
            string[] summaryRow = Console.ReadLine().Split(' ');
            int rowNumber = Convert.ToInt32(summaryRow[0]);
            int columnNumber = Convert.ToInt32(summaryRow[1]);
            int k = Convert.ToInt32(summaryRow[2]);

            var map = new int[k];
            var rowsOfTrainTracks = new List<int>();
            var trainTracks = new List<Tuple<int, int>>();

            for (int i = 0; i < k; i++)
            {
                var rowData = Console.ReadLine().Split(' ');

                int rowNo = Convert.ToInt32(rowData[0]);
                int startColumn = Convert.ToInt32(rowData[1]);
                int endColumn = Convert.ToInt32(rowData[2]);

                rowsOfTrainTracks.Add(rowNo);
                trainTracks.Add(new Tuple<int, int>(startColumn, endColumn));
            }

            long sum = rowNumber;
            sum *= columnNumber;

            Console.WriteLine(sum - CalculateNumberOfCellsTakenByTrainTracks(rowsOfTrainTracks, trainTracks));
        }

        /*
         * requirement:
         * 1. Lampposts can not be placed on a train track
         * 2. Train track is always on horizontal row, and train tracks may overlap other train tracks
         * within the same row
         * 3. Calculate the number of cells where the mayor can place lampposts
         * 
         * Design: 
         * merge intervals for each row - it is classical problem of Leetcode 56: Merge Intervals
         * 
         * @rowsOfTrainTracks - row number for each train track
         * @trainTracks - train track's start column and end column 
         * 
         * train tracks row information: rowsOfTrainTracks
         * and each train track's columns information are stored in trainTracks respectively
         * 
         */
        public static long CalculateNumberOfCellsTakenByTrainTracks(
            IList<int>             rowsOfTrainTracks,
            IList<Tuple<int, int>> trainTracks
            )
        {
            var distinctRowsOfTrainTracks = rowsOfTrainTracks.Distinct().ToArray();
            Array.Sort(distinctRowsOfTrainTracks);            

            long sum = 0;
            var trainTracksRows = rowsOfTrainTracks.ToArray();

            foreach (int row in distinctRowsOfTrainTracks)
            {
                var numberOfTrainTracks = rowsOfTrainTracks.Count(a => a == row);                

                int index = 0;
                int start = 0;

                var trainTracksOnSameRow = new List<Tuple<int, int>>();
                while (index < numberOfTrainTracks)
                {
                    int rowIndex = Array.IndexOf(trainTracksRows, row, start);
                    var trainTrack = trainTracks[rowIndex];
                    trainTracksOnSameRow.Add(trainTrack);

                    start = rowIndex + 1;
                    index++;
                }

                sum += SumCellsTakenByTrainTracksForSameRow(trainTracksOnSameRow);                
            }

            return sum;
        }

        /*
         * train tracks on same row
         * - merge intervals - train track stands for one interval
         * - sort train tracks by start column
         * - the array is based on start index 1 not 0
         * Add all cells taken by train tracks on the same row. 
         */
        private static long SumCellsTakenByTrainTracksForSameRow(IList<Tuple<int, int>> trainTrackOnSameRow)
        {
            var trainTracks = trainTrackOnSameRow.ToArray();
            IComparer<Tuple<int, int>> myComparer = new MyComparer();
            Array.Sort(trainTracks, myComparer);             

            var previous = trainTracks[0];
            long cellsTakensByTrainTracks = 0;
            for (int i = 1; i < trainTracks.Length; i++)
            {
                var current = trainTracks[i];

                // no overlap 
                if (previous.Item2 < current.Item1)
                {
                    cellsTakensByTrainTracks += previous.Item2 - previous.Item1 + 1;
                    previous = current;
                }

                // reset the previous 
                int start = previous.Item1;
                int end   = Math.Max(previous.Item2, current.Item2);

                previous = new Tuple<int, int>(start, end);
            }

            // edge case: Last one
            cellsTakensByTrainTracks += previous.Item2 - previous.Item1 + 1;

            return cellsTakensByTrainTracks;
        }
    }
}

Answer 1

Easier way to group tracks in the same row

Your code works correctly, but it is quite complex because of the way you gather all of the same tracks in the same row into an array. Your method is to:

1. Create an array of the distinct row numbers.
2. Sort the array of distinct row numbers.
3. For each distinct row, count the number of tracks on that row.
4. For each distinct row, gather the tracks that are on that row into an array.
5. For each distinct row, process the array of tracks on that row in a separate function.

Rather than do all of the above, you could just treat each track as a tuple of 3 integers: row, start column, and end column. Then you could sort the list of tuples by row followed by start column (i.e. the default sort order for a tuple). This leaves you with a list of tracks where all the tracks on the same row are adjacent to each other.

From there it is a simple matter to do the same thing that you did for each row.

Rewrite

Here is a rewrite of your program using the tuple sorting mentioned above. I removed the test cases and long comments, for brevity:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GridlandMetro
{
    /*
     * problem statement:
     * https://www.hackerrank.com/contests/world-codesprint-7/challenges/gridland-metro
     */
    class Program
    {
        static void Main(string[] args)
        {
            ProcessInput();
        }

        public static void ProcessInput()
        {
            string[] summaryRow = Console.ReadLine().Split(' ');
            int rowNumber = Convert.ToInt32(summaryRow[0]);
            int columnNumber = Convert.ToInt32(summaryRow[1]);
            int k = Convert.ToInt32(summaryRow[2]);

            var tracks = new List<Tuple<int, int, int>>();

            for (int i = 0; i < k; i++)
            {
                var rowData = Console.ReadLine().Split(' ');

                int row      = Convert.ToInt32(rowData[0]);
                int colStart = Convert.ToInt32(rowData[1]);
                int colEnd   = Convert.ToInt32(rowData[2]);

                tracks.Add(new Tuple<int, int, int>(row, colStart, colEnd));
            }
            tracks.Sort();

            long sum = (long) rowNumber * columnNumber;

            Console.WriteLine(sum -
                    CalculateNumberOfCellsTakenByTrainTracks(tracks));
        }

        public static long CalculateNumberOfCellsTakenByTrainTracks(
            IList<Tuple<int, int, int>> tracks
            )
        {
            // Set currentColEnd to -1 so that this track's length is 0.
            int  currentRow        = -1;
            int  currentColStart   = 0;
            int  currentColEnd     = -1;
            long cellsTakenByTrack = 0;

            foreach (var track in tracks)
            {
                int row      = track.Item1;
                int colStart = track.Item2;
                int colEnd   = track.Item3;

                if (row != currentRow || colStart > currentColEnd)
                {
                    // No overlap with current track.
                    // First add length of current track to total.
                    cellsTakenByTrack += (currentColEnd - currentColStart + 1);
                    // Now set current track to this track.
                    currentRow      = row;
                    currentColStart = colStart;
                    currentColEnd   = colEnd;
                }
                else if (colEnd > currentColEnd)
                {
                    // Extend current track.
                    currentColEnd = colEnd;
                }
            }

            cellsTakenByTrack += (currentColEnd - currentColStart + 1);
            return cellsTakenByTrack;
        }
    }
}

Answer 2

I don't understand all the code but I can help you with an idea to solve the problem

-If there are not train tracks then the solution will be n*m

-If there are train tracks we need to subtract this to n*m. How we subtract this?

First we save the train tracks in array, we will call this array trainTracks. Each of the cells consist of three values like in the input (row, start_column, end_column). Sort this array by row

Now we will solve each row. Take all the train tracks of a row (this is easy because you know that the train tracks are sorted by row) and take the start and end column in array. Something like this

//suppose we are in the row r1
while trainTracks[i]->row == r1
    Points.add(trainTracks[i]->start_column, 1)   //We will refer to this elements Points[i]->first and Points[i]->second
    Points.add(trainTracks[i]->end_column+1, -1)
    i = i + 1

We will see next why construct in that way the array

Now, we sort this array by the first element and if there are tie we take first the greater of the second element.

Create a new array of the same length that Points. In this array keep the cumulative sum of the second elements of Points

That is

//Points it´s already sorted
//cum is the array of the cumulative sum

s = Points.length()
cum[0] = Points[0]->second    

j = 1
while j < s
    cum[j] = Points[j]->second + cum[j-1]
    j = j + 1

Then, we look for the zeros in the array. That because when we put a 1 in the array Points it's because a new train track start and when we put -1 is because the train track finish one position before, but also are using this cell. So, when compute the cumulative sum and find a zero it's because finish a range of train tracks.

Now compute the ranges where are not zeros

s = Points.length()
last = Points[0]->first   //The first cell of Points is always the beginning of a train track

j = 1
while j < s 
    if cum[j] == 0   
        solution -= (Points[j]->first - last)
        if j + 1 < s
            last = Points[j+1]->first        //The beginning of a new range
    j = j + 1

Doing it for each row that appear in the input you can solve it.

I expect it was helpful!