32

El propósito de este desafío es determinar si una colección de piezas unidimensionales se puede colocar en mosaico para formar un trozo continuo finito.

Una pieza es una secuencia finita no vacía de ceros y unos que comienza y termina con uno. Algunas piezas son posibles 1, 101, 1111, 1100101.

Mosaico significa organizar las piezas de manera que se forme un bloque contiguo de unidades. Un uno de una pieza puede ocupar el lugar de un cero, pero no de un uno, de otra pieza.

De manera equivalente, si consideramos que uno es "material sólido" y un cero como "agujero", las piezas deben encajar para formar un solo tramo, sin dejar ningún agujero.

Para formar un mosaico, las piezas solo se pueden desplazar a lo largo de su espacio unidimensional. (No se pueden dividir ni reflejar). Cada pieza se usa exactamente una vez.

Ejemplos

Las tres piezas 101, 11, 101se pueden embaldosar como se muestra en la siguiente, donde cada pieza está representado con el cambio requerido:

  101
11
   101

entonces el mosaico obtenido es

Como segundo ejemplo, las piezas 11011y 1001101no pueden ser en mosaico. En particular, el cambio

 11011
1001101

no es válido porque hay dos que chocan; y

11011
  1001101

no es válido porque el resultado contendría un cero.

Reglas adicionales

La entrada es una colección de una o más piezas. Se permite cualquier formato razonable; por ejemplo:

Una lista de cadenas, donde cada cadena puede contener dos caracteres diferentes y consistentes;
Varios conjuntos, donde cada conjunto contiene las posiciones de unos para una pieza;
Una lista de enteros (impares) como la representación binaria de cada número define una pieza.

La salida debe ser un valor verdadero si es posible un mosaico, y un valor falso de lo contrario. Los valores de salida no necesitan ser consistentes; es decir, pueden ser diferentes para diferentes entradas.

Se permiten programas o funciones , en cualquier lenguaje de programación . Las lagunas estándar están prohibidas.

El código más corto en bytes gana.

Casos de prueba

Cada entrada está en una línea diferente

Verdad

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

Falsa

101
101, 11
1, 1001
1011, 1011
11011, 1001101
1001, 11011, 1000001
1001, 11011, 1000001, 10101

code-golf decision-problem binary tiling Luis Mendo
fuente

1

Relacionado

Wheat Wizard

3

La versión infinita de este problema también puede ser interesante (es decir, si un conjunto de mosaicos puede llenar completamente la línea 1D sin superposiciones). Entonces, cosas como 101101serían verdaderas, aunque ningún número finito de ellas dé como resultado un bloque contiguo.

Martin Ender

4

Jalea , 15 bytes

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

Toma una lista de índices y devuelve un entero positivo (verdadero) o 0 (falso).

Pruébalo en línea! o verificar la mayoría de los casos de prueba .

Dennis
fuente

8

JavaScript (ES6), 74 73 70 bytes

Toma datos como una matriz de enteros de 32 bits. Devuelve un booleano.

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

O 66 bytes con valores de verdad / falsedad invertidos:

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

Casos de prueba

Mostrar fragmento de código

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

Expandir fragmento

¿Cómo?

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
fuente

4

Casco , 16 bytes

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

Toma una lista de listas de índices basados en 1. Pruébalo en línea!

Explicación

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
fuente

3

Jalea , 16 bytes

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

Un enlace monádico que toma una lista de listas de unos y ceros que devuelven 1(verdad) o 0(falsey).

Pruébalo en línea! o vea un conjunto de pruebas (acortado: los primeros 6 falseys seguidos de los primeros ocho trueys, ya que los cuatro largos tardan demasiado en incluirse debido al uso del producto cartesiano).

¿Cómo?

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)

Jonathan Allan
fuente

2

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)

Pruébalo en línea!

Halvard Hummel
fuente

1

153 bytes

2017

2

Jalea , 16 bytes

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

Pruébalo en línea!

-1 byte gracias al Sr. Xcoder

Desarrollé esto completamente independiente de Jonathan Allan, pero ahora mirarlo es exactamente lo mismo:

Hiperneutrino
fuente

1

J 74 bytes

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

Podría intentar hacerlo tácito más tarde, pero por ahora es un verbo explícito. Explicaré la versión sin golf. Toma una lista de enteros en caja y retornos 1(verdadero) o 0(falso).

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

Pruébalo en línea!

Galen Ivanov
fuente

Inclinación finita en una dimensión

Ejemplos

Reglas adicionales

Casos de prueba

Verdad

Falsa

Respuestas:

Jalea , 15 bytes

JavaScript (ES6), 74 73 70 bytes

Casos de prueba

¿Cómo?

Casco , 16 bytes

Explicación

Jalea , 16 bytes

¿Cómo?

Python 2 , 159 bytes

Jalea , 16 bytes

J 74 bytes