Road Construction - Solution for Coding Challenge by Capgemini

Introduction

Recently, Capgemini, has launced a coding contest.This article will show the solution of the second level coding challenge.The challenge(s) can be found here.

The Challenge Question - Level 2

Solution

The below is the solution in C#

using System;
using System.Linq;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var input1 = new string[] { "A", "B", "C", "D" };
            var input2 = new int[] { 2, 1, 3, 2, 4, 3 };
            var res = CandidateCode.minimum_cost(input1, input2);

            Console.ReadKey();
        }
    }

    public class CandidateCode
    {
        public static int minimum_cost(string[] input1, int[] input2)
        {           
            var mappings = new string[input1.Length * input2.Length]; //initial array
            var cities = input1;
            int cityLength = cities.Length;
            var counter = 1;           
            int index = 0;

            for (int i = 0; i < cityLength - 1; i++)
            {
                int cityIndex = 0;

                var newArray = cities.Skip(counter).ToArray();
                int newArrayLength = newArray.Length;

                for (int j = 0; j < newArrayLength; j++)
                {                  
                    mappings.SetValue(cities[cityIndex]+"," +  newArray[j] + "," + input2[index], index);
                    index++;
                }
                cities = newArray;
            }

            var result = from c in input1
                         select new
                         {
                             c,
                             cost =
                                     mappings
                                     .Take(index)
                                     .Where(m => m.Split(',')[0] == c || m.Split(',')[1] == c)
                                     .Sum(m => Convert.ToDecimal(m.Split(',')[2]))
                         };
            return Convert.ToInt32(result.Min(a => a.cost));           
        }        
    }
}

Now let us explain the program.first we are creating a mapping between city and cost, so we can easily access the cost of each edge.

for (int i = 0; i < cityLength - 1; i++)
	{
		int cityIndex = 0;

		var newArray = cities.Skip(counter).ToArray();
		int newArrayLength = newArray.Length;

		for (int j = 0; j < newArrayLength; j++)
		{                  
			mappings.SetValue(cities[cityIndex]+"," +  newArray[j] + "," + input2[index], index);
			index++;
		}
		cities = newArray;
	}

Now since we have an appropriate data structure, finding the path costs is easy:

 var result = from c in input1
                         select new
                         {
                             c,
                             cost =
                                     mappings
                                     .Take(index)
                                     .Where(m => m.Split(',')[0] == c || m.Split(',')[1] == c)
                                     .Sum(m => Convert.ToDecimal(m.Split(',')[2]))
                         };

And the shortest path is

Convert.ToInt32(result.Min(a => a.cost)) // 6

Conclusion

I hope that this will be a good learning exercise for those whose are beginners in C#.Also participating in challenges helps us to hone our skills.Thanks for reading.

Disclaimer: This solution has been personally prepared by me and submitted for the knowledge sharing purpose.