Tolong, saya terjebak di pabrik yang tak terbatas!

26

Tantangan ini secara longgar terinspirasi oleh permainan Zachtronics Infinifactory .

Anda diberi tampilan top-down dari grid konveyor persegi panjang, diwakili oleh >v<^. Mungkin ada sel tanpa konveyor, diwakili oleh spasi. Berikut ini sebuah contoh:

> <vv    <
 v ^ >v v 
  >v^^>vv^
    ^>^ v 
>  v<v  >>
  >v v<^  

Pengaturan ini secara implisit dikelilingi oleh jumlah ruang yang tak terbatas.

Selanjutnya, Anda diberi dimensi selembar kargo persegi panjang yang ditempatkan di konveyor di sudut kiri atas kisi. Tugas Anda adalah untuk mencari tahu apakah kargo pernah datang untuk beristirahat atau apakah akan berakhir bergerak dalam satu lingkaran.

Tentu saja, kargo kemungkinan akan mencakup beberapa konveyor sekaligus, jadi berikut adalah aturan untuk mengetahui arah kargo di setiap langkah:

  1. Saling berlawanan membatalkan satu sama lain. Jadi jika kargo 3x2 mencakup salah satu tambalan berikut (diuraikan dengan tanda hubung dan pipa untuk kejelasan), hasilnya akan sama:

    +---+   +---+   +---+
    |>>^|   |  ^|   |v^^|
    |^<<|   |^  |   |^^v|
    +---+   +---+   +---+
    

    Hal yang sama berlaku untuk ini:

    +---+   +---+   +---+
    |v^<|   |   |   |><>|
    |>>>|   |>> |   |>><|
    +---+   +---+   +---+
    

    Karena posisi tepat konveyor di bawah kargo tidak relevan, tidak masalah pasangan mana yang Anda batalkan.

    Pembatalan ini diterapkan sebelum aturan lainnya. Oleh karena itu, untuk aturan lainnya hanya akan ada konveyor paling banyak di dua arah.

  2. Jika kargo sama sekali tidak mencakup konveyor (baik karena semua konveyor dibatalkan, karena hanya mencakup ruang atau karena sepenuhnya bergerak dari grid), maka ia akan beristirahat.
  3. Jika kargo mencakup lebih banyak konveyor dari satu arah daripada yang lain, kargo bergerak ke arah itu. Misalnya, jika kargo 3x2 menutupi tambalan berikut

    >>
    ^>^
    

    itu akan bergerak ke kanan, karena ada lebih >dari ^. Di sisi lain, jika tertutup

    >>^
      ^
    

    aturan ini tidak akan berlaku, karena ada ikatan antara >dan ^.

  4. Ini hanya menyisakan kasus di mana ada ikatan antara arah yang berdekatan (dasi antara arah yang berlawanan akan dibatalkan). Dalam hal ini, kargo terus bergerak sepanjang sumbu yang sudah bergerak masuk. Misalnya jika kargo 3x2 yang bergerak ke kanan atau ke kiri sekarang menutupi tambalan

    >>^
    ^  
    

    itu akan bergerak ke kanan. Jika tiba di tambalan ini bergerak ke atas atau ke bawah, sekarang akan pindah ke atas. Jika konflik semacam ini terjadi pada langkah pertama simulasi, anggaplah bahwa kargo telah bergerak ke kanan.

Contoh terperinci

Pertimbangkan grid konveyor di bagian atas dan kargo 3x2. Berikut ini adalah visualisasi langkah demi langkah proses. Setiap langkah terdiri dari kisi, dengan muatan diwakili oleh #, sebuah kotak kecil yang menunjukkan konveyor yang dicakup oleh kargo, kotak lain dengan konveyor setelah pembatalan, dan aturan yang menentukan kemana kargo bergerak:

 ###vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <
 ###^ >v v     ###^ >v v      v ^ >v v      v ^ >v v      v ^ >v v      v ^ >v v 
   >v^^>vv^    ###v^^>vv^    ###v^^>vv^     ###^^>vv^      ###^>vv^      >###>vv^
     ^>^ v         ^>^ v     ### ^>^ v      ###^>^ v       ###>^ v        ###^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>
   >v v<^        >v v<^        >v v<^        >v v<^        >v v<^        >v v<^  

+---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+
|> <|  |   |  | v |  | v |  |  >|  |  >|  | >v|  | >v|  |>v^|  |> ^|  |v^^|  | ^^|
| v |  | v |  |  >|  |  >|  |   |  |   |  |   |  |   |  |  ^|  |   |  | ^>|  |  >|
+---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+

   Rule 3        Rule 4        Rule 3        Rule 4        Rule 4        Rule 3

 ================================================================================

 > <vv    <    > <###   <    > <vv    <
  v ###v v      v ###v v      v ###v v 
   >###>vv^      >v^^>vv^      >###>vv^
     ^>^ v         ^>^ v         ^>^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>
   >v v<^        >v v<^        >v v<^  

+---+  +---+  +---+  +---+  +---+  +---+
|^ >|  |  >|  |vv |  | v |  |^ >|  |  >|
|v^^|  | ^^|  |^ >|  |  >|  |v^^|  | ^^|
+---+  +---+  +---+  +---+  +---+  +---+

   Rule 3        Rule 4        Rule 3

Pada titik ini, kargo memasuki lingkaran antara dua frame terakhir.

Sekarang pertimbangkan kargo 2x3 sebagai gantinya:

 ##<vv    <    >##vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <
 ## ^ >v v      ##^ >v v      ##^ >v v      v ^ >v v      v ^ >v v      v ^ >v v 
 ##>v^^>vv^     ##v^^>vv^     ##v^^>vv^     ##v^^>vv^      ##^^>vv^      >v^^>vv^
     ^>^ v         ^>^ v      ## ^>^ v      ## ^>^ v       ##^>^ v       ##^>^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>    >##v<v  >>    > ##<v  >>    > ##<v  >>
   >v v<^        >v v<^        >v v<^        >v v<^        >v v<^        ## v<^  

 +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+
 |> |  |> |    | <|  |  |    |v |  |v |    | >|  | >|    |>v|  |>v|    |  |  |  |
 | v|  | v|    |v |  |v |    | >|  | >|    |  |  |  |    |  |  |  |    | v|  | v|
 |  |  |  |    | >|  |  |    |  |  |  |    |  |  |  |    | v|  | v|    |>v|  |>v|
 +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+

   Rule 4        Rule 3        Rule 4        Rule 3        Rule 3        Rule 3

 ================================================================================

 > <vv    <    > <vv    <    > <vv    <
  v ^ >v v      v ^ >v v      v ^ >v v 
   >v^^>vv^      >v^^>vv^      >v^^>vv^
     ^>^ v         ^>^ v         ^>^ v 
 > ##<v  >>    >  v<v  >>    >  v<v  >>
   ## v<^        ## v<^        >v v<^  
   ##            ##            ##
                 ##            ##
                               ##

 +--+  +--+    +--+  +--+    +--+  +--+
 | v|  | v|    |>v|  |>v|    |  |  |  |
 |>v|  |>v|    |  |  |  |    |  |  |  |
 |  |  |  |    |  |  |  |    |  |  |  |
 +--+  +--+    +--+  +--+    +--+  +--+

   Rule 3        Rule 4        Rule 2

Pada langkah terakhir, aturan 2 berlaku karena kargo telah pindah dari grid, sehingga ia beristirahat dan tidak akan ada loop.

Aturan dan Asumsi

Input Anda akan menjadi grid konveyor seperti yang dijelaskan di atas bersama dengan lebar dan tinggi kargo. Anda dapat mengambil ketiga parameter ini dalam urutan dan format yang mudah. Untuk kisi, ini berarti Anda dapat membaca string tunggal dengan garis yang dipisahkan oleh baris baru atau karakter lain, atau array string, atau array array karakter, selama masing-masing sel grid masih diwakili oleh karakter >v<^dan spasi.

Anda harus menampilkan nilai kebenaran jika hasil pengaturan dalam loop setidaknya dua frame atau nilai palsu jika kargo akan datang untuk beristirahat.

Anda dapat berasumsi bahwa kisi-kisi akan diisi ke sebuah persegi panjang dengan ruang, dan bahwa kargo pada awalnya akan masuk ke dalam kisi.

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

Ini kode golf, jadi jawaban tersingkat (dalam byte) menang.

Uji Kasus

Kasing uji dikelompokkan berdasarkan kisi-kisi.

Grid (2x2):

>v
^<

Width  Height  Loop?
1      1       True
1      2       True
2      1       True
2      2       False

Grid (3x3):

> v

^ <

Width  Height  Loop?
1      1       False
1      2       False
1      3       False
2      1       False
2      2       True
2      3       True
3      1       False
3      2       True
3      3       False

Grid (4x3):

>^>v
v^v 
^ <<

Width  Height  Loop?
2      2       False

Grid (6x5):

>v>v>v
^v^v^v
^v^v^v
^>^>^v
^<<<<<

Width  Height  Loop?
1      1       True
1      2       False
2      1       True
2      2       True
2      4       True
2      5       False
3      1       False
3      2       True
3      3       True
3      5       True
6      2       False
6      3       True
6      5       False

Grid (10x6):

> <vv    <
 v ^ >v v 
  >v^^>vv^
    ^>^ v 
>  v<v  >>
  >v v<^  

Width  Height  Loop?
1      1       False
2      3       False
2      6       False
3      2       True
5      4       False
6      1       True
10     6       False

Sebagai satu set tambahan kasus uji, pertimbangkan bahwa input apa pun di mana grid hanya terdiri dari spasi harus menghasilkan hasil yang palsu.

Saya telah memeriksa semua test case secara manual, jadi beri tahu saya jika Anda merasa telah melakukan kesalahan.

Martin Ender
sumber
10
Fitting music
Fatalize
4
@Falalize Saya mendapat flashbacks Twitch Plays Plays ...
undergroundmonorail
"Input Anda akan menjadi grid konveyor seperti yang dijelaskan di atas bersama dengan lebar dan tinggi kargo. Anda dapat mengambil tiga parameter ini dalam urutan dan format yang nyaman." - apakah ini berarti kita dapat menggunakan grid konveyor sebagai array array? Artinya, kotak 2x2 dengan [^^/v<]menjadi [[0,1] [0,1];[0,-1] [-1,0]]? Atau maksud Anda terserah kita apakah itu STDIN, input string, input array char, dll, tetapi masih harus dalam bentuk ^, v,>, dan <?
Glen O
@ GlenO Anda dapat mengambil string yang dipisah baris baru (atau karakter lain), array string, atau array array karakter, tetapi setiap sel masih harus diwakili oleh karakter ><^vatau spasi. Saya akan mengklarifikasi itu.
Martin Ender
Jadi apa yang terjadi jika kargo bergerak ke konflik di mana arah lanjutan bukan salah satu pilihan? Yaitu, jika itu bergerak ke kanan, dan sekarang harus memilih antara atas dan kiri.
Joshua

Jawaban:

7

Ruby, 306 298 251 204 198

->g,w,h{m=->y,x,d,v=[]{q=y,x
r=->s{([""]*h+g)[y+h,h].map{|l|(?x*w+l)[x+w,w]}.join.count s}
z=k=r[?v]-r[?^],j=r[?>]-r[?<]
q[d=[d,1,0][j*j<=>k*k]]+=z[d]<=>0
v&[q<<d]!=[]?q!=v[-1]:m[*q,v<<q]}
m[0,0,1]}

Sunting: Terima kasih banyak untuk Ventero yang sering memperpendek kode dengan menerapkan beberapa trik luar biasa!

Masukan dan keluaran

Kode mewakili fungsi ruby ​​yang mengambil tiga parameter:

  • kisi, direpresentasikan sebagai larik string (setiap baris adalah string yang berbeda)
  • lebar muatan
  • ketinggian kargo

Ia mengembalikan 1(kebenaran) jika ada loop, atau nil(falsy) kalau-kalau kargo terletak.

Tes

Ini dia melewati semua tes Martin: http://ideone.com/zPPZdR

Penjelasan

Tidak ada trik pintar dalam kode; ini adalah implementasi aturan yang cukup mudah.

Dalam kode di bawah ini, moveadalah fungsi rekursif yang bergerak menurut aturan, dan:

  • mengembalikan kebenaran jika terjadi loop
  • mengembalikan falsy dalam hal istirahat
  • jika tidak, panggilan itu sendiri untuk menjalankan langkah selanjutnya

Versi yang lebih mudah dibaca tersedia di sini .

Catatan: kode golf telah mengalami beberapa modifikasi dan tidak lagi mirip dengan versi yang dapat dibaca.

Cristian Lupascu
sumber
Karena tidak masalah apakah rberisi entri tambahan selain empat arah, r[y>=0&&x>=0&&g[y]&&g[y][x]]+=1harus menyimpan beberapa byte.
Ventero
Aku mengambil kebebasan bermain golf hal-hal kecil lebih lanjut, harap Anda tidak keberatan: ideone.com/k69BmH
Ventero
@Ventero Wow, Anda telah melakukan hal-hal luar biasa pada kode. Saya tidak akan pernah berpikir untuk mengubah hash menjadi lambda. Saya mencoba beberapa ide saya untuk mempersingkat program, tetapi tidak ada yang dekat dengan apa yang Anda lakukan. Terima kasih banyak!
Cristian Lupascu
2
Mendapatkannya ke 200 melalui penanganan sedikit lebih pendek dari indeks negatif, kira saya akan berhenti di situ untuk saat ini: ideone.com/k69BmH
Ventero
2
Sebenarnya, 198: ideone.com/ptKrzf :)
Ventero
8

Python 2, 207 byte

def f(L,w,h,u=0,v=0,D=1,S=[]):a,b,c,d=map(`[r[u*(u>0):u+w]for r in L[v*(v>0):v+h]]`.count,"v^><");D=cmp(abs(a-b),abs(c-d))<D;T=u,v,D;return T in S or a-b|c-d and f(L,w,h,u+cmp(c,d)*D,v+cmp(a,b)*0**D,D,S+[T])

Masukkan kisi sebagai daftar baris, mis

['>v>v>v', '^v^v^v', '^v^v^v', '^>^>^v', '^<<<<<']

diikuti oleh lebar dan tinggi. Pengembalian 0atau Truesesuai.

Penjelasan

def f(L,          # Grid
      w,h,        # Width, height of cargo
      u=0,v=0,    # Position of top-left of cargo, initially (0, 0)
      D=1,        # Moving left/right = 1, up/down = 0
      S=[]        # Seen (pos, axis) pairs, initially empty
     ):     

     # Arrows under cargo - no need for "".join since we only need to count v^<>
     A = `[r[u*(u>0):u+w]for r in L[v*(v>0):v+h]]`

     # Count for each arrow
     a,b,c,d=map(A.count,"v^><")

     # Golfed form of abs(a-b) < abs(c-d) or (abs(a-b) == abs(c-d) and D == 1)
     D=cmp(abs(a-b),abs(c-d))<D
     T=u,v,D

     return (T in S                # Return True if (pos, axis) previously seen
             or a-b|c-d               # Return 0 if all conveyors cancel
             and f(L,w,h,             # Otherwise, recurse
                   u+cmp(c,d)*D,      # Update u if moving left/right
                   v+cmp(a,b)*0**D,   # Update v if moving up/down
                   D,
                   S+[T]          # Add (pos, axis) to seen
                  )
            )
Sp3000
sumber
Tidak bisakah Anda mempersingkat dengan menetapkan cmpke variabel?
Biru
Apakah cukup untuk mendeteksi siklus dengan memeriksa posisi yang sudah dikunjungi? Berdasarkan aturan 4, langkah selanjutnya juga dapat dipengaruhi oleh arah sebelumnya. Jadi sepertinya mungkin Anda bisa tiba di posisi yang sama dua kali, tetapi tidak memiliki siklus karena Anda bergerak ke arah yang berbeda berdasarkan arah yang berbeda sebelumnya.
Reto Koradi
@muddyfish Itu baru saja impas
Sp3000
@RetoKoradi Semoga diperbaiki
Sp3000
Ya, menambahkan Dke kunci posisi harus melakukannya.
Reto Koradi
8

Julia - 394 300 246 214 byte

f(A,x,y)=(Z=sign;(S,T)=size(A);X=x+1;Y=y+1;G=fill(5,S+2y,T+2x);G[Y:S+y,X:T+x]=A;C=0G;D=1;while C[Y,X]!=D C[Y,X]=D;i,j=sum(i->1-[19 8]i%82%3,G[Y:Y+y-1,X:X+x-1]);D=Z(2i^2-2j^2+(i!=0)D);X+=Z(i+D*i);Y+=Z(j-D*j)end;D^2)

Mengembalikan 1 jika kargo berputar, dan 0 jika berhenti. Ini bukan "benar-benar" kebenaran / kepalsuan, karena Julia tidak mengizinkan 0 dan 1 dalam konteks boolean ... tapi saya menganggap nilai x- nilai yang bool(x)==truebenar dan salah bool(x)==false.

Input Aharus berupa array karakter. Jika Anda menyalin / menempel grid konveyor, Anda harus memasukkannya ke formulir yang sesuai. Untuk menyelamatkan Anda dari keharusan menangani secara manual, gunakan yang berikut ini:

A=foldl(hcat,map(collect,split("""(PASTE GRID HERE)""","\n")))'

Di mana jelas, (PASTE GRID HERE)harus diganti dengan grid itu sendiri. Periksa ulang spasi di akhir setiap baris, untuk memastikan itu benar-benar memiliki semua spasi (itu tidak memeriksa untuk memastikan bahwa semua garis panjangnya sama). Perhatikan bahwa baris ini bukan bagian dari kode solusi aktual, hanya sepotong kode yang nyaman untuk membuat menggunakan kode solusi sedikit lebih mudah.

Tidak Disatukan:

function f(A,x,y)
  # Determine size of grid for use later
  (S,T)=size(A)
  # Initialise starting position (performed here to save characters)
  X=x+1
  Y=y+1
  # Create an expanded field that is functionally "spaces" (to provide
  # spaces at edges for the cargo to stop in)
  G=fill(5,S+2y,T+2x)
  # Put the conveyor grid into centre of the expanded field
  G[Y:S+y,X:T+x]=A
  # Create an array storing the most recent movement direction:
  # will use 1=horizontal, -1=vertical, 0=stopped
  C=0G
  # Initialise current direction (same system as C)
  D=1
  # Loop until it finds itself repeating a coordinate/direction pair
  while C[Y,X]!=D
    # Mark current coordinate/direction pair in array
    C[Y,X]=D
    # Determine the net coordinate pairing, stored in two variables
    # for golf purposes *SEE NOTE*
    i,j=sum(i->1-[19 8]i%82%3,G[Y:Y+y-1,X:X+x-1])
    # Determine new movement axis (if D=0, cargo stopped)
    D=sign(2i^2-2j^2+(i!=0)D)
    # Update X or Y depending on signs of D and the appropriate direction
    X+=sign(i+D*i)
    Y+=sign(j-D*j)
  end
  # if D=±1, return 1 (cargo is still moving), otherwise return 0
  return D^2
end

Catatan: 1-[19 8]i%82%3telah dipilih untuk memetakan lima karakter yang memungkinkan ke pasangan koordinat yang sesuai dengan metode paling efisien yang bisa saya temukan. Ini juga alasan untuk menggunakan 5 untuk mengisi spasi saat membuat G- ini adalah karakter satu digit yang dipetakan [0 0].

Contoh penggunaan:

julia> A=foldl(hcat,map(collect,split(""">v>v>v
       ^v^v^v
       ^v^v^v
       ^>^>^v
       ^<<<<<""","\n")))';

julia> f(A,2,1)
true

julia> f(A,3,3)
true

julia> f(A,5,2)
false
Glen O
sumber
f(A,x,y)=lebih pendek dari f=(A,x,y)->.
Alex A.
@AlexA. - benar, tapi kemudian, saya mungkin akan menghapus f=dan membuatnya menjadi fungsi anonim ketika saya selesai bermain golf.
Glen O
1
Panjangnya akan sama jika fungsi bernama versus fungsi anonim saat ada beberapa parameter. f()=versus ()->.
Alex A.