Optimized Painting

You are given a range [first, last], initially white. You need to paint it black.
For this purpose you have a set of triples
[(f, l, cost), …] – where each triple means that you can paint the range [f, l] for ‘cost’ coins (limitations: cost is floating point >= 0; f, l are integers representing start and end of the range to be painted black).
Find minimum cost needed to paint the whole range [first, last] or return -1 if it’s impossible

Example:
[first, last] = [0, 5] and set of triples are
[[0, 5, 10], [0, 4, 1], [0, 2, 5], [2, 5, 1]]
Clearly the answer is to take [0, 4, 1] and [2, 5, 1] – the total cost will be 2.

Another example:
[first, last] = [0, 5]
triples are [[1,4, 10], [2, 5, 6]]
answer is -1, because it’s impossible to color the whole range.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace ConsoleApplication1
{
    public class Triplet
    {
        public int start;
        public int end;
        public float cost;
    }

    class Program
    {
        public static void Main(string[] args)
        {
            string rangeStr = "[0, 5]";
            string tripletStr = "[0, 5, 10], [0, 4, 1], [0, 2, 5], [2, 5, 1]";
            char[] trimChar = { '[', ']' };
            Regex reg = new Regex(",");
            string[] rangeSplit = reg.Split(rangeStr.Trim(trimChar));
            int start = int.Parse(rangeSplit[0].Trim());
            int end = int.Parse(rangeSplit[1].Trim());
            Triplet[] triplets = ParseTriplet(tripletStr);
            //Filter out valid triplets
            ArrayList al = new ArrayList();
            for (int i = 0; i < triplets.Length; i++)
            {
                if ((start >= triplets[i].start && start < triplets[i].end) || (end > triplets[i].start && end <= triplets[i].end) || (triplets[i].start >= start && triplets[i].start < end) || (triplets[i].end > start && triplets[i].end <= end))
                {
                    al.Add(i);
                }
            }
            //Generate combinations
            float minCost = 0; ArrayList comboList = new ArrayList();
            int flag = 0;
            int maxLimit = (int)Math.Pow(2, al.Count) - 1;
            for (int i = 1; i <= maxLimit; i++)
            {
                string binary = DecimalToBinary(i).PadLeft(al.Count, '0');
                float tempCost = 0; ArrayList tempList = new ArrayList();
                for (int j = 0; j < binary.Length; j++)
                {
                    if (binary[j] != '0')
                    {
                        tempCost = tempCost + triplets[(int)al[j]].cost;
                        tempList.Add(triplets[(int)al[j]]);
                    }
                }
                //Check for valid combinations
                if (ValidCombo(tempList, start, end))
                {
                    if (flag == 0)
                    {
                        flag = 1;
                        comboList.AddRange(tempList);
                        minCost = tempCost;
                    }
                    else if (tempCost < minCost)
                    {
                        comboList.Clear();
                        comboList.AddRange(tempList);
                        minCost = tempCost;
                    }
                }
            }
            if (comboList.Count == 0)
            {
                Console.WriteLine("No solution found...");
            }
            else
            {
                Console.WriteLine("Minimum Cost = " + minCost);
                for (int i = 0; i < comboList.Count; i++)
                {
                    Console.WriteLine("[" + ((Triplet)comboList[i]).start + ", " + ((Triplet)comboList[i]).end + ", " + ((Triplet)comboList[i]).cost + "]");
                }
            }
        }

        public static bool ValidCombo(ArrayList tempList, int start, int end)
        {
            Hashtable ht = CreateHashTable(start, end);
            for (int i = 0; i < tempList.Count; i++)
            {
                for (int j = ((Triplet)tempList[i]).start; j < ((Triplet)tempList[i]).end; j++)
                {
                    if (ht.Contains(j.ToString() + ";" + (j + 1).ToString()))
                    {
                        ht[j.ToString() + ";" + (j + 1).ToString()] = 1;
                    }
                }
            }
            return CheckHashTable(ht);
        }

        public static bool CheckHashTable(Hashtable ht)
        {
            foreach (DictionaryEntry entry in ht)
            {
                if ((int)entry.Value == 0)
                    return false;
            }
            return true;
        }

        public static Hashtable CreateHashTable(int start, int end)
        {
            Hashtable ht = new Hashtable();
            for (int i = start; i < end; i++)
            {
                ht.Add(i.ToString() + ";" + (i + 1).ToString(), 0);
            }
            return ht;
        }

        public static string DecimalToBinary(int num)
        {
            string rem = "";
            while (num >= 1)
            {
                int quot = num / 2;
                rem += (num % 2).ToString();
                num = quot;
            }
            // Reversing the  value
            string bin = "";
            for (int i = rem.Length - 1; i >= 0; i--)
            {
                bin = bin + rem[i];
            }
            return bin;
        }

        public static Triplet[] ParseTriplet(string tripletStr)
        {
            Triplet[] triplets = new Triplet[GetNumberOfTriplets(tripletStr)];
            string tempStr = ""; int flag = 0, counter = 0;
            for (int i = 0; i < tripletStr.Length; i++)
            {
                if (tripletStr[i] == '[')
                {
                    flag = 1;
                }
                else if (tripletStr[i] == ']')
                {
                    flag = 0;
                    Regex reg = new Regex(",");
                    string[] tripletSplit = reg.Split(tempStr);
                    triplets[counter] = new Triplet();
                    triplets[counter].start = int.Parse(tripletSplit[0].Trim());
                    triplets[counter].end = int.Parse(tripletSplit[1].Trim());
                    triplets[counter].cost = float.Parse(tripletSplit[2].Trim());
                    counter++;
                    tempStr = "";
                }
                else if (flag == 1)
                {
                    tempStr = tempStr + tripletStr[i];
                }
            }
            return triplets;
        }

        public static int GetNumberOfTriplets(string tripletStr)
        {
            int count = 0;
            for (int i = 0; i < tripletStr.Length; i++)
            {
                if (tripletStr[i] == '[')
                    count++;
            }
            return count;
        }
    }
}

Output
=======
Minimum Cost = 2
[0, 4, 1]
[2, 5, 1]
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s