Friday, May 1, 2015

Turning a riddle/puzzle into code


I stumbled upon a little random coding exercise and I coded it just as a mental stretch if you will.  It is not artistically beautiful code but it works.  I found it difficult to create the logic in such a way that it could apply to something other than just this exact case.

The challenge basically is you have 3 things you are responsible for but two of them are dangerous to something else.  How do you transport them one at a time without having any of them get harmed.  In this case a wolf, goat, and a salad.  The wolf will eat the goat and the goat would eat the salad if you aren't there to stop them.  How do you move them one at time


The original puzzle can be found here.
https://go-left.com/blog/programming/100-little-programming-exercises/#C.1





import java.util.ArrayList;
import java.util.List;


public class Main {

    public static void main(String[] args) throws Exception {

//        https://go-left.com/blog/programming/100-little-programming-exercises/#C.1
//        Goat-Wolf-Salad
//
//        A goat, a wolf and a salad are on one side of a river and you need to get them to the other side 
//        using your boat. You can carry one item in your boat to the other side at any given time. 
//        However, when the goat and the wolf are left alone the wolf will eat the goat. 
//        If the goat and the salad are left alone the goat will eat the salad. As long as you 
//        are with them nothing will happen, i.e. the wolf won’t eat the goat and the goat won’t eat the salad.
//
//        W > G   G > S        
//        Write a program which determines algorithmically an order in which you carry them all to the other side.

        /**
         *  Solution: 
               WGSU |    |  ____   
                W S | UG |
                W S |    | UG
                WSU |    | G
                S   | UW | G
                S   |    | UWG
                S   | UG | W
                GSU |    | W
                G   | US | W
                G   |    | UWS                
                UG  |    | WS
                ___ | UG | WS
                    |    | UWGS
                
         */

         
        Main thisClass = new Main();
        Traveler you = thisClass.new Traveler("You"null);
        Traveler salad = thisClass.new Traveler("Salad"null);
        Traveler goat = thisClass.new Traveler("Goat", salad);
        Traveler wolf = thisClass.new Traveler("Wolf", goat);
        
        List leftbank = new ArrayList();
        leftbank.add(you);
        leftbank.add(salad);
        leftbank.add(goat);
        leftbank.add(wolf);

        List rightbank = new ArrayList();
                
        while(!leftbank.isEmpty()) {
            //determine who to move
            //move passenger
            //check if both sides safe or else throw exception
            transportPassenger(leftbank,rightbank, you);
            System.out.println("left: " + leftbank);
            System.out.println("right: " + rightbank);
            if(!isSafe(leftbank, you) || !isSafe(rightbank, you)) {
                throw new Exception("Someone got eatten");
            }
        }
        
    }
    
    private static void transportPassenger(List leftbank, List rightbank,  Traveler you) {
        if (leftbank.contains(you)) {
            Traveler passenger =  nextPassenger(leftbank, you);
            if (passenger == null) {
                //get the most dangerous traveler on the river bank
                for (Traveler traveler: leftbank) {
                    if (traveler.dangerousTo != null) {
                        passenger = traveler;
                        break;
                    }
                }
            }
            
            if (passenger != null) {
                leftbank.remove(passenger);
                rightbank.add(passenger);
                System.out.println("transporting: " + passenger.name);
            } else {
                System.out.println("transporting: none");
            }
            leftbank.remove(you);
            rightbank.add(you);
            
        } else if (!leftbank.isEmpty()) {                        
            Traveler passenger = null;
            if (rightbank .size() != 2) {
                passenger =  nextPassenger(rightbank, you);
                
            }
            if (passenger != null) {
                rightbank.remove(passenger);
                leftbank.add(passenger);
                System.out.println("transporting: " + passenger.name);
            } else {
                System.out.println("transporting: none");
            }
            rightbank.remove(you);
            leftbank.add(you);
        }        
    }
    
    
    private static Traveler nextPassenger(List riverbank,  Traveler you) {
        Traveler passenger = null;
        List inDanger = new ArrayList();
        //get the travelers that are in danger
        for (Traveler traveler: riverbank) {
            if (traveler.dangerousTo != null) {
                for (Traveler anotherPassenger : riverbank) {
                    if (traveler != anotherPassenger && traveler.dangerousTo == anotherPassenger) {
                        inDanger.add(anotherPassenger);
                        System.out.println("in Danger: " + anotherPassenger.name);
                    }
                }
            }
        }
        if (inDanger.size() == 1) {
            passenger = inDanger.get(0);
        } else if (inDanger.size() > 1){
            //get most dangerous in danger
            for (Traveler traveler: inDanger) {
                if (traveler.dangerousTo != null) {
                    passenger = traveler;
                    break;
                }
            }
        }
        
        return passenger;        
    }
    
    private static boolean isSafe(List group, Traveler you) {
        boolean isSafe = true;
        
        if (!group.contains(you)) { 
            for (Traveler passenger : group) {
                if (passenger.dangerousTo != null) {
                    for (Traveler anotherPassenger : group) {
                        if (passenger.dangerousTo == anotherPassenger) {
                            isSafe = false;
                        }
                    }            
                }
            }
        }
        
        return isSafe;        
    }
    
    private class Traveler {
        public String name;
        public Traveler dangerousTo;
        
        public Traveler(String name, Traveler dangerousTo) {
            this.name = name;
            this.dangerousTo = dangerousTo;
        }
        
        public String toString() {
            return name;
        }
    }

}

No comments:

Post a Comment