Rätselthread

[Terep]

Ein Rätsel mit Geschichte:

Mein Hotelaufenthalt für das 3tägige Seminar verspricht wirklich gut zu werden. Meine Sitznachbarin ist super und lacht selbst über meine Blondinenwitze, obwohl sie blond ist.
Dann schaute sie mir tief in die Augen und sagte, sie würde gerne mit mir essen gehen und gab mir einen Briefumschlag, in dem Ihre Zimmernummer sei. Bis 8 Uhr würde sie auf mich warten, nicht länger.

Tja, frisch geduscht machte ich den Umschlag auf. Darin war eine kurze Notiz:
Obwohl ich blond bin, mag ich keine dummen Männer. Finde meine Zimmernummer aus den 60 vorhandenen Zimmern heraus und komme zu mir. Du hast 6 Karten, davon sind einige angekreuzt. Die Zimmernummer steht auf den angekreuzten Karten. Wenn Du schlau genug bist, weist Du wohin.

Das X vor dem Wort Karte bedeutet angekreuzt.

X Karte 1
8 9 10 11 12 13 14 15
24 25 26 27 28 29 30 31
40 41 42 43 44 45 46 47
56 57 58 59 60

X Karte 2
1 3 5 7 9 11 13 15
17 19 21 23 25 27 29 31
33 35 37 39 41 43 45 47
49 51 53 55 57 59

X Karte 3
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
48 49 50 51 52 53 54 55
56 57 58 59 60

Karte 4
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60

Karte 5
2 3 6 7 10 11 14 15
18 19 22 23 26 27 30 31
34 35 38 39 42 43 46 47
50 51 54 55 58 59

Karte 6
4 5 6 7 12 13 14 15
20 21 22 23 28 29 30 31
36 37 38 39 44 45 46 47
52 53 54 55 60



Soweit die Story, nun die Aufgaben
Welche Zimmernummer ist es?
Wieso funktioniert das ?
Ein Programm schreiben, dass immer die richtige Lösung ausgibt.

Solltest Du ohne eigene Lösung schnell einfach runter scrollen, machst Du Dir das Rätsel selbst kaputt.

Terep

[Alexander Kornrumpf]

LaTex Mod für das Forum?!

mit Ki = {x | x steht auf Karte i}

^ = geschnitten
v = vereinigt
\ = ohne

Lösung:

(K1^K2^K3)\(K4 v K5 v K6)

[eXile]

Der Satz "Die Zimmernummer steht auf den angekreuzten Karten." bedeutet lange noch nicht "Die Zimmernummer steht nicht auf den nicht angekreuzten Karten.".

[Alexander Kornrumpf]

Ist richtig, ich nehme aber an dass es so gemeint war. Die Sprache ist eben hier nicht präzise.

[eXile]

Fixed that for you: "Die Zimmernummer steht genau auf den angekreuzten Karten."

Man kann schon, wenn man nur will ;) Natürlich stimme ich deiner Lösung zu :)

[Aramis]

Von eXile's Einwand abgesehen, eine Loesung in Python 3 (theoretisch ein Einzeiler). Unnoetig zu erwaehnen dass Alex Kornrumpf' Loesung die kompakteste ist :-)

Code: Alles auswählen

n = next(iter(num for num in set(itertools.chain(*cards)) \
	if not len([c for c in cards if checked[c] and \
		not num in c or not checked[c] and num in c]) 
))

[Jonathan]

Ich kenne das Rätsel, aber es ist gut.

Hier mal ein paar Gedanken dazu:

Die erste Zahl jeder angekreuzten Karten addieren, die Summer ergibt die Zimmernummer.

Ist ein prima Trick, wenn man jemanden die 6 Karten zeigt und jedes mal fragt, ob seine gedachte Zahl auf einer von ihnen ist, und man am Ende direkt sagen kann, wie die Zahl war.

Generieren kann man die Karten einfach, indem man sich die Binärdarstellung der Zahlen anguckt. (die erste Zahl ist ne zweierpotenz, den Rest könnt ihr euch denken)

So kann man das noch wesentlich schneller lösen^^

[Aramis]

Interessanter Ansatz, das muss ich zugeben. Leider gibt es da schon wieder eine Ungenauigkeit in der Aufgabenstellung: "ein Programm schreiben, dass immer die richtige Loesung ausgibt". Was 'immer'? Da steht nirgendwo dass die Karten immer gleich bleiben und sich das 'immer' auf verschiedene Kreuzchen bezieht. So wie die Aufgabe dasteht ist die Brute-Force Variante die einzige Loesung die (abgesehen von eXile's Korrektur) keine Zusatzannahmen trifft.

[Alexander Kornrumpf]

Um das herauszufinden muss man es ja auch mindestens einmal überprüfen.

[Terep]

Interessanter Ansatz, das muss ich zugeben. Leider gibt es da schon wieder eine Ungenauigkeit in der Aufgabenstellung:

Das ist der Unterschied zwischen Aufgabe und Rätsel. Ungenauigkeiten. Da mir klar war, dass es für einen Informatiker
bei klarer Aufgabenstellung schnell erkennbar ist, wollte ich es mit der Story etwas tarnen.

Wie Jonathan richtig sagt, kommt die Lösung mittels Binärzahlen zustande. Hat man den Algorithmus verstanden, kann es auch programmiert werden. Zielgruppe sind eigentlich die Leute, die noch auf der Konsole programmieren. Manche sagen auch newbies.

Terep

[Chromanoid]

du siehst wie gierig auch nicht-newbies dieses rätsel aufgenommen haben :) also gerne mehr davon ^^

[eXile]

Nur eine kleine Sache hätte ich noch: Es ist auch unklar, ob nur diese eine Probleminstanz (d.h. die gegebene Kartenbelegung) gegeben ist, oder eine ganz allgemeine (welche lediglich der Bedingung genüge, dass eine eindeutige Lösung herauskommen soll).

Bei ersterem kann man einfach ein Programm schreiben, dass 42 (oder was auch immer die richtige Antwort ist) ausgibt, und schon ist das "Problem gelöst". Das geht bei letzerem von beiden nicht, hier muss man mind. n-1 Zimmer betrachten, um das "Problem zu lösen".

PS:

Zielgruppe sind eigentlich die Leute, die noch auf der Konsole programmieren. Manche sagen auch newbies.

Wohohow. Haltet die Pferde zurück! Ich wage zu Sagen, dass die komplexesten Programme der Welt nur auf der Konsole laufen, z.B. der Linux Kernel, die Basissoftware vom CERN (auch wenn die mittlerweile lustige GUIs haben), der Crawler von Google, Statistikprogramme unter COBOL die die Preise für deine Versicherungen ausrechnen, usw.

Aber bitte mehr Rätsel! ;)

[Chromanoid]

btw. irgendwie passt das nicht hier her :) rätsel sind keine ressourcen. also leute denkt euch für dieses rätsel auch mal eine lösung aus. spontan würde ich sagen: "algorithmen und datenstrukturen" (rätsel lässt sich durch logik/algorithmus lösen) oder "Allgemeines Talkbrett". Wenn ein Kollege das thema verschiebt, kann er es ja mit wichtig markieren.

[Alexander Kornrumpf]

Done

[Terep]

Es gibt mehr Lösungsansätze als ich dachte.

Jonathan hat in seiner Antwort die Aufgabe richtig beschrieben.

Die Rätselvariation entstand in der Aufarbeitung zu diesem Thema.
Ich war von diesen 6 Karten faziniert und habe bemerkt, dass es für das Verständnis gut ist, wenn man es ausführlich aufschreibt.
Das heißt, alle 60 Möglichkeiten vor sich liegen zu haben. Die 6 Spalten entsprechen den 6 Karten.
Da es ziemlich umfangreich ist, habe ich es in dem Posting "Binärsystem oder auch Dualsystem" dargestellt.

Dank Jonathan muss ich die Lösung als solche nicht mehr formulieren.

Ich war beeindruckt von der Qualität der Lösungsansätze und der Schnelligkeit der Antworten.

Terep