[Python-de] Meine Denksportaufgabe

Gerson Kurz Gerson.Kurz at t-online.de
Sat Oct 12 12:43:05 EDT 2002


Da wir das jetzt schon mal hatten, kann es nicht schaden, auch eine zu
stellen. Hat nicht sosehr mit normalen Algorithmen zu tun, mehr mit dem
Versuch, dem Computer Kreativität beizubringen.

Also. Gegeben sei ein Bildraum (x,y). Du kannst das ganze mit "*"-Grafik
machen (wie ich im folgenden), oder per PIL
(http://www.pythonware.com/products/pil/) oder was auch immer, wobei es
vermutlich am einfachsten ist, am Ende aus einer "*"-Grafik ein BMP (oder
sonst ein beliebiges verlustfreies Bildformat) zu basteln.

Du möchtest kreativ sein und willkürliche (hallo
Pseudozufallszahlengenerator!) Figuren machen, die aus geraden horizontalen
und vertikalen Linien zusammengesetzt sind. Beispiel:


    ****************
    *              *
    ********       *
           *       *
           *       *
           *       *
           *       *
           *********

1) Es sind /nur/ horizontale oder vertikale Linien, keine Schrägen.

2) Die Struktur muss sich "irgendwann" wieder treffen. Es hilft also nichts,
einfach Zufallspunkt an Zufallspunkt zu reihen, du musst eine Bedingung
einbauen, daß sich das Ding irgendwann wieder schliesst.

3) In meinen Tests scheint es schwieriger zu sein, eine einfache Struktur zu
machen, als eine komplexere - wenn man die Punkte per Zufallszahlengenerator
wählt, haben sie die Tendenz erst sehr spät (und unter Einfluß der weiter
unten genannten Randbedingungen) wieder eine Figur zu bilden, es wäre aber
ästhetisch besser, wenn es nicht ganz so komplexe Strukturen sind. Eine
echte Herausforderung ist also, die Komplexität nicht aus dem Ruder laufen
zu lassen.

4) Die ganze Fläche (x,y) soll zugemalt werden, bis der Computer keine
weitere Fläche findet.

5) Die Struktur darf sich überschneiden, etwa so:

    ****************
    *              *
    ********       *
           *       *
        ************
        *  *
        *  *
        ****

5) ABER, Die Struktur darf, und das ist eine scharfe Randbedingung, keine
Fläche füllen; genauer: zwischen zwei Linien muß immer ein Bildpunkt frei
bleiben. Also wäre das hier möglich:

    ****************
    *              *
    ********       *
           *       *
     ***********   *
     *     *   *   *
     *     *   *   *
     *     *********
     *         *
     ***********

aber das hier NICHT:

    ****************
    *              *
    ********       *
     ***********   *
     *     *   *   *
     *     *   *   *
     *     *   *   *
     *     *********
     *         *
     ***********

weil hier in Zeile 3 kein Punkt zwischen den beiden Figuren frei ist.

6) Das Bild, das sich am Ende ergibt, hat die Eigenschaft: Es kann in exakt
zwei Farben koloriert werden, so, daß nie eine Fläche die Farbe einer
angrenzenden Fläche hat. (Das ist kein gesonderter Bestandteil der Aufgabe,
das ergibt sich einfach aus den oben genannten Bedingungen. Die Colorierung
muß auch nicht ins Programm aufgenommen werden).

    ****************
    *oooooooooooooo*
    ********ooooooo*
           *ooooooo*
     ***********ooo*
     *ooooo*   *ooo*
     *ooooo*   *ooo*
     *ooooo*********
     *ooooooooo*
     ***********

7) Hinweis: Es kann natürlich auch Sackgassen geben. Der Algorithmus muß
diese unbedingt vermeiden (siehe Bedingung 2). Beispiel für eine Sackgasse:

*************
*           *
* ***********
* *
* * ??? <-------- SACKGASSE
* *
*************
  *         *
  ***********

Er muß also vor der Sackgasse "abbiegen", nach oben oder unten. Damit ist
übrigens auch gesagt, daß die Fläche keine Kugel ist, d.h. man kann nicht
über den linken rand hinaus in den rechten malen etc.

Ich selber habe bisher keine sehr gute Lösung dafür, aber ich arbeite daran
;)






More information about the Python-de mailing list