Écrivez un programme ou une fonction qui accepte une chaîne multiligne de 0«et 1». Aucun autre caractère ne sera dans la chaîne et la chaîne sera toujours rectangulaire (toutes les lignes auront le même nombre de caractères), avec des dimensions aussi petites que 1 × 1, mais sinon les 0'et 1' peuvent être arrangés arbitrairement.

Vous pouvez supposer que la chaîne a un retour à la ligne facultatif et si vous le souhaitez, vous pouvez utiliser deux caractères ASCII imprimables distincts à la place de 0et 1.

Affiche ou retourne une valeur vraie si toutes les régions connectées au chemin des deux 0et 1de la chaîne sont des rectangles pleins , sinon émettent une valeur fausse .

Un chemin région connectée de 0« les moyens de qu'à partir de l' une quelconque 0de la région, tous les autres 0» s peut être atteint que par le déplacement de haut en bas, à gauche et à droite avec une autre 0« s (et ne se déplaçant en diagonale, pas se déplacer l' une quelconque 1, et ne se déplace pas en dehors des limites de la chaîne). La même idée s'applique aux 1régions connectées au chemin.

Un rectangle plein de 0«s» signifie que toute la zone du rectangle est remplie de 0«et de non 1». La même idée s'applique aux 1rectangles pleins.

Le code le plus court en octets gagne. Tiebreaker est une réponse antérieure.

(Notez que la chaîne ne s'enroule pas avec des conditions aux limites toroïdales .)

Exemples

1) Cette chaîne d'entrée a 3 régions connectées au chemin (2 pour 0et 1 pour 1). 00Cependant, seule la région inférieure droite est un rectangle plein, donc la sortie serait fausse.

0011
0111
0100

2) Cette chaîne d'entrée a 4 régions connectées au chemin (2 pour les deux 0et 1). Tous sont des rectangles pleins donc la sortie serait véridique.

0011
0011
1100

3) Cette entrée a 2 régions connectées à un chemin, mais une seule d'entre elles est un rectangle plein, donc la sortie serait fausse.

00000000
01111110
00000000

4) Cette entrée n'a qu'une seule région connectée par chemin et est trivialement un rectangle plein, donc la sortie est véridique.

11111111
11111111
11111111

Cas de test

Un Tjuste en dessous de la chaîne d'entrée signifie véridique, Fsignifie fausseté.

0
T

1
T

00
T

01
T

10
T

11
T

0000000
T

1111111
T

011100100100101100110100100100101010100011100101
T

00
11
T

01
10
T

01
11
F

00
01
F

11
11
T

110
100
F

111
000
T

111
101
111
F

101
010
101
T

1101
0010
1101
0010
T

1101
0010
1111
0010
F

0011
0111
0100
F

0011
0011
1100
T

00000000
01111110
00000000
F

11111111
11111111
11111111
T

0000001111
0000001111
T

0000001111
0000011111
F

0000001111
1000001111
F

1000001111
1000001111
T

1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111
F

Gelée , 7 octets

ṣ⁷µ=ḢZE

Cela utilise le même algorithme que la réponse Ruby de @ LevelRiverSt . L'algorithme réel tient dans les 4 derniers octets; les 3 premiers octets sont nécessaires pour analyser le format d'entrée.

Essayez-le en ligne!

Comment ça marche

ṣ⁷µ=ḢZE  Main link. Argument: t (string)

ṣ⁷       Split t at linefeeds..
  µ      Begin a new, monadic link. Argument: A (list of strings)
    Ḣ    Pop the first string of A.
   =     Compare all other strings in A with the first.
         = compares characters, so this yields a list of Booleans for each string.
         For a truthy input, all pairs of lines now have been transformed in lists
         of only 1's or only 0's. That means all columns must be equal.
     Z   Zip; transpose rows with columns.
      E  Check if all rows (former columns) are equal to each other.

Gelée , 11 10 octets

ṣ⁷^2\⁺€FS¬

Un grand merci à @Dennis pour avoir joué à celui-ci jusqu'à la moitié de sa taille d'origine (via des fonctionnalités non documentées).

Essayez-le en ligne ! Notez que les guillemets triples sont pour une chaîne multiligne.

Explication

L'algorithme de base est le suivant: renvoyer true ssi chaque sous-grille 2x2 a un nombre pair de 1 (ou, de manière équivalente, de 0).

Il est clair pourquoi un nombre impair de 1 ne peut pas fonctionner, car nous aurions l'un des éléments suivants:

10  01  00  00  01  10  11  11
00  00  01  10  11  11  10  01

Notez que les 4 premiers sont des rotations de la même chose, et idem pour les 4 derniers. L'angle réflexe ne peut pas faire partie d'un rectangle, d'où pourquoi il serait invalide.

En d'autres termes, toutes les sous-grilles 2x2 doivent être l'une des suivantes:

00  00  11  01  10  01  10  11
00  11  00  01  10  10  01  11

qui, si nous regardons les limites, peuvent être imaginées comme les "pièces du puzzle" suivantes:

 ___    ___    ___    ___
|   |  | | |  |   |  | | |
|   |  | | |  |---|  |-|-|
|___|  |_|_|  |___|  |_|_|

Et essayez de former un non-rectangle avec ces pièces du puzzle :) (tout en faisant correspondre les extrémités)

La mise en œuvre réelle est donc:

ṣ⁷               Split input by newlines to give rows
  ^2\            Taking overlapping sets of 2 rows at a time: accumulate rows by XOR
                 Note that strings cast to integers automatically for bitwise operators
     ⁺€          Repeat the previous link (⁺), on each (€) element in the resulting array
       F         Flatten the array
        S        Sum (effectively reducing by OR)
         ¬       Logical negation of the result

Par exemple, pour l'entrée

100
010
000
101

on a:

  ṣ⁷: ["100", "010", "000", "101"]
 ^2\: [[1, 1, 0], [0, 1, 0], [1, 0, 1]]    (e.g. first entry is "100" ^ "010")
^2\€: [[0, 1], [1, 1], [1, 1]]             (e.g. the first entry is [1^1, 1^0] - this
                                            gives the counts of 1s in each subgrid, mod 2)
   F: [0, 1, 1, 1, 1, 1]
   S: 5                                    (this gives the number of invalid 2x2 subgrids,
                                            which is indeed all but the top left)
   ¬: 0

Rubis, 76

->s{j=!r=1
s.lines{|t|i=t.to_i(2)
j&&r&&=(j^i)%t.tr(?0,?1).to_i(2)<1
j=i}
r}

Dans toute grille composée entièrement de rectangles, chaque ligne doit être identique à la ligne précédente, ou avoir tous les bits inversés de 0 à 1 et vice versa.

C'est facile à prouver. Prenez un morceau de papier et tracez des lignes verticales et horizontales arbitraires tout le long. Maintenant coloriez les rectangles en utilisant seulement 2 couleurs. Vous vous retrouverez avec un damier déformé, où toutes les couleurs basculent à chaque ligne.

Vous voulez dessiner des rectangles avec des lignes à mi-chemin? essayez de supprimer un segment de l'une de vos lignes. Vous aurez maintenant besoin de plus de 2 couleurs pour colorer votre design, car vous aurez des points où 3 rectangles se rencontrent (2 coins et un bord.) De tels designs ne sont donc pas pertinents pour cette question.

Je suis surpris que les réponses jusqu'à présent ne l'aient pas remarqué.

Je pense que cet algorithme devrait être beaucoup plus court dans une autre langue.

Non testé dans le programme de test

f=->s{
  j=!r=1                              #r = truthy, j=falsy
  s.lines{|t|                         #for each line
    i=t.to_i(2)                       #i = value of current line, converted to a number in base 2 (binary)
    j&&                               #if j is truthy (i.e this is not the first line)
      r&&=(j^i)%t.tr(?0,?1).to_i(2)<1 #XOR i with the previous line. Take the result modulo (current line with all 0 replaced by 1)
                                      #if the result of the XOR was all 0 or all 1, the modulo == zero (<1). Otherwise, it will be a positive number.   
j=i}                                  #j = value of current line (always truthy in ruby, even if zero)
r}                                    #return 1 or true if all the modulo calculations were zero, else false.



#text to print after test case to check answer is as desired
T='T

'
F='F

'

#test cases
puts f['0'],T

puts f['1'],T

puts f['00
'],T

puts f['01'],T

puts f['10'],T

puts f['11
'],T

puts f['0000000'],T

puts f['1111111'],T

puts f['011100100100101100110100100100101010100011100101'],T

puts f['00
11'],T

puts f['01
10'],T


puts f['01
11'],F

puts f['00
01'],F

puts f['11
11
'],T

puts f['110
100'],F

puts f['111
000'],T

puts f['111
101
111'],F

puts f['101
010
101
'],T

puts f['1101
0010
1101
0010'],T

puts f['1101
0010
1111
0010'],F

puts f['0011
0111
0100
'],F

puts f['0011
0011
1100'],T

puts f['00000000
01111110
00000000'],F

puts f['11111111
11111111
11111111'],T

puts f['0000001111
0000001111'],T

puts f['0000001111
0000011111'],F

puts f['0000001111
1000001111'],F

puts f['1000001111
1000001111'],T

puts f['1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111'],F

Escargots , 20 octets

!{to{\0w`3\1|\1w`3\0

Imprime la zone de la grille s'il n'y a pas de carré 2x2 avec 3 zéros et un ou 3 uns et un zéro, ou 0si un tel carré 2x2 existe.

MATL , 12 octets

Ybc2thYCs2\~

Même algorithme que la grande réponse de @ sp3000 .

Pour autoriser la saisie multiligne, MATL a besoin que le tableau de caractères de la ligne (chaîne) soit explicitement construit à l'aide de caractère 10pour la nouvelle ligne. Donc, l'entrée des quatre exemples est (notez que []c'est la concaténation, donc chacun d'eux est un tableau de caractères):

['0011' 10 '0111' 10 '0100']
['0011' 10 '0011' 10 '1100']
['00000000' 10 '01111110' 10 '00000000']
['11111111' 10 '11111111' 10 '11111111']

et les trois derniers cas de test sont

['0000001111' 10 '1000001111']
['1000001111' 10 '1000001111']
['1110100110101010110100010111011101000101111' 10 '1010100100101010100100010101010101100101000' 10 '1110100110010010110101010111010101010101011' 10 '1010100100101010010101010110010101001101001' 10 '1010110110101010110111110101011101000101111']

La sortie véridique est un tableau n'en contenant que des uns.

Essayez-le en ligne!

Explication

Cela utilise le fait que la parité des caractères '0'et '1'est la même que celle des nombres 0et 1, donc il n'est pas nécessaire de convertir de char au chiffre qu'il représente,

Yb     % split implicit input by whitespace. Gives a cell array
c      % concatenate cell contents into 2D char array
2th    % push array [2 2]
YC     % get 2×2 sliding blocks and arrange as columns
s      % sum of each column
2\     % modulo 2 of each sum
~      % negate. Implicit display

JavaScript (ES6), 69 octets

s=>!s.split`
`.some((t,i,u)=>[...t].some((v,j)=>v^t[0]^u[0][j]^s[0]))

Je crois que le critère du rectangle de connexité de chemin équivaut à exiger que, compte tenu des quatre points qui forment les coins d'un rectangle arbitraire, il existe un nombre pair de 1s. Notez que la parité du rectangle (0, b), (x, y) est la même que (0, b), (a, y) ^(a, b), (x, y) donc je n'ai qu'à vérifier ces rectangles dont le coin supérieur gauche est à (0, 0). Aussi par les lois de De Morgan, !.some()est la même que celle .every(!)qui me fait gagner quelques octets.

Edit: je remarque que la solution Jelly vérifie la parité des coins de tous les rectangles 2 × 2, qui peuvent être équivalents.

JavaScript (ES6), 79

Même algorithme de réponse Jelly de @ Sp3000 (et heureux de ne pas avoir à prouver que cela fonctionne). Seulement 8 fois plus

s=>[...s].every((x,i)=>[++i,i+=s.search`
`,i+1].some(p=>!(x^=p=s[p],p>`
`))|!x) 

Moins golfé

s=>[...s].every((x,i)=> // repeat check for every sub square
     [++i,                  // array of position for next char in row
      i+=s.search`\n`, i+1] // and 2 chars at same column in next row
       .some(p=> // for each position 
          !( 
            x^=s[p],  // xor current value with value at position p
            s[p]>`\n` // true if value at position p is valid
           ) // the condition is negated
       ) // if any value scanned is not valid, .some return true
         // else, we must consider the check for current square
       | !x // x can be 0 or 1, to be valid must be 0
   ) 

Suite de tests

f=s=>[...s].every((x,i)=>[++i,i+=s.search`
`,i+1].some(p=>!(x^=p=s[p],p>`
`))|!x) 

testData=`
0
T

1
T

00
T

01
T

10
T

11
T

0000000
T

1111111
T

011100100100101100110100100100101010100011100101
T

00
11
T

01
10
T

01
11
F

00
01
F

11
11
T

110
100
F

111
000
T

111
101
111
F

101
010
101
T

1101
0010
1101
0010
T

1101
0010
1111
0010
F

0011
0111
0100
F

0011
0011
1100
T

00000000
01111110
00000000
F

11111111
11111111
11111111
T

0000001111
0000001111
T

0000001111
0000011111
F

0000001111
1000001111
F

1000001111
1000001111
T

1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111
F`

console.log=x=>O.textContent+=x+'\n'

testData.split('\n\n').forEach(t=>{
  var k=t.slice(-1)=='T',
      r=f(t.slice(0,-1))
  console.log(t+' '+r+ (k==r?' OK\n':' KO\n'))
})  

<pre id=O></pre>

Grime v0.1, 31 octets

E=\0+|\1+
N=.+&E!
e`(E/N|N/E)#!

Imprime 1pour correspondance et 0pour aucune correspondance. Essayez-le en ligne!

Explication

Grime est mon langage de correspondance de motifs 2D. Je l'ai modifié aujourd'hui, mais uniquement pour changer le caractère d'un élément de syntaxe ( `au lieu de ,), donc cela n'affecte pas mon score.

J'utilise une approche similaire à celle de Sp3000 : une entrée est fausse si elle contient un rectangle 2 × N dont une ligne contient à la fois 0et 1et l'autre pas.

E=             Define a nonterminal E, which matches
  \0+|           a horizontal run of one or more 0s, OR
      \1+        a horizontal run of one or more 1s.
N=             Define a nonterminal N, which matches
  .+             a horizontal run of one or more characters,
    &E!          which is NOT matched by E (so contains both 0 and 1).
e`             Match entire input to this pattern:
            !    not
           #     contains
  (E/N|N/E)      E on top of N, or N on top of E

JavaScript (ES6), 64 octets

s=>(a=s.split`
`).every(l=>l==a[0]|l==a[0].replace(/./g,n=>n^1))

Basé sur l'observation de @ LevelRiverSt que chaque ligne doit être identique ou opposée à la première.