Spis treści

Dzień 20 - poszukiwanie potworów

Spis treści

To był jeden z najtrudnieszych dni. Składanie zdjęć satelitarnych z fragmentów to świetna zabawa, pod warunkiem, że się ten proces już wcześniej przećwiczyło. W zadaniu Jurassic Jigsaw można się było wykazać spostrzegawczością.

Fragment pełnego "zdjęcia satelitarnego"

Najpierw popełniłam błąd w definicjach funcji przekształcających współrzędne punktów obrazu w transformacjach (obrotach i odbiciach względem osi).

Poniżej funkcja transformująca frament (tile) w obrocie (wartość 0-3 oznaczająca odpowiednio obrót o 0, 90, 180, 270 stopni) i odbiciu (wartość 0-2 oznaczająca odpowiednio: brak odbicia, odbicie horyzonralne

  • symetria względem osi Y, odbicie wertykalne - symetria względem osi X). Rotacja i odbicie są operacjami przemiennymi, więc ich kolejność nie ma znaczenia: poniższy kod dokonuje transformacji obrazu przez złożenie obrotu i odbicia:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
  def transform(t, rot, flip):
      n = len(t)

      # 0, 90, 180, 270
      rots = [
              lambda x, y : (x, y),
              lambda x, y: (n - y - 1, n - x - 1),
              lambda x, y: (n - x - 1, n - y - 1),
              lambda x, y: (y, n - x - 1), 
              ]

      # 0, H, V
      flips = [
              lambda x, y: (x, y),
              lambda x, y: (n - x - 1, y),
              lambda x, y: (x, n - y - 1),
              ]

      def _transform(arr, arridx, t):
          rows = [['.' for j in range(n)] for i in range(n)]
          for y in range(n):
              for x in range(n):
                  x1, y1 = arr[arridx](x, y) 
                  rows[y][x] = t[y1][x1]
          return rows

      def _r(t):
          return _transform(rots, rot, t)

      def _f(t):
          return _transform(flips, flip, t)

      return _r(_f(t))

Minęło też dużo czasu zanim zrozumiałam, że układanie pełnego obrazu mogę rozpocząć od dowolnego elementu, a pozostałe ułożą się ładnie, jeśli będę przeszukiwać graf elementów "wszerz", dobierając te, które pasują do odpowiedniej krawędzi odpowiadającą jej stroną. Wcale nie muszę zaczynać od narożnika.

A ostatni błąd - klasyka gatunku! - to mój upór w wysyłaniu liczby znalezionych potworów, podczas gdy należało znaleźć liczbę znaków # nie należących do potwora. Nie wiem zresztą, czy skanowanie obrazu przesuwającym się "okienkiem", którego zawartość - spłaszczoną do jednego wiersza - sprawdzałam wyrażeniem regularnym o kształce potwora - to najlepsza strategia, ale tylko na taką było mnie stać.

Udało się. Mój kawałek morza z potworami poniżej:

Pełne "zdjęcie satelitarne" i zaznaczone potwory