Number of ways to have breakfast

Find the number of ways you can have breakfast in ‘n’ days, given Bread-butter can be eaten every day, Pizza can be eaten every alternate day and Burger can be eaten every two days.

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

namespace ConsoleApplication1
{
    class Program
    {
        public static int counter = 0;
        static void Main(string[] args)
        {
            string[] menu = {"Bread-Butter", "Pizza", "Burger" };
            int[] constraint = { 0, 1, 2 };
            int days = 3;
            GenerateCombinations(menu, constraint, days, "", 0);
            Console.WriteLine("\nNumber of ways to have breakfast = " + counter);
        }

        public static void GenerateCombinations(string[] menu, int[] constraint, int days, string str, int depth)
        {
            if(depth == days)
            {
                //Check for valid combinations and return
                if(IsValidCombo(menu, constraint, str))
                {
                    counter++;
                    Console.WriteLine(str);
                }
                return;
            }
            else
            {
                for(int i = 1; i <= Math.Pow(2, menu.Length) - 1; i++)
                {
                    string comboStr = Convert.ToString(i, 2).PadLeft(menu.Length, '0');
                    string tempStr = "";
                    for (int j = 0; j < comboStr.Length; j++)
                    {
                        if (int.Parse(comboStr[j].ToString()) == 1)
                        {
                            tempStr = tempStr + menu[j] + " ";
                        }
                    }
                    GenerateCombinations(menu, constraint, days, str + tempStr.Trim() + ";", depth + 1);
                }
            }
        }
        public static bool IsValidCombo(string[] menu, int[] constraint, string combo)
        {
            combo = combo.Trim(';');
            int[] position = new int[constraint.Length];
            for(int i = 0; i < position.Length; i++)
            {
                position[i] = -1;
            }
            Regex reg = new Regex(";");
            string[] str = reg.Split(combo);
            reg = new Regex(" ");
            for (int i = 0; i < str.Length; i++)//loop count = number of days
            {
                string[] tempStr = reg.Split(str[i]);
                for(int j = 0; j < tempStr.Length; j++)//loop for each day
                {
                    int k = GetIndex(menu, tempStr[j]);
                    if (position[k] == -1)
                    {
                        position[k] = i;
                    }
                    else//food item was consumed before
                    {
                        if(i - position[k] < constraint[k] + 1)
                        {
                            return false;
                        }
                        else
                        {
                            position[k] = i;
                        }
                    }
                }
            }
            return true;
        }
        public static int GetIndex(string[] menu, string str)
        {
            for(int i = 0; i < menu.Length; i++)
            {
                if (menu[i] == str)
                    return i;
            }
            return -1;
        }
    }
}

Output
=======
Burger;Pizza;Bread-Butter;
Burger;Bread-Butter;Pizza;
Burger;Bread-Butter;Bread-Butter;
Burger;Bread-Butter;Bread-Butter Pizza;
Burger;Bread-Butter Pizza;Bread-Butter;
Pizza;Burger;Pizza;
Pizza;Burger;Bread-Butter;
Pizza;Burger;Bread-Butter Pizza;
Pizza;Bread-Butter;Burger;
Pizza;Bread-Butter;Pizza;
Pizza;Bread-Butter;Pizza Burger;
Pizza;Bread-Butter;Bread-Butter;
Pizza;Bread-Butter;Bread-Butter Burger;
Pizza;Bread-Butter;Bread-Butter Pizza;
Pizza;Bread-Butter;Bread-Butter Pizza Burger;
Pizza;Bread-Butter Burger;Pizza;
Pizza;Bread-Butter Burger;Bread-Butter;
Pizza;Bread-Butter Burger;Bread-Butter Pizza;
Pizza Burger;Bread-Butter;Pizza;
Pizza Burger;Bread-Butter;Bread-Butter;
Pizza Burger;Bread-Butter;Bread-Butter Pizza;
Bread-Butter;Burger;Pizza;
Bread-Butter;Burger;Bread-Butter;
Bread-Butter;Burger;Bread-Butter Pizza;
Bread-Butter;Pizza;Burger;
Bread-Butter;Pizza;Bread-Butter;
Bread-Butter;Pizza;Bread-Butter Burger;
Bread-Butter;Pizza Burger;Bread-Butter;
Bread-Butter;Bread-Butter;Burger;
Bread-Butter;Bread-Butter;Pizza;
Bread-Butter;Bread-Butter;Pizza Burger;
Bread-Butter;Bread-Butter;Bread-Butter;
Bread-Butter;Bread-Butter;Bread-Butter Burger;
Bread-Butter;Bread-Butter;Bread-Butter Pizza;
Bread-Butter;Bread-Butter;Bread-Butter Pizza Burger;
Bread-Butter;Bread-Butter Burger;Pizza;
Bread-Butter;Bread-Butter Burger;Bread-Butter;
Bread-Butter;Bread-Butter Burger;Bread-Butter Pizza;
Bread-Butter;Bread-Butter Pizza;Burger;
Bread-Butter;Bread-Butter Pizza;Bread-Butter;
Bread-Butter;Bread-Butter Pizza;Bread-Butter Burger;
Bread-Butter;Bread-Butter Pizza Burger;Bread-Butter;
Bread-Butter Burger;Pizza;Bread-Butter;
Bread-Butter Burger;Bread-Butter;Pizza;
Bread-Butter Burger;Bread-Butter;Bread-Butter;
Bread-Butter Burger;Bread-Butter;Bread-Butter Pizza;
Bread-Butter Burger;Bread-Butter Pizza;Bread-Butter;
Bread-Butter Pizza;Burger;Pizza;
Bread-Butter Pizza;Burger;Bread-Butter;
Bread-Butter Pizza;Burger;Bread-Butter Pizza;
Bread-Butter Pizza;Bread-Butter;Burger;
Bread-Butter Pizza;Bread-Butter;Pizza;
Bread-Butter Pizza;Bread-Butter;Pizza Burger;
Bread-Butter Pizza;Bread-Butter;Bread-Butter;
Bread-Butter Pizza;Bread-Butter;Bread-Butter Burger;
Bread-Butter Pizza;Bread-Butter;Bread-Butter Pizza;
Bread-Butter Pizza;Bread-Butter;Bread-Butter Pizza Burger;
Bread-Butter Pizza;Bread-Butter Burger;Pizza;
Bread-Butter Pizza;Bread-Butter Burger;Bread-Butter;
Bread-Butter Pizza;Bread-Butter Burger;Bread-Butter Pizza;
Bread-Butter Pizza Burger;Bread-Butter;Pizza;
Bread-Butter Pizza Burger;Bread-Butter;Bread-Butter;
Bread-Butter Pizza Burger;Bread-Butter;Bread-Butter Pizza;

Number of ways to have breakfast = 63
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