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
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.
The three pieces
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
As a second example, the pieces
1001101 cannot be tiled. In particular, the shift
is not valid because there are two ones that collide; and
is not valid because the result would contain a zero.
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.
Shortest code in bytes wins.
Each input is on a different line
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
101 101, 11 1, 1001 1011, 1011 11011, 1001101 1001, 11011, 1000001 1001, 11011, 1000001, 10101