Rozwiąż Grid-Tangram

22

Tangram jest zagadką rozwarstwienie wykonany z siedmiu kształtach: pięć różnej wielkości trójkąty, równoległoboku i kwadratowych. Biorąc pod uwagę kształt, celem jest odtworzenie kształtu przy użyciu wszystkich elementów i bez nakładania się. Istnieje oczywiście nieskończenie wiele sposobów na rozmieszczenie tego zestawu elementów w samolocie. Ciekawym podzbiorem są

Siatki Tangrams

Możemy narysować „standardowy” kwadrat Tangram na większy kwadrat, który jest podzielony siatką na 16 mniejszych kwadratów. Tangramy siatki to tylko kształty złożone z elementów tangramu, tak że wszystkie wierzchołki elementów znajdują się w punktach siatki.

To są rodzaje zagadek Tangram, które chcemy wziąć pod uwagę w tym wyzwaniu, ponieważ prawdopodobnie są łatwiejsze w obsłudze niż te bardziej ogólne.

Na marginesie: chińscy matematycy Chuan-Chin Hsiung i Fu Traing Wang udowodnili w 1942 r., Że istnieje tylko 13 wypukłych tangramów. Najpierw wykazali, że problem można zredukować do tangramów siatki, a następnie wykorzystali kilka argumentów kombinatorycznych i geometrycznych. Oto wszystkie 13:

Wyzwanie

Biorąc pod uwagę rozwiązywalny tangram siatki, wyślij podział tangramu siatki na siedem kawałków tangramu.

IO

Tangram jest podawany jako obraz czarno-biały (kształt jest w kolorze czarnym, tło w kolorze białym), z wielokrotnością 50 stron po obu stronach. Siatka ma szerokość dokładnie 50 pikseli. Linie siatki są równoległe do boków obrazu.

EDYCJA: Obraz można zaakceptować jako dane wejściowe i zwrócić jako dane wyjściowe w dowolnym dogodnym formacie obrazu rastrowego, takim jak PNG, TIFF, PBM itp., Ale akceptacja może być reprezentowana jako binarna tablica 2d lub łańcuch lub matryca.

Wyjście powinno ponownie mieć ten sam rozmiar i ponownie mieć ten sam kształt, ale z każdym kawałkiem inny kolor lub alternatywnie z białymi liniami oddzielającymi wszystkie kawałki. Warto zauważyć, że nieprostokątny czworokąt można odwrócić.

Piksele na granicy elementów nie muszą dokładnie odpowiadać pikselom na kształcie, również jeśli występują efekty aliasingu lub inne zakłócenia, jest to w porządku.

Przykładowe dane wejściowe i wyjściowe:

Przykłady:

Możliwe rozwiązania:

wada
źródło
Przetwarzanie obrazu jest całkowicie niepotrzebną przeszkodą w tym wyzwaniu. Uważałbym to za znacznie bardziej atrakcyjne, jeśli podałeś dane wejściowe jako małą tablicę binarną.
Sparr
1
Tak jak powiedziałem, zostało to omówione, gdy było w piaskownicy. Wątpię jednak, czy to dodaje dużo bajtów, ponieważ samo zadanie jest znacznie trudniejsze.
flawr
3
Byłem jedną z osób, które zalecały, aby dane wejściowe i wyjściowe były takie, jakie są, i wydałem to zalecenie, ponieważ moim zdaniem jest to najbardziej naturalny i odpowiedni sposób na przedstawienie wyzwania Tangram. Każda forma wejścia / wyjścia zajęłaby znaczną liczbę bajtów, więc nie sądzę, że to naprawdę problem.
El'endia Starman
1
Zgadzam się z Elendią. Jedynym problemem związanym z graficznym We / Wy jest to, że może ograniczać języki, które nie mają funkcji graficznych. To powiedziawszy, PBM i PGM są tak bliskie sztuce ASCII, że nie ma prawdziwego problemu, JEŚLI ludzie zdają sobie sprawę z takich formatów. en.wikipedia.org/wiki/Netpbm_format
Level River St
1
@LevelRiverSt To dobra uwaga, myślę, że byłoby całkowicie akceptowalne użycie tych formatów, a nawet np. Tablicy 2d / ciąg zer i jedynek.
flawr

Odpowiedzi:

31

BBC BASIC, 570 514 490 bajtów ASCII

Pobierz tłumacza na http://www.bbcbasic.co.uk/bbcwin/download.html

435 bajtów tokenizowanych

Pełny program wyświetla dane wejściowe z L.bmpekranu, a następnie modyfikuje je, aby znaleźć rozwiązanie.

*DISPLAY L
t=PI/8q=FNa(1)
DEFFNa(n)IFn=7END
LOCALz,j,p,i,c,s,x,y,m,u,v
F.z=0TO99u=z MOD10*100v=z DIV10*100ORIGINu,v
F.j=0TO12S.4p=0F.i=j+3TOj+9S.2c=9*COS(i*t)s=9*SIN(i*t)p=p*4-(POINT(c,s)<>0)*2-(POINT(9*c,9*s)<>0)N.
m=n:IFn=5A.(43A.p)=0p=0m=7
IF(ASCM."??O|(C",n)-64A.p)=0THEN
F.i=-1TO0GCOL0,-i*n:c=99*COS(j*t)s=99*SIN(j*t)y=402/3^m MOD3-1MOVE-c-s*y,c*y-s:x=n<3MOVEc*x-s*x,s*x+c*x:x=2778/3^m MOD3-1y=5775/3^m MOD3-1PLOT85-32*(n MOD6>3),c*x-s*y,s*x+c*y:IFi q=FNa(n+1)ORIGINu,v
N.
ENDIF
N.N.=0

Wyjaśnienie

Zauważ, że w podstawowym BBC odległość 1 piksel = 2 jednostki, więc siatka 50 x 50 pikseli staje się siatką 100 x 100.

Używamy funkcji rekurencyjnej, aby umieścić 2 duże trójkąty, średni trójkąt, kwadrat i równoległobok w kształcie. Wcześniejszy kształt na liście jest rysowany przed wykonaniem następnego połączenia rekurencyjnego. jeśli wywołanie rekurencyjne powróci bez znalezienia rozwiązania, wcześniejszy kształt zostanie naszkicowany na czarno i wypróbowana zostanie nowa pozycja wcześniejszego kształtu.

Po narysowaniu tych pięciu kształtów umieszczenie dwóch małych trójkątów jest już tylko formalnością. Konieczne jest jednak narysowanie jednego z nich, aby je rozróżnić, jeśli mają wspólną krawędź. Kolorujemy tylko jeden z dwóch małych trójkątów. Drugi pozostawia naturalną czerń.

Próbuje się umieścić każdy kształt przy różnych współrzędnych x, y i 4 różnych obrotach. Aby sprawdzić, czy jest wolna przestrzeń do narysowania kształtu, korzystamy z poniższego szablonu z kątami 45 stopni. Obroty są wykonywane wokół, *a 8 badanych pikseli znajduje się w 2 półkolach o promieniu 9 i 81 jednostek i spada na linie promieniujące w nieparzystych wielokrotnościach 22,5 stopni względem osi xiy.

W przypadku dużego trójkąta należy wyczyścić wszystkie 8 spacji. W przypadku innych kształtów tylko niektóre komórki muszą być czyste, aby zastosować maskę.

+----+----   Shape             Mask HGFEDCBA Mask decimal 
|\ E/|\G /  
| \/F|H\/    1,2. Large triangle    11111111    -1
|C/\ | /     3. Med triangle        00001111    15
|/ D\|/      4. Square              00111100    60
+----*       5. Parallelogram       11101000   -24
|\ B/        6. Small triangle      00000011     3
|A\/         7. Parallogr reversed  00101011    43
| /          Note: reversed parallelogram is checked/drawn at recursion depth n=5
|/           with a special check, but the coordinates are encoded as m=7.  

Po ustaleniu, że kształt będzie pasował, należy go narysować. Jeśli jest to trójkąt, na którym jest drukowany PLOT 85, jeśli jest to równoległobok, liczba jest o 32 wyższa (zwróć uwagę, że dla PLOTcelów uważamy kwadrat za specjalny równoległobok). W obu przypadkach należy podać 3 kolejne wierzchołki. Drugi wierzchołek jest początkiem kształtu (zaznaczonego *w powyższej tabeli), z wyjątkiem dużego trójkąta, w którym (przed obrotem) jest -1,-1.. Pozostałe 2 wierzchołki mogą mieć współrzędne xiy, -1,0 or 1które są uzyskiwane z podstawy 3 zakodowane liczby, następnie skalowane o 99 i obracane w razie potrzeby przez transformację za pomocą ci s.

Nieskluczony kod

  *DISPLAY L
  t=PI/8                                          :REM Constant 22.5 degrees.
  q=FNa(1)                                        :REM Call function, return dummy value to q
  END                                             :REM End the program gracefully if no solution. Absent in golfed version.

  DEFFNa(n)                                       :REM Recursive function to place shapes.
  IFn=7END                                        :REM If n=7 solution found, end program.
  LOCALk,z,j,p,i,c,s,x,y,m,u,v                    :REM declare local variables for function.
  k=ASCMID$("??O|(C",n)-64                        :REM Bitmasks for big tri, big tri, med tri, sq, normal paralellogram, small tri.
  FORz=0TO99                                      :REM For each point on the grid
    u=z MOD10*100:v=z DIV10*100                   :REM calculate its x and y coordinates relative to bottom left of screen
    ORIGINu,v                                     :REM and set the origin to this point.
    FORj=0TO12STEP4                               :REM For each rotation 0,90,180,270deg
      p=0                                         :REM assume no non-black pixels found
      FORi=j+3TOj+9STEP2                          :REM test angles of 3,5,7,9 times 22.5 deg anticlockwise from right x axis.
        c=9*COS(i*t)                             :REM Coords of test points at radius ll
        s=9*SIN(i*t)
        p*=4                                      :REM Leftshift any existing data in p
        p-=(POINT(c,s)<>0)*2+(POINT(9*c,9*s)<>0)  :REM and check pixels at radius 11 and 99.
      NEXT
      m=n                                         :REM The index of the shape to plot normally corresponds with recursion depth n.
      IF n=5 AND (43ANDp)=0 p=0:m=7               :REM If n=5 check if a reverse parallelogram is possible (mask 43). If so, clear p and change m to 7.
      REM                                         :REM Check p against mask k, if the shape fits then...
      IF (k ANDp)=0 THEN
        FOR i=-1 TO 0                               :REM draw the shape in colour, and if deeper recursions prove unsuccesful, redraw it in black.
          GCOL0,-i*n                                :REM Colour is equal to n.
          c=99*COS(j*t)                             :REM Set parameters c and s for scaling by 99
          s=99*SIN(j*t)                             :REM and rotation by 0,90,180 or 270 as appropriate.
          x=-1                                      :REM For vertex 1, x=-1 always.
          y=402/3^m MOD3-1                          :REM Lookup y value for vertex 1.
          MOVEc*x-s*y,s*x+c*y                       :REM Use c and s to transform the vertex and move to it.
          x=n<3                                     :REM For vertex 2, coords are 0,0 except for large triangle where they are -1,-1
          y=x                                       :REM in BBC BASIC, TRUE=-1
          MOVEc*x-s*y,s*x+c*y                       :REM Use c and s to transform the vertex and move to it.
          x=2778/3^m MOD3-1                         :REM Lookup x and y value for vertex 3.
          y=5775/3^m MOD3-1                         :REM PLOT85 uses last 2 points + specified point to make triangle, PLOT85+32 makes paralelogram (or square.)
          PLOT85-32*(n MOD6>3),c*x-s*y,s*x+c*y      :REM Use c and s to transform the vertex and draw shape.
          IFi q=FNa(n+1):ORIGINu,v                  :REM If i=-1 recurse to next level. If it fails, reset the origin before replotting this level's shape in black.
        NEXT
      ENDIF
    NEXT
  NEXT
  =0                                                :REM Dummy value to return from function

Wydajność

Jest to montaż rozwiązań znalezionych przez program dla przypadków testowych. Zastosowanie 99 zamiast 100 ze względów golfowych pozostawia niewielkie czarne luki. Ponieważ kształty są przerysowywane podczas wyszukiwania, w niektórych przypadkach może potrwać kilka sekund, a oglądanie ich jest dość fascynujące.

wprowadź opis zdjęcia tutaj

Level River St
źródło
4
Wow jestem pod wrażeniem. Teraz chciałbym zobaczyć film z tego w akcji! =)
wada