Contexte

J'ai un tas d'images anciennes et granuleuses en noir et blanc. Certains d'entre eux représentent des vignes grimpant sur un mur, d'autres non - votre tâche est de les classer pour moi.

Entrée et sortie

Votre entrée est un tableau 2D rectangulaire de bits A , donné dans n'importe quel format pratique. Il ne sera pas vide, mais il n'est pas garanti qu'il contienne à la fois des 0 et des 1. Le tableau représente une vigne si les conditions suivantes sont réunies:

• La rangée inférieure de A contient au moins un 1. Ce sont les racines de la vigne.
• Chaque 1 dans A est connecté à la rangée inférieure par un chemin de 1 qui ne va que vers la gauche, la droite et le bas (pas vers le haut et pas en diagonale). Ces chemins sont les sarments de la vigne.

Votre sortie est une valeur véridique cohérente si l'entrée représente une vigne, et une valeur de fausseté cohérente sinon.

Exemples

Ce tableau représente une vigne:

0 0 1 0 0 1
0 1 1 0 0 1
0 1 0 1 1 1
1 1 0 1 0 1
0 1 1 1 0 1
0 0 1 0 1 1

Cette entrée ne représente pas une vigne, car il y a un 1 au milieu de la bordure droite qui n'est pas connecté aux racines par une branche:

0 0 0 1 1 0
0 1 0 1 1 1
0 1 0 1 0 1
0 1 1 1 1 0
0 0 1 1 0 1

Le tableau tout-0 ne représente jamais une vigne, mais le tableau tout-1 le fait toujours.

Règles et notation

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites.

Cas de test

Entrées véridiques:

1

0
1
1

01
11

0000
0111
1100
1001

1111
1111
1111
1111

001001
011001
010111
110101
011101
001011

1011011
1001001
1111111
0100000
0111111
1111001
1001111
1111101

0000000
0011100
0010100
0011100
0001000
1111111
0001000
0011100
0010100
0010100

Entrées fausses:

0

1
0

10
01

000
000
000

011
110
000

111111
000000
101011
111001

010010
001000
000010
110001

001100
111111
110101
010011
111011

000110
010111
010101
011110
001101

11000000
10110001
10011111
11110001
01100011
00110110
01101100
01100001
01111111

Escargots , 25 19 17 octets

&
\0z),(\1dlr)+d~

Essayez-le en ligne!

Explication

Snails est un langage de correspondance de motifs 2D inspiré de l'expression régulière, qui a été développé à l'origine pour notre défi de conception de langage de correspondance de motifs 2D .

Les &escargots font essayer le motif à partir de toutes les positions de départ possibles et s'impriment 0ou 1selon que le motif échoue dans l'un d'eux ou correspond à tous.

Maintenant, les escargots peuvent fonctionner avec des parenthèses implicites, donc le modèle est un raccourci pour les éléments suivants:

(\0z),(\1dlr)+d~

Le ,agit comme un *dans regex (c'est-à-dire correspondre à zéro ou plusieurs fois), tandis que le +est le même que dans regex (correspondre à une ou plusieurs fois). Nous commençons donc par faire correspondre \0zaussi souvent que nécessaire, ce qui correspond à un seul 0, puis permet à l'escargot de réinitialiser arbitrairement sa direction avec z. Cela permet des zéros dans l'entrée, à condition qu'une cellule de vigne valide puisse être trouvée ailleurs.

Ensuite, nous correspondons à au moins un \1dlr, qui correspond à un seul 1, puis permet à l'escargot de réinitialiser sa direction vers le bas, la gauche ou la droite. Notez que si la cellule dans laquelle nous avons commencé contient un, 1nous ne faisons correspondre que cette partie. Il permet essentiellement à l'escargot de traverser une vigne d'une branche jusqu'aux racines.

Enfin, nous devons nous assurer d'avoir atteint le sol en recherchant une cellule hors limites ( ~) sous ( d).

JavaScript (ES6), 135 octets

s=>s.replace(/^[^1]*\n/,``).split`
`.map(s=>+`0b${s}`).reverse(g=(n,m,o=(m<<1|m|m>>1)&n)=>n-m?o-m&&g(n,o):n).reduce((m,n,i)=>g(n,n&m))

Remarque: En raison des limitations du type entier, ne fonctionne que pour les vignes jusqu'à 31 caractères de large. Explication: chaque ligne est AND au niveau du bit avec la ligne adjacente pour déterminer les points de connexion, puis la gfonction est utilisée pour développer récursivement la ligne horizontalement jusqu'à ce qu'elle ne puisse plus se développer. Par exemple, si deux lignes adjacentes le sont 1110111et que 1011100les points de connexion le sont 1010100et que cela est ensuite étendu à 1110110puis 1110111qui détecte alors que la ligne est connectée. Si la gfonction échoue, elle renvoie zéro, ce qui entraîne gégalement l'échec de toutes les fonctions suivantes , et le résultat est alors faux. Si la gfonction réussit, elle renvoie la nouvelle ligne qui est ensuite propagée à travers le reducepour tester la ligne suivante.

s=>s.replace(/^[^1]*\n/,``)         Remove irrelevant leading "blank" rows
    .split`\n`                      Split into lines
    .map(s=>+`0b${s}`)              Convert into binary
    .reverse(                       Process from bottom to top
     g=(n,m,o=(m<<1|m|m>>1)&n)=>     Expand row horizontally
      n-m?o-m&&g(n,o):n)             Check whether rows are connected
    .reduce((m,n,i)=>g(n,n&m))      Check all rows

Python 2, 254 octets

Pas de bibliothèques

def f(A,r=0,c=-1):
 B=A[r];R=len(A)-1;C=len(B);i=1 in A[R]
 if c<0:
    for j in range(R*C+C):
        if A[j/C][j%C]:i&=f(A,j/C,j%C)
    return i&1
 _=B[c];B[c]=0;i=_&(r==R)
 if _:
    if c>0:i|=f(A,r,c-1)
    if r<R:i|=f(A,r+1,c)
    if c<C-1:i|=f(A,r,c+1)
 B[c]=_;return i

Notez que les retraits de deuxième et troisième niveau sont formés avec des tabulations dans le nombre d'octets.

Essayez-le en ligne

Wolfram - 254

Passez un peu de temps à faire ce travail, alors je vais le laisser ici:

f[s_]:=(
v=Characters@StringSplit@s;
{h,w}=Dimensions@v;
g=GridGraph@{w,h};
r=First/@Position[Flatten@v,"0"];
g=VertexDelete[Graph[VertexList@g,
EdgeList@g/.x_y_/;Abs[x-y]>1yx],r];
v=VertexList@g;
v≠{}∧v~Complement~VertexOutComponent[g,Select[v,#>w h-w&]]{}
)

Fondamentalement, je construis un graphique en grille avec des bords dirigés pointant vers le haut, supprime les sommets qui correspondent à 0, vérifie que les composants des sommets inférieurs contiennent tous les sommets. Ridicule, je sais ...

Python + numpy 204 202 195 Octets

from numpy import*
def f(A):
 r,c=A.shape
 z,s=zeros((r,1)),array([0,2,c+3])
 B=hstack((z,A,z)).flat
 for i in range(1,(r-1)*(c+2)):
    if B[i]and not any(B[s]):return 1<0
    s+=1
 return any(B[i:])

S'attend Aà être un tableau numpy 2D.

Prend la matrice, remplit les colonnes zéro à gauche et à droite et aplatit la matrice. sest un pochoir qui pointe vers l'élément gauche, droit et inférieur. La boucle vérifie chaque élément sauf la dernière ligne s'il l'est 1et au moins un de ses gabarits 1, renvoie Falsesinon. Ensuite, vérifiez si la dernière ligne en contient 1.

Deux tests pour vous:

I1 = '001001\n011001\n010111\n110101\n011101\n001011'
A1 = array([int(c) for c in I1.replace('\n','')]).reshape(6,6)
print f(A1) #True

I2 = '001100\n111111\n110101\n010011\n111011'
A2 = array([int(c) for c in I2.replace('\n','')]).reshape(5,6)
print f(A2) #False

Edit1: 1<0est plus court queFalse

Edit2: flatest une bonne alternative à flatten()et en utilisant des tabulateurs pour la deuxième intention dans la boucle