32

Celem tego wyzwania jest ustalenie, czy zbiór kawałków o jednym wymiarze można kafelkować, tworząc skończoną ciągłą bryłę.

Kawałek jest niepusty, skończony ciąg zer i jedynek, które zaczyna się i kończy o jeden. Niektóre kawałki są możliwe 1, 101, 1111, 1100101.

Układanie płytek oznacza takie ułożenie elementów, aby powstał jeden ciągły blok. Jeden z jednego kawałka może zajmować miejsce zero, ale nie jednego z drugiego kawałka.

Odpowiednio, jeśli uważamy, że jeden jest „litym materiałem”, a zero jako „dziurą”, elementy powinny pasować tak, aby tworzyły pojedynczy odcinek, nie pozostawiając żadnych otworów.

Aby utworzyć płytki, elementy można przesuwać tylko wzdłuż ich jednowymiarowej przestrzeni. (Nie można ich podzielić ani odzwierciedlić). Każdy element jest używany dokładnie raz.

Przykłady

Te trzy części 101, 11, 101mogą być wyłożone jak pokazano poniżej, w której każdy element jest reprezentowany wymaganym przesunięciem:

  101
11
   101

więc uzyskane płytki są

Jako drugi przykład, kawałki 11011i 1001101nie można kafelkować. W szczególności przesunięcie

 11011
1001101

nie jest poprawny, ponieważ zderzają się dwa; i

11011
  1001101

nie jest poprawny, ponieważ wynik zawiera zero.

Dodatkowe zasady

Dane wejściowe to zbiór jednego lub więcej elementów. Dowolny rozsądny format jest dozwolony; na przykład:

Lista ciągów, gdzie każdy ciąg może zawierać dwa różne, spójne znaki;
Kilka tablic, gdzie każda tablica zawiera pozycje jedności dla kawałka;
Lista (nieparzystych) liczb całkowitych, takich jak binarna reprezentacja każdej liczby, definiuje kawałek.

Dane wyjściowe powinny mieć wartość zgodną z prawdą, jeśli możliwe jest kafelkowanie, a wartość fałszowania w przeciwnym razie. Wartości wyjściowe nie muszą być spójne; oznacza to, że mogą być różne dla różnych danych wejściowych.

Programy lub funkcje są dozwolone w dowolnym języku programowania . Standardowe luki są zabronione.

Najkrótszy kod w bajtach wygrywa.

Przypadki testowe

Każde wejście jest w innej linii

Prawda

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

Falsy

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

code-golf decision-problem binary tiling Luis Mendo
źródło

1

Powiązane

Wheat Wizard,

3

Nieskończona wersja tego problemu może być również interesująca (tj. Czy zestaw płytek może całkowicie wypełnić linię 1D bez nakładania się). Wtedy rzeczy takie jak 101101byłyby prawdziwe, nawet jeśli żadna ich skończona liczba nie powoduje ciągłego blokowania.

Martin Ender,

4

Galaretka , 15 bajtów

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

Pobiera listę indeksów i zwraca dodatnią liczbę całkowitą (prawda) lub 0 (fałsz).

Wypróbuj online! lub zweryfikuj większość przypadków testowych .

Dennis
źródło

8

JavaScript (ES6), 74 73 70 bajtów

Pobiera dane wejściowe jako tablicę 32-bitowych liczb całkowitych. Zwraca wartość logiczną.

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

Lub 66 bajtów z odwróconymi wartościami prawda / fałsz:

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

Przypadki testowe

Pokaż fragment kodu

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

Rozwiń fragment kodu

W jaki sposób?

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
źródło

4

Łuska , 16 bajtów

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

Pobiera listę indeksów opartych na 1. Wypróbuj online!

Wyjaśnienie

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
źródło

3

Galaretka , 16 bajtów

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

Monadyczny link zawierający listę list zer i jedynek zwracających albo 1(prawda) albo 0(falsey).

Wypróbuj online! lub zobacz zestaw testowy (skrócony - pierwsze 6 fałszywych, a następnie pierwszych ośmiu prawdziwych, ponieważ długość czterech z nich zajmuje zbyt wiele czasu ze względu na użycie produktu kartezjańskiego).

W jaki sposób?

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
źródło

2

Python 2 , 159 bajtów

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)

Wypróbuj online!

Halvard Hummel
źródło

1

153 bajty

ovs

2

Galaretka , 16 bajtów

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

Wypróbuj online!

-1 bajt dzięki Mr. Xcoder

Opracowałem to całkowicie niezależnie od Jonathana Allana, ale teraz patrzenie na jego jest dokładnie takie samo:

HyperNeutrino
źródło

1

J , 74 bajty

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

Mogę spróbować zrobić to milcząco później, ale na razie jest to wyraźny czasownik. Wyjaśnię wersję bez golfa. Pobiera listę zapakowanych liczb całkowitych i zwraca 1(prawda) lub 0(fałsz).

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

Wypróbuj online!

Galen Iwanow
źródło

Skończone dachówki w jednym wymiarze

Przykłady

Dodatkowe zasady

Przypadki testowe

Prawda

Falsy

Odpowiedzi:

Galaretka , 15 bajtów

JavaScript (ES6), 74 73 70 bajtów

Przypadki testowe

W jaki sposób?

Łuska , 16 bajtów

Wyjaśnienie

Galaretka , 16 bajtów

W jaki sposób?

Python 2 , 159 bajtów

Galaretka , 16 bajtów

J , 74 bajty