# Finite tilings in one dimension

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.

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

• Related Nov 10, 2017 at 4:25
• The 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. Nov 10, 2017 at 9:32

# JavaScript (ES6), 7473 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


# Jelly, 15 bytes

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


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

# 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


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


# 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!

• 153 bytes
– ovs
Nov 9, 2017 at 22:20

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: # 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,

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!