Foren » 37. BwInf

Veröffentlichung von Einsendungen (2. Runde)

    • 20 Beiträge
    30. April 2019 00:29:01 CEST

    Gestern (29.4.19) war Einsendeschluss der 2. Runde. Nach dem Einsendeschluss könnt ihr hier über Lösungsideen und deren Umsetzung diskutieren und eure Einsendung für andere online zur Verfügung stellen (z.B. mit GitHub/GitLab/Bitbucket oder einem Cloud-Speicher eurer Wahl). Postet dann am besten hier einen Link.

    Das PMS wird voraussichtlich irgendwann in der Nacht vom Montag zum Dienstag geschlossen. Um auf Nummer sicher zu gehen, sollte mit der Veröffentlichung von Einsendungen bis zum Dienstag Abend gewartet werden.

    Viel Spaß noch bei der Diskussion eurer Lösungsideen. Besonders Aufgabe 2 würde mich da interessieren (War Aufgabe 3 wirklich so schwierig, dass die niemand bearbeitet hat? ;-).

     

    EDIT Weitere online verfügbare Einsendungen:


    Dieser Beitrag wurde am 3. Mai 2019 18:34:53 CEST von Lukas Rost bearbeitet
    • 5 Beiträge
    2. Mai 2019 17:06:48 CEST

    Ich fang dann mal an: https://gitlab.com/jrpie/bwinf2

    Bei Aufgabe 1 deckt mein Programm nicht alle Sonderfälle ab, die Ergebnisse für die Beispiele sind vermutlich aber richtig (?). Grundsätzlich: kantengewichteten Graphen aufstellen und dann A*

    Für Aufgabe 2 habe ich keine optimale Lösung gefunden (geht das ohne Brute Force?). Mein Programm versucht, mit einem Greedy-Algorithmus diejenigen Dreiecke auszuwählen, welche mit einer Seite an der Straße anliegen, und versucht dann, die restlichen Dreiecke dazwischen einzuordnen. Das ist nicht notwendigerweise optimal (in einiger der  Beispiele definitiv nicht)

    Habe für die Aufgaben eine Geometrie-Bibliothek geschrieben (ca. 1000 LoC) und hinterher erst festgestellt, dass man auch fertige Bibliotheken hätte verwenden dürfen *facepalm*. Kann irgendwer da eine gute Bibliothek empfehlen (für Java)?


    Dieser Beitrag wurde am 2. Mai 2019 17:07:17 CEST von Josia Pietsch bearbeitet
    • 5 Beiträge
    2. Mai 2019 18:17:15 CEST

    Ich habe die Aufgaben 1 und 2 bearbeitet (in Python): https://bitbucket.org/CubeFlo/bwinf37runde2/

    Bei Aufgabe 1 benutze ich auch einen Sichtbarkeitsgraphen und den Dijkstra-Algorithmus. Außerdem habe ich es als Zusatz möglich gemacht, Lisa durch ein Polygon statt durch einen unendlich kleinen Punkt darzustellen. Das funktioniert auch meistens (wenn es mit konkaven Polygonen Schwierigkeiten gibt, sollten diese zuerst in konvexe zerlegt werden, siehe auch Beispiele 4). Auch mit Überlappungen kommt das Programm zurecht. 

    Für Aufgabe 2 sucht mein Programm mehrere Möglichkeiten für Basisdreiecke (Dreiecke, die gut mit einer Kante an der x-Achse platziert werden können), und zwar in einer aufsteigenden Länge auf der x-Achse, und füllt für jede Auswahl an Basisdreiecken die übrigen Dreiecken in die Lücken (kleinster Winkel an der x-Achse). Sollte die Länge der nächsten Auswahl der Basisdreiecke länger sein als das bisher beste gefundene Ergebnis, ist die Suche beendet. Nach passenden Dreiecken wird mit dem Teilsummenproblem ("subset sum problem") gesucht: https://de.wikipedia.org/wiki/Teilsummenproblem . Außerdem gibt es verschiedene Optimierungen (z.B. das Rotieren der eingefügten übrigen Dreiecke, falls noch Platz ist); und letztendlich kann ich bei den Ergebnissen keine weiteren Verbesserungen finden (es gibt manchmal aber bestimmt welche). Die Gesamtlängen lauten 143; 0; 72; 171; 657. 

    • 1 Beiträge
    3. Mai 2019 17:58:53 CEST

    Hier sind meine Lösungen. Ich habe Aufgaben 1 und 2 bearbeitet, dabei sind beide am ende relativ kompakt geworden.

    https://github.com/georgijs01/BWINF_37_2

    Meine Ansätze sind relativ ähnlich wie die bisher dargestellten.

    Mich würde eine Lösung zu Aufgabe 3 interessieren, bei der hatte ich keine Vorstellung, wie man dort herangehen könnte.

    • 20 Beiträge
    3. Mai 2019 18:32:48 CEST

    Eigentlich wollte ich meine Einsendung erstmal nicht veröffentlichen, aber dann mach ich das mal doch. Ich habe natürlich auch Aufgabe 1 (Python) und 2 (C++) bearbeitet, beide nicht sooo kompakt (was vielleicht daran liegt, dass ich bereits letztes Jahr an der Endrunde teilgenommen habe ;-).

    Mein Ansatz bei Aufgabe 1 entspricht im Prinzip auch dem bereits bekannten Vorgehen (Visibility Graph und Dijkstra). Ich habe es mithilfe der sogenannten Minkowski-Summe möglich gemacht, Lisa als Polygon darzustellen.

    Bei Aufgabe 2 verwende ich ebenfalls eine Heuristik, die auf Subset Sum (wie bei Florian) über die kleinsten Winkel der Dreiecke und einigen Optimierungen (Sortierung usw.) basiert. Meine Ergebnisse können im großen und ganzen auch mit euren mithalten.

    https://github.com/laugengebaeck/BwInf-37-R2

    EDIT: Für Aufgabe 2 kenne ich nur bei Beispiel 5 jemanden, der was besseres hat. 639 mit einem evolutionären Algorithmus.
    Dieser Beitrag wurde am 3. Mai 2019 21:56:23 CEST von Lukas Rost bearbeitet
    • 5 Beiträge
    3. Mai 2019 21:04:51 CEST

    Für Aufgabe 1 bin ich wie Lukas auf die Minkowski-Summe gestoßen, habe mich aber nur "inspirieren" lassen. Letztendlich habe ich einen eigenen Algorithmus verwendet, der (meistens) funktioniert und Lisas Polygon an jeder Ecke einmal anlegt und für das größere Polygon alle Ecken der angelegten Polygone verbindet, wobei alle Ecken ausgeschlossen werden, von denen beide Kanten das ursprüngliche Polygon schneiden. Das kommt dem eigentlich vergrößerten Polygon für den Visibility Graph ausreichend nahe. 

    Für Aufgabe 2 würde mich interessieren, ob jemand bessere Ergebnisse als meine (auch ohne Programm) gefunden hat?

    Danke an Lukas für die weiteren Einsendungen!

    • 1 Beiträge
    3. Mai 2019 21:54:00 CEST

    Dann mache ich mal weiter. ;)

    Ich habe Aufgabe 1 und 2 (Welch eine Überraschung ^^) bearbeitet. Im Kern ähnelt meine Einsendung den bisherigen, weshalb ich darauf nicht mehr explizit eingehe.

    Einsendung BWInf 2. Runde

    Da ich neben der Aufgabe 1 zunächst mit der Aufgabe 3 angefangen habe, würde ich aber meinen bisherigen Ansatz zu dieser Aufgabe kurz vorstellen:

    Der Kerngedanke besteht darin, dass ein Matt in einer der vier Ecken in der Regel (jedoch nicht immer) erzwungen werden kann. Die Zugfolge, die durch einen effizient implementierten Minimax-Algorithmus oder einer Endspieldatenbank entnommen werden kann, wird jedoch nicht vollständig ausgeführt. Bevor der König matt gesetzt wird, ist er in aller Regel in einem Bereich aus zwei Feldern "gefangen", kann sich daher nur auf den beiden Feldern bewegen. Um diesen Zustand zu erhalten, sind insbesondere in der Ecke nicht alle Spielfiguren notwendig. Es ist daher für Weiß möglich, seine Figuren in eine einzige Position zu bewegen, die als Grundstellung bezeichnet wird. Ein Beispiel für diese ist hier zu finden. Ausgehend von dieser Grundstellung ist es mit geeigneten Zugfolgen möglich, das Matt auf allen anderen Randfeldern zu erzwingen, unabhängig davon was der schwarze König macht. Dieser befindet sich nämlich die ganze Zeit über in einem solchen "Käfig". Diese Zugfolgen habe ich schon ausgearbeitet und kann ich auf Nachfrage auch gerne nochmal reinstellen. Damit kann ein Matt, sofern es überhaupt möglich ist, auch auf jedem Randfeld erzwungen werden. Auf einem inneren Feld kann das Matt nicht erzwungen werden, dafür hat Weiß nicht genügend Figuren.

    Eine Problematik stellt die Zahl der Züge dar, die ggf. sehr schnell sehr groß werden kann und unter Berücksichtigung der 50-Züge-Regel meistens in einem Unentschieden enden würde. Bereits im Forum wurde die Frage beantwortet, dass diese Regel nicht zur Geltung kommen muss, wodurch die Zahl der Züge mit der Nachvollziehbarkeit für den Betrachter kompensiert werden würde. Eine genauere Lösung würde vielleicht eine sinnvolle Erweiterung darstellen.

    Joa, soweit war es das von mir. Würde mich natürlich auch sehr freuen eine fertige Umsetzung von Aufgabe 3 mir mal genauer anschauen zu können. :D

    Würde mich natürlich auch über Feedback zu meiner Einsendung freuen!

    • 5 Beiträge
    4. Mai 2019 21:49:57 CEST

    Hat irgendjemand einen schönen/eleganten Beweis dafür gefunden, dass die Richtung in die Lisa läuft, einen 30° Winkel mit der x-Achse einschließt? So wie ich das sehe, wurde bei den Beweisen hier mehr auf das Rechnen und nicht so wirklich auf die Schönheit/Eleganz geachtet :)

    • 5 Beiträge
    5. Mai 2019 13:12:24 CEST
    Erik Sünderhauf said:

    Hat irgendjemand einen schönen/eleganten Beweis dafür gefunden, dass die Richtung in die Lisa läuft, einen 30° Winkel mit der x-Achse einschließt? So wie ich das sehe, wurde bei den Beweisen hier mehr auf das Rechnen und nicht so wirklich auf die Schönheit/Eleganz geachtet :)

     

    Ja, das ist einfach nur ein Optimierungsproblem: https://gitlab.com/jrpie/bwinf2/blob/master/fertig/Aufgabe1.pdf



    Es sei der Startpunkt von Lisa bei P(x | y) und der Treffpunkt mit dem Bus bei T(x + d | 0).

    Es ergibt sich für einen optimalen Weg: d = y / sqrt(3) (s. Beweis in meiner Lösungseinsendung).
    Daraus folgt alpha = arctan(1 / sqrt(3)) = 30°


    Edit: Da habe ich wohl die Achsen vertauscht... Es muss natürlich T(0 | y + d) heißen, dementsprechend sind dann auch x und y vertauscht.


    Dieser Beitrag wurde am 5. Mai 2019 16:32:39 CEST von Josia Pietsch bearbeitet
    • 5 Beiträge
    5. Mai 2019 15:43:24 CEST

    Den Beweis habe ich schon gesehen. Allerdings ist das nicht wirklich schön, sondern es wurde mehr oder weniger der erstbeste Ansatz durchgeprügelt. :)

    Ich würde sagen, dass zu einem schönen Beweis dazu gehört, dass man (fast) nicht rechnen muss, sondern durch cleveres überlegen genau das zeigt, was man zeigen will.

    • 5 Beiträge
    5. Mai 2019 16:09:31 CEST

    Man kann für zwei Geschwindigkeiten vL und vB den Winkel mit asin(vL/vB) berechnen, weil die entsprechenden Seitenlängen eines entstehenden Dreiecks der Geschwindigkeit von Lisa und dem Bus entsprechen müssen (siehe meine Dokumentation). Die Gegenkathete (y-Achse, Bus) ist also halb so lang wie die Hypotenuse (Lisas Weg). Das liegt daran, dass nun beide dieselbe Zeit für diese beiden Strecken benötigen. Da beide dieselbe Zeit benötigen, heißt das, dass Lisa keine Zeit verliert. Es geht also im Prinzip darum, einen Punkt zu finden, zu dem jeder der zwei dieselbe Zeit benötigt. Hier der Link zu  GeoGebra dazu (Bild in meiner Dokumentation, enthält auch eine Funktion, deren Extremum der y-Koordinate auf der y-Achse entspricht): https://ggbm.at/m5uzyf97

     


    Dieser Beitrag wurde am 5. Mai 2019 16:22:22 CEST von Florian Rädiker bearbeitet
    • 5 Beiträge
    5. Mai 2019 16:21:45 CEST

    Ok, ich probiere es noch mal. Ein mutmaßlich schönerer Ansatz mit weniger Rechnen:

    I. Der letztmögliche Zeitpunkt, zu dem Lisa starten kann, der Zeitpunkt ist, an dem sie und der Bus auf gleicher Höhe sind. Da sie langsamer als der Bus ist, kann sie diesen nach diesem Zeitpunkt nicht mehr einholen.

    II. Wegen sin(30°) = vL / vB  kann Lisa den Bus, wenn sie unter dem Winkel 30° zur x-Achse läuft, noch erreichen, wenn sie startet, sobald der Bus ihre Höhe erreicht. Wegen I. muss dies der bestmögliche Weg sein.

    Edit: Alles Schwachsinn.


    Dieser Beitrag wurde am 6. Mai 2019 13:34:33 CEST von Josia Pietsch bearbeitet
    • 5 Beiträge
    5. Mai 2019 16:25:14 CEST

    Ich habe in meinem Beweis noch ein bisschen was hinzugefügt. Stimmt das so? (Die Strecke des Busses startet erst ab der Höhe von Lisas Haus)

    • 5 Beiträge
    5. Mai 2019 16:30:51 CEST
    Florian Rädiker said:

    Ich habe in meinem Beweis noch ein bisschen was hinzugefügt. Stimmt das so? (Die Strecke des Busses startet erst ab der Höhe von Lisas Haus)

    Was bei dir noch fehlt, ist das, was ich jetzt im zweiten Beweis unter I. gefasst habe. Du musst für einen mathematischen Beweis zeigen, dass dies für Lisa tatsächlich der spätest mögliche Zeitpunkt zum Losgehen ist. Nur weil Lisa "keine Zeit verliert" bedeutet das nicht automatisch, dass Lisa nicht auch "Zeit gewinnen" könnte. Ansonsten ist das aber richtig.
    Edit: Sorry, habe dich glaube ich falsch verstanden. Du hast die auf deine GeoGebra-Berechnung bezogen, richtig? Das ist letztendlich die Argumentation, die ich im ersten Beweis auch hatte und müsste denke ich richtig sein.

     


    Dieser Beitrag wurde am 5. Mai 2019 16:37:13 CEST von Josia Pietsch bearbeitet
    • 5 Beiträge
    5. Mai 2019 16:36:43 CEST
    Josia Pietsch said:
    Florian Rädiker said:

    Ich habe in meinem Beweis noch ein bisschen was hinzugefügt. Stimmt das so? (Die Strecke des Busses startet erst ab der Höhe von Lisas Haus)

    Was bei dir noch fehlt, ist das, was ich jetzt im zweiten Beweis unter I. gefasst habe. Du musst für einen mathematischen Beweis zeigen, dass dies für Lisa tatsächlich der spätest mögliche Zeitpunkt zum Losgehen ist. Nur weil Lisa "keine Zeit verliert" bedeutet das nicht automatisch, dass Lisa nicht auch "Zeit gewinnen" könnte. Ansonsten ist das aber richtig.

    Ok, danke. Edit: Ja, danke. 


    Dieser Beitrag wurde am 5. Mai 2019 19:49:18 CEST von Florian Rädiker bearbeitet
    • 5 Beiträge
    6. Mai 2019 12:43:27 CEST
    Josia Pietsch said:

    Ok, ich probiere es noch mal. Ein mutmaßlich schönerer Ansatz mit weniger Rechnen:

    I. Der letztmögliche Zeitpunkt, zu dem Lisa starten kann, der Zeitpunkt ist, an dem sie und der Bus auf gleicher Höhe sind. Da sie langsamer als der Bus ist, kann sie diesen nach diesem Zeitpunkt nicht mehr einholen.

    II. Wegen sin(30°) = vL / vB  kann Lisa den Bus, wenn sie unter dem Winkel 30° zur x-Achse läuft, noch erreichen, wenn sie startet, sobald der Bus ihre Höhe erreicht. Wegen I. muss dies der bestmögliche Weg sein.

    Wenn Lisa losläuft und sich zum selben Zeitpunkt auf der gleichen Höhe wie der Bus befindet, dann kann sie ihn gar nicht erreichen. Da in dem Dreieck Bus, Lisa, Treffpunkt ein rechter Winkel beim Bus ist, muss die Strecke von Lisa zum Treffpunkt die längste sein. (alle anderen Innenwinkel sind kleiner als  π {\displaystyle \pi\pi /2) Sie ist also langsamer als der Bus ist, ihr Weg zum Treffpunkt aber länger. Aus diesem Grund verpassen sich beide. Lisa muss deshalb schon früher starten.
    Es ist in der Tat so, dass Lisa losaufen muss, wenn das Dreieck Bus, Lisa, Treffpunkt einen rechten Winkel bei Lisa hat. (Das ist aber kein Beweis, sondern nur eine Behauptung :))

    • 5 Beiträge
    6. Mai 2019 14:01:29 CEST

    Du hast natürlich Recht. Keine Ahnung, wie ich auf solche abstrusen Ideen komme.

    Das hindert mich jedoch nicht daran, es nochmal zu versuchen :)



    Durch die Position des Busses ist zu jedem Zeitpunkt eine Fläche definiert, in der Lisa den Bus noch erreichen kann. Lisa startet im optimalen Fall erst, sobald die Begrenzungslinie dieser Fläche sie errreicht. Um dann optimal vor der Begrenzungslinie zu "fliehen" muss sie orthogonal zu dieser laufen. Daraus folgt, dass sie - wie du behauptet hast- starten muss, sobald das Dreieck aus ihr, dem Bus und dem Zielpunkt bei ihr einen rechten Winkel hat. Durch das Verhältnis der Geschwindigkeiten v_Bus und v_Lisa ergibt sich für die Begrenzungslinie ein Winkel von arcsin(v_Lisa / v_Bus) = arcsin(0.5) = 30° zur y-Achse. Da Lisas Laufweg orthogonal zu Begrenzungslinie verläuft liegt dieser entsprechend in einem Winkel von 30° zur x-Achse


    Dieser Beitrag wurde am 6. Mai 2019 14:09:56 CEST von Josia Pietsch bearbeitet
    • 5 Beiträge
    8. Mai 2019 15:42:50 CEST

    Mein erster Beweis war da wohl etwas komplizierter :)
    Ich hatte mir gedacht, dass man das ganze im Bezugssystem des Busses betrachten
    kann. In diesem System läuft Lisa erst mit der Geschwindigkeit 2 in Richtung x-Achse
    und anschließend auf direktem Weg zum Bus. (Die Geschwindigkeitsvektoren werden
    einfach addiert. Da sich im Laborsystem beide auf einer Geraden bewegen, macht Lisa
    dies auch im neuen Bezugssystem.) Da sie möglichst spät loslaufen will, muss der
    direkte Weg zum Bus einen minimalen Anstieg haben. Schaut man sich alle möglichen
    Richtungen an (was äquivalent ist zu dem Geschwindigkeitsvektor von Lisa ist),
    in die sie laufen kann, dann erhält man einen Kreis. Dies kann man damit begründen,
    dass ihr Geschw.vektor gleich der Vektorsumme von -1 * "Busvektor" im Laborsystem
    und  "Lisavektor" im Laborsystem ist. (siehe die beiden Vektoren in der Skizze) Wie
    oben bereits begründet muss die entstehende Gerade einen minimalen Anstieg haben,
    was offensichtlich der Fall ist, wenn diese Gerade die Tangente an den konstruierten
    Kreis ist. Aus der Konstruktion ergibt sich außerdem sin(α1)=1/2 und α1=α2. Da α2 der
    Winkel zwischen x-Achse und Lisas Bewegungsrichtung im Laborsystem ist, folgt die
    Behauptung.

    Link zur Skizze: https://pasteboard.co/IdKLNiA.png


    Dieser Beitrag wurde am 8. Mai 2019 15:44:13 CEST von Erik Sünderhauf bearbeitet
    • 4 Beiträge
    20. Mai 2019 14:16:27 CEST

    Hat jemand die Aufgabe 3 gelöst, wenn ja wie?

    Und welche Laufzeiten habt ihr dabei erreicht?

     

    Ich habe sie mit einer Graphensuche gelöst und komme auf Laufzeiten zwischen 10 Sekunden und teilweise auch 2 Minuten, allerdings habe ich hierfür in kauf genommen, dass auch teilweise 70 Züge oder mehr gemacht werden.


    Dieser Beitrag wurde am 20. Mai 2019 14:16:55 CEST von Manuel Raimann bearbeitet
    • 3 Beiträge
    22. August 2019 20:09:53 CEST
    Hier sind meine Lösungen: Aufgabe 1, Aufgabe 2
     
     
    Aufgabe 1 habe ich auch als kürzester-Pfad-Problem modelliert. Ich benutze den Bellman-Ford-Algorithmus.
    In der Doku findet ihr auch meine Methode, um zu prüfen, ob eine Strecke ein Polygon schneidet. Ich finde sie originell und cool, könnte man aber wahrscheinlich auch noch eleganter machen...wink
     
    Für Aufgabe 2 verwende ich Simulated Annealing. In der Doku gibt es viele interessante Formeln.