The Tangram adalah teka-teki diseksi terbuat dari tujuh bentuk: Lima segitiga berukuran berbeda, genjang dan persegi. Diberikan bentuk, tujuannya adalah menciptakan kembali bentuk menggunakan semua potongan dan tanpa tumpang tindih. Jelas ada banyak cara untuk mengatur set potongan-potongan ini di pesawat. Subset yang menarik adalah

Grid Tangrams

Kita bisa menggambar persegi Tangram "standar" menjadi persegi yang lebih besar yang dibagi lagi oleh sebuah kotak menjadi 16 kotak yang lebih kecil. Tangrams kotak hanya bentuk yang terbuat dari potongan tangram, sehingga semua simpul potongan berada di titik-titik grid.

Ini adalah jenis teka-teki Tangram yang ingin kita pertimbangkan dalam tantangan ini, karena mungkin lebih mudah ditangani daripada yang lebih umum.

Sebagai catatan tambahan: Matematikawan Cina Chuan-Chin Hsiung dan Fu Traing Wang membuktikan pada tahun 1942 bahwa hanya ada 13 tangram cembung. Mereka pertama-tama menunjukkan bahwa masalahnya dapat direduksi menjadi grid tangrams, dan kemudian menggunakan beberapa argumen kombinatorial dan geometris. Ini semua dari 13:

Tantangan

Diberikan tangram grid yang dapat dipecahkan, mengeluarkan pembedahan tangram grid menjadi tujuh potong tangram.

IO

Tangram diberikan sebagai gambar hitam dan putih (bentuknya hitam, latar belakang putih), dengan kedua sisi berlipat 50px. Grid memiliki lebar tepat 50px. Garis kisi paralel dengan sisi gambar.

EDIT: Gambar dapat diterima sebagai input dan dikembalikan sebagai output dalam format gambar raster yang nyaman seperti PNG, TIFF, PBM dll. Tetapi representasi sebagai array 2d biner atau string atau matriks dapat diterima.

Keluaran harus lagi memiliki ukuran yang sama dan harus memiliki lagi bentuk yang sama, tetapi dengan masing-masing bagian warna yang berbeda, atau sebagai alternatif dengan garis putih yang memisahkan semua bagian. Perlu dicatat bahwa segi empat yang tidak persegi dapat dibalik.

Pixel pada batas potongan tidak harus benar-benar cocok dengan yang ada di bentuk, juga jika ada efek aliasing atau fuzz lain ini masih ok.

Contoh Input dan Output:

Contoh:

Solusi yang memungkinkan:

BBC BASIC, 570 514 490 byte ASCII

Unduh juru bahasa di http://www.bbcbasic.co.uk/bbcwin/download.html

435 byte dibatalkan

Program lengkap menampilkan input dari L.bmplayar, lalu memodifikasinya untuk menemukan solusi.

*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

Penjelasan

Perhatikan bahwa di dasar BBC jarak 1 piksel = 2 unit, sehingga kisi 50x50 piksel menjadi kisi 100x100.

Kami menggunakan fungsi rekursif untuk menempatkan 2 segitiga besar, segitiga sedang, persegi dan jajaran genjang ke dalam bentuk. Bentuk sebelumnya dalam daftar dibuat sebelum panggilan rekursif berikutnya dibuat. jika panggilan rekursif kembali tanpa menemukan solusi, bentuk sebelumnya ditarik dalam warna hitam dan posisi baru bentuk sebelumnya akan dicoba.

Setelah lima bentuk ini digambar, menempatkan dua segitiga kecil hanyalah formalitas. Adalah perlu untuk menggambar salah satu dari mereka, untuk membedakan mereka jika mereka memiliki keunggulan bersama. Kami hanya mewarnai salah satu dari dua segitiga kecil. Yang lainnya dibiarkan hitam alami.

Penempatan setiap bentuk dicoba pada koordinat x, y yang berbeda dan dalam 4 rotasi yang berbeda. Untuk menguji apakah ada ruang kosong untuk menggambar bentuk, kami menggunakan templat di bawah ini, dengan sudut 45 derajat. Rotasi dibuat tentang *dan 8 piksel yang diuji berada dalam 2 setengah lingkaran dari jari-jari 9 dan 81 unit dan jatuh pada garis yang terpancar pada kelipatan ganjil 22,5 derajat ke sumbu x dan y.

Untuk segitiga besar, semua 8 ruang harus jelas. Untuk bentuk lain hanya beberapa sel yang harus jelas sehingga masker diterapkan.

+----+----   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.  

Setelah ditetapkan bahwa suatu bentuk akan cocok, itu harus ditarik. Jika itu adalah segitiga yang diplot dengan PLOT 85, jika itu adalah jajaran genjang, angkanya 32 lebih tinggi (perhatikan bahwa untuk PLOTtujuan kami menganggap kuadrat sebagai jajar genjang khusus). Dalam kedua kasus, 3 simpul berurutan harus diberikan. Vertex kedua adalah asal dari bentuk (ditandai *dalam tabel di atas) kecuali dalam kasus segitiga besar, di mana (sebelum rotasi) itu adalah -1,-1.2 simpul lainnya dapat memiliki koordinat x dan y -1,0 or 1yang diekstraksi dari basis 3 angka yang disandikan, kemudian diskalakan dengan 99 dan diputar seperlunya dengan transformasi dengan cdan s.

Kode tidak dikunci

  *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

Keluaran

Ini adalah montase dari solusi yang ditemukan oleh program untuk kasus uji. Penggunaan 99 bukannya 100 karena alasan golf menyisakan beberapa celah hitam kecil. Karena bentuk digambar ulang selama pencarian, dibutuhkan beberapa detik untuk menjalankan beberapa kasus, dan cukup menarik untuk ditonton.