32

Цель этой задачи состоит в том, чтобы определить, можно ли выложить мозаику из набора одномерных частей для формирования конечного непрерывного фрагмента.

Часть является непустым, конечная последовательность нулей и единиц , которые начинаются и заканчиваются в одном. Некоторые возможные куски 1, 101, 1111, 1100101.

Черепица означает расположение кусков так, чтобы формировался один непрерывный блок из них. Один из одного куска может занимать место нуля, но не одного, из другого куска.

Эквивалентно, если мы рассматриваем единицу как «твердый материал», а ноль как «дыру», кусочки должны соответствовать так, чтобы образовать единое растяжение, не оставляя никаких отверстий.

Чтобы сформировать плитку, кусочки можно перемещать только вдоль их одномерного пространства. (Они не могут быть разделены или отражены). Каждый кусок используется ровно один раз.

Примеры

Три части 101, 11, 101может быть черепичные , как показано в следующем, где каждая часть представлена с требуемым сдвигом:

  101
11
   101

так что полученная черепица

В качестве второго примера, кусочки 11011и 1001101не могут быть выложены плиткой. В частности, смена

 11011
1001101

недопустимо, потому что есть два, которые сталкиваются; а также

11011
  1001101

недопустимо, потому что результат будет содержать ноль.

Дополнительные правила

Ввода представляет собой набор из одной или нескольких частей. Разрешен любой разумный формат; например:

Список строк, где каждая строка может содержать два разных, согласованных символа;
Несколько массивов, где каждый массив содержит позиции единиц для куска;
Список (нечетных) целых чисел, таких как двоичное представление каждого числа, определяет кусок.

Выход должен быть значением truthy , если плиточные можно и falsy значение в противном случае. Выходные значения не должны быть согласованными; то есть они могут быть разными для разных входов.

Программы или функции разрешены на любом языке программирования . Стандартные лазейки запрещены.

Самый короткий код в байтах побеждает.

Контрольные примеры

Каждый вход находится на отдельной строке

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

code-golf decision-problem binary tiling Луис Мендо
источник

1

Связанный

Волшебник Пшеницы

3

Также может быть интересна бесконечная версия этой проблемы (то есть может ли набор плиток полностью заполнить 1D линию без перекрытий). Тогда подобные вещи 101101будут правдивыми, даже если их конечное число не приведет к непрерывному блоку.

Мартин Эндер

4

Желе , 15 байт

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

Принимает список индексов и возвращает положительное целое число (истина) или 0 (ложь).

Попробуйте онлайн! или проверьте большинство тестовых случаев .

Деннис
источник

8

JavaScript (ES6), 74 73 70 байт

Принимает ввод в виде массива 32-битных целых чисел. Возвращает логическое значение.

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

Или 66 байтов с инвертированными значениями правда / ложь:

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

Контрольные примеры

Показать фрагмент кода

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

Развернуть фрагмент

Как?

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
источник

4

Шелуха , 16 байт

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

Принимает список списков на основе 1 индексов. Попробуйте онлайн!

объяснение

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
источник

3

Желе , 16 байт

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

Монадическая ссылка, содержащая список списков единиц и нулей, возвращающих либо 1(правдиво), либо 0(фалси).

Попробуйте онлайн! или посмотрите набор тестов (укороченный - первые 6 ложных значений, за которыми следуют первые восемь истинных значений, поскольку длина четырех из них занимает слишком много времени из-за использования декартового произведения).

Как?

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)

Джонатан Аллан
источник

2

Python 2 , 159 байт

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)

Попробуйте онлайн!

Халвард Хаммель
источник

1

153 байт

овс

2

Желе , 16 байт

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

Попробуйте онлайн!

-1 байт благодаря мистеру Xcoder

Я разработал это совершенно независимо от Джонатана Аллана, но теперь смотрю на него точно так же:

HyperNeutrino
источник

1

J , 74 байта

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

Я мог бы попытаться сделать это молчаливым позже, но пока это явный глагол. Я объясню неоправданную версию. Он принимает список целых чисел в штучной упаковке и возвращает 1(правда) или 0(ложь).

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

Попробуйте онлайн!

Гален Иванов
источник

Конечные плитки в одном измерении

Примеры

Дополнительные правила

Контрольные примеры

Truthy

Falsy

Ответы:

Желе , 15 байт

JavaScript (ES6), 74 73 70 байт

Контрольные примеры

Как?

Шелуха , 16 байт

объяснение

Желе , 16 байт

Как?

Python 2 , 159 байт

Желе , 16 байт

J , 74 байта