Kisi bisa melengkung. Berapa lama milikmu?

12

Pertimbangkan untuk menggambarkan kurva dua dimensi yang sederhana , terbuka , pada W lebar dengan H grid teks tinggi di mana Xmerupakan bagian dari kurva dan .mewakili ruang kosong dan tidak ada karakter lain yang digunakan.

Setiap ruang grid memiliki 8 ruang grid tetangga, lingkungan Moore -nya . Ruang kotak di luar batas dianggap kosong.

Kotak berisi kurva jika memiliki tepat satu X ATAU jika memiliki lebih dari satu Xtempat:

  • Tepatnya dua Xs hanya memiliki satu tetangga X. Ini adalah titik akhir kurva.
  • Setiap Xselain titik akhir tetangga tepat dua Xs. Ini membentuk sebagian besar kurva.

Misalnya, kisi ini di mana W = 9 dan H = 4 berisi kurva:

....X....
.X.X.X.X.
X..X..X.X
.XX.....X

Demikian juga, kisi-kisi ini (W = 4, H = 3) memiliki kurva:

....  .X..  ....  ....  .X.X
....  X..X  ..X.  XX..  X.X.
..X.  .XX.  .X..  ....  ....

Namun kisi-kisi ini tidak mengandung kurva:

....  .XX.  ...X  XX..  ....  X.X.
....  X..X  ..XX  XX..  .X.X  .X..
....  .XX.  .X..  ....  ...X  X.X.

Kita dapat menemukan panjang kurva dengan menjumlahkan jarak antara semua pasangan tetangga Xs:

  • Jarak antara dua Xs yang bertetangga secara orthogonal adalah 1 unit.

    XX
    X
X

  • Jarak antara dua Xs diagonal yang bersebelahan adalah √2 unit.

    X.
.X
    .X
X.

Misalnya panjang kurva di kisi

XXX.
...X
..X.

dapat divisualisasikan sebagai

contoh panjang

jadi kita bisa melihatnya 1 + 1 + √2 + √2 = 4.828427 ...

Panjang kurva dengan hanya satu Xadalah nol.

Ketika kisi tidak membentuk kurva, panjangnya tidak didefinisikan dengan baik.

Tantangan

Diberi kisi-kisi teks Xs dan .s, mengeluarkan panjang kurva yang dikandungnya, atau menampilkan sesuatu seperti -1atau Nulluntuk menunjukkan kisi tidak memiliki kurva.

Untuk input Anda dapat menggunakan karakter lain selain Xdan .jika diinginkan, dan H dan W dapat diambil sebagai input jika diperlukan. Input sebagai daftar bersarang atau matriks diisi dengan 1s dan 0s sebagai ganti string juga baik-baik saja.

Anda dapat menampilkan pelampung untuk panjang kurva atau alternatif dua bilangan bulat A dan B di mana length = A + B*√2.

Kode terpendek dalam byte menang.

Uji Kasus

XXX.
...X
..X.
2 + 2*√2 = 4.828427...

....X....
.X.X.X.X.
X..X..X.X
.XX.....X
3 + 8*√2 = 14.313708...

....
....
..X.
0 + 0*√2 = 0

.X..
X..X
.XX.
1 + 3*√2 = 5.242640...

....
..X.
.X..
0 + 1*√2 = 1.414213...

....
XX..
....
1 + 0*√2 = 1

.X.X
X.X.
....
0 + 3*√2 = 4.242640...

....
....
....
....
-1

.XX.
X..X
.XX.
-1

...X
..XX
.X..
-1

....
.X.X
...X
-1

X.X.
.X..
X.X.
-1
code-golf arithmetic geometry grid graph-theory Hobi Calvin
sumber
Saya sarankan mengizinkan pemecah untuk memilih format output mereka untuk kisi-kisi yang tidak memiliki kurva (nilai konsisten apa pun yang bukan dari bentuk m + n * sqrt (2) untuk m apa pun, n≥0).
Greg Martin
@Reg Terdengar baik. Selesai
Hobi Calvin
[x.x,...,.x.]bukan kurva yang valid, bukan?
Magic Octopus Urn
@carusocomputing benar
Hobi Calvin

Jawaban:

3

MATL , 52 51 byte

t2Y6~Z+*ssGt3Y6Z+*tt1=z2=wssGzqE=*Gz1=+?}_q]ssy-h2/

Input adalah matriks nol dan satu.

Outputnya B, kalau begitu A. Non-kurva memberi negatif A.

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

Menghitung panjang kurva menggunakan dua konvolusi 2D 1 : satu dengan topeng Moore, dan yang lainnya dengan topeng yang hanya berisi tetangga diagonal. Hasilnya adalah dua matriks dengan ukuran input yang sama, yang akan dilambangkan sebagai M dan D masing-masing. M memberikan jumlah total tetangga untuk setiap titik, sedangkan D memberikan jumlah tetangga diagonal.

Hasil dalam M dan D harus disaring untuk membuang titik yang bukan milik kurva. Juga, mereka harus dibagi dengan 2, karena "menjadi tetangga" adalah hubungan simetris, sehingga setiap titik dalam kurva dihitung dua kali.

Menentukan apakah kurva valid lebih rumit dari yang saya harapkan. Untuk melakukan ini, kode menguji tiga kondisi:

  1. Apakah jumlah yang ada di M sama 2? (Yaitu, apakah benar dua poin dengan satu tetangga?)
  2. Apakah jumlah total M sama dengan jumlah poin dalam kurva input 2minus 2? (Bersama dengan kondisi 1, ini menguji jika semua nilai non-nol dalam M kecuali dua di antaranya sama 2)
  3. Apakah kurva input berisi satu titik?

Kurva valid jika kondisi 1 dan 2 benar, atau jika kondisi 3 adalah.

t       % Implicit input matrix of zeros and ones. Duplicate
2Y6~    % Push [1 0 1; 0 0 0; 1 0 1]
Z+      % 2D convolution, keeping size
*       % Multiply to zero out results for non-curve points. Gives matrix D
ss      % Sum of matrix D
Gt      % Push input again wtice
3Y6     % Push [1 1 1; 1 0 1; 1 1 1]
Z+      % 2D convolution, keeping size
*       % Multiply to zero out results for non-curve points. Gives matrix M
tt      % Duplicate twice
1=z     % Number of ones
2=      % Does it equal 2? This is condition 1
wss     % Swap. Sum of matrix
G       % Push input again
zqE     % Number of nonzeros values minus 1, and then multiplied by 2
=       % Are they equal? This is condition 2
*       % Multiply. This is a logical AND of conditions 1 and 2
G       % Push input again
z1=     % Does it contain exactly one nonzero value? This is condition 3
+       % Add. This is a logical OR with condition 3
?}      % If result was false
  _q    %   Negate and subtract 1. This makes sure we get a negative value
]       % End
ss      % Sum of matrix M
y       % Duplicate sum of matrix D from below
-       % Subtract
h       % Concatenate horizontally
2/      % Divide by 2. Implicitly display

1 Konvolusi adalah kunci kesuksesan .

Luis Mendo
sumber
1

Python 3 , 316 315 311 byte

Saya pikir ini mencakup semua kasus; setidaknya test case berfungsi.

Selain itu, pasti masih banyak yang bisa dimainkan, mungkin pada awalnya di mana kasus tepi ditangani.

def f(d,R,C):
 s=sum;d=[0]*(C+2),*[[0,*r,0]for r in d],[0]*(C+2);o=-1,0,1;k=[[[(1,0),(0,1)][i*j]for i in o for j in o if d[r+i][c+j]and i|j]for c in range(1,-~C)for r in range(1,-~R)if d[r][c]];w=[x/2for x in map(s,zip(*s(k,[])))]or[0,0];print([w,-1][s(w)!=s([s(z)for z in d])-1or[len(t)for t in k].count(1)>2])

Cobalah online!

Bagaimana itu bekerja:

  1. d,R,C adalah 1. daftar daftar dengan 1 sebagai kurva dan 0 sebagai latar belakang, 2. jumlah baris dan kolom
  2. Masukkan baris 0 sebelum dan sesudah dan kolom 0 sebelum dan sesudah dsehingga kita tidak perlu khawatir tentang tepi array 2d
  3. Untuk setiap 1 dalam array 2d, pindai lingkungan untuk 1's dan tambahkan (1,0) ke daftar jika relasinya diagonal, kalau tidak tambahkan (0,1)
  4. Jumlahkan semua tupel, sehingga (n, m) masing-masing mewakili jumlah tetangga diagonal dan non-diagonal
  5. Periksa apakah jumlah hubungan persis jumlah 1 minus satu; jika tidak, bukan kurva.

Terima kasih kepada @Helka Homba karena menunjukkan kasing yang hilang. Terima kasih kepada @TuukkaX dan @Trelzevir untuk tips golfnya.

sungai nil
sumber
Sepertinya d=[[1,0,1],[0,1,0],[1,0,1]]akan gagal di sini (tambah testcase).
Calvin Hobbies
@HelkaHomba Anda benar, saya mengawasi itu. Terima kasih! Perbaiki (sekarang sayangnya dengan lebih banyak byte).
nil
1
s=summenghemat 4 byte.
Trelzevir
0

Mathematica, 153 150 byte

Switch[Sort[Join@@BlockMap[If[#[[2,2]]<1,Nothing,Tr[Tr/@#]]&,#~ArrayPad~1,{3,3},1]],{1},0,{2,2,3...},1/.#~ComponentMeasurements~"PolygonalLength",_,]&

Mengambil array 2D, dengan 0s untuk .s dan 1s untuk Xs. Output Nulluntuk non-kurva.

1/.#~ComponentMeasurements~"PolygonalLength"&

Mathematica memiliki built-in 45-byte untuk ini, tetapi output beberapa angka untuk non-kurva dan 1 / sqrt (2) untuk input {{1}}. Memperbaiki biaya 105 byte ini (bisa golf?).

JungHwan Min
sumber