Kohlkopf, Ziege, Wolf und Java


Wie in meinem letzten Beitrag angekündigt hier die Java-Variante des Problems:

package cabbagegoatwolf;

import java.util.ArrayList;
import java.util.Collections;
import java.util.EnumSet;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import static cabbagegoatwolf.CabbageGoatWolf.Item.*;

public class CabbageGoatWolf {

    enum Item { Farmer, Cabbage, Goat, Wolf }

    private static class Position {

        public final Set<Item> left;
        public final Set<Item> right;

        public Position(Set<Item> left, Set<Item> right) {
            this.left = Collections.unmodifiableSet(left);
            this.right = Collections.unmodifiableSet(right);
        }

        @Override public boolean equals(Object o){
            return o instanceof Position
                   ? left.equals(((Position)o).left) && right.equals(((Position)o).right)
                   : false;
        }

        @Override public int hashCode() {
            return left.hashCode() + 257 * right.hashCode();
        }

        @Override public String toString() {
            return left.toString() + " ~~~ " + right.toString();
        }
    }

    private static boolean isValid(Set<Item> set) {
        return set.contains(Farmer) || !set.contains(Goat)
              || !(set.contains(Wolf) || set.contains(Cabbage));
    }

    private static Set<Position> findMoves(Position pos) {
        Set<Position> result = new HashSet<Position>();
        boolean farmerLeft = pos.left.contains(Farmer);
        for(Item item : farmerLeft ? pos.left : pos.right) {
            Set<Item> fromSet = EnumSet.noneOf(Item.class);
            fromSet.addAll(farmerLeft ? pos.left : pos.right);
            Set<Item> toSet = EnumSet.noneOf(Item.class);
            toSet.addAll(farmerLeft ? pos.right : pos.left);
            fromSet.remove(Farmer);
            toSet.add(Farmer);
            fromSet.remove(item);
            toSet.add(item);
            if(isValid(fromSet)) {
                result.add(farmerLeft ? new Position(fromSet, toSet)
                                      : new Position(toSet, fromSet));
            }
        }
        return result;
    }

    private static List<Position> loop(Position fromPos, Position toPos, List<Position> list) {
        if (list.get(list.size() - 1).equals(toPos)) return list;
        for(Position move: findMoves(fromPos)) {
            if (! list.contains(move)) {
                List<Position> nextList = new ArrayList<Position>(list);
                nextList.add(move);
                List<Position> resultList = loop(move, toPos, nextList);
                if (resultList != null) {
                    return resultList;
                }
            }
        }
        return null;
    }

    private static List<Position> findSolution(Position fromPos, Position toPos) {
        List<Position> list = new ArrayList<Position>();
        list.add(fromPos);
        return loop(fromPos, toPos, list);
    }

    public static void main(String... args) {
        Set<Item> fullSet = EnumSet.allOf(Item.class);
        Set<Item> emptySet = EnumSet.noneOf(Item.class);
        for(Position pos : findSolution(new Position(fullSet, emptySet),
                                        new Position(emptySet, fullSet))) {
            System.out.println(pos);
        }
    }
}

Wie man sieht, habe ich all die güldenen Java-Regeln über Bord geworfen, damit die Implementierung der Scala-Variante möglichst ähnlich sieht. Wie zu erwarten war, ist aus der dreizeiligen Position-Klasse ein kleines Monster geworden – wobei ich gnädigerweise auf Getter-Methoden verzichtet habe. In findMoves und loop kann man die Eleganz der veränderlichen Java-Collections in all ihrer iterativen Pracht bewundern. Ärgerlich war, dass sich fromSet und toSet nicht einfach mit EnumSet.copyOf kopieren ließen, denn diese Methode macht uns den sterbenden Schwan, falls das zu kopierende Set zufällig einmal leer ist. Ansonsten ist alles beim Alten geblieben, und auch mit Java kommen Kohlkopf, Ziege, Wolf und Bauer schließlich am anderen Ufer an, auch wenn es ein paar Zeilen mehr gekostet hat.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s