Finite tilings in one dimension

Question

The purpose of this challenge is to determine if a collection of one-dimensonal pieces can be tiled to form a finite continuous chunk.

A piece is a non-empty, finite sequence of zeros and ones that starts and ends with a one. Some possible pieces are 1, 101, 1111, 1100101.

Tiling means arranging the pieces so that a single contiguous block of ones is formed. A one from one piece can occupy the place of a zero, but not of a one, from another piece.

Equivalently, if we view a one as being "solid material" and a zero as a "hole", the pieces should fit so as to form a single stretch, without leaving any holes.

To form a tiling, pieces can only be shifted along their one-dimensional space. (They cannot be split, or reflected). Each piece is used exactly once.

Examples

The three pieces 101, 11, 101 can be tiled as shown in the following, where each piece is represented with the required shift:

  101
11
   101

so the obtained tiling is

111111

As a second example, the pieces 11011 and 1001101 cannot be tiled. In particular, the shift

 11011
1001101

is not valid because there are two ones that collide; and

11011
  1001101

is not valid because the result would contain a zero.

Additional rules

The input is a collection of one or more pieces. Any reasonable format is allowed; for example:

• A list of strings, where each string can contain two different, consistent characters;
• Several arrays, where each array contains the positions of ones for a piece;
• A list of (odd) integers such the binary representation of each number defines a piece.

The output should be a truthy value if a tiling is possible, and a falsy value otherwise. Output values need not be consistent; that is, they can be different for different inputs.

Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

Shortest code in bytes wins.

Test cases

Each input is on a different line

Truthy

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

Answer 1

Jelly, 15 bytes

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

Takes a list of indices and returns a positive integer (truthy) or 0 (falsy).

Try it online! or verify most test cases.

Answer 2

JavaScript (ES6), 74 73 70 bytes

Takes input as an array of 32-bit integers. Returns a boolean.

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

Or 66 bytes with inverted truthy/falsy values:

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

Test cases

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

How?

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

Answer 3

Husk, 16 bytes

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

Takes a list of lists of 1-based indices. Try it online!

Explanation

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

Answer 4

Jelly, 16 bytes

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

A monadic link taking a list of lists of ones and zeros returning either 1 (truthy) or 0 (falsey).

Try it online! or see a test-suite (shortened - first 6 falseys followed by first eight truthys since the length four ones take too long to include due to the use of the Cartesian product).

How?

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)

Answer 5

Jelly, 16 bytes

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

Try it online!

-1 byte thanks to Mr. Xcoder

I developed this completely independently of Jonathan Allan but now looking at his is exactly the same:

Answer 6

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)

Try it online!

Answer 7

J, 74 bytes

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

I might try to make it tacit later, but for now it's an explicit verb. I'll explain the ungolfed version. It takes a list of boxed integers and returns 1 (truthy) or 0 (falsy).

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 

Try it online!