Wolf Kohlkopf Ziege

[Landei]

Ihr kennt bestimmt das genannte Puzzle. Nun lässt sich sowas am besten in "logischen" Sprachen (wie Prolog) und am schlechtesten mit imperativen oder OO-Sprachen implementieren. Wie würdet ihr die Sache angehen?

Meine Version im eSCALAtion Blog sollte der Scala-Variante möglichst ähnlich sein, und läuft damit allen Java-Programmier-Regeln zuwider und außerdem außer Konkurrenz.

Das beste Programm gewinnt eine Luftgitarre!!!

 

[0x7F800000]

Wie würdet ihr die Sache angehen?

Prolog interpreter schreiben :autsch:

Das beste Programm gewinnt eine Luftgitarre!!!

willst du eine Java-Lösung oder wie ist das jetzt gemeint?

 

[bygones]

Ihr kennt bestimmt das genannte Puzzle.

noch nie gehoert.

Meine Version im eSCALAtion Blog sollte der Scala-Variante möglichst ähnlich sein, und läuft damit allen Java-Programmier-Regeln zuwider und außerdem außer Konkurrenz.

kommen zuwenig leute auf den Blog als dass du hier verlinkung betreiben musst ?

sinn des Posts ?

*such*

 

[Landei]

Prolog interpreter schreiben :autsch:

willst du eine Java-Lösung oder wie ist das jetzt gemeint?

Ja. Aber wenn du einen Prolog-Interpreter in Java schreibst, ist das auch OK.

kommen zuwenig leute auf den Blog als dass du hier verlinkung betreiben musst ?

Psssst!

sinn des Posts ?

Vergleichende Studien. Ich tue mich bei solchen Logik-Problemchen immer schwer in Java, und will einfach sehen, ob andere besser damit zurechtkommen. Oder darf ich solche Fragen nur in der Plauderecke stellen?

 

[tfa]

Wen dieses Puzzle unterfordert, kann sich ja mal an dem Vater-Mutter-Tochter-Tochter-Sohn-Sohn-Polizist-Sträfling-Problem versuchen:

http://freeweb.siol.net/danej/riverIQGame.swf

Acht Leute wollen über den Fluss: die Mutter mit zwei Töchtern, der Vater mit zwei Söhnen und der Polizist mit einer Gefangenen.

Allerdings gibt es bestimmte Regeln:

1. Auf das Floß dürfen maximal zwei Personen.
2. Der Papa darf nicht mit einer Tochter ohne Anwesenheit der Mutter sein.
3. Die Mama darf nicht mit einem Sohn ohne Anwesenheit des Papas sein.
4. Die Gefangene darf mit keinem Familienmitglied alleine sein.
5. Nur der Polizist und die Eltern können das Floß bedienen.

 

[bygones]

Vergleichende Studien. Ich tue mich bei solchen Logik-Problemchen immer schwer in Java, und will einfach sehen, ob andere besser damit zurechtkommen. Oder darf ich solche Fragen nur in der Plauderecke stellen?

mhm jedenfalls fuer mich war in keiner weise ersichtlich dass es sich hierbei um eine sinnige bzw um eine Frage ueberhaupt handele... bygones ;-)

 

[peetpan]

Implementierung gibt es nicht, aber einen modellierungsansatz:

modelliere das problem als grafenproblem. knoten sind systemzustaende - wer befindet sich auf welcher seite des flusses. sollte reichen eine seite anzugeben, die andere ist implizit. kanten entsprechen ueberfahrten. analysen koennen durch grafalgorithmen gemacht werden. hier sind wohl auch zwei ansaetze moeglich:

a) modelliere nur regelkonforme kanten (ueberfahrten)
b) erlaube bei den grafalgorithmen nur das ablaufen regelkonformer kanten.

Fragestellungen:
- gibt es eine loesung? -> ist vom Knoten {} der Knoten {Bauer,Wolf,Ziege,Kohl} erreichbar.
- gib eine loesung aus. -> gib einen pfad zwischen {} und {Bauer,Wolf,Ziege,Kohl} aus, falls existent.

grafen lassen sich oo orientiert und imperativ ja gut implementieren. da hier nur erreichbarkeit betrachtet wird waehre auch ein symbolischer bdd ansatz denkbar.

lg, peet

 

[0x7F800000]

Ooch mist, bei mir ist eben der Wolf mit dem Kohl selbstständig ans andere Ufer gepaddelt, obwohl ich das explizit verboten hab ???:L

ich verschieb's mal auf später^^

 

[Landei]

Ooch mist, bei mir ist eben der Wolf mit dem Kohl selbstständig ans andere Ufer gepaddelt, obwohl ich das explizit verboten hab ???:L

ich verschieb's mal auf später^^

Sehr verwunderlich, insbesondere dass der Wolf den Kohl nicht aufgefressen hat. An unserem Helmut ist ja deutlich mehr dran als an so einem mageren Zicklein...

 

[Marco13]

Ich befürchte, einige hier im Forum wissen nicht, von wem du gerade redest ("... yet I'm old enough to have this conversation with you")


EDIT: Ahh, hab' gesucht, aber dann hat brute force die schnellste Lösung gebracht: Wollte noch darauf verlinken xkcd - A Webcomic - Designated Drivers

 

[diggaa1984]

wir ham das ganze mal mit petrinetzen modelliert, da kann man dann sofern ma eine lösung hat auch ewig an optimierungen sitzen

war aber spassig

 

[marasek]

Wenn ich es in Basic oder JavaScript noch kürzer frickle, sind diese Sprachen dann besser als Scala?

Meiner Ansicht ist es unsinnig, Sprachen an Hand von Trivialproblemen zu vergleichen. Das ist in etwa so sinnig wie die verschiedenen Formulierungsstärken von natürlichen Sprachen. Ich kann im Englischen nicht Den Mann biss der Hund sagen und im Deutschen nicht so schön frei neue Wörter bauen wie im Englischen.

 

[0x7F800000]

Wenn ich es in Basic oder JavaScript noch kürzer frickle

...dann wird das auf Dauer unübersichtlich und schwer wartbar.
Und dieses konkrete Problem kriegst du auch weder in Basic noch in JavaScript kürzer hin.

 

[Landei]

Wenn ich es in Basic oder JavaScript noch kürzer frickle, sind diese Sprachen dann besser als Scala?

Meiner Ansicht ist es unsinnig, Sprachen an Hand von Trivialproblemen zu vergleichen. Das ist in etwa so sinnig wie die verschiedenen Formulierungsstärken von natürlichen Sprachen. Ich kann im Englischen nicht Den Mann biss der Hund sagen und im Deutschen nicht so schön frei neue Wörter bauen wie im Englischen.

Scala ist fast immer kürzer als Java, das brauche ich nicht zu "beweisen". Außerdem war - wie erwähnt - meine Java-Lösung eben kein idiomatisches Java, sondern eine möglichst getreue Rückübersetzung der Scala-Version. Sinn der Übung war, Unterschiede zwischen den Sprachen an zwei "vergleichbaren" Versionen deutlich zu machen. Z.B. konnte man gut erkennen, wie case classes bzw. case objects in Scala die Aufgabe von enums übernehmen. Interessant war auch der Vergleich der veränderlichen Java Collections gegenüber den unveränderlichen Scala-Pendants.

Sprachen anhand von Trivialproblemen zu vergleichen halte ich für eine durchaus sinnvolle Strategie (allerdings nur für einen erste Annäherung). Seiten wie Listerate Programs oder sogar 99 Bottles können schon einen gewissen Eindruck von der Sprache vermitteln, man bekommt ein ungefähres Gefühl dafür, mit was für einer Sprache man es zu tun hat...

 

[marasek]

Scala ist fast immer kürzer als Java, das brauche ich nicht zu "beweisen". Außerdem war - wie erwähnt - meine Java-Lösung eben kein idiomatisches Java, sondern eine möglichst getreue Rückübersetzung der Scala-Version. Sinn der Übung war, Unterschiede zwischen den Sprachen an zwei "vergleichbaren" Versionen deutlich zu machen. Z.B. konnte man gut erkennen, wie case classes bzw. case objects in Scala die Aufgabe von enums übernehmen. Interessant war auch der Vergleich der veränderlichen Java Collections gegenüber den unveränderlichen Scala-Pendants.

Sprachen anhand von Trivialproblemen zu vergleichen halte ich für eine durchaus sinnvolle Strategie (allerdings nur für einen erste Annäherung). Seiten wie Listerate Programs oder sogar 99 Bottles können schon einen gewissen Eindruck von der Sprache vermitteln, man bekommt ein ungefähres Gefühl dafür, mit was für einer Sprache man es zu tun hat...

Ich halte diese Vergleiche nach wie vor nicht für sonderlich aussagekräftig.
Nehmen wir mal ein Beispiel: Ich habe eine CSV-Datei. Deren Inhalt soll als HTML-Tabelle ausgegeben werden. In der ersten Spalte sind Klassen/Funktionsnamen nach Underscore-Konvention, die für die Ausgabe in CamelCase umgewandelt werden sollen.
Das sieht mit PHP richtig kuschlig aus, mit Java dürfte das ein längeres Grauen werden.

Aber was besagt das? Einige der häufigeren PHP-Stringfunktionen baut man sich halt kurz nach, damit ist die Sache gegessen. Aber dass in einem grösseren Projekt meine IDE zuverlässig weiss, was someMethod() zurückliefert, ist ein nicht zu unterschätzender Vorteil.

Für mich lautet die Frage eher: in welcher Sprache würde ich ein bestimmtes Projekt lieber realisieren? Und noch gruseliger: was bekäme ich als Fremdcode lieber vorgesetzt?

 

[0x7F800000]

Aber was besagt das? Einige der häufigeren PHP-Stringfunktionen baut man sich halt kurz nach, damit ist die Sache gegessen. Aber dass in einem grösseren Projekt meine IDE zuverlässig weiss, was someMethod() zurückliefert, ist ein nicht zu unterschätzender Vorteil.

Für mich lautet die Frage eher: in welcher Sprache würde ich ein bestimmtes Projekt lieber realisieren? Und noch gruseliger: was bekäme ich als Fremdcode lieber vorgesetzt?

Scala ist statisch typisiert, und wurde so entworfen, dass sich damit beliebig große Projekte möglichst einfach und übersichtlich umsetzen lassen... Deswegen heißt die Sprache ja so.

Dass PHP vergleichsweise hässlich und nervtötend ist, hast du auch anderswo schon erwähnt, und das war uns davor auch schon kein Geheimnis. Was ist also der Punkt?

 

[marasek]

Scala ist statisch typisiert, und wurde so entworfen, dass sich damit beliebig große Projekte möglichst einfach und übersichtlich umsetzen lassen... Deswegen heißt die Sprache ja so.

Dass PHP vergleichsweise hässlich und nervtötend ist, hast du auch anderswo schon erwähnt, und das war uns davor auch schon kein Geheimnis. Was ist also der Punkt?

Der Punkt ist, dass ich im Vergleich zweier Sprachen eigentlich das Beispiel beliebig wählen kann, um die andere Sprache schlecht dastehen zu lassen. Mithin sind Sprachvergleiche an Hand von Trivialbeispielen mit Vorsicht zu genießen, ähnlich wie Benchmarks.

Bei dem erwähnten Beispiel würde PHP für den unbedarften Beobachter besser dastehen.

 

[Landei]

Bei dem erwähnten Beispiel würde PHP für den unbedarften Beobachter besser dastehen.

Weil es vielleicht in diesem Punkt auch "besser" wäre?

Scala sieht bei XML besser aus, weil XML-Literale schon eingebaut sind. Java sieht bei enums besser aus, weil Scala selbige nicht als Sprachfeature, sondern nur als Bibliotheksklasse realisiert (weil sie wegen case classes hier auch nicht so wichtig sind) u.s.w.

Vergleichen heißt nun mal, einzelne Plus- und Minuspunkte gegeneineinader abzuwägen. Wer das einseitig macht, ist selber schuld. In meinem Blog ging es vor allem um Sprachfeatures, die verglichen werden sollten, nicht so sehr um die Fähigkeit, dieses spezielle Problem zu lösen. Das wollte ich u.a. mit diesem Thread nachholen. Eine idiomatische Java-Version würde nämlich einen Vergleich auf Problemebene (und nicht auf "Feature-Ebene", wie ich es getan habe) erlauben. Aber statt cleverer Implementierungen, an denen man was lernen kann, haben wir jetzt eine dieser herrlichen Metadiskussion darüber, was ich eigentlich will, ob es in Ordnung ist, das überhaupt zu wollen, wie man Sprachen am besten vergleicht und so weiter ad nauseam. Kann man keinen Thread dieser Art aufmachen, ohne gleich einen Religionskrieg vom Zaun zu brechen?

 

[0x7F800000]

Aber statt cleverer Implementierungen, an denen man was lernen kann, haben wir jetzt eine dieser herrlichen Metadiskussion darüber, was ich eigentlich will, ob es in Ordnung ist, das überhaupt zu wollen, wie man Sprachen am besten vergleicht und so weiter ad nauseam. Kann man keinen Thread dieser Art aufmachen, ohne gleich einen Religionskrieg vom Zaun zu brechen?

Okay okay^^

import java.util.*;
import static java.util.Arrays.*;
import static java.lang.System.*;

public class PolicemanPrisonerFamily {
	private static enum Item{
		Boat(false),
		Policeman(true),Mom(true),Dad(true),
		Son1(false),Son2(false),Dgh1(false),Dgh2(false),
		Prisoner(false);
		final boolean canPaddle;
		private Item(boolean b){ canPaddle=b; }
	}
	private static boolean isSafe(Collection<Item> c){
		if(c.contains(Item.Mom) && !c.contains(Item.Dad) 
			&& (c.contains(Item.Son1) || c.contains(Item.Son2))) return false;
		if(c.contains(Item.Dad) && !c.contains(Item.Mom) 
			&& (c.contains(Item.Dgh1) || c.contains(Item.Dgh2))) return false;
		if(c.size()>=2 && c.contains(Item.Prisoner) 
			&& !c.contains(Item.Policeman)) return false;
		return true;
	}
	private static boolean canPaddle(Collection<Item> c){
		for(Item i:c) if(i.canPaddle) return true;
		return false;
	}
	private static Collection<Collection<Item>> getPossibleTransfers(Collection<Item> from){
		Collection<Collection<Item>> result=new LinkedList<Collection<Item>>();
		if(from.contains(Item.Boat)){
			for(Item i:from){
				for(Item j:from){
					Collection<Item> transfer=new HashSet<Item>(asList(i,j,Item.Boat));
					if(transfer.size()<=3 && isSafe(transfer) && canPaddle(transfer)){
						result.add(transfer);
					}
				}
			}
		}
		return result;
	}
	
	@SuppressWarnings("unchecked")
	private static Collection<Item>[] makeTransfer(
			Collection<Item> from, 
			Collection<Item> to, 
			Collection<Item> transfer){
		Collection<Item> f=new HashSet<Item>(from);
		f.removeAll(transfer);
		Collection<Item> t=new HashSet<Item>(to);
		t.addAll(transfer);
		return (Collection<Item>[]) new Collection[]{f,t};
	}
	
	private static class State{
		Collection<Item> left, right;
		State(Collection<Item> l,Collection<Item> r){ 
			left=new HashSet<Item>(l); 
			right=new HashSet<Item>(r);
		}
		@Override public String toString(){ return left+"|"+right;}
		@Override public int hashCode(){ return left.hashCode()+right.hashCode(); }
		@Override public boolean equals(Object o){
			if(o instanceof State){
				State other=(State)o;
				return left.equals(other.left) && right.equals(other.right);
			}
			return false;
		}
		
		Collection<State> successors(){
			Collection<State> result=new HashSet<State>();
			for(Collection<Item> transfer:getPossibleTransfers(left)){
				Collection<Item>[] temp = makeTransfer(left,right,transfer);
				if(isSafe(temp[0]) && isSafe(temp[1])) result.add(new State(temp[0],temp[1]));
			}
			for(Collection<Item> transfer:getPossibleTransfers(right)){
				Collection<Item>[] temp = makeTransfer(right,left,transfer);
				if(isSafe(temp[0]) && isSafe(temp[1])) result.add(new State(temp[1],temp[0]));
			}
			return result;
		}
	}
	
	private static List<State> dfs(State start, State searched){
		return dfsRec(start,searched,new HashSet<State>());
	}
	
	private static LinkedList<State> dfsRec(State current, State searched, Set<State> visited){
		visited.add(current);
		if(current.equals(searched)){
			return new LinkedList<State>(asList(current));
		}else{
			for(State succ:current.successors()){
				if(!visited.contains(succ)){
					LinkedList<State> path=dfsRec(succ,searched,visited);
					if(path!=null){
						path.addFirst(current);
						return path;
					}
				}
			}
			return null;
		}
	}
	
	public static void main(String... _){
		for(Object o:dfs(
				new State(asList(Item.values()),new HashSet<Item>()),
				new State(new HashSet<Item>(),asList(Item.values())))) 
		out.println(o);
	}
}

spuckt folgende (wohl korrekte) aber furchtbar lange Lösung raus:

[Mom, Dgh1, Son2, Son1, Boat, Dgh2, Policeman, Dad, Prisoner]|[]
[Mom, Dgh1, Son2, Son1, Dgh2, Dad]|[Boat, Policeman, Prisoner]
[Mom, Dgh1, Son2, Son1, Boat, Dgh2, Policeman, Dad]|[Prisoner]
[Mom, Dgh1, Son2, Son1, Dad]|[Boat, Dgh2, Policeman, Prisoner]
[Mom, Dgh1, Son2, Son1, Boat, Policeman, Dad, Prisoner]|[Dgh2]
[Son2, Son1, Policeman, Dad, Prisoner]|[Mom, Dgh1, Boat, Dgh2]
[Mom, Son2, Son1, Boat, Policeman, Dad, Prisoner]|[Dgh1, Dgh2]
[Son2, Son1, Policeman, Prisoner]|[Mom, Dgh1, Boat, Dgh2, Dad]
[Son2, Son1, Boat, Policeman, Dad, Prisoner]|[Mom, Dgh1, Dgh2]
[Son2, Son1, Dad]|[Mom, Dgh1, Boat, Dgh2, Policeman, Prisoner]
[Mom, Son2, Son1, Boat, Dad]|[Dgh1, Dgh2, Policeman, Prisoner]
[Son2, Son1]|[Mom, Dgh1, Boat, Dgh2, Policeman, Dad, Prisoner]
[Son2, Son1, Boat, Dad]|[Mom, Dgh1, Dgh2, Policeman, Prisoner]
[Son2]|[Mom, Dgh1, Son1, Boat, Dgh2, Policeman, Dad, Prisoner]
[Son2, Boat, Policeman, Prisoner]|[Mom, Dgh1, Son1, Dgh2, Dad]
[Prisoner]|[Mom, Dgh1, Son2, Son1, Boat, Dgh2, Policeman, Dad]
[Boat, Policeman, Prisoner]|[Mom, Dgh1, Son2, Son1, Dgh2, Dad]
[]|[Mom, Dgh1, Son2, Son1, Boat, Dgh2, Policeman, Dad, Prisoner]

Hab jetzt sogar 4 zeilen mehr gebraucht, anscheinend ohne viel an flexibilität zu gewinnen... Naja, es funzt jedenfalls^^ :autsch:

edit: hab jetzt paar zeilenumbrüche mehr eingebaut, dadurch werden's noch mehr Zeilen^^

Störend:

• immutable Kollektionen fehlen sehr
• Sets lassen sich nicht kurz instantiieren und füllen
• ohne closures ist es schlimm: code redundanz etwa um z. 64

 

[tfa]

spuckt folgende (wohl korrekte) aber furchtbar lange Lösung raus:

[Dad, Dgh2, Dgh1, Son2, Boat, Policeman, Prisoner, Mom, Son1]|[]
[Dad, Dgh2, Dgh1, Son2, Prisoner, Mom]|[Boat, Policeman, Son1]

Die zweite Zeile ist schon falsch. Regel 4 wird verletzt. Der Gefangene ist ohne Aufsicht bei Familienmitgliedern.

 

[0x7F800000]

Die zweite Zeile ist schon falsch. Regel 4 wird verletzt. Der Gefangene ist ohne Aufsicht bei Familienmitgliedern.

Die Gefangene darf mit keinem Familienmitglied alleine sein.

So wie ich das interpretiert bedeutet "mit jemandem alleine zu sein" dass da nur zwei personen sind, von den eine der Sträfling ist. D.h. es wird davon ausgegangen, dass der Sträfling unmöglich 2 leuten gleichzeitig entkommen kann, selbst wenn es unbewaffnete familienmitglieder sind.

 

[tfa]

So wie ich das interpretiert bedeutet "mit jemandem alleine zu sein" dass da nur zwei personen sind, von den eine der Sträfling ist. D.h. es wird davon ausgegangen, dass der Sträfling unmöglich 2 leuten gleichzeitig entkommen kann, selbst wenn es unbewaffnete familienmitglieder sind.

War vielleicht nicht eindeutig ausgedrückt. Aber ein Verbrecher, der von zwei kleinen Mädchen in Schach gehalten wird...? Also ich weiß nicht...

Hast du denn das Flash-Spielchen mal mitgemacht?

 

[0x7F800000]

War vielleicht nicht eindeutig ausgedrückt. Aber ein Verbrecher, der von zwei kleinen Mädchen in Schach gehalten wird...? Also ich weiß nicht...

Zum einen steht da nicht, dass die Töchter klein sind, zum anderen steht da nicht, dass sie keine Antiterror-Ausbildung absolviert haben. Ansonsten ist das Problem doch sofort nicht lösbar, weil keiner der 3 "Ruderer" sich von der stelle bewegen darf. Also kann es nur so gemeint sein, wie ich es verstanden habe, imho... ???:L

Hast du denn das Flash-Spielchen mal mitgemacht?

Was'n Flash-spielchen? :bahnhof:

 

[tfa]

Zum einen steht da nicht, dass die Töchter klein sind, zum anderen steht da nicht, dass sie keine Antiterror-Ausbildung absolviert haben. Ansonsten ist das Problem doch sofort nicht lösbar, weil keiner der 3 "Ruderer" sich von der stelle bewegen darf.

Klar. Vater und Mutter können losrudern. Oder Polizist und Gefangener. (Zur Sicherheit noch eine Info: Der Gefangene kann auch ganz allein an einem Ufer zurück bleiben, ohne Bewachung.)

Was'n Flash-spielchen? :bahnhof:

OK, extra nochmal für dich der Link:
http://freeweb.siol.net/danej/riverIQGame.swf

 

[0x7F800000]

Klar. Vater und Mutter können losrudern.

stimmt...

Zur Sicherheit noch eine Info: Der Gefangene kann auch ganz allein an einem Ufer zurück bleiben, ohne Bewachung.

lol, okay^^ Keine chance wegzurennen

OK, extra nochmal für dich der Link:
http://freeweb.siol.net/danej/riverIQGame.swf

sorry, du hast immer so viele links in der signatur, da wird einem ganz bunt vor Augen^^ Hab's übersehen...

edit: habe jetzt im ursprünglichen code [c]==[/c] gegen [c]>=[/c] abgeändert, die Lösung ist auch geschrumpft...

edit2: am spiel getestet: die lösung ist richtig^^ Was sollen diese merkwürdige bewegungen symbolisieren?

 

[Landei]

Jetzt wird's doch noch richtig konstruktiv. Werd' mir deine Lösung bei Gelegenheit mal reinziehen, sah beim Drüberblinzeln schonmal interessant aus.

 

[0x7F800000]

Jetzt wird's doch noch richtig konstruktiv.

Naja... sagen wir mal so: "vor einer halben Woche"

 

[faetzminator]

Hab mir die die aktuelle Lösung nicht genau angesehen, aber grundsätzlich darf kein Status mehr angenommen werden, welcher bereits ein Mal angenommen wurde.

 

[0x7F800000]

Hab mir die die aktuelle Lösung nicht genau angesehen, aber grundsätzlich darf kein Status mehr angenommen werden, welcher bereits ein Mal angenommen wurde.

was genau meinst du? ???:L
Das kann bei meiner Lösung eh nicht vorkommen, weil die Tiefensuche sich ansonsten in einer unendlichen Schleife drehen würde. Aber das heißt noch nicht, dass der kürzeste Weg gefunden wurde.