32

Tujuan dari tantangan ini adalah untuk menentukan apakah koleksi potongan satu-dimensonal dapat dibentuk untuk membentuk potongan kontinu yang terbatas.

Sebuah karya adalah, urutan yang terbatas tidak kosong dari nol dan satu yang dimulai dan berakhir dengan satu a. Beberapa potongan yang mungkin adalah 1, 101, 1111, 1100101.

Ubin berarti mengatur potongan sehingga satu blok yang berdekatan terbentuk. Satu dari satu bagian dapat menempati tempat nol, tetapi bukan bagian satu, dari bagian lain.

Sama halnya, jika kita melihat satu sebagai "bahan padat" dan nol sebagai "lubang", potongan harus pas sehingga membentuk satu regangan, tanpa meninggalkan lubang.

Untuk membentuk ubin, potongan hanya dapat digeser sepanjang ruang satu dimensi mereka. (Mereka tidak dapat dibagi, atau tercermin). Setiap bagian digunakan tepat sekali.

Contohnya

Tiga buah 101, 11, 101dapat ubin seperti yang ditunjukkan pada berikut, di mana masing-masing bagian diwakili dengan pergeseran yang diperlukan:

  101
11
   101

jadi ubin yang didapat adalah

Sebagai contoh kedua, potongan 11011dan 1001101tidak bisa ubin. Secara khusus, pergeseran

 11011
1001101

tidak valid karena ada dua yang bertabrakan; dan

11011
  1001101

tidak valid karena hasilnya akan mengandung nol.

Aturan tambahan

The masukan adalah kumpulan dari satu atau lebih potongan. Format wajar apa pun diizinkan; sebagai contoh:

Daftar string, di mana setiap string dapat berisi dua karakter yang berbeda dan konsisten;
Beberapa array, di mana setiap array berisi posisi yang untuk sepotong;
Daftar bilangan bulat (ganjil) seperti representasi biner dari setiap angka mendefinisikan suatu bagian.

The keluaran harus menjadi nilai truthy jika ubin adalah mungkin, dan nilai falsy sebaliknya. Nilai output tidak perlu konsisten; yaitu, mereka dapat berbeda untuk input yang berbeda.

Program atau fungsi diizinkan, dalam bahasa pemrograman apa pun . Celah standar dilarang.

Kode terpendek dalam byte menang.

Uji kasus

Setiap input berada pada jalur yang berbeda

Sejujurnya

1
111
1, 1
11, 111, 1111
101, 11, 1
101, 11, 101
10001, 11001, 10001
100001, 1001, 1011
10010001, 1001, 1001, 101
10110101, 11001, 100001, 1
110111, 100001, 11, 101
1001101, 110111, 1, 11, 1

Palsu

101
101, 11
1, 1001
1011, 1011
11011, 1001101
1001, 11011, 1000001
1001, 11011, 1000001, 10101

code-golf decision-problem binary tiling Luis Mendo
sumber

1

Terkait

Wheat Wizard

3

Versi tak terbatas dari masalah ini mungkin menarik juga (yaitu apakah satu set ubin dapat sepenuhnya mengisi garis 1D tanpa tumpang tindih). Maka hal-hal seperti 101101akan menjadi kebenaran, meskipun tidak ada jumlah terbatas dari mereka menghasilkan blok yang berdekatan.

Martin Ender

4

Jelly , 15 byte

+"FṢIP
FSṗLç€ċ1

Mengambil daftar indeks dan mengembalikan bilangan bulat positif (kebenaran) atau 0 (salah).

Cobalah online! atau verifikasi sebagian besar kasus uji .

Dennis
sumber

8

JavaScript (ES6), 74 73 70 byte

Mengambil input sebagai array bilangan bulat 32-bit. Mengembalikan boolean.

f=([n,...a],x)=>n?[...f+''].some(_=>n&&!(x&n)&f(a,x|n,n<<=1)):!(x&-~x)

Atau 66 byte dengan nilai kebenaran / kepalsuan terbalik:

f=([n,...a],x)=>n?[...Array(32)].every(_=>x&n|f(a,x|n,n*=2)):x&-~x

Uji kasus

Tampilkan cuplikan kode

f=([n,...a],x)=>n?[...f+''].some(_=>n&&!(x&n)&f(a,x|n,n<<=1)):!(x&-~x)

console.log('[Truthy]')
console.log(f([0b1]))
console.log(f([0b111]))
console.log(f([0b1,0b1]))
console.log(f([0b11,0b111,0b1111]))
console.log(f([0b101,0b11,0b1]))
console.log(f([0b101,0b11,0b101]))
console.log(f([0b10001,0b11001,0b10001]))
console.log(f([0b100001,0b1001,0b1011]))
console.log(f([0b10010001,0b1001,0b1001,0b101]))
console.log(f([0b10110101,0b11001,0b100001,0b1]))
console.log(f([0b110111,0b100001,0b11,0b101]))
console.log(f([0b1001101,0b110111,0b1,0b11,0b1]))

console.log('[Falsy]')
console.log(f([0b101]))
console.log(f([0b101,0b11]))
console.log(f([0b1,0b1001]))
console.log(f([0b1011,0b1011]))
console.log(f([0b11011,0b1001101]))
console.log(f([0b1001,0b11011,0b1000001]))
console.log(f([0b1001,0b11011,0b1000001,0b10101]))

Luaskan cuplikan

Bagaimana?

f = (                       // f = recursive function taking:
  [n, ...a],                //   n = next integer, a = array of remaining integers
  x                         //   x = solution bitmask, initially undefined
) =>                        //
  n ?                       // if n is defined:
    [... f + ''].some(_ =>  //   iterate 32+ times:
      n &&                  //     if n is not zero:
        !(x & n)            //       if x and n have some bits in common,
        &                   //       force invalidation of the following result
        f(                  //       do a recursive call with:
          a,                //         the remaining integers
          x | n,            //         the updated bitmask
          n <<= 1           //         and update n for the next iteration
        )                   //       end of recursive call
    )                       //   end of some()
  :                         // else (all integers have been processed):
    !(x & -~x)              //   check that x is a continuous chunk of 1's

Arnauld
sumber

4

Sekam , 16 byte

V§=OŀF×+ṠṀṪ+oŀṁ▲

Mengambil daftar daftar indeks berbasis 1. Cobalah online!

Penjelasan

V§=OŀF×+ṠṀṪ+oŀṁ▲  Implicit input, say x=[[1,3],[1]]
              ṁ▲  Sum of maxima: 4
            oŀ    Lowered range: r=[0,1,2,3]
        ṠṀ        For each list in x,
          Ṫ+      create addition table with r: [[[1,3],[2,4],[3,5],[4,6]],
                                                 [[1],[2],[3],[4]]]
     F×+          Reduce by concatenating all combinations: [[1,3,1],[1,3,2],...,[4,6,4]]
V                 1-based index of first list y
    ŀ             whose list of 1-based indices [1,2,...,length(y)]
 §=               is equal to
   O              y sorted: 2

Zgarb
sumber

3

Jelly , 16 byte

FLḶ0ẋ;þ⁸ŒpS€P€1e

Tautan monadik yang mengambil daftar daftar satu dan nol yang mengembalikan keduanya 1 (kebenaran) atau 0(falsey).

Cobalah online!atau lihat test-suite (disingkat - 6 kesalahan pertama diikuti oleh delapan kebenaran pertama karena panjang empat yang terlalu lama untuk dimasukkan karena penggunaan produk Cartesian).

Bagaimana?

FLḶ0ẋ;þ⁸ŒpS€P€1e - Link: list of lists, tiles
F                - flatten (the list of tiles into a single list)
 L               - length (gets the total number of 1s and zeros in the tiles)
  Ḷ              - lowered range = [0,1,2,...,that-1] (how many zeros to try to prepend)
   0             - literal zero
    ẋ            - repeat = [[],[0],[0,0],...[0,0,...,0]] (the zeros to prepend)
       ⁸         - chain's left argument, tiles
      þ          - outer product with:
     ;           -   concatenation (make a list of all of the zero-prepended versions)

        Œp       - Cartesian product (all ways that could be chosen, including man
                 -   redundant ones like prepending n-1 zeros to every tile)
          S€     - sum €ach (good yielding list of only ones)
            P€   - product of €ach (good yielding 1, others yielding 0 or >1)
              1  - literal one
               e - exists in that? (1 if so 0 if not)

Jonathan Allan
sumber

2

Python 2 , 159 byte

lambda x:g([0]*sum(map(sum,x)),x)
g=lambda z,x:x and any(g([a|x[0][j-l]if-1<j-l<len(x[0])else a for j,a in enumerate(z)],x[1:])for l in range(len(z)))or all(z)

Cobalah online!

Halvard Hummel
sumber

1

153 byte

ovs

2

Jelly , 16 byte

FLḶ0ẋ;þµŒpSP$€1e

Cobalah online!

-1 byte terima kasih kepada Tn. Xcoder

Saya mengembangkan ini sepenuhnya independen dari Jonathan Allan tetapi sekarang melihat miliknya persis sama:

HyperNeutrino
sumber

1

J , 74 byte

f=:3 :'*+/1=*/"1+/"2(l{."1 b)|.~"1 0"_ 1>,{($,y)#<i.l=:+/+/b=:>,.&.":&.>y'

Saya mungkin mencoba membuatnya diam-diam nanti, tetapi untuk sekarang ini adalah kata kerja eksplisit. Saya akan menjelaskan versi yang tidak diserang. Dibutuhkan daftar bilangan bulat kotak dan mengembalikan 1(benar) atau 0(salah).

This will be my test case, a list of boxed integers:
   ]a=:100001; 1001; 1011                
┌──────┬────┬────┐
│100001│1001│1011│
└──────┴────┴────┘
b is the rectangular array from the input, binary digits. Shorter numbers are padded
with trailing zeroes:
   ]b =: > ,. &. ": &.> a   NB. Unbox each number, convert it to a list of digits 
1 0 0 0 0 1
1 0 0 1 0 0
1 0 1 1 0 0

l is the total number of 1s in the array: 
   ]l=: +/ +/ b             NB. add up all rows, find the sum of the resulting row)
7

r contains all possible offsets needed for rotations of each row: 
   r=: > , { ($,a) # < i.l  NB. a catalogue of all triplets (in this case, the list
has 3 items) containing the offsets from 0 to l:
0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
 ...
6 6 3
6 6 4
6 6 5
6 6 6

m is the array after all possible rotations of the rows of b by the offsets in r. 
But I first extend each row of b to the total length l:
   m=: r |."0 1"1 _ (l {."1 b)  NB. rotate the extended rows of b with offsets in r,
ranks adjusted

For example 14-th row of the offsets array applied to b:
    13{r
0 1 6
   13{m
1 0 0 0 0 1 0
0 0 1 0 0 0 1
0 1 0 1 1 0 0

Finally I add the rows for each permutation, take the product to check if it's all 1, and
check if there is any 1 in each permuted array.
   * +/ 1= */"1 +/"2 m
1

Cobalah online!

Galen Ivanov
sumber

Miring terbatas dalam satu dimensi

Contohnya

Aturan tambahan

Uji kasus

Sejujurnya

Palsu

Jawaban:

Jelly , 15 byte

JavaScript (ES6), 74 73 70 byte

Uji kasus

Bagaimana?

Sekam , 16 byte

Penjelasan

Jelly , 16 byte

Bagaimana?

Python 2 , 159 byte

Jelly , 16 byte

J , 74 byte