Bridge Crossing

A party of four travelers comes to a rickety bridge at night. The bridge can hold the weight of at most two of the travelers at a time, and it cannot be crossed without using a flashlight. The travelers have one flashlight among them. Each traveler walks at a different speed: The first can cross the bridge in 1 minute, the second in 2 minutes, the third in 5 minutes, and the fourth takes 10 minutes to cross the bridge. If two travelers cross together, they walk at the speed of the slower traveler.
What is the least amount of time in which all the travelers can cross from one side of the bridge to the other? 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace BridgeCrossing
{
    class Program
    {
        static void Main(string[] args)
        {
            string person = "ABCD";
            char[,] combination = new char[(person.Length)*2, person.Length];
            for (int i = 0; i < (person.Length) * 2; i++)
            {
                for (int j = 0; j < person.Length; j++)
                {
                    combination[i, j] = char.Parse(person.Substring(j, 1));
                }
            }
            int minTime = -1;
            int[] pointer = new int[(person.Length) * 2];
            pointer[((person.Length) * 2) – 1] = -1;
            int row;
            do
            {
                row = ((person.Length) * 2) – 1;
            label1:
                pointer[row]++;
                if (pointer[row] == person.Length && row !=0)
                {
                    pointer[row] = 0;
                    row–;
                    goto label1;
                }
                else if (pointer[row] == person.Length && row == 0)
                {
                    break;
                }
                else
                {
                    string str = "";
                    for (int j = 0; j < (person.Length) * 2; j++)
                    {
                        str = string.Concat(str, combination[j, pointer[j]]);
                    }
                    if (validString(str))
                    {
                        //Console.WriteLine(str);
                        if (minTime == -1)
                        {
                            minTime = getTotalTime(str);
                            Console.WriteLine("Current optimized sequence and time: " + str + " —> " + minTime);
                        }
                        else
                        {
                            if (minTime > getTotalTime(str))
                            {
                                minTime = getTotalTime(str);
                                Console.WriteLine("Current optimized sequence and time: " + str + " —> " + minTime);
                            }
                        }
                    }
                }
            } while (pointer[0] != person.Length);
        }
        public static bool validString(string str)
        {
            //Condition to check that ABCD appears atleast once
            if (str.Contains(‘A’) && str.Contains(‘B’) && str.Contains(‘C’) && str.Contains(‘D’))
            {
                //Condition to check that (1,2), (4,5) and (7,8) characters are not same
                if (str.Substring(0, 1) != str.Substring(1, 1) &&
                    str.Substring(3, 1) != str.Substring(4, 1) &&
                    str.Substring(6, 1) != str.Substring(7, 1))
                {
                    //Condition to check that there are odd number of occurrences of the
                    //last two characters in the string
                    int count = 0;
                    for (int i = 0; i < str.Length; i++)
                    {
                        if (str.Substring(i, 1) == str.Substring(6, 1))
                        {
                            count++;
                        }
                    }
                    if (count % 2 != 0)
                    {
                        count = 0;
                        for (int j = 0; j < str.Length; j++)
                        {
                            if (str.Substring(j, 1) == str.Substring(7, 1))
                            {
                                count++;
                            }
                        }
                        if (count % 2 != 0)
                        {
                            //Condition to check that 3 is contained in (1,2) and 6 is contained in (7,8)
                            if (str.Substring(0, 2).Contains(char.Parse(str.Substring(2, 1))) &&
                                str.Substring(6, 2).Contains(char.Parse(str.Substring(5, 1))))
                            {
                                //Condition to check that non repeated character among (1,2,3) doesn’t appear in (4,5)
                                string tempStr = str.Substring(0, 3);
                                tempStr = tempStr.Replace(tempStr.Substring(2, 1), " ");
                                tempStr = tempStr.Trim();
                                if (!str.Substring(3, 2).Contains(tempStr))
                                {
                                    //Condition to check that non repeated character among (4,5,6) doesn’t appear in (7,8)
                                    if (str.Substring(3, 2).Contains(str.Substring(5, 1)))
                                    {
                                        tempStr = str.Substring(3, 3);
                                        tempStr = tempStr.Replace(str.Substring(5, 1), " ");
                                        tempStr = tempStr.Trim();
                                        if (!str.Substring(6, 2).Contains(tempStr))
                                        {
                                            return true;
                                        }
                                        else
                                        {
                                            return false;
                                        }
                                    }
                                    else
                                    {
                                        //Condition to check that if there are no repeated characters among (4,5,6),
                                        //then (4,5) and (7,8) should be different
                                        if (!str.Substring(6, 2).Contains(char.Parse(str.Substring(3, 1))) &&
                                !str.Substring(6, 2).Contains(char.Parse(str.Substring(4, 1))))
                                        {
                                            //Condition to check that 6 is always contained in (1,2,3,4,5)
                                            if (str.Substring(0, 5).Contains(char.Parse(str.Substring(5, 1))))
                                            {
                                                return true;
                                            }
                                            else
                                            {
                                                return false;
                                            }
                                        }
                                        else
                                        {
                                            return false;
                                        }
                                    }
                                }
                                else
                                {
                                    return false;
                                }
                            }
                            else
                            {
                                return false;
                            }
                        }
                        else
                        {
                            return false;
                        }
                    }
                    else
                    {
                        return false;
                    }
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        public static int getTotalTime(string str)
        {
            int totalTime = 0;
            totalTime = Math.Max(getPersonTime(str.Substring(0, 1)), getPersonTime(str.Substring(1, 1)));
            totalTime = totalTime + getPersonTime(str.Substring(2, 1));
            totalTime = totalTime + Math.Max(getPersonTime(str.Substring(3, 1)), getPersonTime(str.Substring(4, 1)));
            totalTime = totalTime + getPersonTime(str.Substring(5, 1));
            totalTime = totalTime + Math.Max(getPersonTime(str.Substring(6, 1)), getPersonTime(str.Substring(7, 1)));
            return totalTime;
        }
        public static int getPersonTime(string str)
        {
            //A = 1 minute
            //B = 2 minutes
            //C = 5 minutes
            //D = 10 minutes
            switch (str)
            {
                case "A": return 1;
                case "B": return 2;
                case "C": return 5;
                case "D": return 10;
                default: return 0;
            }
        }
    }
}
//Output
//Current optimized sequence and time: ABAACAAD —> 19
//Current optimized sequence and time: ABACDBAB —> 17
//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