32

Le but de ce défi est de déterminer si une collection de pièces unidimensionnelles peut être carrelée pour former un morceau continu fini.

Une pièce est une séquence finie non vide de zéros et de uns qui commence et se termine par un. Certaines pièces sont possibles 1, 101, 1111, 1100101.

Le carrelage consiste à disposer les pièces de manière à former un seul bloc contigu de pièces. Un un d'une pièce peut occuper la place d'un zéro, mais pas d'un, d'une autre pièce.

De manière équivalente, si nous considérons l'un comme étant un "matériau solide" et un zéro comme un "trou", les pièces doivent s'ajuster de manière à former un seul étirement, sans laisser de trous.

Pour former un carrelage, les pièces ne peuvent être déplacées que le long de leur espace unidimensionnel. (Ils ne peuvent pas être divisés ou réfléchis). Chaque pièce est utilisée exactement une fois.

Exemples

Les trois pièces 101, 11, 101peuvent être carrelée comme indiqué ci - après, où chaque pièce est représentée par le décalage requis:

  101
11
   101

de sorte que le carrelage obtenu est

Comme deuxième exemple, les pièces 11011et 1001101ne peuvent pas être carrelées. En particulier, le changement

 11011
1001101

n'est pas valide car il y en a deux qui entrent en collision; et

11011
  1001101

n'est pas valide car le résultat contiendrait un zéro.

Règles supplémentaires

L' entrée est une collection d'une ou plusieurs pièces. Tout format raisonnable est autorisé; par exemple:

Une liste de chaînes, où chaque chaîne peut contenir deux caractères différents et cohérents;
Plusieurs tableaux, où chaque tableau contient les positions de ceux d'un morceau;
Une liste d'entiers (impairs) tels que la représentation binaire de chaque nombre définit une pièce.

La sortie doit être une valeur véridique si un pavage est possible, et une valeur fausse dans le cas contraire. Les valeurs de sortie n'ont pas besoin d'être cohérentes; c'est-à-dire qu'ils peuvent être différents pour différentes entrées.

Les programmes ou fonctions sont autorisés, dans n'importe quel langage de programmation . Les failles standard sont interdites.

Le code le plus court en octets gagne.

Cas de test

Chaque entrée est sur une ligne différente

Vérité

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 Luis Mendo
la source

1

En relation

Wheat Wizard

3

La version infinie de ce problème pourrait également être intéressante (c'est-à-dire si un ensemble de tuiles peut remplir complètement la ligne 1D sans chevauchements). Alors des trucs comme 101101seraient véridiques, même si aucun nombre fini d'entre eux ne résulte en un bloc contigu.

Martin Ender

4

Gelée , 15 octets

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

Prend une liste d'indices et renvoie un entier positif (véridique) ou 0 (falsifié).

Essayez-le en ligne! ou vérifiez la plupart des cas de test .

Dennis
la source

8

JavaScript (ES6), 74 73 70 octets

Prend l'entrée comme un tableau d'entiers 32 bits. Retourne un booléen.

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

Ou 66 octets avec des valeurs de vérité / fausse inversées:

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

Cas de test

Afficher l'extrait de code

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

Développer l'extrait

Comment?

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
la source

4

Husk , 16 octets

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

Prend une liste de listes d'indices basés sur 1. Essayez-le en ligne!

Explication

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
la source

3

Gelée , 16 octets

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

Un lien monadique contenant une liste de listes de uns et de zéros renvoyant soit 1(véridique), soit 0(falsey).

Essayez-le en ligne! ou voir une suite de tests (raccourci - les 6 premiers faux suivis des huit premiers véridiques car la longueur quatre est trop longue à inclure en raison de l'utilisation du produit cartésien).

Comment?

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
la source

2

Python 2 , 159 octets

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)

Essayez-le en ligne!

Halvard Hummel
la source

1

153 octets

ovs

2

Gelée , 16 octets

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

Essayez-le en ligne!

-1 octet merci à M. Xcoder

J'ai développé cela complètement indépendamment de Jonathan Allan, mais maintenant, regarder le sien est exactement le même:

HyperNeutrino
la source

1

J , 74 octets

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

Je pourrais essayer de le rendre tacite plus tard, mais pour l'instant c'est un verbe explicite. Je vais vous expliquer la version non golfée. Il prend une liste d'entiers encadrés et renvoie 1(véridique) ou 0(falsifié).

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

Essayez-le en ligne!

Galen Ivanov
la source

Carrelages finis en une dimension

Exemples

Règles supplémentaires

Cas de test

Vérité

Falsy

Réponses:

Gelée , 15 octets

JavaScript (ES6), 74 73 70 octets

Cas de test

Comment?

Husk , 16 octets

Explication

Gelée , 16 octets

Comment?

Python 2 , 159 octets

Gelée , 16 octets

J , 74 octets