Kohlkopf, Ziege, Wolf und Scala


Der Titel sagt schon alles: Ich habe mich an diesem einfach zu lösenden, aber in imperativen Sprachen schlecht zu formulierenden Puzzle versucht. Auch wenn sich Scala bei der Implementierung derartiger Problemstellungen deklarativen (oder „logischen“) Programmiersprachen wie Prolog geschlagen geben muss, macht es gegenüber Java trotzdem eine gute Figur. Java schwächelt nämlich, wenn es darum geht, Problembereiche mit Bedingungen zu beschreiben und zu durchsuchen.

Ich habe die Erfahrung gemacht, dass sich derartige Logik-Puzzle gut „Bottom-Up“ schreiben lassen. Fangen wir also ganz unten bei den Datentypen an:

abstract class Item
case object Farmer extends Item
case object Cabbage  extends Item
case object Goat  extends Item
case object Wolf  extends Item

case class Position(left:Set[Item], right:Set[Item]) {
    override def toString() = left.mkString(",") + " ~~~ " + right.mkString(",")
}

Dieser Teil ist wohl ziemlich selbsterklärend. Position gibt an, welche Gegenstände sich links und rechts des Flusses befinden, und sorgt auch für eine ordentliche Ausgabe.

object cabbageGoatWolf {

    def valid(set:Set[Item]) =
       set.contains(Farmer) ||
       !set.contains(Goat) ||
       !(set.contains(Cabbage) || set.contains(Wolf))

    def findMoves(pos:Position):Set[Position] = if (pos.left.contains(Farmer)) 
        pos.left.map(item => Position(pos.left - Farmer - item,
                     pos.right + Farmer + item)).filter(p => valid(p.left))
     else 
        pos.right.map(item => Position(pos.left + Farmer + item,
                      pos.right - Farmer - item)).filter(p => valid(p.right))

    def findSolution(from:Position, to:Position):List[Position] = {
        def loop(from:Position, to:Position, positions:List[Position]):Option[List[Position]] = {
           val moves = findMoves(from).filter(! positions.contains(_))
           if (moves.contains(to)) Some((to :: positions).reverse)
           else moves.map(m => loop(m, to, m :: positions)).find(_ != None).getOrElse(None)
        }
        loop(from,to,List(from)).getOrElse(error("no solution"))
    }

    def main(args:Array[String]) {
        val fullSet:Set[Item] = Set(Farmer, Cabbage, Goat, Wolf)
        findSolution(Position(fullSet, Set()),
                     Position(Set(), fullSet)).foreach(println)
    }
}

/* Ausgabe:
Farmer,Cabbage,Goat,Wolf ~~~ 
Cabbage,Wolf ~~~ Farmer,Goat
Cabbage,Wolf,Farmer ~~~ Goat
Wolf ~~~ Goat,Farmer,Cabbage
Wolf,Farmer,Goat ~~~ Cabbage
Goat ~~~ Cabbage,Farmer,Wolf
Goat,Farmer ~~~ Cabbage,Wolf
 ~~~ Farmer,Cabbage,Goat,Wolf
*/

Die Methode valid testet, ob ein bestimmtes Set „unbedenklich“ ist: Entweder der Farmer ist dabei, oder keine Ziege (die fressen oder gefressen werden könnte), oder falls doch, dann weder Wolf noch Kohlkopf.

In findMoves werden alle möglichen Züge von einer gegebenen Position ermittelt. Leider ist hier alles doppelt gemoppelt, je nachdem, ob sich der Farmer links oder rechts des Flusses befindet. Interessanterweise wird durch die Verwendung von Sets eine Unterscheidung zwischen Fahrten mit Fracht und Leerfahrten überflüssig, den Set + Farmer + Farmer ist ja das Gleiche wie Set + Farmer.

Mit der Methode findSolution bin ich nicht besonders zufrieden, sie ist etwas konfus (hauptsächlich durch das Hin und Her mit Options) und nicht endrekursiv, dafür aber recht kompakt. Eine kleine Feinheit ist, dass man beim Ergebnis von findMoves noch die Positionen herausfiltern muss, die man schon einmal hatte, weil man sich sonst (bis zum Stacküberlauf) im Kreis dreht.

Alles in allem nicht übel. Übrigens sind unveränderliche Datentypen für derartige Puzzle sehr vorteilhaft – selbst in Java kann es sich lohnen, darauf zurückzugreifen (wie ich schon hier erwähnt habe). Ich werde versuchen, spaßeshalber auch eine Java-Lösung nachzuliefern.

So, ich setze jetzt erst einmal Kohlsuppe auf, melke die Ziege und gehe Gassi mit dem Wolf…

Advertisements

Ein Gedanke zu “Kohlkopf, Ziege, Wolf und Scala

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