Labirynt cz II

Normalnie bym nie pisał - bo sesja, ale udało mi się odratować kod źródłowy słynnego już labiryntu. Oto i on:

Rysuj
  | form pen ile i |
  form := Display.
  pen := Pen newOnForm: form.
  pen up.
  form fillWhite.
 
  ile := lab size.
  i := 1.
  [i <= ile] whileTrue:
  [
    pen goto: (lab at: i).
    pen down.
    pen goto: (lab at: (i+1)).
    pen up.
    i := i + 2.
  ]

  pen goto: 0@0.
  pen down.
  pen goto: (10*xsize)@0.
  pen goto: (10*xsize)@(10*(ysize // 2)).
  pen goto: 0@(10*(ysize // 2)).
  pen goto: 0@0.
  pen up.

  pen goto: 0@(10*((ysize // 2) +1)).
  pen down.
  pen goto: (10*xsize)@(10*((ysize // 2) +1)).
  pen goto: (10*xsize)@(10*ysize).
  pen goto: 0@(10*ysize).
  pen goto: 0@(10*((ysize // 2) +1)).
  pen up.

  pen goto: 0@(10*((ysize // 2) +1) + 1).
  pen down.
  pen goto: (10*xsize)@(10*((ysize // 2) +1) + 1).
  pen up.

  pen goto: 0@(10*((ysize // 2)) - 1).
  pen down.
  pen goto: (10*xsize)@(10*((ysize // 2)) - 1).
  pen up.

  [Sensor keyboardPressed] whileFalse: [].
  Display restore.

Stworz: x y: y
  | r v |
  xsize := x.
  ysize := y.
  r := Random new.
  lab := OrderedCollection new.
  0 to: (x-1) do:
    [:x1 |
      0 to: (y-1) do:
        [:y1 |
          (y1 = (y // 2)) ifFalse:
          [
            v := r nextInt: 5.
            (v > 2) ifTrue:
            [ lab addLast: (10*x1)@(10*y1)
              lab addLast: (10*(x1+1))@(10*y1) ].
            (v < 4) ifTrue:
            [ lab addLast: (10*x1)@(10*y1)
              lab addLast: (10*x1)@(10*(y1+1)) ].
          ].
        ].
    ].

Labirynt

Zadanie brzmiało:

Zaprogramuj klasę generującą i rysującą labirynt o rozmiarze zadanym podczas tworzenia obiektu. Przyjmij że w labiryncie są tylko dwa wejścia oraz że istnieje droga łącząca te dwa wejścia.

Zadanie rozwiązałem po najmniejszej linii oporu. Labirynty generowane przez mój algorytm wyglądały mniej więcej tak:Prowadzący chciał mnie za to poćwiartkować.. Ale przyznał, że mój algorytm spełnia specyfikację zadania (jest to labirynt z dwoma wejściami taki, że istnieje ścieżka między nimi) i skończyło się na zaliczeniu programu na maksymalną ilość punktów.

Jako feature dodałem wysoce specjalistyczny algorytm sztucznej inteligencji znajdujący rozwiązania tego typu labiryntów 8)

Cykl Eulera cz II.

Cyklem Eulera w grafie nazywamy następujące obejście grafu:

- zaczynamy w wybranym przez nas wierzchołku
- obchodzimy graf w ten sposób, że każdą krawędź przechodzimy dokładnie raz
- kończymy na wierzchołku w którym zaczęliśmy.

Jakie warunki musi spełniać graf aby istniał w nim cykl Eulera? Graf przede wszystkim musi być spójny. Jeśli by nie był mogłaby istnieć krawędź do której nie możemy dojść. Ponadto za każdym razem gdy wchodzimy do jakiegoś wierzchołka musimy umieć z niego wyjść. Zatem stopień każdego wierzchołka musi być wielokrotnością dwójki.

Okazuje się, że jeśli graf spełnia te dwa warunki to istnieje w nim cykl Eulera (dowód przez podanie algorytmu Fleury'ego będzie przedstawiony w którejś z kolejnych notek).

Zadanie z winniczkiem wydaje się teraz banalne. Spójność grafu mamy dane w treści zadania. Ponadto każdą krawędź w tym grafie musimy przejść dwukrotnie (ścieżki są dwa razy szersze od kosiarki) - zatem spełniony jest również drugi warunek. Zatem w grafie istnieje cykl Eulera. Ponieważ w zadaniu nie proszą nas o znalezienie tego cyklu, a jedynie o podanie w jakim czasie Winicjusz jest w stanie przejść ten graf, więc odpowiadamy: suma wag na krawędziach przemnożona przez dwa.