Temukan binarray!

24

Kami mendefinisikan binarray sebagai array yang memenuhi properti berikut:

  • ini tidak kosong
  • nilai pertama adalah a 1
  • nilai terakhir adalah a 1
  • semua nilai lainnya adalah 0atau1

Misalnya, array [ 1, 1, 0, 1 ]adalah binarray yang valid .

Tugas

Mengingat non-kosong array yang Sebuah bilangan bulat non-negatif dan positif bilangan bulat N , tugas Anda adalah untuk menemukan binarray B panjang N yang memungkinkan untuk menghasilkan A dengan menjumlahkan jumlah tak terbatas salinan B , digeser oleh jumlah tak terbatas posisi.

Contoh

A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
N = 4

Untuk input ini, binarray B = [ 1, 1, 0, 1 ] akan menjadi jawaban yang valid karena kita dapat melakukan:

  [ 1, 1, 0, 1 ]
+       [ 1, 1, 0, 1 ]
+       [ 1, 1, 0, 1 ]
+          [ 1, 1, 0, 1 ]
+                   [ 1, 1, 0, 1 ]
+                                  [ 1, 1, 0, 1 ]
  -----------------------------------------------
= [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]

Aturan

  • Masukan dapat diambil dalam format apa pun yang masuk akal.
  • Output dapat berupa array asli (misalnya [1, 1, 0, 1]) atau string biner dengan atau tanpa pemisah (misalnya "1,1,0,1"atau "1101")
  • Anda hanya perlu mencetak atau mengembalikan satu binarray yang valid . Atau, Anda dapat memilih untuk mencetak atau mengembalikan semuanya ketika ada beberapa solusi.
  • Anda tidak diharuskan mendukung input yang tidak mengarah ke solusi apa pun.
  • Jumlahnya mungkin termasuk nol implisit yang tidak tumpang tindih dengan salinan B . Nol kedua dalam jumlah di atas adalah nol yang tersirat.
  • Anda dapat mengasumsikan bahwa ukuran maksimum A adalah 100 dan ukuran maksimum B adalah 30.
  • Ini adalah kode-golf, jadi jawaban tersingkat dalam byte menang. Celah standar dilarang.

Uji kasus

Input : N = 1 / A = [ 1, 2, 3, 4, 5 ]
Output: [ 1 ]

Input : N = 2 / A = [ 1, 2, 100, 99 ]
Output: [ 1, 1 ]

Input : N = 3 / A = [ 1, 1, 1 ]
Output: [ 1, 1, 1 ]

Input : N = 3 / A = [ 1, 1, 3, 2, 2 ]
Output: [ 1, 1, 1 ]

Input : N = 3 / A = [ 1, 0, 2, 1, 1, 1, 0, 0, 1, 0, 1 ]
Output: [ 1, 0, 1 ]

Input : N = 4 / A = [ 1, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1 ]

Input : N = 4 / A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1 ]

Input : N = 4 / A = [ 1, 1, 0, 2, 1, 0, 1 ]
Output: [ 1, 0, 0, 1 ] or [ 1, 1, 0, 1 ]

Input : N = 5 / A = [ 1, 3, 6, 9, 8, 6, 3, 4 ]
Output: [ 1, 1, 1, 0, 1 ]

Input : N = 8 / A = [ 2, 1, 0, 2, 3, 3, 1, 2, 1 ]
Output: [ 1, 0, 0, 1, 1, 1, 0, 1 ]

Input : N = 10 / A = [ 1, 2, 1, 2, 2, 1, 3, 3, 3, 2, 3, 0, 2, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 ]

Input : N = 13 / A = [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 ]
Output: [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]

Input : N = 5 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1, 1 ]

Input : N = 6 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 0, 0, 0, 1 ]

Input : N = 7 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 0, 0, 0, 1, 1 ]

Input : N = 9 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 1, 0, 1, 0, 1, 0, 1 ]
code-golf array-manipulation polynomials Arnauld
sumber
Apa nilai terbesar dari Nyang seharusnya didukung?
Neil
@Neil Saya telah menambahkan batas ukuran pada A dan B.
Arnauld
1
@ fəˈnɛtɪk Mungkin, tetapi untuk N=4, A = [ 1, 1, 2, 4, 1, 2, 2, 2, 1, 2, 2, 1, 2, 0, 1 ], Anda mendapatkan 30459 yang dapat dibagi oleh 11 dan 13 namun hanya satu [ 1, 1, 0, 1 ]dan [ 1, 0, 1, 1 ]jawaban yang valid.
Neil
1
@ fəˈnɛtɪk Angka-angka ini tidak ditulis dalam basis 2 sehingga aturan aritmatika tidak berlaku. Misalnya, Anda tidak dapat membawa secara eksplisit saat menambahkan.
BallpointBen
2
Silakan tambahkan kotak uji ini, yang tampaknya memecah hampir semua jawaban yang diposting: N = 3, A = [1, 0, 2, 0, 2, 0, 1], output = [1, 0, 1]; N = 3, A = [1, 1, 1, 0, 0, 0, 1, 1, 1], output = [1, 1, 1].
Anders Kaseorg

Jawaban:

8

PHP, 105 92 90 86 byte

Solusi Jörg diperbaiki dan golf :

for($b=1+2**$argv[1];;)--$argc>1?$s+=$argv[$argc]*2**$i++:$s%($b-=2)||die(decbin($b));

mengambil Ndari argumen baris perintah pertama, nilai setelah itu; jalankan dengan -ratau coba online .
mencetak nomor biner (format 10001); mencetak solusi yang tidak valid atau berjalan mati jika tidak ada solusi yang valid.

versi pertama (sekarang 97 byte) yang tidak mencetak apa pun untuk input yang tidak valid: uji secara online

for($b=1+$m=2**$argv[1];$m/2<=$b;)--$argc>1?$s+=$argv[$argc]*2**$i++:$s%($b-=2)||die(decbin($b));

kerusakan

for($b=1+$m=2**$argv[1];$m/2<=$b;)  # second loop: loop $b from 2^N-1 by -2 to 2^(N-1)
--$argc>1                           # first loop: decrease $argc ...
    ?$s+=$argv[$argc]*2**$i++           # while $argc>1: binary sum from last to 2nd argument
    :$s%($b-=2)||die(decbin($b));       # later: if $b divides $s, print in binary and exit
Titus
sumber
Bagus tidak bisakah Anda mencapai jumlah byte di bawah 100?
Jörg Hülsermann
1
@ JörgHülsermann saya bisa.
Titus
Berpikir Berat. Saya tahu sebelumnya bahwa Anda lebih baik. Saya harap Anda dapat memegang hitungan byte terendah
Jörg Hülsermann
1
Pada N = 3, A = [1, 0, 2, 0, 2, 0, 1], ini secara keliru mengembalikan di111 mana satu-satunya hasil yang benar adalah [1, 0, 1].
Anders Kaseorg
8

PHP , 219 byte

<?for(list($g,$z)=$_GET,$d=~-$l=2**$z;$d>=$l/2;max(array_diff_assoc($r,$g)?:[0])?:$o[]=$b,$d-=2)for($r=[],$b=decbin($d),$k=0;$k<count($g);$k++)for($u=$g[$k]-$r[$k],$i=0;$i<$z;$i++)$u<1?:$r[$k+$i]+=$u*$b[$i];print_r($o);

Cobalah online!

-4 Bytes menggunakan [$g,$z]=$_GETPHP 7.1 sebagai gantilist($g,$z)=$_GET

Jörg Hülsermann
sumber
Sepertinya ini menghasilkan [1,0,1,0,1,0,1,0,1]jawaban yang valid ( ) dan tidak valid ( [1,0,0,0,1,0,1,1,1]) untuk kasus uji terakhir.
Arnauld
-8 byte: while($_GET[0])$s+=2**$i++*array_pop($_GET[0]);. -5 byte: range(1|.5*$m=2**$_GET[1],$m,2).
Titus
@Arnauld Ya saya harus memberikan sebagai Output hanya binarray tertinggi juga membuat solusi ini valid
Jörg Hülsermann
2
@ fəˈnɛtɪk Saya setuju dengan matematika Anda, tetapi tantangannya adalah tentang menemukan pola yang dapat dijumlahkan tepat ke A, bukan pengaturan yang setara. Di sini, kita dapatkan [ 1,0,1,1,1,0,2,2,2,2,2,1 ].
Arnauld
1
-1 byte dengan for($g=$_GET[0];$g;).
Titus
3

Python, 166 byte

def f(a,n):
 for i in range(1<<n-1,1<<n):
  b=bin(i)[2:];u,v=(int(('0{:0>%d}'%sum(a)*len(s)).format(*s))for s in[a,b])
  if u%v<1>int(str(u//v*10)[::~sum(a)]):yield b

Cobalah online!

Bagaimana itu bekerja

Pertimbangkan A dan B sebagai angka dasar k nomor u dan v . Misalnya (kami akan menggunakan k = 1000 untuk ilustrasi):

A = [1, 2, 1, 3, 2, 1, 2]
B = [1, 0, 0, 1]
u = 1 002 001 003 002 001 002
v = 1 000 000 001

Seperti yang banyak diperhatikan oleh penjawab lain, jika B adalah jawaban yang valid, maka Anda dapat dibagi dengan v . Pada kasus ini,

u = 1 002 001 002 ⋅ v

Hasil bagi ini, diterjemahkan kembali ke array [1, 2, 1, 2], memberi tahu kita dengan tepat berapa banyak salinan B yang perlu kita ubah ke setiap posisi.

  [1, 0, 0, 1]
+    [1, 0, 0, 1]
+    [1, 0, 0, 1]
+       [1, 0, 0, 1]
+          [1, 0, 0, 1]
+          [1, 0, 0, 1]
-----------------------
  [1, 2, 1, 3, 2, 1, 2]

(Kenapa? Karena itulah tepatnya berapa lama perkalian bekerja di basis k .)

Yang gagal diperhatikan oleh penjawab lain adalah bahwa kondisi di atas tidak memadai . Sebagai contoh:

A = [1, 2, 1, 3, 2, 1, 2]
B = [1, 1, 1, 1]
u = 1 002 001 003 002 001 002
v = 1 001 001 001
u = 1 000 999 002 ⋅ v

Secara matematis, kita masih bisa menerjemahkan hasil bagi itu kembali ke array [1, 1, −1, 2], yang berfungsi dengan baik jika kita diperbolehkan menggunakan salinan negatif B:

  [1, 1, 1, 1]
+    [1, 1, 1, 1]
−       [1, 1, 1, 1]
+          [1, 1, 1, 1]
+          [1, 1, 1, 1]
-----------------------
  [1, 2, 1, 3, 2, 1, 2]

tetapi tentu saja tantangannya tidak memungkinkan salinan negatif. Jadi kita perlu cek tambahan.

Menjelang akhir itu, kami memilih basis k = 10 e di mana k > 10 ⋅ jumlah (A), dan memeriksa bahwa tidak ada digit basis k yang meluap ke digit basis k berikutnya ketika kami mengalikan hasil bagi dengan sepuluh. Artinya, setiap e th dasar sepuluh digit, dimulai di akhir, di dasar sepuluh representasi dari kali quotient sepuluh, harus 0. Ini jaminan bahwa hasil bagi diterjemahkan kembali ke array dengan elemen non-negatif.

Anders Kaseorg
sumber
1
Saya suka trik Anda menggunakan kekuatan besar 10 sebagai basis untuk membuat konversi basis lebih mudah.
Neil
2

PHP, 213 Bytes

Cara yang sama sedikit golf

<?for($b=2**~-$l=$_GET[1];$b<2**$l;array_filter($t[$b++])?:$d[]=$o)for($g=count($t[$b]=$_GET[$i=0]);min($t[$b])>-1&$i<=$g-$l;$i++)for($e=$t[$b][$i],$k=0,$o=decbin($b);$k<$l;)$t[$b][$k+$i]-=$o[$k++]*$e;print_r($d);

Cobalah online!

PHP, 344 Bytes pertama berfungsi

Setelah jawaban pertama saya, saya memutuskan untuk mencoba lagi yang memberikan semua solusi yang valid.

<?foreach(range(2**($l=$_GET[1])-1,2**($l-1))as$b){$t[$b]=($g=$_GET[0]);for($i=0;$t[$b]&&$i<=count($g)-$l;$i++){$e=reset($y=array_slice($t[$b],$i,$l));foreach(str_split(decbin($b))as$k=>$v)$t[$b][$k+$i]=$y[$k]-$e*$v;if(min($t[$b])<0)unset($t[$b]);}}foreach($t as$k=>$v)if(max($v)>0)unset($t[$k]);echo join(",",array_map(decbin,array_keys($t)));

Versi Online

Kerusakan

foreach(
    range(2**($l=$_GET[1])-1
    ,2**($l-1)
    ) # make decimal range of a binarray with given length
    as$b){
$t[$b]=($g=$_GET[0]); # make a copy for each possible solution pattern
    for($i=0;$t[$b]&&$i<=count($g)-$l;$i++){ # Loop till solution is valid or reach last digit
        $e=reset($y=array_slice($t[$b],$i,$l)); # take first value of a sequence with the length
        foreach(str_split(decbin($b))as$k=>$v)
            $t[$b][$k+$i]=$y[$k]-$e*$v; # replace values in copy
        if(min($t[$b])<0)unset($t[$b]); # kill solution if a minimum <0 exists
    }
}
foreach($t as$k=>$v)if(max($v)>0)unset($t[$k]); # drop all solutions where the sum is not zero 


echo join(",",array_map(decbin,array_keys($t))); #Output all solutions
Jörg Hülsermann
sumber
Ini tampaknya bekerja untuk N ≥ 2, tetapi gagal pada N = 1 kasus, seperti kasus uji pertama dalam tantangan.
Anders Kaseorg
@AndersKaseorg Sekarang ini mendukung N = 1 Kasing, hanya perlu mengatur =di loop pertama untuk versi yang lebih pendek. Dalam versi yang lebih besar perlu menghapus empat Bytes
Jörg Hülsermann
1

Python, 205 byte

def f(a,l):
 b=lambda s:b(s[:-1])*sum(a)*8+int(s[-1])if s else 0
 c=lambda n:n and(n/sum(a)/4%2 or c(n/sum(a)/8))
 for i in range(2**~-l,2**l):
  j=bin(i)[2:]
  if b(a)%b(j)<1 and not c(b(a)/b(j)):return j

Mengembalikan string biner tanpa pemisah. Seperti yang ditunjukkan oleh @AndersKaseorg, ada input yang solusi @ fəˈnɛtɪk tidak berfungsi karena divisi tersebut menunjukkan koefisien negatif yang tidak diizinkan. Untuk mengatasi ini, saya menggunakan basis yang sangat besar dan menguji bahwa tidak ada pinjaman di divisi.

Neil
sumber
Oke, saya pikir ini adalah contoh tandingan yang sebenarnya: f([1, 1, 1, 0, 0, 0, 1, 1, 1], 3)salah mengembalikan 101.
Anders Kaseorg
@AndersKaseorg Hmm, apakah membalik urutan bantuan loop, atau apakah algoritma masih rusak secara fundamental?
Neil
Saya pikir ini rusak secara mendasar tanpa pemeriksaan tambahan. Varian balik gagal f([1, 0, 2, 0, 2, 0, 1], 3), dan varian maju dan mundur gagal f([1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0], 5).
Anders Kaseorg
Dan bahkan jika Anda memeriksa itu ianeh, varian maju dan mundur gagal f([1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]*10, 5).
Anders Kaseorg
1
@AndersKaseorg Ah ya, ketika gcd (k, n) = 1, (x^kn-1)/(x^k-1)selalu memiliki (x^n-1)/(x-1)faktor, yang membodohi solusi @ fəˈnɛtɪk di basis apa pun.
Neil
1

Pyth, 32 byte

f!|%FKiRJysQ,QT>#sQj/FKJ+L1^U2tE

Cobalah online

Bagaimana itu bekerja

                           ^U2tE   Cartesian power [0, 1]^(N - 1)
                        +L1        prepend 1 to every list
f                                  filter for lists T such that:
          sQ                         sum(A)
         y                           double
        J                            assign to J
      iR    ,QT                      convert [A, T] from base J
     K                               assign to K
   %F                                fold modulo
  |                                  logical OR with
                    /FK                fold integer division over K
                   j   J               convert to base J
               >#sQ                    filter for digits greater than sum(A)
 !                                   logical NOT

Strategi ini mirip dengan jawaban Python saya , kecuali karena Pyth memiliki builtin untuk konversi basis, kita dapat menggunakan basis yang lebih efisien k = 2 ⋅ jumlah (A), dan memeriksa secara langsung bahwa setiap digit hasil bagi adalah paling banyak jumlah (A ).

Anders Kaseorg
sumber
1

Pari / GP , 77 74 96 80 byte

n->a->[v|d<-divisors(b=Pol(a)),(v=Vec(d))%2==v&&vecmin(Vec(b/d))>=0&&d%x&&#d==n]

Mengembalikan semua solusi.

Pertama-tama, mengubah array amenjadi polinomial b. Kemudian memilih dari pembagi bpolinomial dsedemikian sehingga koefisien dsemua 1dan 0, dan koefisien b / dsemua tidak negatif, dan d(0) = 1, dan deg(d) = n + 1. Akhirnya, ubah mereka kembali ke array.

Cobalah online!

alephalpha
sumber