Kisi Segitiga: Poliamond Yang Terhubung Secara Sederhana

9

Sementara kami menggunakan tendangan grid segitiga , saya ingin menunjukkan bahwa ada yang setara dengan polyomino pada grid segitiga. Mereka disebut poliamond , dan mereka adalah bentuk yang dibentuk dengan menempelkan segitiga sama sisi di sepanjang tepinya. Dalam tantangan ini, Anda akan menentukan himpunan bagian dari kisi segitiga yang merupakan poliamond, dan apakah ada lubang di dalamnya. Karena hanya membutuhkan 9 segitiga untuk membuat polyiamond dengan lubang di dalamnya, kode Anda harus sesingkat mungkin.

Grid

Kami akan menggunakan tata letak kotak segitiga Martin untuk input:

kotak segitiga

Perhatikan fakta bahwa pusat-pusat segitiga membentuk kotak persegi panjang kasar dan bahwa segitiga kiri atas "menunjuk" ke atas. Kita dapat menggambarkan subset dari kisi ini, kemudian, dengan memberikan "peta bintang" persegi panjang yang mengindikasikan segitiga mana yang dimasukkan dan mana yang tidak termasuk. Misalnya, peta ini:

** **
*****

sesuai dengan poliamond terkecil yang mengandung lubang:

9-iamond dengan lubang

Lubang

Sebuah polyiamond yang berisi sebuah lubang seperti contoh di atas (daerah bukan bagian dari polyiamond, yang dikelilingi oleh daerah yang berada ) tidak, topologi berbicara, hanya terhubung .

Tantangan

Tulis fungsi atau program yang mengambil input "peta bintang" seperti yang dijelaskan di atas dan menampilkan kebenaran jika dan hanya jika subset yang ditunjukkan dari grid segitiga adalah poliamond yang terhubung sederhana .

Lebih banyak contoh

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

sesuai dengan polyiamond

13-iamond tanpa lubang

yang hanya terhubung.


*   *
** **
 ***

sesuai dengan polyiamond

9-iamond tanpa lubang

yang hanya terhubung.


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

sesuai dengan non- polyiamond

13 segitiga yang tidak menarik

yang tidak akan hanya terhubung bahkan jika itu adalah polyiamond.

Input Spec

  • Input hanya akan terdiri dari tanda bintang, spasi, dan umpan baris.
  • Karakter input pertama akan selalu berupa spasi atau tanda bintang (sesuai dengan segitiga pengarah ke atas di sudut kiri atas kisi).
  • Akan selalu ada setidaknya satu tanda bintang di baris pertama dan terakhir.
  • Tidak ada jaminan bahwa baris setelah baris pertama tidak akan kosong. Dua umpan baris dalam satu baris dapat muncul di input yang sah.
  • Panjang garis tidak harus sama.

Kondisi Menang

Ini adalah , jadi jawaban tersingkat dalam byte menang.

Uji Kasus

Peta Truthy:

1) *

2) *
   *

3) **

4) *** ***
   *******

5) *   *
   ** **
    ***

6) *
   **
    *

7)    **
     ***
   ****

8) ****
   **   *
    *****

9) ***********
   **    **  **
    ****  **  **
              **
   ************

Peta Falsy:

1) *
   *
   *

2) * *

3) *
    *

4)  **
   **

5) ***

   ***

6) ** **
   *****

7) **  **
   *** **
    ****

8)  *
    *

9) *****
   **   *
    *****
kuintopia
sumber
1
pertanyaan yang bagus Jika kisi-kisi segitiga akan menjadi sesuatu, bolehkah saya menyarankan agar mereka direpresentasikan sebagai contoh AV VA\nVAVAValih-alih ** **\n*****karena memudahkan manusia untuk memvisualisasikan. Saya sudah melakukan edit ke salah satu diagram ASCII Martin.
Level River St
Saya tidak terlalu peduli dengan keterbacaan manusia, tidak. Saya ingin melakukan apa pun yang lebih mudah bagi sebuah program untuk membaca sambil tetap kecil.
kuintopia
Jadi pada dasarnya, jika iff ada bagian hanya "terhubung" oleh sudut?
Michael Klein
1
Atau jika ada bagian yang tidak terhubung sama sekali. Martin mengatakan begini: Benar jika sosok dan tanah keduanya terhubung di sepanjang tepi, sehingga 2 isian banjir cukup untuk mewarnai ulang pesawat.
kuintopia

Jawaban:

4

Siput , 95 byte

F&
lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}\*}+l\ ,~a~|{\ (lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}+~

Ini benar-benar menderita duplikasi, karena saya belum menerapkan makro atau referensi balik apa pun. Apa yang dilakukannya adalah memeriksa bahwa untuk setiap bintang, ada jalur ke bintang paling kiri di baris atas; dan untuk setiap ruang, ada jalur ke tepi kisi.

F&                         ,, option F: pad lines with spaces to the length of the longest
                           ,, option &: print 1 iff match succeeds from every cell
lr                         ,, direction left or right, or
      | =((ul.)2 ,l~a~) d  ,, direction down, if we are an even number of orthogonal moves from the top left
      | !((ul.)2 ,l~a~) u  ,, or, direction up if we are odd number of moves from the top left
    }  \*                  ,, literal '*'
}+                         ,, 1 or more times
l\ ,~a~                    ,, check that we are on the leftmost * in the top line

|                          ,, the part before this is for starting on '*'; part after for starting on ' '

{ \                        ,, literal ' '
    (   lr                 ,, direction left or right, or
      | =((ul.)2 ,l~a~) d  ,, same drill as before...
      | !((ul.)2 ,l~a~) u 
}+                         ,, 1 or more times
~                          ,, end on an out of bounds cell
feersum
sumber
Saya tidak mengerti cara kerjanya, tapi itu benar-benar berfungsi.
kuintopia
3

CJam, 101 98 byte

qN/_z,f{' e]}{S2*f+W%z}4*:eeee::f+:~{_(aL{+_{_2,.+1$2,.-@_:+1&!2*(a.+}%2${a1$&},\;@1$-@@}h;\;-}2*!

Cobalah online.

Saya akhirnya mengatasi ketakutan saya menerapkan banjir mengisi CJam. Ini tentang jelek seperti yang saya harapkan, dan itu pasti bisa golf.

Gagasan umumnya adalah melakukan dua pengisian banjir (yang sebenarnya diimplementasikan sebagai pemindahan dari daftar sel yang belum dikunjungi). Lulus pertama akan menghapus semua ruang yang dapat dijangkau dari tepi. Lulus kedua kemudian akan memilih yang pertama *dalam urutan membaca dan menghapus semua segitiga yang bisa dijangkau dari itu. Jika dan hanya jika daftar yang dihasilkan kosong, poliamond itu hanya terhubung:

  • Jika polyiamond memiliki lubang, pengisian banjir pertama tidak dapat mencapai dan menghapus lubang itu.
  • Jika input terdiri dari beberapa polyiamond yang terputus, pengisian banjir kedua tidak dapat mencapai dan menghapus semuanya.
Martin Ender
sumber