Kode Gray yang digeneralisasi

13

Input: Array I dari k bilangan bulat positif. Bilangan bulat tidak akan lebih besar dari 100 dan k ≤ 100 .

Output: Kode Anda harus menampilkan semua kemungkinan array O dari bilangan bulat non-negatif dengan k dengan batasan 0 ≤ O i ≤ I i . Untuk mendapatkan dari satu array ke array berikutnya, Anda dapat menambah atau mengurangi 1 ke satu nilai dalam array. Kode Anda tidak boleh menampilkan array yang sama dua kali. Jika jumlah array yang berbeda untuk di-output sangat besar, kode Anda harus menjalankan keluaran selamanya sampai mati.

Contohnya

  • Jika saya adalah array dari k maka ini adalah masalah iterasi pada semua kode Gray dengan lebar bit k , kecuali bahwa elemen pertama dan terakhir tidak perlu dapat dijangkau dalam satu langkah.

  • Jika I = [2,1]kemudian salah satu kemungkinan pemesanan array output adalah(0,0),(0,1),(1,1),(1,0),(2,0),(2,1)

  • Jika I = [2,1,3]kemudian salah satu kemungkinan pemesanan array output adalah (0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,1,3),(0,1,2),(0,1,1),(0,1,0),(1,1,0),(1,1,1),(1,1,2),(1,1,3),(2,1,3),(2,1,2),(2,1,1),(2,1,0),....

Ini adalah tantangan kode-golf, pengajuan dengan kode sumber dengan kemenangan terpendek. Jangan biarkan jawaban singkat dalam bahasa golf menghalangi Anda untuk mengirim jawaban dalam bahasa lain. Cobalah untuk memberikan jawaban terpendek dalam bahasa apa pun.

Ini juga merupakan tantangan dengan kompleksitas terbatas. Setiap array baru harus di-output dengan O (k) waktu berlalu sejak array yang di-output sebelumnya (atau awal program untuk array pertama yang di -output ). Ini berarti bahwa waktu berjalan per larik keluaran baru (masing-masing panjang k ) tidak boleh lebih besar dari O (k) . Itu harus mengambil proporsi waktu untuk k dan tidak, misalnya k 2 atau 2 k . Catatan ini bukan waktu rata-rata per output tetapi waktu kasus terburuk untuk setiap array yang dihasilkan.

Anda dapat mengasumsikan bahwa semua aritmatika pada bilangan bulat 64 bit dapat dilakukan dalam waktu konstan seperti dapat membaca dan mengeluarkannya serta penugasan dan mencari dan mengubah nilai dalam array.

Salah satu konsekuensi dari kompleksitas terbatas adalah bahwa solusi yang hanya dihasilkan pada saat keluar dari program tidak dapat diterima.

Anush
sumber
1
(haruskah "menambah atau mengurangi 1" dilakukan modulo I_i+1? Bisakah Anda mencapai 0 dari I_i?)
user202729
@ user202720 Tidak, saya tidak bermaksud itu.
Anush
Bagaimana kompleksitas bekerja saat ndan kterbatas? dengan asumsi mereka pergi hingga tak terbatas dengan lebar bit bagaimana cara pergi
14m2
@ l4m2 Untuk keperluan analisis kompleksitas anggap k pergi ke infinity.
Anush
@Anush jadi bagaimana lebar bit pergi?
14m2

Jawaban:

4

Python 3 , 116 byte

def f(a):
 l=len(a);t=[0]*l;d=[1]*l
 while 1:
  i=0;yield t
  while not-1<t[i]+d[i]<=a[i]:d[i]*=-1;i+=1
  t[i]+=d[i]

Cobalah online!

Terima kasih Mnemonic untuk -1 byte.

Fungsi generator. (terima kasih Dennis untuk mengingatkan saya, saya lupa fitur ada) Jika output harus dicetak ke stdout kemudian gunakan print(t,flush=1)untuk 9 byte tambahan, atau jika Python dipanggil dengan -u, print(t)cukup untuk +1 byte.

Berhenti dengan kesalahan ( IndexError). Jika Anda ingin memanggil fungsi ini dan kemudian melanjutkan program, Anda harus menangkapnya.

pengguna202729
sumber
Berapa lama loop internal saat dijalankan?
Anush
@Anush Pada sebagian besar klangkah, karena pada setiap langkah imeningkat dengan 1dan setelah klangkah i==kdan d[i]menyebabkan kesalahan.
user202729
Ini solusi yang sangat bagus.
Anush
Anda dapat menyimpan byte dengan menggantinya not 0<=dengan not-1<.
1
Bisakah Anda menggunakan yield tbukan print(t,flush=1)?
Dennis
2

Stax , 22 byte

▒)∙ñ╚▀NK♀F☺S(A#P`░]╪Db

Jalankan dan debug itu

Inilah yang besar untuk menunjukkan perilaku asimptotik .

Dibongkar, tidak diserang, dan dikomentari, sepertinya ini.

,           pop from input to main stack
W           run the rest of the program repeatedly until explicitly cancelled
  cJP       copy top of stack and print, delimited by spaces
            get the index to mutate
  i^            iteration index + 1
  x{^|%}I       repeatedly apply divmod using l[k]+1 from input
                get the index of the first value that returns modulus >0
  cU=C      if the result is -1 (no match), then terminate the program
            get the direction to mutate
  s             get the "div" part of the last div operation called "d"
  ^|1           -1 ^ (d+1)
  ~{+}&     increment element in array at the index by the calculated amount

Jalankan yang ini

rekursif
sumber
1
Mengukur dalam kompleksitas bit, indeks iterasi adalah O(k)bit, jadi kwaktu pembagian mungkin memakan O(k²)waktu ...
user202729
1

JavaScript (Node.js) , 114 byte

a=>{b=a.map(_=>0);c=a.map(_=>1);for(i=0;a[i];b[i]+=c[i]||-1){console.log(b);for(i=0;b[i]==a[i]*c[i];i++)c[i]^=1;}}

Cobalah online! Tidak Disatukan:

function ggray(maxima) {
    var current = Array(maxima.length).fill(0);
    var flag = Array(maxima.length).fill(1);
    for (;;) {
        console.log(current);
        for (var i = 0; ; i++) {
            if (i == maxima.length) return;
            if (current[i] != maxima[i] * flag[i]) break;
            flag[i] = 1 - flag[i];
        }
        if (flag[i]) current[i]++;
        else current[i]--;
    }
}
Neil
sumber
1

Kotlin , 181 178 byte

Terima kasih kepada: Anush menunjukkan bahwa saya salah memahami tantangan menghemat 2 byte. Ovs menunjukkan penghematan 1 byte.

val p={a:List<Int>->var l=a.size
val v=Array(l,{0})
val i=Array(l,{1})
l-=1
o@while(0<1){println(v)
var p=l
while(v[p]+i[p]!in 0..a[p]){i[p]*=-1
p-=1
if(p<0)break@o}
v[p]+=i[p]}}

Cobalah online!

JohnWells
sumber
1
Sebagai contoh dalam pertanyaan dengan 2 1 3 kode Anda membutuhkan 3 2 4 sebagai input tampaknya.
Anush
1
while(true)dapatwhile(1<2)
ovs