32

0

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
```

1Related – Post Rock Garf Hunter – 2017-11-10T04:25:36.373

3The infinite version of this problem might be interesting as well (i.e. whether a set of tiles can completely fill the 1D line without overlaps). Then stuff like

`101101`

would be truthy, even though no finite number of them result in a contiguous block. – Martin Ender – 2017-11-10T09:32:14.657