Tugas

Tentukan mod-fold sebagai fungsi dari bentuk f (x) = x% a ₁  % a ₂  % ...% a _k , di mana a _i adalah bilangan bulat positif dan k ≥ 0 . (Di sini, % adalah operator modulo asosiatif kiri.)

Diberikan daftar n bilangan bulat y ₀ ,…, y _{n − 1} , tentukan apakah ada mod-fold f sehingga masing-masing y _i  = f (i) .

Anda dapat memilih dan memperbaiki dua output Y dan N untuk fungsi / program Anda. Jika ada huruf f seperti itu , Anda harus selalu mengembalikan / mencetak dengan tepat Y ; jika tidak, Anda harus selalu kembali / mencetak persis N . (Ini bisa menjadi true/ false, atau 1/ 0, atau false/ true, dll.) Sebutkan ini dalam jawaban Anda.

Pengajuan terpendek dalam byte menang.

Contoh

Tentukan f (x) = x% 7% 3 . Nilai-nilainya mulai:

|   x  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ...
| f(x) | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 0 | 1 | 2 | ...

Dengan demikian, diberikan 0 1 2 0 1 2 0 0 1 2sebagai masukan untuk solusi kami, kami akan mencetak Y , karena hal ini f menghasilkan urutan itu. Namun, diberikan 0 1 0 1 2sebagai input, kita akan mencetak N , karena tidak ada f yang menghasilkan urutan itu.

Uji kasus

Rumus yang diberikan ketika output adalah Y hanya untuk referensi; Anda tidak boleh mencetaknya.

0 1 2 3 4 5              Y    (x)
1                        N
0 0 0                    Y    (x%1)
0 1 2 0 1 2 0 0 1 2      Y    (x%7%3)
0 0 1                    N
0 1 2 3 4 5 6 0 0 1 2    Y    (x%8%7)
0 1 2 0 1 2 0 1 2 3      N
0 2 1 0 2 1 0 2 1        N
0 1 0 0 0 1 0 0 0 0 1    Y    (x%9%4%3%2)

Pyth, 14 byte

}Qm%M+RdUQy_Sl

Pengembalian True/False. Cobalah online: Demonstrasi atau Test Suite

Penjelasan:

}Qm%M+RdUQy_SlQ   implicit Q (=input) at the end
             lQ   length of input list
            S     create the list [1, 2, ..., len]
           _      reverse => [len, ..., 2, 1]
          y       generate all subsets (these are all possible mod-folds)
  m               map each subset d to:
        UQ           take the range [0, 1, ..., len-1]
     +Rd             transform each number into a list by prepending it to d
                     e.g. if mod-fold = [7,3], than it creates:
                        [[0,7,3], [1,7,3], [2,7,3], [3,7,3], ...]
   %M                fold each list by the modulo operator
                  this gives all possible truthy sequences of length len
}Q                so checking if Q appears in the list returns True or False

Pyth, 11 byte

q%M.e+k_tx0

Berdasarkan ide @ ferrsum . Saya benar-benar berpikir tentang menggunakan indeks nol untuk generasi subset, tetapi tidak menyadari, bahwa semua indeks nol harus sudah menjadi solusi.

Python 3, 239 218 byte

from itertools import*
lambda z:z in[[eval(''.join([str(l)]+['%'+str(i[::-1][k])for k in range(len(i))]))for l in range(len(z))]for i in(i for j in(combinations(range(1,len(z)+1),i+1)for i in range(len(z)))for i in j)]

Fungsi anonim yang mengambil input dari daftar zdan mengembalikan Trueatau Falseuntuk Ydan N.

Ini menggunakan metode yang mirip dengan jawaban @Jakube , dan meskipun pada dasarnya adalah kekuatan kasar, berjalan sangat cepat.

from itertools import*               Import everything from the Python module for
                                     iterable generation
lambda z                             Anonymous function with input list z
combinations(range(1,len(z)+1),i+1)  Yield all sorted i+1 length subsets of the range
                                     [1,len(z)]...
...for i in range(len(z))            ...for all possible subset lengths
(i for j in(...)for i in j)          Flatten, yielding an iterator containing all possible
                                     mod-fold values as separate lists
...for i in...                       For all possible mod-fold values...
...for k in range(len(i))            ...for all mod-fold values indices k...
...for l in range(len(z))            ...for all function domain values in [0,len(z)-1]...
[str(l)]+['%'+str(i[::-1][k])...]    ...create a list containing each character of the
                                     expression representing the function defined by the
                                     mod-fold values (reversed such that the divisors
                                     decrease in magnitude) applied to the domain value...
 eval(''.join(...))                  ...concatenate to string and evaluate...
 [...]                               ...and pack all the values for that particular
                                     function as a list
 [...]                               Pack all lists representing all functions into a list
 ...:z in...                         If z is in this list, it must be a valid mod-fold, so
                                     return True. Else, return False

Cobalah di Ideone

Python 2, 69 byte

f=lambda a,i=0:i/len(a)or a[i]in[a[i-1]+1,i,0][i<=max(a)::2]*f(a,i+1)

Penggunaan True/ False.

Jawaban untuk apa yang mencirikan seri mod-lipat ternyata kurang menarik daripada yang tampak pada awalnya. Ini adalah serangkaian bentuk 0, 1, ..., M - 1, 0, 1, ... x ₁ , 0, 1, ..., x ₂ , ... sedemikian rupa sehingga untuk semua i, 0 <= x _i <M. Urutan seperti itu dapat diproduksi oleh rantai mod semua indeks (berbasis 0) dari nol dalam array, tidak termasuk yang pertama.

Jelly , 19 15 14 byte

LṗLUZ’1¦%/sLe@

Mengembalikan 1 untuk truey, 0 untuk falsy. Cobalah online!

Algoritma ini adalah O (n ⁿ ) , di mana n adalah panjang daftar, membuatnya terlalu lambat dan intensif memori untuk sebagian besar kasus uji.

Versi yang dimodifikasi - yang menggantikan yang kedua Ldengan a 5- dapat digunakan untuk memverifikasi semua kasus uji . Perhatikan bahwa versi modifikasi ini tidak akan berfungsi untuk daftar panjang yang sewenang-wenang.

Bagaimana itu bekerja

LṗLUZ’1¦%/sLe@  Main link. Argument: A (array of integers)

L L             Yield the length l of A.
 ṗ              Take the l-th Cartesian power of [1, ..., l], i.e., construct
                all arrays of length l that consist of elements of [1, ..., l].
   U            Upend/reverse each array. This way, the first l arrays start
                with [1, ..., l], as do the next l arrays, etc.
    Z           Zip/transpose the array of arrays.
     ’1¦        Decrement the first array to map [1, ..., l] to [0, ..., l - 1].
        %/      Reduce the array's columns by modulus/residue.
          sL    Split the result into chunks of length l.
            e@  Verify if A belongs to the resulting array.

JavaScript (ES6), 98 byte

a=>a.every((n,i)=>n?n<(l+=p==i)&&n==p++:p=1,l=p=1)

Disimpan 48 byte dengan beralih ke penemuan @ Feersum. Nilai apa pun yang diberikan ndalam array adalah nol, dalam hal ini prediksi berikutnya padalah 1, atau sama dengan prediksi berikutnya, di mana case pbertambah. Kami juga mengukur panjang ldari urutan awal dengan membandingkan puntuk i, sebagai nkeharusan selalu kurang dari lsetiap saat.

Python 2, 103 99 byte

f=lambda l,r:r==x or l and f(l-1,[t%l for t in r])|f(l-1,r)
x=input();l=len(x);print+f(l,range(l))

Mencetak 1 untuk truey dan 0 untuk falsy. Uji di Ideone .