OO Puzzle

Jvizzle

Hi,

Can someone do me a favour, I was looking on a coding website and saw an article that mentioned a puzzle called "the 17 minute bridge". As a test of my OO Programming ( which I havent done for sometime ) I knocked up a solution.

What im hoping is that someone will take 5 mins to look over the code from an OO sense and tell me if im on the right lines and what could be done to improve it.

The solution itself isnt ideal as its using a brute force method over a maths algorythm , but you can ignore that , as that wasnt the aim when I started coding. Its purely the OO code.

URL To Puzzle : http://members.aol.com/DrMWEcker/BrdgPuzl.htm

Attatched is the solution zip. The solution is done is VB.Net (2003) contains no exe's and has been scanned for viruses. Also this isnt a school / college project, its just me trying to get my head back around OO code.

Thanks

Mutant_Fruit

If you're looking for a good test of OO programming, write a library that decodes and encodes BEncoded material. That can be a fairly good test of your OO skills. If you do it a non-OO way, it can be quite messy :P

BEncoding is described here: http://wiki.theory.org/BitTorrentSpecification#bencoding

Jvizzle

Im quite happy with what I have done , although it did take me a little over an hour, that was quite enough to get me started , now I'm hoping that someone will rip it apart and point out the places that I have messed up with.

I would say bencoding is jumping in at the deep end As an estimate is it a large job doing the decoding library ? If its not hours of work I will certainly look into it.

Jvizzle

9 downloads and noone has an opinion ? Someone must have an opinion, anything welcome .....

I will start off with the fact that 2 of the properties have no return type and another access a public type that could have been best setup as a property.

Mutant_Fruit

I haven't had time to look at it, but i am right now.

As for BEncoding, a simple one wouldn't take too long. i.e. program assuming that you're getting 100% valid input. (i can supply you with loads of BEncoded strings if you need any to decode). I'd guesstimate 5 hours of work (not knowing your level of coding or if you'll spot the easy OO way of doing it).

EDIT: But i am a C# man at heart though

Mutant_Fruit

Jvizzle wrote:

9 downloads and noone has an opinion ? Someone must have an opinion, anything welcome .....

One thing i would say is that you solved it the wrong way You are relying on the right combination randomly coming up. This one should probably be solved using combinations. There's a finite set of possible ways 4 people can cross forwards and backwards, so test each solution. But due to the fact that different people can cross forwads and backwards at different times, it gets a little tricky to code that though.

    Public Manx As clsMan
    Public Many As clsMan

Should be private instead of public. They would be populated through your constructor, and would be visible through a public GET.

    Public Event PairCrossed(ByVal TimeTakenToCross As Integer, ByVal PairsNames As String)

Problem with this is that you'll need to subscribe to the event in each instance of clPairCrossing as you declare new ones. A better option would be to put that event in your CrossingMen class and call it in that class every time you send a pair across the river. The pair class wouldn't have the event in it.


Your clsMan class shouldnt have an option "cross as pair". A man class would just be a man. He'd have a "name", "crossing time", "number of times crossed" property and a "crossnow" method.

If you want to send to people across as a pair you put the two people into a "clsCrossingPair" instance and call myCrossingPairInstance.Cross(). That will handle all the logic for crossing as a pair.

Thats about it so far

Jvizzle

Thanks Mutant,

The solution isnt tidy , as I said its brute force, I didnt want to sit down and try and work out movements of men over the bridge. It was purely for the code.

I have changed the men pair objects to :

Private m_Manx As clsMan
Private m_Many As clsMan

That was an obvious over sight on my half that I should have caught.

Now to the interesting part the "clsCrossingPair" was added for the purpose of returning an event that fires the time to cross for the pair, if this fired per person crossed, the total time would added up wrong ( as the solution states the time crossed is the time of the slowest person of the pair ). I agree having a sub called "CrossAsPair" in a cls designed for a instance of a single person is wrong. Maybe its just poorly worded and should be called something like "CrossAsPartOfPair" ??

Just to clarify the clsCrossingPair was design to have one event for the pair , which gave the pairs crossing time. Also to beable to pass the slowest crossing time into the individual men classes so they dont think they have crossed at thier own speed, but the pair speed.

Again thank you for looking over it and I looking fwd to seeing what you make of the above.

Jvizzle

For anyone who is following this , these are the minor ammendments before the clsCrossingPair class is worked through

Mutant_Fruit

Jvizzle wrote:

Now to the interesting part the "clsCrossingPair" was added for the purpose of returning an event that fires the time to cross for the pair, if this fired per person crossed, the total time would added up wrong

Aye, thats perfect, there's no problems there.

Just to clarify the clsCrossingPair was design to have one event for the pair , which gave the pairs crossing time. Also to beable to pass the slowest crossing time into the individual men classes so they dont think they have crossed at thier own speed, but the pair speed.

Well, this is where i'd do it slightly differently (maybe not "better", just different). If i wanted to make 2 men cross as a pair, i'd create a "Pair" class. Then i'd go Pair mypair = new Pair(Man1, Man2); Then i'd call Pair.Cross().

Pair.Cross() would then calculate how long it'd take that pair to cross, update the two mens time accordingly and then set both of those men's positions equal to opposite side to the one in which they started. You could then fire the event for PairCrossed from this instance of the Pair Class.

pH

Based on previous comments about not solving it randomly but actually searching the problem space, here is a java solution based on the objects Puzzle, State and Member, single source file. I was going to try to explain the approach, but I find recursive code easier to write than to explain!

Performs a recursive depth first search of the the solution space until a solution with t <= 17 is found and then prints result.

The 'State' object is the key, it manages the state of the puzzle (who is on which side, where the torch is, and how long has gone).

/*
 * Puzzle.java
 */
package messing;

import java.util.*;

/**
 *
 * @author pH
 * Java U2 puzzle zolver.
 */
public class Puzzle {
    private static int count = 0;
    private static final Member BONO = new Member("Bono",1);
    private static final Member EDGE = new Member("Edge",2);
    private static final Member ADAM = new Member("Adam",5);
    private static final Member LARRY = new Member("Larry",10);
    
    private List<String> solution = new ArrayList<String>(5);  // Stores the solution to print in reverse order
    
    public Puzzle() {
        List<Member> side1 = new ArrayList<Member>(4);
        List<Member> side2 = new ArrayList<Member>(1);
        side1.add(BONO);
        side1.add(EDGE);
        side1.add(ADAM);
        side1.add(LARRY);
        State initial = new State(0, side1, side2, 1);
        if ( solve(initial) ) {
            for (int i = solution.size()-1; i >=0; i--)
                System.out.println( solution.get(i) );
        } else
            System.out.println("Failed to find a solution");
    }
    
    public static void main(String[] args) {
        new Puzzle();
    }
    
    private boolean solve(State state) {
        
        if (state.timeElaspsed > 17)  // Cannot take more than 17 minutes
            return false;
        
        if (state.side1.size() == 0 && state.side2.size() == 4 ) {
            solution.add("Final : " + state );
            return true;
        }
        
        for (State possible : generateMoves(state)) {
            
            if ( solve(possible) ) {
                solution.add("Step   :" + state );
                return true;
            }
        }
        
        return false;
    }
    
    /**
     * From this state, build a list of all valid states reachable by moving
     * One or Two members (From the side with the torch!)
     */
    List<State> generateMoves(State state) {
        List<State> possibles = new ArrayList<State>();
        List<Member> from = ( state.torch == 1 ) ? state.side1 : state.side2;
        for (int i=0;i<from.size();i++) {
            if (from.size() != 4)
                possibles.add( state.move( from.get(i) ) ); // Single Move
            int secMember = 1;
            while ( i + secMember < from.size() ) {
                possibles.add( state.move(from.get(i), from.get(i + secMember)));
                secMember++;
            }
        }
        
        return possibles;
    }
    /*
     * A U2 Band Member/Name and time taken to cross the bridge
     * No setter/getters - v.poor!
     */
    private static class Member {
        private String name;
        private int time;
        
        private Member(String name, int time) {
            this.name = name;
            this.time = time;
        }
        
        public String toString() {
            return this.name;
        }
    }
    /**
     * Represents the state of the puzzle, members on each side, time taken
     * and where the torch is.
     */
    private class State {
        
        private int timeElaspsed;
        private List<Member>side1; // Starting side
        private List<Member>side2; // Side to get to
        private int torch;
        
        private State(int timeElapsed, List<Member> side1, List<Member>side2, int torch ) {
            this.timeElaspsed = timeElapsed;
            this.side1 = side1;
            this.side2 = side2;
            this.torch = torch;
        }
        
        private State move(Member... a_members) {
            
            List<Member> newSide1 = copy(side1);
            List<Member> newSide2 = copy(side2);
            
            for (Member member : a_members) {
                if (newSide1.contains( member ) ) {
                    newSide1.remove(member);
                    newSide2.add(member);
                } else {
                    newSide2.remove(member);
                    newSide1.add(member);
                }
            }
            
            return new State(this.timeElaspsed + max(a_members), newSide1, newSide2, (torch ==1 ) ? 2 : 1);
        }
        
        public String toString() {
            return  side1.toString() + " +------+ " + side2.toString() + " (" + this.timeElaspsed + ")";
        }
        
    }
    
    private static final List<Member> copy(List<Member> source) {
        List<Member> dest = new ArrayList<Member>(source.size());
        for (Member member : source)
            dest.add(member);
        return dest;
    }
    
    private static final int max(Member[] members) {
        int max = 0;
        for (int i=0;i<members.length; i++ )
            if (members[i].time > max)
                max = members[i].time;
        
        return max;
    }
}

Output
Step :[Bono, Edge, Adam, Larry] +

---

+ [] (0)
Step :[Adam, Larry] +

---

+ [Bono, Edge] (2)
Step :[Adam, Larry, Bono] +

---

+ [Edge] (3)
Step :[Bono] +

---

+ [Edge, Adam, Larry] (13)
Step :[Bono, Edge] +

---

+ [Adam, Larry] (15)
Final : [] +

---

+ [Adam, Larry, Bono, Edge] (17)

Jvizzle

Thanks for th solutions pH, I will take some time over the next few days to read through how it works and probably try my own version using recursive methods.