Lokasi Ambigu di Grid

11

Anda memiliki robot kecil dengan empat sensor jarak. Ia tahu tata letak ruangan, tetapi tidak memiliki orientasi selain dapat mengunci ke arah kisi. Anda ingin dapat mengetahui di mana robot didasarkan pada bacaan, tetapi dapat menjadi ambigu karena sensor yang terbatas.

Penjelasan Tantangan

Anda akan diberi tata letak ruangan dan empat pembacaan jarak searah jarum jam memberikan jumlah sel antara Anda dan dinding. Mungkin ada dinding di tengah ruangan dan ujung-ujungnya juga dinding. Robot tidak dapat ditempatkan di atas tembok.

Tujuan Anda adalah membuat daftar semua lokasi di dalam ruangan tempat robot berada yang akan memberikan bacaan yang diberikan. Perlu diingat bahwa robot tidak memiliki orientasi (selain dikunci ke sudut 90 derajat di grid-yaitu robot tidak akan pernah berorientasi secara diagonal atau sudut miring lainnya), sehingga pembacaan [1, 2, 3, 4], misalnya, sama dengan membaca [3, 4, 1, 2].

Contohnya

Untuk contoh ini, koordinat sel akan diberikan sebagai pasangan terindeks 0 (x, y) dari sel kiri atas. Bacaan akan diberikan dalam urutan searah jarum jam dalam daftar kurung siku. Tata letak akan menggunakan tanda pon untuk dinding dan karakter lain (biasanya titik) untuk mewakili sel kosong.

Kasus 1

. . . .
. . . .
. . # .
. . . .
  • [1, 0, 2, 3] ==> (1, 0), (3, 1)
  • [0, 0, 3, 3] ==> (0, 0), (3, 0), (0, 3), (3, 3)
  • [2, 1, 1, 0] ==> (0, 2), (2, 1)
  • [1, 1, 2, 2] ==> (1, 1)

Kasus 2

# a . # a .
a # . . # a
. . # . . #
# . . # . .
a # . . # a
. a # . a #
  • [0, 0, 1, 1] ==> setiap posisi di grid yang merupakan titik
  • [1, 0, 0, 0] ==> semua a ada di grid

Kasus 3

.
  • [0, 0, 0, 0] ==> (0, 0)

Kasus 4

. # #
. . .
  • [1, 2, 0, 0] ==> (0, 1)
  • [0, 1, 2, 0] ==> (0, 1)
  • [0, 0, 1, 0] ==> (0, 0)
  • [1, 0, 1, 0] ==> (1, 1)
  • [0, 1, 0, 1] ==> (1, 1)

Kasus 5

. # . .
. . . .
. . # .
. . . .
  • [2, 1, 1, 0] ==> (0, 2), (2, 1)
  • [0, 2, 2, 1] ==> (1, 1)
  • [1, 0, 2, 2] ==> (1, 1)
  • [0, 3, 0, 0] ==> (0, 0)
  • [1, 0, 1, 1] ==> (1, 2)

Peraturan Lainnya

  • Input mungkin dalam format apa pun yang nyaman. Input adalah kisi-kisi dinding dan spasi dan daftar empat jarak dalam urutan searah jarum jam.
  • Output dapat berupa daftar semua sel yang memenuhi pembacaan atau versi modifikasi dari grid yang menunjukkan sel mana yang memenuhi pembacaan. Format output yang tepat tidak masalah asalkan masuk akal dan konsisten. Format output yang valid termasuk, tetapi tidak terbatas pada :
    • Mencetak garis untuk setiap koordinat sel sebagai pasangan yang dipesan
    • Mencetak kisi-kisi dengan .,, #dan !untuk ruang, dinding, dan lokasi yang memungkinkan, masing-masing.
    • Mengembalikan daftar pasangan yang dipesan
    • Mengembalikan daftar indeks
    • Mengembalikan daftar daftar menggunakan nilai yang berbeda untuk ruang, dinding, dan lokasi yang memungkinkan
    • Kembalikan / cetak matriks 0s dan 1s, menggunakan 1s untuk mewakili sel tempat pembacaan akan terjadi. (Tidak perlu untuk memasukkan dinding)
    • Sekali lagi, daftar ini tidak lengkap, jadi representasi lain valid selama konsisten dan menunjukkan setiap lokasi yang mungkin valid dalam kisi atau daftar. Jika Anda tidak yakin, tinggalkan komentar dan saya akan dengan senang hati menjelaskan.
  • Anda dapat berasumsi bahwa pembacaan berhubungan dengan setidaknya satu lokasi di grid.
  • Anda dapat mengasumsikan bahwa grid input berukuran setidaknya 1x1 dan memiliki setidaknya satu ruang kosong.
  • Anda dapat mengasumsikan bahwa grid input tidak lebih besar dari 256 sel di setiap dimensi.
  • Anda dapat mengasumsikan bahwa kisi input selalu berbentuk kotak sempurna dan tidak bergerigi.
  • Tidak ada penalti atau bonus jika program Anda kebetulan memberikan output yang masuk akal untuk input yang tidak valid.
  • Ini kode golf, jadi kode terpendek menang.
Beefster
sumber
Testcases untuk Case 5tampaknya tidak tepat. Saya mendapatkan (0,2),(2,1), (1,3), (1,3), dan nothing.
TFeld
@Tfeld Terima kasih. Tetap.
Beefster
1
@Arnauld Sepertinya masuk akal bagi saya. Saya akan menambahkannya ke daftar yang sudah tidak lengkap.
Beefster

Jawaban:

3

JavaScript (ES6),  130 128 126  125 byte

(m)(l)m01l

1

m=>l=>m.map((r,y)=>r.map((v,x)=>v&!!([...'3210321'].map(d=>(g=X=>(m[Y+=~-d%2]||0)[X+=(d-2)%2]?1+g(X):0)(x,Y=y))+g).match(l)))

Cobalah online! (dengan output pasca-proses agar mudah dibaca)

Berkomentar

m => l =>                         // m[] = layout matrix; l[] = list of distances
  m.map((r, y) =>                 // for each row r[] at position y in m[]:
    r.map((v, x) =>               //   for each cell v at position x in r[];
      v &&                        //     yield 0 if v = 0
      !!(                         //     otherwise, test whether we can find l[] within a
        [...'3210321']            //     list containing twice the results of the sensors
        .map(d =>                 //       for each direction d:
          (g = X => (             //         g = recursive function taking X
              m[Y += ~-d % 2]     //         add dy[d] to Y
              || 0                //         use a dummy object if we're out of the board
            )[X += (d - 2) % 2] ? //         add dx[d] to X; if (m[Y] || 0)[X] is equal to 1:
              1 +                 //           add 1 to the final result
              g(X)                //           and do a recursive call
            :                     //         else:
              0                   //           yield 0 and stop recursion
          )(x, Y = y)             //         initial call to g with X = x and Y = y
        )                         //       end of map() over directions
        + g                       //       coerce the result to a comma-separated string,
                                  //       followed by harmless garbage
      ).match(l)                  //     test whether l[] can be found in this string
                                  //     (l[] is implicitly coerced to a string as well)
    )                             //   end of map() over r[]
  )                               // end of map() over m[]
Arnauld
sumber
1

Python 2 , 234 202 200 191 byte

lambda m,a:[(i,j)for j,l in e(m)for i,c in e(l)if('#'<c)*[(''.join(L)[::-1]+'#').find('#')for L in l[:i],zip(*m)[i][:j],l[:i:-1],zip(*m)[i][:j:-1]]in[a[q:]+a[:q]for q in 0,1,2,3]]
e=enumerate

Cobalah online!

TFeld
sumber
1

Arang , 42 byte

PθFθ¿⁼¶ι⸿¿№E⁴E⁴⊖⌕⁺⪫KD⊕⌈η✳§⟦→↓←↑⟧⁺κμω#¦#η!ι

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Arang tampaknya menambahkan beberapa padding ke output untuk beberapa alasan; Saya berasumsi itu bug di Charcoal. Penjelasan:

Pθ

Cetak peta tanpa memindahkan kursor.

Fθ

Ulangi setiap karakter di peta.

¿⁼¶ι⸿

Jika itu adalah baris baru, maka pindahkan kursor ke awal baris berikutnya.

⊖⌕⁺⪫KD⊕⌈η✳§⟦→↓←↑⟧⁺κμω#¦#

Temukan jarak ke dinding ke arah k+m.

¿№E⁴E⁴...η!ι

Ulangi keempat arah awal k, mengintip ke empat arah searah jarum jam m, dan jika hasilnya menyertakan input kedua, maka cetak a !jika tidak, cetak karakter saat ini.

Neil
sumber