Kissat ja hiiret speksin mukaan

package fpchallenge;

import java.lang.management.ManagementFactory;
import java.lang.management.OperatingSystemMXBean;
import java.lang.management.RuntimeMXBean;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Timer;
import java.util.TimerTask;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

public class MazeTest {
    public static void main(String[] args) throws InterruptedException {
        Maze maze = new Maze( 10,10,false );
        for( int i = 0; i < 15; i++ )
            maze.enter( new Cat( maze ) );
        for( int i = 0; i < 45; i++ )
            maze.enter( new Rat( maze ) );
        for( int i = 0; i < 5; i++ )
            maze.enter( new Dog( maze ) );
        maze.start( );
        Thread.sleep( 10000 );
        maze.stop( 5,TimeUnit.SECONDS );
    }
}

// Maze.java

class Maze {
    private static class Room {
        final Location location;
        Animal animal;

        Room( Location location ) {
            this.location = location;
        }

        public String toString( ) {
            return animal != null ? animal.toString( ) : "N/A" + " at " + location;
        }
    }

    private static class MazeEvent {
        private static final AtomicInteger nextOrdinal = new AtomicInteger( );
        private final String message;
        private final Date timestamp;
        private final int ordinal;

        MazeEvent( String message ) {
            this.message = message;
            timestamp = new Date( );
            ordinal = nextOrdinal.incrementAndGet( );
        }

        @Override
        public String toString( ) {
            DateFormat df = new SimpleDateFormat( "HH:mm:ss.SSS" );
            return String.format( "Event %5d at %s %s",ordinal,df.format( timestamp ), message );
        }
    }

    private final int width;
    private final int height;
    private final Map<Location,Room> rooms;
    private ExecutorService threads;
    private final Random random = new Random( System.currentTimeMillis( ) );
    private final List<MazeEvent> events = new ArrayList<MazeEvent>( );
    private final Collection<Animal> animals = new ArrayList<Animal>( );
    private final AtomicInteger animalCount = new AtomicInteger( );
    private final boolean predatorsAnnihilateOnCollission;

    Maze( int width,int height,boolean predatorsAnnihilateOnCollission ) {
        this.width = width;
        this.height = height;
        this.predatorsAnnihilateOnCollission = predatorsAnnihilateOnCollission;
        rooms = new HashMap<Location,Room>( );
        for( int x = 0; x < width; x++ )
             for( int y = 0; y < height; y++ )
                 rooms.put( new Location( x,y ),new Room( new Location( x,y ) ) );
    }

    void logEvent( String message ) {
        synchronized( events ) {
            events.add( new MazeEvent( message ) );
        }
    }

    public int getWidth( ) {
        return width;
    }

    public int getHeight( ) {
        return height;
    }

    synchronized boolean moveTo( Animal animal,Location currLocation,Location newLocation ) {
        // Dead animals do not move
        if( ! animal.isAlive( ) || newLocation.equals( currLocation ) )
            return false;

        Room newRoom = rooms.get( newLocation );
        Room currRoom = rooms.get( currLocation );

        if( animal != newRoom.animal ) {
            if( newRoom.animal == null ) {
                newRoom.animal = animal;
                currRoom.animal = null;
                logEvent( animal + " moved from " + currLocation + " to " + newLocation );
                return true;
            }
            // Two non-predators cannot fit the same room, prevent movement
            if( ! newRoom.animal.isPredator( ) && ! animal.isPredator( ) )
                return false;

            // Both are predators, they annihilate each other
            if( newRoom.animal.isPredator( ) && animal.isPredator( ) ) {
                if( predatorsAnnihilateOnCollission ) {
                    logEvent( animal + " moved from " + currLocation + " to " + newLocation );
                    logEvent( animal + " and " + newRoom.animal + " annihilated each other at location " + newRoom.location );
                    ( ( AbstractAnimal ) animal ).killed( newRoom.animal );
                    ( ( AbstractAnimal ) newRoom.animal ).killed( animal );
                    ( ( AbstractAnimal ) newRoom.animal ).setTerminated( newRoom.location );
                    ( ( AbstractAnimal ) animal ).setTerminated( currRoom.location );
                    return true;
                }
                else
                    return false;
            }
            // Only one of two is a predator
            else if( newRoom.animal.isPredator( ) || animal.isPredator( ) ) {
                logEvent( animal + " moved from " + currLocation + " to " + newLocation );
                //dumpMaze( animal,newRoom.animal );
                if( animal.isPredator( ) ) {
                    logEvent( newRoom.animal + " was killed by " + animal + " at location " + newRoom.location );
                    ( ( AbstractAnimal ) newRoom.animal ).setTerminated( newRoom.location );
                    ( ( AbstractAnimal ) animal ).killed( newRoom.animal );
                    currRoom.animal = null;
                    newRoom.animal = animal;
                }
                else {
                    logEvent( animal + " was killed by " + newRoom.animal + " at location " + newRoom.location );
                    ( ( AbstractAnimal ) newRoom.animal ).killed( animal );
                    ( ( AbstractAnimal ) animal ).setTerminated( currRoom.location );
                }
                return true;
            }

            return true;
        }

        return false;
    }

    synchronized void animalDestroyed( Animal animal,Location atLocation ) {
        Room room = rooms.get( atLocation );
        if( room.animal == animal ) {
            room.animal = null;
            animalCount.decrementAndGet( );
            logEvent( "Destroyed " + animal + " at " + room.location );
        }
    }

    synchronized Location getInitialLocation( Animal animal ) {
        // First try random (x,y)
        int randomX = width - random.nextInt( width ) - 1;
        int randomY = height - random.nextInt( height ) - 1;
        Location location = new Location( randomX,randomY );
        Room room = rooms.get( location );
        if( room.animal == null ) {
            room.animal = animal;
            animalCount.incrementAndGet( );
            return location;
        }

        // No luck, then try brute force
        for( int x = 0; x < width; x++ ) {
            for( int y = 0; y < height; y++ ) {
                location = new Location( x,y );
                room = rooms.get( location );
                if( room != null && room.animal == null ) {
                    room.animal = animal;
                    animalCount.incrementAndGet( );
                    return location;
                }
            }
        }

        throw new IllegalStateException( "No free locations available" );
    }

    public void enter( Animal animal ) {
        if( animals.size( ) == width * height )
            throw new IllegalStateException( "No free locations available" );

        animals.add( animal );
    }

    public synchronized void start( ) {
        OperatingSystemMXBean osBean = ManagementFactory.getOperatingSystemMXBean( );
        int nop = osBean.getAvailableProcessors( );
        logEvent(   "Running " + animals.size( ) + " threads concurrently" );
        logEvent( "Number of cores is " + nop + " and thus true parallelism degree is restricted to " + nop );
        logEvent( "Predators annihilate each other on collission is set to " + predatorsAnnihilateOnCollission );
        threads = Executors.newFixedThreadPool( animals.size( ) );
        for( Animal animal : animals )
            threads.submit( ( AbstractAnimal ) animal );
        animals.clear( );
    }

    public void stop( long timeout,TimeUnit tu ) throws InterruptedException {
        threads.shutdownNow( );
        threads.awaitTermination( timeout,tu );
        synchronized( events ) {
            Collections.sort( events,
                    new Comparator<MazeEvent>( ) {
                        @Override
                        public int compare( MazeEvent e1,MazeEvent e2 ) {
                            return ( int ) ( e1.ordinal - e2.ordinal );
                        }
                    }
            );
            for( MazeEvent event : events ) {
                System.out.println( event );
            }
        }

        System.out.println( "\nGame Over. Survived animals (" + animalCount.get() + ") are: " );
        synchronized( this ) {
            for( Room room : rooms.values( ) ) {
                if( room.animal != null ) {
                    if( ! room.animal.isAlive( ) )
                        System.out.println( room.animal + " is terminated so this is a BUG" );
                    else {
                        AbstractAnimal animal = ( AbstractAnimal ) room.animal;
                        if( animal.isPredator( ) ) {
                            System.out.println( animal + " at location " + room.location +
                                                ". Killed " + animal.getNumberOfKilledAnimals( ) +
                                                " animal(s)." );
                        }
                        else
                            System.out.println( animal + " at location " + room.location );
                    }
                }
            }
        }
        RuntimeMXBean rtbean = ManagementFactory.getRuntimeMXBean( );
        System.out.println( "\nJVM uptime upon terminatation is " + rtbean.getUptime( ) + " ms" );
    }
}

// Animal.java (not useful in this case, but ..)

interface Animal {
    public Location getLocation( );
    public boolean isPredator( );
    public boolean isAlive( );
}

// AbstractAnimal.java

abstract class AbstractAnimal implements Animal, Runnable {
    private final Maze maze;
    private final Random random = new Random( System.nanoTime( ) );
    private volatile Location location;
    private volatile boolean terminated;
    private final int minThinkTime;
    private final int maxThinkTime;
    private AtomicInteger killedAnimals = new AtomicInteger( );

    public AbstractAnimal( Maze maze ) {
        this( maze,100,1000 );
    }

    public AbstractAnimal( Maze maze,int minThinkTime,int maxThinkTime ) {
        this.maze = maze;
        this.minThinkTime = minThinkTime;
        this.maxThinkTime = maxThinkTime;
    }

    protected Maze getMaze( ) {
        return maze;
    }

    protected long getRandom( int low,int high ) {
        return low + random.nextInt( high - low );
    }

    public Location getLocation( ) {
        return location;
    }

    void killed( Animal animal ) {
        killedAnimals.incrementAndGet( );
    }

    public int getNumberOfKilledAnimals( ) {
        return killedAnimals.get( );
    }

    void setTerminated( Location atLocation ) {
        if( isAlive( ) ) {
            terminated = true;
            location = atLocation;
            maze.animalDestroyed( this,atLocation );
        }
    }

    public boolean isAlive( ) {
        return ! terminated;
    }

    @Override
    public void run( ) {
        try {
            location = maze.getInitialLocation( this );
            maze.logEvent( "Initial location of " + this + " is set to " + location );

            while( isAlive( ) ) {
                move( );
                if( isAlive( ) ) {
                    long thinkTime = getRandom( minThinkTime,maxThinkTime );
                    maze.logEvent( this + " thinking " + thinkTime + " millisecs before next move" );
                    Thread.sleep( thinkTime );
                }
            }
        }
        catch( IllegalStateException e ) {
            maze.logEvent( this + " couldn't enter the maze due to exception: " + e );
        }
        catch( InterruptedException e ) {
            Thread.currentThread().interrupt( );
        }
        maze.logEvent( "Thread " + Thread.currentThread( ).getName( ) + " serving " + this + " is returned to the pool" );
    }

    private void move( ) {
        // Get stable reference
        Location l = location;
        int x = l.x;
        int y = l.y;
        int direction = random.nextInt( 8 );
        for( int i = 0; i < 4; i++, direction++ ) {
            switch( direction % 8 ) {
                case 0 :
                    // North
                    y = l.y > 0 ? l.y - 1 : l.y;
                    break;
                case 1 :
                    // South
                    y = l.y < ( maze.getHeight( ) - 1 ) ? l.y + 1 : l.y;
                    break;
                case 2 :
                    // West
                    x = l.x > 0 ? l.x - 1 : l.x;
                    break;
                case 3 :
                    // East
                    x = l.x < ( maze.getWidth( ) - 1 ) ? l.x + 1 : l.x;
                    break;
                case 4 :
                    // North-east
                    x = l.x < ( maze.getWidth( ) - 1 ) ? l.x + 1 : l.x;
                    y = l.y < ( maze.getHeight( ) - 1 ) ? l.y + 1 : l.y;
                    break;
                case 5 :
                    // North-west
                    x = l.x > 0 ? l.x - 1 : 0;
                    y = l.y < ( maze.getHeight( ) - 1 ) ? l.y + 1 : l.y;
                    break;
                case 6 :
                    // South-west
                    x = l.x > 0 ? l.x - 1 : l.x;
                    y = l.y > 0 ? l.y - 1 : l.y;
                    break;
                case 7 :
                    // South-east
                    x = l.x < ( maze.getWidth( ) - 1 ) ? l.x + 1 : l.x;
                    y = l.y > 0 ? l.y - 1 : l.y;
                    break;
                default :
                    throw new RuntimeException( "This is a bug" );
            }

            Location newLocation = new Location( x,y );
            Location currLocation = location;
            location = newLocation;
            if( maze.moveTo( this,currLocation,newLocation ) ) {
                location = newLocation;
                break;
            }
            else {
                // If movement fails
                location = currLocation;
            }
        }
        if( location == l && isAlive( ) )
            maze.logEvent( this + " couln't move due to congestion near location " + location );
    }
}

// Location.java

class Location {
    public final int x, y;

    Location( int x,int y ) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString( ) {
        return "(" + x + ", " + y + ")";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + x;
        result = prime * result + y;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Location other = (Location) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }
}

// Cat.java

class Cat extends AbstractAnimal {
    private static final AtomicInteger ordinals = new AtomicInteger( );
    private final int id;

    public Cat( Maze maze ) {
        super( maze );
        id = ordinals.incrementAndGet( );
    }

    @Override
    public boolean isPredator( ) {
        return true;
    }

    @Override
    public String toString( ) {
        return "Cat " + id;
    }
}

// Rat.java

class Rat extends AbstractAnimal {
    private static final AtomicInteger ordinals = new AtomicInteger( );
    private final int id;

    public Rat( Maze maze ) {
        super( maze );
        id = ordinals.incrementAndGet( );
    }

    @Override
    public boolean isPredator( ) {
        return false;
    }

    @Override
    public String toString( ) {
        return "Rat " + id;
    }
}

// Dog.java

class Dog extends AbstractAnimal {
    private static final AtomicInteger ordinals = new AtomicInteger( );
    private final int id;
    private final long maxLifeTime;
    private final Timer timer = new Timer( );

    public Dog( Maze maze ) {
        super( maze );
        id = ordinals.incrementAndGet( );
        maxLifeTime = getRandom( 2000,20000 );
    }

    @Override
    void setTerminated( Location atLocation ) {
        timer.cancel( );
        super.setTerminated( atLocation );
    }

    @Override
    public void run( ) {
        timer.schedule(
                new TimerTask( ) {
                    @Override
                    public void run() {
                        getMaze( ).logEvent( Dog.this + " is dying since maximum life time " + maxLifeTime + " ms has now elapsed. Killed " +
                                            getNumberOfKilledAnimals( ) + " animals." );
                        setTerminated( getLocation( ) );
                    }
                },
                maxLifeTime
        );
        super.run( );
    }

    @Override
    public boolean isPredator( ) {
        return true;
    }

    @Override
    public String toString( ) {
        return "Dog " + id;
    }
}