using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

​

/* The objective of this exercise is to build a road network connecting every pair of cities.

   Each city should be connected to each other city once.

*/

public class Program

{

    /* Your function RoadBuilder should return a list of new roads required to be built,

    if the existing roads are given by builtRoads and the total number of 

    cities is nCities. Roads should not connect cities to themselves.

    */

    public static int[][] RoadBuilder(int nCities, int[, ] builtRoads)

    {

        //implement the function here

        int totalRoads = 0;

        for (int r = 1; r < nCities; r++)

            totalRoads += r;

        Console.WriteLine("Total number of Roads to be created: " + totalRoads);

        List<string> ttlroads = new List<string>();

        for (int i = 0; i < nCities; i++)

            for (int j = i + 1; j < nCities; j++)

                ttlroads.Add(i + "," + j);

​

        int width = builtRoads.GetLength(0);

        int height = builtRoads.GetLength(1);

        List<string> bltroads = new List<string>(width * height);

        for (int i = 0; i < width; i++)

        {

            for (int j = 0; j < height - 1; j++)

            {

                bltroads.Add(builtRoads[i, j] + "," + builtRoads[i, j + 1]);

            }

        }

        var results = ttlroads.Except(bltroads);

        int[][] ival = new int[0][];

        //for (int k = 0; k < results.Count(); k++)

        //{

        //    ival[0][k] = results;

        //}

        return ival;

    }

​

    public static void Main()

    {

        int[, ] test1 = new int[3, 2]{{0, 1}, {1, 2}, {3, 2}};

        Console.WriteLine(RoadBuilder(4, test1)); // expected result should be {{0,2}, {0, 3}, {1, 3}}

    }

}