Python Tutorial, Dreieckspuzzle, Bundeswettbewerb Informatik

Hier programmieren wir die Lösung eines Dreieckspuzzles mit 9 Teilen. Dies war eine Aufgabe aus dem 39. Bundeswettbewerb für Informatik (Runde 1, Aufgabe 2).

[ralfkohler]

Vielen Danke für die super Erklärung, ich hätte das Problem nicht lösen können. Aber Dein Erläutern hilft sehr beim Umgang mit Listen. Im kleinen Rahmen komme ich mit Listen und Dictionary besser zurecht.

[romanbuchta]

Sehr knifflige Aufgabe! Hätte ich vor 21 nicht geschafft und jetzt mit 50 auch nicht! :-)

[familieduscher]

Wirklich guter Beitrag (wie die anderen auch). Ich will jetzt kein Klugscheißer sein, aber bei der Anzahl der Möglichkeiten musst Du nochmals durch drei dividieren, denn es geht ja um die Stellung der Puzzleteile zu einander (so lese ich die Aufgabe). Damit ist die Aufgabe auch gelöst, wenn das Bild des Puzzles um 120 oder 240 Grad gedreht ist; zumindest verstehe ich die Aufgabe so. Ist aber Griffelspitzerei :-) Richtig ist: Für einen Schülerwettbewerb ist das knackig; da ich selbst Programmieren unterrichte, kann ich allerdings auch sagen: Die zwei besten Schüler (m/w/d), die ich je hatte, waren zwei (damals) 17-jährige Schülerinnen. Will damit sagen: Unter den Schülern sind teils echt sehr helle Köpfe... heller als ich "alter Sack" 😃

[dbn]

Ich bin ansonsten schwer beeindruckt von der Analyse und Lösung für das Puzzle. Ich nehme das als Anlass, mich stärker mit Backtracking zu beschäftigen. Mein Ansatz für die Topologiefindung ist ja eher eine Fleißarbeit. Eben ziemlich linear. Vielen, vielen Dank für das Video. Ich freue mich darauf, auch weiterhin so interessante Problemstellungen und Lösungen von Dir zu sehen. Super!

[dbn]

Kennt man die Gesamtzahl der Fliesen eines Dreieckspuzzles, lässt sich die Länge der Grundreihe daraus leicht ermitteln, und folglich auch aufbauend immer die Setznummern der ersten Fliesen der aufsteigend kürzeren Reihen. Man kann deshalb jeweils die erste Fliese einer Reihe bei Erreichen ihrer Setzpositionen leicht erkennen und ihr die (relative) Reihen-Setznummer 0 zuweisen. Die Fliese mit der Reihen-Setznummer 0 der Grundreihe hat keine Nachbarn. Alle folgenden Fliesen der Reihe haben zum Setz-Zeitpunkt genau einen Nachbarn, nämlich die Fliese mit (Reihen-Setznummer - 1). Die Reihen-Setznummer 0 jeder folgenden Reihe hat ebenfalls genau einen Nachbarn, nämlich die Reihen-Setznummer 1 der vorausgehenden Reihe. Reihen-Setznummer 1 steht auf dem Kopf und hat deshalb wieder nur Reihen-Setznummer 0 als Nachbarn. Reihen-Setznummer 3 und alle weiteren aufrechten Fliesen haben dann immer zwei Nachbarn, nämlich an der Grundseite und an der linken Schrägseite. Für die Höhe 3 entspricht dies genau der im Video ermittelten Nachbarschaftsliste, nur mit anders markierter Setzreihenfolge und Nachbarschaftsrelation. Fortsetzung folgt.

[jimlyjimlesson]

Hi Gravitar, Coole Themen, coole Lösungen. Ich verfolge das schon einige Zeit! Sagmal was für ein Theme verwendest Du in VS-Code - ich finde die Zeichen != wird zu ≠, etc... total cool...

[findikvedat]

Kommt noch weitere Wettbewerb-Aufgaben?

[dbn]

Dreieckspuzzles sind immer gleichseitige Dreiecke, die mit gleichseitigen Dreiecken gefliest sind. Sei nun eine der drei Seiten des Puzzles als Grundseite definiert, die anderen beiden als Schrägseiten. Eine einzelne Fliese steht aufrecht, wenn sie wie das gesamte Puzzle orientiert ist. Sie steht dann auf der Grundseite. Eine um 90 Grad gedrehte Fliese steht auf dem Kopf. Ihre durch die Schrägen gebildete Spitze ist dann auf die Grundseite gerichtet. Eine Reihe des Puzzles sei eine Anordnung von abwechselnd aufrecht und kopfstehend aneinandergereihten Fliesen. Dabei stehen die erste und letzte Fliese einer Reihe immer aufrecht, so dass die Fliesenanzahl der Reihe ungeradzahlig sein muss. Das Puzzle setzt sich insgesamt aus zu seiner Spitze hin kürzer werdenden Fliesenreihen zusammen. Wegen der Geometrie des Puzzles muss die Fliesenanzahl Schicht für Schicht um 2 Fliesen abnehmen, und wegen ungerade ist die letzte Schicht an der Spitze nur noch 1 Fliese lang. Die Anzahl der Reihen inklusive erster Reihe und Spitze sei die Höhe des Puzzles, eine ganze positive Zahl größer 0. Das heißt, ein Puzzle der Höhe 0 existiert nicht. Die Anzahl der Fliesen eines Puzzles der Höhe h ist h**2. Die Reihe (genannt Grundreihe), die auf der Grundseite aufliegt, besteht dann aus 2*h-1 Fliesen. Wir nummerieren die Fliesen jetzt Reihe für Reihe aufsteigend, von der Grundreihe beginnend, immer von links nach rechts mit Setzpositionen. Dabei ist die ganz linke Fliese die Setzposition 0. Ein Puzzle der Höhe 3 besteht aus 9 Setzpositionen (0…8), mit einer Grundreihe der Länge 5, nummeriert von 0 bis 4. Die erste Reihe wird dann mit 5 bis 7 nummeriert, und die dritte Reihe (Spitze) ist die 8. Fortsetzung folgt.

[pyuc]

Hi, danke für das extrem lernreiche Tutorial und die anschaulichen Erklärungen!

14:32 das puzzle so zu durchlaufen hat bei mir nicht funktioniert. Ich bekomme dann diese Fehlmeldung hier
"ValueError: invalid literal for int() with base 10: '1-'"

Ich habe dann den Ansatz genommen, den du auch beim Advent of Code benutzt hast, nämlich:
"puzzle = [list(map(int, re.findall('-?\d+\.?\d*', zeile))) for zeile in f.readlines()][2:]"
Weißt du warum er bei deiner Version wie im Video diese Fehlmeldung rausschmeißt?

[dbn]

Fliesen, die auf dem Kopf stehen, haben in allen Reihen außer der Grundreihe immer nur einen Nachbarn zum Setzzeitpunkt, nämlich die rechte Schräge der vorausgehenden aufrechten Fliese. Die drei Seiten einer aufrecht stehenden Fliese seien aufsteigend ab 0 nummeriert. Dabei sei die Grundseite einer Fliese die 0, die linke Schräge die 1 und die rechte Schräge die 2. Aufrechte und kopfstehende Fliesen treffen dann an der Reihengrenze immer an Seite 0 aufeinander. Die Seitennummer bleibt fest zugeordnet, auch bei Rotation einer Fliese. Innerhalb der Reihe treffen immer die rechte Schräge der aufrechten Fliesen (Seite 2) auf Seite 2 der kopfstehenden Fliesen. Seite 1 einer kopfstehenden Fliese grenzt immer an Seite 1 ihres rechten (aufrechten) Nachbarn. Zwischen der Benennung der Fliesenseiten und ihrer eventuellen Symbolmarkierung besteht kein zwingender Zusammenhang, so dass die Fliesen innerhalb der durch Setzpositionen und Seitenmarkierung festgelegten Topologie beliebig permutiert und bei der Setzung rotiert werden dürfen, ohne die Topologie zu stören. Durch die Symbolanordnung auf den realen Fliesen wird die Lösung des Puzzles beeinflusst, aber nicht die Topologie der Setzpunkte und Nachbarschaften wären des Fliesungsablaufes. Die Lösungsstrategie des Videos kann deshalb unverändert beibehalten werden. Die obigen Überlegungen sollten aber nun die Formulierung der Topologieliste automatisierbar machen, als Ableitung aus der Fliesen-Gesamtzahl aus der Parameterdatei (Zeile 2).