32

Der Zweck dieser Herausforderung besteht darin, festzustellen, ob eine Sammlung von eindimensonalen Stücken gekachelt werden kann, um einen endlichen kontinuierlichen Block zu bilden.

Ein Stück ist eine nicht leere, endliche Folge von Nullen und Einsen, die mit einer Eins beginnt und endet. Einige mögliche Stücke sind 1, 101, 1111, 1100101.

Kacheln bedeutet, die Teile so anzuordnen, dass ein einzelner zusammenhängender Einsenblock entsteht. Eine Eins aus einem Stück kann die Stelle einer Null, aber nicht einer Eins aus einem anderen Stück einnehmen.

Wenn wir eine Eins als "festes Material" und eine Null als "Loch" betrachten, sollten die Teile so passen, dass sie eine einzelne Strecke bilden, ohne Löcher zu hinterlassen.

Um eine Kachelung zu bilden, können Teile nur entlang ihres eindimensionalen Raums verschoben werden. (Sie können nicht geteilt oder reflektiert werden). Jedes Stück wird genau einmal verwendet.

Beispiele

Die drei Stücke 101, 11, 101können gefliest werden , wie im Folgenden gezeigt, wobei jedes Stück mit der erforderlichen Verschiebung dargestellt wird:

  101
11
   101

so ist die erhaltene Kachelung

Als zweites Beispiel können die Stücke 11011und 1001101nicht gekachelt werden. Insbesondere die Verschiebung

 11011
1001101

ist nicht gültig, weil zwei kollidieren; und

11011
  1001101

ist nicht gültig, da das Ergebnis eine Null enthalten würde.

Zusätzliche Regeln

Die Eingabe ist eine Sammlung von einem oder mehreren Stücken. Jedes vernünftige Format ist zulässig. beispielsweise:

Eine Liste von Zeichenfolgen, wobei jede Zeichenfolge zwei verschiedene, konsistente Zeichen enthalten kann.
Mehrere Arrays, wobei jedes Array die Positionen von Einsen für ein Stück enthält;
Eine Liste von (ungeraden) ganzen Zahlen wie die binäre Darstellung jeder Zahl definiert ein Stück.

Die Ausgabe sollte ein wahrer Wert sein, wenn eine Kachelung möglich ist, und ein falscher Wert, wenn keine Kachelung möglich ist. Ausgabewerte müssen nicht konsistent sein; Das heißt, sie können für verschiedene Eingaben unterschiedlich sein.

Programme oder Funktionen sind in jeder Programmiersprache zulässig . Standardlücken sind verboten.

Kürzester Code in Bytes gewinnt.

Testfälle

Jeder Eingang befindet sich in einer anderen Zeile

Wahrheit

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

Falsch

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

code-golf decision-problem binary tiling Luis Mendo
quelle

1

3

Die unendliche Version dieses Problems könnte ebenfalls interessant sein (dh, ob eine Reihe von Kacheln die 1D-Linie ohne Überlappungen vollständig ausfüllen kann). Dann 101101wären solche Dinge wahr, obwohl keine endliche Anzahl von ihnen zu einem zusammenhängenden Block führt.

Martin Ender

4

Gelee , 15 Bytes

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

Nimmt eine Liste von Indizes und gibt eine positive Ganzzahl (wahr) oder 0 (falsch) zurück.

Probieren Sie es online! oder überprüfen Sie die meisten Testfälle .

Dennis
quelle

8

JavaScript (ES6), 74 73 70 Byte

Übernimmt die Eingabe als Array von 32-Bit-Ganzzahlen. Gibt einen Booleschen Wert zurück.

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

Oder 66 Bytes mit invertierten Wahrheits- / Falschwerten:

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

Testfälle

Code-Snippet anzeigen

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

Erweitern Sie das Snippet

Wie?

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
quelle

4

Schale , 16 Bytes

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

Nimmt eine Liste von Listen mit 1-basierten Indizes auf. Probieren Sie es online!

Erläuterung

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
quelle

3

Gelee , 16 Bytes

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

Ein monadischer Link, der eine Liste mit Einsen und Nullen erstellt, die entweder 1(wahr) oder 0(falsch) zurückgeben.

Probieren Sie es online! oder sehen Sie sich eine Testsuite an (verkürzt - die ersten 6 Falschen, gefolgt von den ersten acht Wahrheiten, da die Länge der vier zu lang ist, um sie aufgrund der Verwendung des kartesischen Produkts einzuschließen).

Wie?

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
quelle

2

Python 2 , 159 Bytes

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)

Probieren Sie es online!

Halvard Hummel
quelle

1

153 Bytes

Ovs

2

Gelee , 16 Bytes

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

Probieren Sie es online!

-1 Byte danke an Herrn Xcoder

Ich habe das völlig unabhängig von Jonathan Allan entwickelt, aber jetzt ist es genau dasselbe, wenn ich es mir ansehe:

HyperNeutrino
quelle

1

J , 74 Bytes

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

Ich könnte versuchen, es später stillschweigend zu machen, aber im Moment ist es ein explizites Verb. Ich werde die ungolfed Version erklären. Es nimmt eine Liste von Ganzzahlen in 1Kästchen und gibt (wahr) oder 0(falsch) zurück.

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

Probieren Sie es online!

Galen Ivanov
quelle

Endliche Fliesen in einer Dimension

Beispiele

Zusätzliche Regeln

Testfälle

Wahrheit

Falsch

Antworten:

Gelee , 15 Bytes

JavaScript (ES6), 74 73 70 Byte

Testfälle

Wie?

Schale , 16 Bytes

Erläuterung

Gelee , 16 Bytes

Wie?

Python 2 , 159 Bytes

Gelee , 16 Bytes

J , 74 Bytes