Road Construction - Solution for Coding Challenge by Capgemini

Niladri.Biswas
Posted by in C# category on for Beginner level | Points: 250 | Views : 2798 red flag

Recently, Capgemini, has launced a coding contest. This article will show the solution as proposed by myself for level 2.

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.

Page copy protected against web site content infringement by Copyscape

About the Author

Niladri.Biswas
Full Name: Niladri Biswas
Member Level: Platinum
Member Status: Member
Member Since: 10/25/2010 11:04:24 AM
Country: India
Best Regards, Niladri Biswas
http://www.dotnetfunda.com
Technical Lead at HCL Technologies

Login to vote for this post.

Comments or Responses

Posted by: Ck.Kislay on: 5/22/2013 | Points: 25
Great Post Niladri!!
Will you explain in some more detail how this LINQ code will work, As I try to run it and it retuns nothing in console output window.

Thanks in advance!
Chandan

Login to post response

Comment using Facebook(Author doesn't get notification)