Combo with minimum price

Given a list of combo items along with their price and the list of items to purchase, determine the optimal combination.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;
using System.IO;
using System.Text.RegularExpressions;
namespace ConsoleApplication1
{
    class Product
    {
        public string serialNumber;
        public float price;
        public string combo;
        public Product()
        {
            serialNumber = "";
            price = 0;
            combo = "";
        }
        public Product(string serialNumber, float price, string combo)
        {
            this.serialNumber = serialNumber;
            this.price = price;
            this.combo = combo;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            ArrayList productArrayList = new ArrayList();
            ArrayList filteredProductArrayList = new ArrayList();
            ArrayList requirementArrayList = new ArrayList();
            Console.WriteLine("Product List");
            Console.WriteLine("------------");
            //Read the data from files
            StreamReader sr = new StreamReader(@"C:\Users\saikatd\input\ProductList.txt");
            for (string str = sr.ReadLine(); str != null; str = sr.ReadLine())
            {
                Product p = new Product();
                p = GetProductList(str.Trim());
                Console.WriteLine(str.Trim());
                productArrayList.Add(p);
            }
            sr.Close();
            Console.WriteLine("------------------");
            sr = new StreamReader(@"C:\Users\saikatd\input\RequirementList.txt");
            Console.WriteLine("Requirement List");
            Console.WriteLine("------------------");
            for (string str = sr.ReadLine(); str != null; str = sr.ReadLine())
            {
                Console.WriteLine(str.Trim());
                requirementArrayList.Add(str.Trim());
            }
            sr.Close();
            Console.WriteLine("------------------");
            //For each requirement determine combo with minimal cost
            for (int i = 0; i < requirementArrayList.Count; i++)
            {
                //Clear the filtered array list
                filteredProductArrayList.Clear();
                for (int j = 0; j < productArrayList.Count; j++)
                {
                    if (ShouldConsiderForProcessing((Product)productArrayList[j], (string)requirementArrayList[i]))
                    {
                        filteredProductArrayList.Add(j);
                    }
                }
                string optimizedCombination = "";
                float optimizedCost = 0;
                //Perform combination of filteredProductArrayList
                int maxLimit = (int)Math.Pow(2, filteredProductArrayList.Count) - 1;
                for (int k = 1; k <= maxLimit; k++)
                {
                    string binary = DecimalToBinary(k).PadLeft(filteredProductArrayList.Count, '0');
                    string combination = "";
                    string combinationItems = "";
                    float tempCost = 0;
                    for (int j = 0; j < binary.Length; j++)
                    {
                        if (binary[j] != '0')
                        {
                            combination = combination + ((Product)productArrayList[(int)filteredProductArrayList[j]]).serialNumber + " ";
                            tempCost = tempCost + ((Product)productArrayList[(int)filteredProductArrayList[j]]).price;
                            combinationItems = combinationItems + ((Product)productArrayList[(int)filteredProductArrayList[j]]).combo + " ";
                        }
                        //Check if optimized combination contains all the required products
                        if (IsValidCombination(combinationItems, (string)requirementArrayList[i]))
                        {
                            if (optimizedCombination == "")
                            {
                                optimizedCost = tempCost;
                                optimizedCombination = combination;
                            }
                            else
                            {
                                if (optimizedCost > tempCost)
                                {
                                    optimizedCost = tempCost;
                                    optimizedCombination = combination;
                                }
                            }
                        }
                    }
                }
                Console.WriteLine("Optimized combination = " + optimizedCombination);
                Console.WriteLine("Optimized Cost = " + optimizedCost);
                Console.WriteLine("---------------------------------");
            }
        }

        public static bool IsValidCombination(string combinationItems, string requirement)
        {
            Regex reg = new Regex(" ");
            string[] requirementStr = reg.Split(requirement);
            combinationItems = combinationItems.Trim();
            string[] combinationStr = reg.Split(combinationItems);
            for (int i = 0; i < requirementStr.Length; i++)
            {
                int flag = 0;
                for (int j = 0; j < combinationStr.Length; j++)
                {
                    if (requirementStr[i] == combinationStr[j])
                    {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0)
                    return false;
            }
            return true;
        }

        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 bool ShouldConsiderForProcessing(Product p, string requirement)
        {
            Regex reg = new Regex(" ");
            string[] requirementStr = reg.Split(requirement);
            string[] productStr = reg.Split(p.combo);
            for (int i = 0; i < requirementStr.Length; i++)
            {
                for (int j = 0; j < productStr.Length; j++)
                {
                    if (requirementStr[i] == productStr[j])
                    {
                        return true;
                    }
                }
            }
            return false;
        }

        public static Product GetProductList(string str)
        {
            Regex reg = new Regex(" ");
            string[] tempStr = reg.Split(str);
            string serialNumber = "";
            float price = 0;
            string combo = "";
            for (int i = 0; i < tempStr.Length; i++)
            {
                if (i == 0)
                {
                    serialNumber = tempStr[i];
                }
                else if (i == 1)
                {
                    price = float.Parse(tempStr[i]);
                }
                else
                {
                    if (i == tempStr.Length - 1)
                    {
                        combo = combo + tempStr[i];
                    }
                    else
                    {
                        combo = combo + tempStr[i] + " ";
                    }
                }
            }
            Product p = new Product(serialNumber, price, combo);
            return p;
        }
    }
}

Output
=======
Product List
------------
1 5 Burger
2 4 French_Frice
3 8 Coldrink
4 12 Burger French_Frice Coldrink
5 14 Burger Coldrink
------------------
Requirement List
------------------
Coldrink
Burger Coldrink
Burger French_Frice
------------------
Optimized combination = 3
Optimized Cost = 8
---------------------------------
Optimized combination = 4
Optimized Cost = 12
---------------------------------
Optimized combination = 1 2
Optimized Cost = 9
---------------------------------
Press any key to continue . . .
Advertisements
This entry was posted in Business, 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