Hallo,

ich wollte auch einen "solver" bauen.
Rekursion ist ja klar.
Man hat ja hier sehr wenig Bewegungsmöglichkeiten, man muss "nur" davor sorgen, das eine zuvor erreichte Stellung, nicht nochmals erreicht wird.

Gruß Horst
Edit: dann eben nicht

Wir sollten Lösungshinweise und -überlegungen zurückhalten, bis das Rätsel abgelaufen ist.

Hallo,

sooo, schnell pinselt man ein solches Programm auch nicht zusammen. OK , das ist der Neid des Älterwerdenden, hoffentlich nur eine Erkältung im Anmarsch.....

Gruß Horst

Horst_H hat folgendes geschrieben :

sooo, schnell pinselt man ein solches Programm auch nicht zusammen.

Na ich habe es doch auch heute geschrieben Wenn ich im "Tunnel" bin, kann ich sehr produktiv sein.
Nur bei dem Projekt für die Uni...da gehts irgendwie nicht so recht vorwärts. Ein Problem ohne mathematisch saubere Definition ist echt fies schwer...wie soll man einem Algorithmus beibringen, ein schönes Bild mit einem Baum drauf zu malen? Naja, wäre doch gelacht wenn ich das nicht noch hinbekomme

//Edit: Heureka!

Hallo,
das heutige Rätsel ist wahrscheinlich doch ganz schön schwer. Bisher sind 8 Lösungen eingegangen.
Man muss aber kein Programm zur Lösung schreiben. Es geht auch, indem man einfach "klickt". Irgendwie spielen die Nummern 4 und 5 die entscheidende Rolle. Diese muss man viel verschieben, um den Platz für die größeren Steine zu schaffen.
Ich weiß schon: Dieser Hinweis hilft nicht viel.

Die Aufgabe vom 16.12. ist eine mathematisch-geometrische.
Mit Ausdauer und Papier und Bleistift kann man die gesuchte Zahl durchaus ermitteln. Ich schätze: Das Rätsel ist mittelschwer.

Ach so: Bevor es zu Verwirrung kommt, sei darauf hingewiesen, dass die linke Abbildung die zu untersuchende ist. Rechts (die hier gezeigte Abbildung) ist nur der fertige Stern zu sehen.
Dieser Stern, das kleine Sterndodekaeder Keplers, ist mein Lieblingspolyeder. Und das ist ernst gemeint.

Beste Grüße
Mathematiker

Wenn jemand Lust hat, hier noch ein (hoffentlich) kniffligeres Rätsel zum Puzzle aus Türchen 15:

In diesem Posting wird ein alternatives Puzzle vorgestellt (Flemings-Puzzle) auf das sich diese Aufgabe hier bezieht:

Geschichte:
Sicherlich habt ihr euch gefragt, warum sich der Weihnachtsmann ein Puzzle (Adventskalender Türchen 15) für euch überlegt hat. Konkret ist er nämlich in einer missligen Lage:

Das Puzzle repräsentiert die Beladung seines Schlittens. Da er am Weihnachtsabend sehr viel zu tun hat, geschieht die Beladung automatisiert. Die Maschine gruppiert bereits die Geschenke nach Zielort und platziert sie in Paketen auf dem Wagen, so dass er nur seine Rentiere umspannen muss und keine Verzögerung fürs Beladen entsteht. Diese Maschine produziert immer Pakete, deren Größe analog zu denen aus Flemings Puzzle ist. Jedoch die Positionierung ist zufällig.

Dies hat die letzten Jahre gut funktioniert. Nun hat sich jedoch die Gesetzeslage verändert. Er muss nun zuerst den braven Kindern die Geschenke bringen. Deren Geschenke sind besonders groß und in Paket 1. Damit die Beladung des Wagens nicht instabil wird, sollten diese Geschenke hinten in der Mitte auf dem Wagen stehen.
Die Wichtel müssen jetzt Überstunden machen und das große Paket an die entsprechende Position befördern. Leider sind Wichtel nicht sehr stark und die Pakete sehr groß, so dass sie die Pakete nur schieben können.
Allerdings gibt es Situationen, in denen es garnicht möglich ist, das Paket entsprechend zu verschieben. Bis die Wichtel dies merken, ist die ganze Zeitplanung durcheinander.

Nun hat der Weihnachtsmann einen Solver programmiert, welche für jede Situationen bestimmen kann, ob sie lösbar ist oder nicht. Leider läuft dieser nur auf dem Mainframe, welcher über Weihnachten zu Wartungszwecken abgeschaltet ist. Die Wichtel können ihn also beim Beladen nicht nutzen. Ein mobiles Gerät wäre besser.

Der Weihnachtsmann hat jedoch noch ein Smartphone vom letzten Jahr übrig, das er ohnehin nicht mehr verschenken kann. Der Wichtel, der die Verschiebeungen durchführt, soll nun dieses Smartphone erhalten. Auf diesem ist für jede Situation gespeichert, ob man die Pakete so verschieben kann, dass Paket 1 an der richtigen Position ist, oder nicht.

Leider haben die Smartphones nur noch genau 128MiByte Speicherplatz übrig, da der Wichtel unbedingt Heavy Metal beim Arbeiten hören will. Wenn es möglich wäre, eine Situation auf 32bit eindeutig darzustellen, so würden 128MiByte gerade ausreichen, für jede Situation ein Bit bereitszustellen, welches angibt, ob die Situation lösbar ist oder nicht.

Aufgabe:
Kannst du dem Weihnachtsmann ein Verfahren erklären, wie für jede mögliche Situation (d.h. jede mögliche Positionierung der Pakete aus Flemings-Puzzle) eindeutig ein 32-bit-Wert bestimmt werden kann, für den dann gespeichert wird, ob die Situation so verschoben werden kann, dass Paket1 an der entsprechenden Position landet? Dann kann der Wichtel dieses Verfahren benutzen und zunächst prüfen, ob es überhaupt eine Lösung gibt.

Beispiel:
Eine einfache Repräsentation der Situation könnte durch Aufzählung der Nummern geschehen, z.B. (von links nach rechts, von oben nach unten):
'22887 1164X 1165X 33990'
Dies kann man natürlich nicht alles in 32bit unterbringen.
Hinweis: Es gibt durchaus mehrere verschiedene Situationen, deren Lösung identisch ist.

Anmerkungen:
Da es sehr schwer ist, eure Lösungen zu verifizieren, wird es wohl keine Auswertung geben. Aber ihr könnt euch ja mal ein paar Gedanken dazu machen Ich werde nach der Auflösung des Rätsels 15 meinen Solver-Code hochladen, der eine (hoffentlich) korrekte Abbildung implementiert.

Hallo,

Xion hat folgendes geschrieben :

Wenn jemand Lust hat, hier noch ein (hoffentlich) kniffligeres Rätsel zum Puzzle aus Türchen 15 ...

Ich verstehe zwar die Aufgabenstellung, hätte auch Lust mich zu versuchen, kann mir aber nicht vorstellen, wie man so etwas löst. Da muss man wohl Informatik studieren/studiert haben.
Ich bin auf mögliche Lösungen sehr gespannt.

Das Rätsel vom 17.12. wird wohl bei einigen Verwirrung auslösen. Es ist gar kein Rätsel, es ist eine reine Fleißaufgabe. Aber irgendwie musste ich diesen Programmteil unterbringen; er gefällt mir zu gut.
Es geht darum, einen "ökologisch vollabbaubaren Memory-Stick" der 1970er Jahre mit Daten zu versehen, d.h. es geht um das Stanzen von Löchern in eine Lochkarte.
Als Schüler habe ich mehrmals im Ferienjob solche Karten und auch Lochstreifen mit Löchern versehen. Anschließend gingen sie in einen Großrechner, der sie als fehlerhaft auswarf. Und danach musste Zeile für Zeile der eine Fehler in Unmengen von Lochkarten per Hand gesucht werden. Das hat Spaß gemacht.

Damit das "mühevolle" Klicken etwas einfacher wird, solltet Ihr in jeder Spalte zuerst die Löcher in den Zeilen 0 bis 9 setzen und danach erst die beiden obersten Zeilen mit dem notwendigen Loch versehen. Das Programm testet nämlich, ob eine Lochkombination überhaupt zum Zeichensatz gehört.

Viel Spaß und Ausdauer
Mathematiker

Hallo,

@Xion:
Ich gehe mal davon aus, dass die Wichtel am Touchpad die Positionen eingeben und das smartphone berechnet den 32-BitWert und dann wird das Bit bestimmt.
Momentan bin ich 33,0858 Bit wenn ich zeilenweise die Kombination speichere, denn es gibt für eine Zeile 309 Verschiedene Anordnungen, der 5 verschiedenen Elemente , Namen sind wie Schall und Rauch, die auf eine Spaltenzahl von 5 kommen.
Also zeilenweise nur die Kombinationsnummer speichern. ( 309 *5 Byte um die Kombination zu finden).
Wenn ich Achsensymmetrien nutzen könnte, wären 2 Bit eingespart.Also müßte ich dafür sorgen das eine "freie Stelle" immer links oben zu liegen kommt. das sind 6 ( 3x2) von 20( 5x4) Feldern, könnte passen ( 309^4 *6/20 = 2^31,3488 ).
Die ersten beiden Zeilen mit 2 möglichen freien Stellen haben jeweils 309 Möglichkeiten,{ Stimmt nicht ganz, denn in einer Zeile muss eine freie Stelle in Spalte 1..3 sein, aber die zu markieren braucht wieder Bits ) die folgenden beiden aber nur 201.
Das sind 309*309*201*201= 2^31,845029 gerade so passend.
Das muss noch weit besser gehen
Denn die Zeilen sind untereinander ja so sehr einander bedingend, das bestimmt nur ( geratene ) 100 Mio mögliche Kombinationen übrigblieben.

Gruß Horst

Horst_H hat folgendes geschrieben :

Ich gehe mal davon aus, dass die Wichtel am Touchpad die Positionen eingeben und das smartphone berechnet den 32-BitWert und dann wird das Bit bestimmt.

Genau so.

Horst_H hat folgendes geschrieben :

Das sind 309*309*201*201= 2^31,845029 gerade so passend.

Wenn ich das richtig verstanden habe ( bin etwas müde ) und ohne jetzt die einzelnen Möglichkeiten nachzuzählen: Du hast damit begründet, dass es insgesamt weniger als 2^32 Möglichkeiten gibt. Eigentlich ist aber ja eine "Abbildungsvorschrift" gesucht, welches der Puzzle-Stellung einem 32-bit-Wert zuordnet. Dabei funktioniert dein Ansatz aber soweit ich das sehe noch nicht:
In der ersten Reihe tritt z.B. "Kombinationsnummer " 25 auf. In Reihe 2 die Nummer 10. Gibt zusammen dann z.B. die 32-bit-Zahl 25*10*201*201. Nur ergibt auch 10*25*201*201 diese Zahl

Hallo,

Ich weiß, dass mein Verfahren recht umständlich ist.
Ich nummeriere nicht, der Name interessiert nicht. ob 8 oder 9 an einer Stelle liegt ist ja für das Ergebnis, ob es lösbar ist, unerheblich.
Also bekomme die 5 verschiedenen Elemente nur eine Nummer
0 := 2x2 Element, gibt es 1-fach ( 2 breit)
1 = 2 er Element waagerecht, gibt es 2-fach ( 2 breit)
2 = 2 er Element senkrecht, gibt es 2-fach ( 1 breit)
3 = 1 er Element, gibt es 2-fach ( 1 breit)
4 = 1 er Element/freies Feld, gibt es 2-fach( 1 breit)

Es gibt 309 Möglickeiten aus diesem 5 Elementen in dieser Vielfachheit eine Zeile zu bilden,die 5 Spalten hat.
ZB: 012 oder 013 oder 014 die 0 ist durch 1 ersetzbar und 2,3,4 untereinander.
oder 23344
Uups, das geht nicht, wenn manche Elemente sehr oft vorkommen,Dann steigt die Anzahl der Kombination zu schnell.

Natürlich kann man auch einfach von links oben beginnen und stur Zeile für Zeile durchlaufen, unter der Berücksichtigung welche durch Elemente von der Zeile darüber belegt sind.Am Ende sind es immer 11 Elemente
www.entwickler-ecke.....php?p=682271#682271

Würde ich nun so schreiben, ob 2,3,8,9 wäre bei mir immer 2er waagerecht.
Die Pfeile besagen nun das dies Feld zu dem davor gehört.

Zu schreiben als 113;0234;(0 und 2 ist von Zeile vorher bekannt,also nur die neuen) 34;113;
Wenn ich 5er System jetzt nach Hornerschema rechne:
(((...((1*5+1)*5+3)*5+0)*5+2)*5+3)*5+4)*5+3)*5+4)*5+1)*5+1)*5+3
Ergibt maximal 5^11-1 = 48'828'124
Knapp 50 Mio Möglichkeiten, das ist knackig kurz , aber es gibt noch weniger Anordnungen, denn das Element 0 ( 2x2) kann nicht in der letzten Zeile und auch nicht in der letzten Spalte sein.

Ich schätze mal die Anzahl ( Spalten = 5/Zeilen=4)
Element 0 an (5-1)*(4-1) = 12 Positionen
Element 1 an (5-1)* 4 = 16 Positionen
Element 2 an 5 *(4-1) = 15 Positionen
Element 3 an 5 * 4 = 20 Positionen
Element 4 an 5 * 4 = 20 Positionen
= 1152000 also maximal 1,152 Mio mögliche Stellungen.
Stimmt schon wieder nicht.
In den Zeilen mit Element 0 gibt es für Element 1 entweder 2,1,1,2 Möglichkeiten maximal 2, im Schnitt 1,5 in den anderen maximal 4 bleiben also maximal 6 weniger als die Hälfte, etc pp.
Es werden immer weniger..

Too Late

Gruß Horst

Horst_H hat folgendes geschrieben :

Ich nummeriere nicht, der Name interessiert nicht. ob 8 oder 9 an einer Stelle liegt ist ja für das Ergebnis, ob es lösbar ist, unerheblich.

Das ist auf jeden Fall ein wesentlicher Trick.

Horst_H hat folgendes geschrieben :

markieren Quelltext     1: 2: 3: 4: 22887 1164F 1165F 33990 Würde ich nun so schreiben, ob 2,3,8,9 wäre bei mir immer 2er waagerecht.

Ich füge mal noch einen Zwischenschritt ein, das sieht dann also so aus:

Horst_H hat folgendes geschrieben :

Die Pfeile besagen nun das dies Feld zu dem davor gehört. markieren Quelltext     1: 2: 3: 4: 5: 1<1<3 0<234 ^^^34 1<1<3 .. Zu schreiben als 113;0234;(0 und 2 ist von Zeile vorher bekannt,also nur die neuen) 34;113; Wenn ich 5er System jetzt nach Hornerschema rechne: (((...((1*5+1)*5+3)*5+0)*5+2)*5+3)*5+4)*5+3)*5+4)*5+1)*5+1)*5+3 Ergibt maximal 5^11-1 = 48'828'124

Schreibe es so
(((...((1)*5+3)*5+0)*5+2)*5+3)*5+4)*5+3)*5+4)*5+1)*5+1)*5+3
und auch ich sehe, warum es 5^11-1 Möglichkeiten sind

Womit die Lösung sogar in 26 bit passt Mein Ansatz ist sehr ähnlich, nur hab ich im entscheidenten Moment zu kompliziert gedacht (siehe nächsten Post)

Hier nun also meine Lösung zum Rätsel aus www.entwickler-ecke.....php?p=682310#682310 (wobei Horst_H's Lösung besser ist).

Wir betrachten wieder die Ausgangswerte, beschrieben wie im vorherigen Posting:
Ausgangswerte:


Ich habe nun immer ein 1-bit gesetzt, wenn der Nachbarblock ein anderer ist:
Zunächst horizontal:

(wichtig: ich kodiere leere Felder als seperate kleine Felder, egal wie sie zueinander liegen)
Nun ist klar, nach jeder 0 kommt immer eine 1, weil wir ja nur Blöcke der Breite 2 haben

Ist das letzte Bit eine 1 (Block der Breite 1), so kann man es weglassen, denn das folgt aus den vorherigen (im Allgemeinen Fall muss das nicht möglich sein, siehe unten).

Wiederum ist das letzte Bit redundant, da zu diesem Zeitpunkt bekannt ist, ob nun noch ein Block der Breite 2 oder 1 übrig ist.
00 011 011 0 (9 Bits + x)

Analog nun vertikal:
10 10 10 111 111 (12 Bits + y)

Wie groß ist nun x und y? Im schlechtesten Fall sind rechts am Rand und unten am Rand zweier-Blöcke (so dass jede Zeile und jede Spalte auf 0 endet). Glücklicherweise ist dies nicht möglich mit den gegebenen Blöcken (es existieren nur 3 Blöcke der Höhe 2). In schlimmsten Fall gilt x+y = 4+3 = 7. Ergibt in Summe: 12+9+(4+3) = 28 bits.

Jetzt fehlt aber noch die Position der leeren Felder (die haben wir bisher analog den kleinen Blöcken behandelt). Aus den bisherigen 28bit können wir herausbekommen, wie die Größen der Blöcke aussehen. Ein leer-Block ist einer der 6 kleinen Blöcke.
Wir können also 6 Bits als die 6 kleinen Blöcke interpretieren, welche in einer vorgegebenen Reihenfolge (links->rechts, oben->unten) abgelaufen werden. Ist der kleine Block ein leerer Block, so setzen wir eine 1.
Für das Beispiel:
001010
00 1 0

Erscheinen zwei Einsen hintereinander, so negiere ich den gesamten Hashwert am Ende. Dies ist möglich, da die füllenden Nullen, welche die ersten Bitfolgen auf 13 bzw. 15 bits erweitern, dann zu einsen werden. Dort können nur im normalen Fall Einsen stehen, wenn x+y=7. Dies ist der Fall, wenn die Breiten Teile rechts, die hohen Teile unten liegen. In diesem Fall stehen an den "Zeilenenden" immer Nullen, die jetzt zu Einsen werden. Kein normaler Wert kann so durch negieren erzeugt werden.

Macht also zusammen mit den 28bit genau 32 bit (worst case). Heureka! Jetzt habe ich aber echt geschwitzt, weil noch ein Fehler in meinem Algorithmus aufgetaucht ist

Für Flemings-Puzzle ergibt sich also die Kodierung:



Anmerkung:
Das selbe funktioniert übrigens auch für das Floyd-Puzzle aus dem Adventskalender, weil dort weniger kleine Blöcke existieren und auch nur ein großes. Es bleiben somit stellenweise bits "übrig", was nicht schadet. Problematisch wird es, sobal mehrere große Blöcke existieren (wegen den vorderen Bits) oder natürlich wenn die freien Felder und kleinen Blöcke zunehmen.

Zum Rätsel vom 16.12. (Pentagramm) stellte ich mir die "Zusatzaufgabe", wieviele Dreiecke es wohl sind, wenn man die Sternspitzen mit Strecken verbindet, das Pentagramm also mit einem Fünfeck umhüllt.

Hallo,

Delphi-Laie hat folgendes geschrieben :

Zum Rätsel vom 16.12. (Pentagramm) stellte ich mir die "Zusatzaufgabe", wieviele Dreiecke es wohl sind, wenn man die Sternspitzen mit Strecken verbindet, das Pentagramm also mit einem Fünfeck umhüllt.

Es werden 50 mehr.

Beste Grüße
Mathematiker

Mathematiker hat folgendes geschrieben :

Hallo, Delphi-Laie hat folgendes geschrieben : Zum Rätsel vom 16.12. (Pentagramm) stellte ich mir die "Zusatzaufgabe", wieviele Dreiecke es wohl sind, wenn man die Sternspitzen mit Strecken verbindet, das Pentagramm also mit einem Fünfeck umhüllt. Es werden 50 mehr.

Damit hätte ich auch bei der Zusatzaufgabe grob gepatzt. Wo sich all' diese Dreiecke verstecken, ist mir rätselhaft.

Ich bin auf jedenfall auf die Auflösung des Rätsels gespannt wie Mathematiker zeigt wo sich die Dreiecke verstecken.

Ralf Jansen hat folgendes geschrieben :

Ich bin auf jedenfall auf die Auflösung des Rätsels gespannt wie Mathematiker zeigt wo sich die Dreiecke verstecken.

Die Auflösung wird sicher so systematisch sein, wie es die Suche schon sein sollte: Ausnutzung der Symmetrie(gruppe). Die Dreiecksanzahl in einem "halben Fünftel des Pentagrammes" analysiert und *10 genommen, dürfte schon einen erheblichen Teil der Dreiecke zutagefördern. Auch im übergeordneten Teil, dem Fünftel, sind weitere zu finden, diese Anzahl natürlich *5. Aber dann...?

Hallo,
nachdem das heutige Rätsel sehr schleppend anläuft (ist wohl doch mühevoll oder langweilig ), sage ich schon etwas zu den nächsten Tagen.
Es sind nun nur noch 7 Tage bis Weihnachten, d.h. normalerweise hat man jetzt anderes zu tun, als Rätsel zu lösen. Da sind noch Geschenke und andere Dinge zu kaufen, das Festessen langfristig zu planen und vorzubereiten, der Weihnachtsbaum im Wald noch zu "besorgen" und evtl. noch die Gans zu schlachten (gruselige Vorstellung), usw. usf.

Aus diesem Grund werden die Aufgaben nun wieder einfacher.
Das Problem vom 18.12. wird den Informatikern nur ein ganz müdes Lächeln abringen, aber es soll ja wieder einfacher werden. Mit ein klein wenig Schaltlogik ist man ganz schnell fertig, obwohl es 2^8 Möglichkeiten gibt.
Der 19.12. ist wieder ein Matherätsel, das aber schon Schüler der Grundschule lösen können, also noch einfacher.
Ja ja, ich lasse nach.

Beste Grüße
Mathematiker

Mathematiker hat folgendes geschrieben :

nachdem das heutige Rätsel sehr schleppend anläuft (ist wohl doch mühevoll oder langweilig )

Also ich für meinen Teil muss erstmal nachlesen, wie eine Lochkarte überhaupt funktioniert. Ich dachte immer da werden einfach 1-Bits reingestanzt...
Was ich gleich total verwirrend finde: Wenn ich unter das zweite T von Mathematiker klicke, dann verschwindet unten das "Loch".
Sowas hätte Bush gebraucht, wenn man den Gegenkandidaten wählen will wird bei Bush das Loch gestanzt Wie auch immer das physikalisch möglich ist

Hallo,

Xion hat folgendes geschrieben :

Sowas hätte Bush gebraucht, wenn man den Gegenkandidaten wählen will wird bei Bush das Loch gestanzt

Genau so ist es doch gelaufen. Und funktioniert es nicht richtig, dann verbietet man eben die Karten richtig(!) zu zählen.

Xion hat folgendes geschrieben :

Was ich gleich total verwirrend finde: Wenn ich unter das zweite T von Mathematiker klicke, dann verschwindet unten das "Loch".

Oben hatte ich schon erwähnt: Erst die Löcher in den Zeilen 0 bis 9 setzen und danach erst die beiden obersten Zeilen mit dem notwendigen Loch versehen. Das Programm testet, ob eine Lochkombination zum Zeichensatz gehört.

Beste Grüße
Mathematiker