Exercise - Walking the Bridge

arithma

Welcome to yet another programming exercise.
So suddenly in the middle of an RPG game, you find yourself stranded on a tower with lava beneath you, a bridge, a candle light, and another tower that is safe and connects you to safety.
Each of your fellows requires a different time to reach the other end.
The bridge can hold two people at most.
No one can cross the bridge without the candle light.
Two people moving together must stay together (at the pace of the slower fellow).
You are all stranded on the dangerous side for starters, along with your candle light.
What is the minimum time required to pass the bridge?

Input: You are given the number of fellows (including you) that want to cross to safety. You are also given an array of positive integers representing the time needed for each of your fellows to cross the bridge.

PS: This is not an easy problem (it's not hard though, classic Computer Science material), and the calculation of the minimum time entails a calculation of the steps required to move to the other tower (at least that's how I had to implement it).

Example:
3 fellows,
Times for each of the fellows: 1 2 3
timer starts
1 and 2 move to the safe side. (Timer reads 2 minutes)
1 alone moves back to the dangerous side. (Timer reads 3 minutes)
1 and 3 move to the safe side. (Timer reads 6 minutes)

Everyone is safe in six minutes if the lava doesn't eat them up by then.

I wrote an implementation in C# and learned a few lessons about the .net collection containers. I am relatively still new to the language.

Hope you'll enjoy, oh and there's possibly a much more elaborate formulation to the problem that I am thinking of - but it will only test your ability to keep your sanity while debugging rather than challenge you algorithmically.

Georges

Here's My Solution:

// Suppose we have 5 persons, with different speeds...
private static int NbOfPers = 5;
private static int[] TimeRequired = new int[] { 4, 5, 1, 2, 3 };

private static int FindFastestPerson(int[] allTimes)
{
    int fastest = TimeRequired[0];

    for (int i = 1; i < allTimes.Length; i++)
    {
        // Find The Fastest Person...
        if (TimeRequired[i] < fastest)
            fastest = TimeRequired[i];
    }
    return fastest;
}

static void Main(string[] args)
{
    int minSpeed = FindFastestPerson(TimeRequired);

    int nbOfCrossings = (NbOfPers - 1) + (NbOfPers - 2);
    // NbOfPers - 1 : Nmb of times in which all the members can cross the bridge - By Pairs, excluding the fastest person since he's the one who's always crossing forward and backward.
    // NbOfPers - 2 : Nmb of times in which the fastest person has to cross the bridge.

    int minTime = 0;

    for (int i = 0; i < NbOfPers; i++)
    {
        minTime += TimeRequired[i] + minSpeed;
    }
    minTime -= 1; // Since the last crossing is not required. ( All Members are already in the other side of the bridge...)
    minTime -= 2 * minSpeed; // Since it refers to the fastest person, who's helping all the others to cross the bridge...

    Console.WriteLine("Number Of Persons : {0}\nFastest Person's Speed : {1}\nNumber of Crossings Required : {2}\nMinimum Time : {3}", NbOfPers, minSpeed, nbOfCrossings, minTime);
    Console.ReadKey();
}

arithma

*BUMP*
No takers?

mesa177

Not for the next two weeks, I have a mountain of paperwork to get from Faiyadieh, Mechref, Balamand, Mathaf and Bir Hassan. Maybe later on...

arithma

BTW George, what are your results for [1, 2, 5, 10, 15] ?

Georges

arithma wroteBTW George, what are your results for [1, 2, 5, 10, 15] ?

Here's the output:

Number of persons: 5
Fastest Person's speed: 1
Total crossings number: 7
Minimum time required: 35

arithma

+ [0] {[ 1 2 5 10 15 ] [ ] / L / 0} NightBridge.Program.State
+ [1] {[ 2 10 15 ] [ 1 5 ] / R / 5 - { [ 1 2 5 10 15 ] [ ] / L }} NightBridge.Program.State
+ [2] {[ 1 2 10 15 ] [ 5 ] / L / 6 - { [ 2 10 15 ] [ 1 5 ] / R }} NightBridge.Program.State
+ [3] {[ 10 15 ] [ 1 2 5 ] / R / 8 - { [ 1 2 10 15 ] [ 5 ] / L }} NightBridge.Program.State
+ [4] {[ 1 10 15 ] [ 2 5 ] / L / 9 - { [ 10 15 ] [ 1 2 5 ] / R }} NightBridge.Program.State
+ [5] {[ 1 ] [ 2 5 10 15 ] / R / 24 - { [ 1 10 15 ] [ 2 5 ] / L }} NightBridge.Program.State
+ [6] {[ 1 2 ] [ 5 10 15 ] / L / 26 - { [ 1 ] [ 2 5 10 15 ] / R }} NightBridge.Program.State
+ [7] {[ ] [ 1 2 5 10 15 ] / R / 28 - { [ 1 2 ] [ 5 10 15 ] / L }} NightBridge.Program.State

This is a dump right out from the debug. It show's different results from what you came forward with.

arithma

Are there no takers here?
This is quite an interesting cranium challenge. And yes, I did solve it. I somehow lost the source though. Yes, I'll go with dog ate my homework excuse. I think I still got it somewhere at work, if not, I believe I'd write it once again.

arithma

Bah, this is becoming a bit boring, but I really wanted to share this code with you guys. This shows how to ease up algorithmics by using an IEnumberable. (Just semantic sweetness).

[ 1 2 5 10 15 ] [ ] / L / 0
[ 2 10 15 ] [ 1 5 ] / R / 5
[ 1 2 10 15 ] [ 5 ] / L / 6
[ 10 15 ] [ 1 2 5 ] / R / 8
[ 1 10 15 ] [ 2 5 ] / L / 9
[ 1 ] [ 2 5 10 15 ] / R / 24
[ 1 2 ] [ 5 10 15 ] / L / 26
[ ] [ 1 2 5 10 15 ] / R / 28

// C# code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NightBridge
{
    class Program
    {
        class Coord : IComparable<Coord>
        {
            public enum Position
            {
                LEFT,
                RIGHT
            }

            public List<int> left;
            public List<int> right;
            public Position position;


            public Coord()
            {
                left = new List<int>();
                right = new List<int>();
                position = Position.LEFT;
            }

            public override string ToString()
            {
                StringBuilder result = new StringBuilder();
                result.Append("[ ");
                foreach(var i in left)
                    result.Append(i + " ");
                result.Append("] [ ");
                foreach(var i in right)
                    result.Append(i + " ");
                result.Append("] / ");
                result.Append(position == Position.LEFT ? "L" : "R");
                return result.ToString();
            }

            public int CompareTo(Coord other)
            {
                if(position != other.position)
                    if(position == Position.LEFT) return -1;
                    else return +1;
                if(left.Count < other.left.Count)
                    return -1;
                else if(left.Count > other.left.Count)
                    return +1;
                else if(right.Count < other.right.Count)
                    return -1;
                else if(right.Count > other.right.Count)
                    return +1;

                for(int i = 0; i < left.Count; i++) {
                    if(left[i] < other.left[i])
                        return -1;
                    else if(left[i] > other.left[i])
                        return +1;
                }

                for(int i = 0; i < right.Count; i++) {
                    if(right[i] < other.right[i])
                        return -1;
                    else if(right[i] > other.right[i])
                        return +1;
                }

                return 0;
            }

        }

        class State : IComparable<State>
        {
            public Coord previous;
            public int move;
            public int sum;
            public Coord coord;

            public State()
            {
                previous = null;
                sum = 0;
                move = 0;
                coord = new Coord();
            }

            public int CompareTo(State other)
            {
                return coord.CompareTo(other.coord);
            }

            public override string ToString()
            {
                return coord.ToString() + " / " + sum; // +(previous != null ? (" - { " + previous.ToString() + " }") : "");
            }

            public IEnumerable<Tuple<Coord, State>> Neighbours
            {
                get
                {
                    List<int> srcList = coord.position == Coord.Position.LEFT ? coord.left : coord.right;

                    for(int i = 0; i < srcList.Count; i++) {
                        State newState = new State();
                        newState.previous = coord;
                        newState.coord.left = new List<int>(coord.left);
                        newState.coord.right = new List<int>(coord.right);

                        List<int> mutateList = coord.position == Coord.Position.LEFT ? newState.coord.left : newState.coord.right;
                        List<int> targetList = coord.position == Coord.Position.LEFT ? newState.coord.right : newState.coord.left;

                        int numb = mutateList[i];
                        mutateList.RemoveAt(i);
                        targetList.Add(numb);
                        targetList.Sort();

                        if(coord.position == Coord.Position.LEFT)
                            newState.coord.position = Coord.Position.RIGHT;
                        else
                            newState.coord.position = Coord.Position.LEFT;

                        newState.move = numb;
                        newState.sum = this.sum + numb;

                        yield return new Tuple<Coord, State>(newState.coord, newState);

                    }
                    for(int i = 0; i < srcList.Count - 1; i++)
                        for(int j = i + 1; j < srcList.Count; j++) {
                            State newState = new State();
                            newState.previous = coord;
                            newState.coord.left = new List<int>(coord.left);
                            newState.coord.right = new List<int>(coord.right);

                            List<int> mutateList = coord.position == Coord.Position.LEFT ? newState.coord.left : newState.coord.right;
                            List<int> targetList = coord.position == Coord.Position.LEFT ? newState.coord.right : newState.coord.left;

                            int numb1 = mutateList[i];
                            mutateList.RemoveAt(i);
                            targetList.Add(numb1);
                            targetList.Sort();

                            int numb2 = mutateList[j - 1];
                            mutateList.RemoveAt(j - 1);
                            targetList.Add(numb2);
                            targetList.Sort();

                            if(coord.position == Coord.Position.LEFT)
                                newState.coord.position = Coord.Position.RIGHT;
                            else
                                newState.coord.position = Coord.Position.LEFT;

                            newState.move = numb2;
                            newState.sum = this.sum + numb2;

                            yield return new Tuple<Coord, State>(newState.coord, newState);
                        }
                }
            }
        }

        static bool IsEndState(State s)
        {
            return s.coord.left.Count == 0;
        }

        static List<State> getStatePath(State s, SortedDictionary<Coord, State> map)
        {
            List<State> r = new List<State>();
            State c = s;

            while(c != null) {
                r.Add(c);
                if(c.previous == null)
                    c = null;
                else
                    c = map[c.previous];
            }
            r.Reverse();
            return r;
        }

        static List<State> SolveBridge(List<int> time)
        {
            List<State> result = null;
            SortedDictionary<Coord, State> map = new SortedDictionary<Coord, State>();
            SortedSet<Coord> open = new SortedSet<Coord>();
            SortedSet<Coord> close = new SortedSet<Coord>();

            State state = new State();
            state.coord.left = (List<int>)time;
            state.coord.left.Sort();

            map.Add(state.coord, state);
            open.Add(state.coord);

            while(open.Count > 0) {
                var nextopen = new SortedSet<Coord>();
                foreach(var c in open) {

                    if(close.Contains(c)) continue;

                    if(result == null || result.Last().sum > map[c].sum) {
                        var neighbours = new List<Tuple<Coord, State>>(map[c].Neighbours);

                        foreach(var tuple in neighbours) {
                            if(close.Contains(tuple.Item1)) continue;

                            if(IsEndState(tuple.Item2) && (result == null || tuple.Item2.sum < result.Last().sum)) {
                                result = getStatePath(tuple.Item2, map);
                            }

                            if(!map.ContainsKey(tuple.Item1)) {
                                map[tuple.Item1] = tuple.Item2;
                                nextopen.Add(tuple.Item1);
                            }

                            else {
                                if(map[tuple.Item1].sum > tuple.Item2.sum) {
                                    map[tuple.Item1] = tuple.Item2;
                                    nextopen.Add(tuple.Item1);
                                }
                            }
                        }
                    }
                    close.Add(c);
                }
                open = nextopen;
           }

            return result;
        }

        static void Main(string[] args)
        {
            List<int> x = new List<int>();
            x.Add(1);
            x.Add(2);
            x.Add(5);
            x.Add(10);
            x.Add(15);

            List<State> sol = SolveBridge(x);
            sol.ForEach(xx => Console.WriteLine(xx));
        }
    }
}

The output shows the state of the left brige in brackets, the state of the right bridge, and using L or R to designate which tower has the candle light.