Alignment pada Triangular Grids

18

Grid heksagonal telah menjadi twist yang cukup populer untuk tantangan tentang data 2 dimensi baru-baru ini. Namun, tampaknya kisi-kisi segitiga yang sama menariknya sebagian besar telah diabaikan sejauh ini. Saya ingin memperbaiki itu dengan tantangan yang agak sederhana.

Pertama, bagaimana kita mewakili kisi segitiga? Pertimbangkan contoh berikut (abaikan diagram kanan untuk saat ini):

masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini

Sel-sel dengan rapi jatuh ke grid biasa (perbedaan ke grid biasa hanya sel mana yang dianggap berdekatan):

1234567
89abcde
fghijkl
mnopqrs

Sekarang, seperti yang ditunjukkan diagram kanan, kisi segitiga memiliki tiga sumbu utama: horizontal dan dua diagonal.

Sorot ini di kisi ASCII:

AVAVAVA
VAabcAV
fVAiAVl
mnVAVrs

Tantangan

Anda diberi string persegi panjang yang mewakili kotak segitiga (di mana sudut kiri atas adalah segitiga yang mengarah ke atas). Sebagian besar sel dengan be ., tetapi tepatnya dua sel akan menjadi #, misalnya:

....#
.#...
.....

Tentukan apakah keduanya #disejajarkan di sepanjang salah satu dari tiga sumbu kisi (yaitu apakah mereka terletak pada satu baris di salah satu dari tiga arah yang disorot di atas). Untuk contoh ini, jawabannya adalah "tidak".

Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).

Input dapat berupa string tunggal yang dibatasi oleh umpan garis atau karakter lain yang sesuai, atau daftar string. Anda dapat menggunakan dua karakter ASCII yang dapat dicetak untuk menggantikan .dan #.

Output harus berupa nilai kebenaran jika sel yang disorot sejajar dan nilai palsu sebaliknya.

Aturan standar berlaku.

Uji Kasus

Kisi kebenaran:

.#..#.

#
#

...........
...#.......
...........
...........
...........
.......#...
...........

...........
.......#...
...........
...........
...........
...#.......
...........

.#.........
...........
...........
...........
...........
.......#...
...........

...........
...#.......
...........
...........
...........
...........
.......#...

.........#.
...........
...........
...........
...........
...#.......
...........

...........
.......#...
...........
...........
...........
...........
...#.......

...........
.#.....#...
...........
...........
...........

Kisi palsu:

#.....
.....#

.....#
#.....

...#.......
...........
...........
...........
...........
.......#...
...........

...........
...#.......
...........
...........
...........
...........
.........#.

.......#...
...........
...........
...........
...........
...#.......
...........

...........
.......#...
...........
...........
...........
...........
.#.........
Martin Ender
sumber

Jawaban:

3

Siput , 40 39 byte

\#{z|=(ul.ul.`,l~a~)(l.a3|.a|d.ea5}.,\#
\ # ,, cocokkan '#'
{
  z | ,, Entah mengubah arah octinilear, atau melakukan semua hal lain sebelum}
  = (,, Jika pernyataan ini berhasil, sel awal adalah "segitiga mengarah ke atas"
    ul.ul.`, ,, Naik satu sel ke atas atau ke kiri dua kali, berapa kali.
              ,, Ini seharusnya satu byte lebih pendek dengan ul.`2, atau ul.`2 +? tapi
              ,, penguraian `adalah buggy.
    l ~ a ~ ,, Pastikan kita berada di sel kiri atas dengan mencocokkan out-of-bounds ke kiri dan kemudian timur laut
  )
  (l.a3 | ,, Pindah ke kiri satu kali, lalu tetapkan arah ke barat laut; atau
    .a | ,, Pindah ke kanan (arah awal) sekali, lalu atur arah ke timur laut; atau
    d.ea5 ,, Bergerak ke bawah sekali, lalu atur arah ke barat laut atau timur laut
}
. ,, ,, Cocokkan sejumlah karakter sewenang-wenang (bergerak ke arah saat ini)
\ # ,, cocokkan '#'
feersum
sumber
2

CJam, 47 byte

Nah, sekarang ada solusi yang lebih pendek. Saya tidak lagi merasa buruk berbagi sendiri. :) (Sebagian besar menunjukkan bahwa ini tidak terlalu sulit, bahkan jika Anda tidak memiliki bahasa pencocokan pola 2D ...)

qN%:eeee::f+:~{S&},2f<:P0f=P::+Xf|P::-Xf|]::=:|

Ini menggunakan ruang di tempat #dan benar-benar apa pun untuk ..

Jalankan semua test case online.

Saya benar-benar benci duplikasi P::+Xf|P::-Xf|tetapi sejauh ini saya belum menemukan apa pun untuk menyingkirkannya.

Penjelasan

Jangan membaca jika Anda ingin mencari solusi untuk diri Anda sendiri.

Pertama, bagian yang membosankan: mendapatkan dua pasangan koordinat dari dua ruang dalam kisi masukan:

qN%   e# Read input and split into lines.
:ee   e# Enumerate the characters in each line. I.e. turn each character 'x into a pair
      e# [N 'x] where N is its horizontal 0-based index.
ee    e# Enumerate the lines themselves, turning each line [...] into [M [...]] where M
      e# is its vertical 0-based index.
::f+  e# This distributes the vertical index over the individual lines, by prepending it
      e# to each pair in that line. So now we've got a 2-D array, where each character 'x
      e# has been turned into [M N 'x].
:~    e# Flatten the outermost dimension, so that we have a flat list of characters with
      e# their coordinates.
{S&}, e# Filter only those lists that contain a space.
2f<   e# Truncate the two results to only their first two elements.
:P    e# Store the result in P.

Sekarang bagian yang menarik adalah bagaimana menentukan apakah koordinat tersebut selaras atau tidak. Kode saya menghitung ketiga sumbu secara terpisah:

  • Sumbu horizontal sepele. Periksa apakah koordinat vertikal cocok.
  • Mari kita lihat diagonal timur laut. Dalam kisi ASCII, selalu ada dua antidiagonal yang dimiliki oleh setiap tri-kisi diagonal:

    ....AV..
    ...AV...
    ..AV....
    

    Kami dapat mengidentifikasi antidiagonal saat ini dengan menjumlahkan xdan ymengoordinasikan:

    01234567
    12345678
    23456789
    

    Jadi kami ingin 0dan 1menjadi bagian dari diagonal yang sama, juga 2dan 3, 4dan 5dan seterusnya. Itu berarti, setelah kami memiliki indeks anti-diagonal kami, kami ingin membulatkan ke angka ganjil berikutnya. Dengan kata lain, kami mengambil bitwise OR dengan 1. (Kita juga bisa membulatkan ke nomor genap berikutnya dengan bitwise DAN dengan -2tetapi itu lebih mahal dalam kode.)

  • Sekarang diagonal tenggara:

    .VA.....
    ..VA....
    ...VA...
    

    Dalam rangka memberikan diagonal indeks, kita kurangi yang xdari y(angka negatif mewakili sebagai huruf) koordinat:

    0abcdefg
    10abcdef
    210abcde
    

    Dalam hal ini, kami ingin 0dan 1menjadi bagian dari diagonal yang sama, serta -1dan -2, atau 2dan 3. Jadi sekali lagi, kami ingin menambah angka ganjil berikutnya.

Ini kode untuk itu:

0f=  e# The coordinates are still on the stack. Replace each with its vertical coordinate
     e# to check for the horizontal axis.
P    e# Push the coordinates again.
::+  e# Sum each pair to get an anti-diagonal index.
Xf|  e# OR each index with 1 to round up to the next odd number.
P    e# Push the coordinates again.
::-  e# In each pair, subtract the horizontal coordinate from the vertical, to
     e# get a diagonal index.
Xf|  e# OR each index with 1.
]    e# Wrap all three index pairs in an array.
::=  e# Check equality for each pair.
:|   e# Fold bitwise OR over the results to check if at least one pair of indices
     e# was equal.
Martin Ender
sumber