Envisagez de représenter une courbe simple , ouverte et bidimensionnelle sur une grille de texte large de large par haute de H où Xreprésente une partie de la courbe et .représente un espace vide et aucun autre caractère n'est utilisé.

Chaque espace de grille a 8 espaces de grille voisins, son quartier Moore . Les espaces de grille au-delà des frontières sont considérés comme vides.

Une grille contient une courbe si elle en a exactement un X OU si elle en a plusieurs Xoù:

• Exactement deux Xn'ont qu'un seul voisin X. Ce sont les points finaux de la courbe.
• En Xplus des points d'extrémité, chaque voisin a exactement deux Xs. Ceux-ci forment l'essentiel de la courbe.

Par exemple, cette grille où W = 9 et H = 4 contient une courbe:

....X....
.X.X.X.X.
X..X..X.X
.XX.....X

De même, ces grilles (W = 4, H = 3) ont des courbes:

....  .X..  ....  ....  .X.X
....  X..X  ..X.  XX..  X.X.
..X.  .XX.  .X..  ....  ....

Ces grilles, cependant, ne contiennent pas de courbe:

....  .XX.  ...X  XX..  ....  X.X.
....  X..X  ..XX  XX..  .X.X  .X..
....  .XX.  .X..  ....  ...X  X.X.

Nous pouvons trouver la longueur d'une courbe en additionnant les distances entre toutes les paires voisines de Xs:

• La distance entre deux Xs orthogonalement voisins est de 1 unité.

  XX

  X
  X

• La distance entre deux Xs diagonalement voisins est de √2 unités.

  X.
  .X

  .X
  X.

Par exemple, la longueur de la courbe dans la grille

XXX.
...X
..X.

peut être visualisé comme

donc on peut voir que c'est 1 + 1 + √2 + √2 = 4.828427 ...

La longueur d'une courbe avec un seul Xest nulle.

Lorsqu'une grille ne forme pas de courbe, sa longueur n'est pas bien définie.

Défi

Étant donné une grille de texte de Xs et .s, sortez la longueur de la courbe qu'il contient, ou bien sortez quelque chose comme -1ou Nullpour indiquer que la grille n'a pas de courbe.

Pour la saisie, vous pouvez utiliser d'autres caractères que Xet .si vous le souhaitez, et H et W peuvent être pris en entrée si nécessaire. L'entrée sous forme de liste imbriquée ou de matrice remplie de 1 et de 0 au lieu d'une chaîne convient également.

Vous pouvez sortir un flottant pour la longueur de la courbe ou alternativement deux entiers A et B où length = A + B*√2.

Le code le plus court en octets gagne.

Cas de test

XXX.
...X
..X.
2 + 2*√2 = 4.828427...

....X....
.X.X.X.X.
X..X..X.X
.XX.....X
3 + 8*√2 = 14.313708...

....
....
..X.
0 + 0*√2 = 0

.X..
X..X
.XX.
1 + 3*√2 = 5.242640...

....
..X.
.X..
0 + 1*√2 = 1.414213...

....
XX..
....
1 + 0*√2 = 1

.X.X
X.X.
....
0 + 3*√2 = 4.242640...

....
....
....
....
-1

.XX.
X..X
.XX.
-1

...X
..XX
.X..
-1

....
.X.X
...X
-1

X.X.
.X..
X.X.
-1

MATL , 52 51 octets

t2Y6~Z+*ssGt3Y6Z+*tt1=z2=wssGzqE=*Gz1=+?}_q]ssy-h2/

L'entrée est une matrice de zéros et de uns.

La sortie est Balors A. Les non courbes donnent un négatif A.

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Le calcul de la longueur de la courbe utilise deux convolutions 2D ¹ : une avec le masque de Moore et une autre avec un masque contenant uniquement les voisins diagonaux. Les résultats sont deux matrices avec la même taille d'entrée, qui seront notées respectivement M et D. M donne le nombre total de voisins pour chaque point, tandis que D donne le nombre de voisins diagonaux.

Les résultats en M et D doivent être filtrés pour éliminer les points qui n'appartiennent pas à la courbe. De plus, ils doivent être divisés par 2, car "être voisin de" est une relation symétrique, donc chaque point de la courbe est compté deux fois.

Déterminer si la courbe est valide est plus lourd que ce à quoi je m'attendais. Pour ce faire, le code teste trois conditions:

1. Le nombre de uns dans M est-il égal 2? (Autrement dit, y a-t-il exactement deux points avec un seul voisin?)
2. La somme totale de M est-elle égale au nombre de points dans les temps d'entrée de la courbe 2moins 2? (Avec la condition 1, cela teste si toutes les valeurs non nulles dans M sauf deux d'entre elles sont égales 2)
3. La courbe d'entrée contient-elle un seul point?

La courbe est valide si les conditions 1 et 2 sont vraies, ou si la condition 3 l'est.

t       % Implicit input matrix of zeros and ones. Duplicate
2Y6~    % Push [1 0 1; 0 0 0; 1 0 1]
Z+      % 2D convolution, keeping size
*       % Multiply to zero out results for non-curve points. Gives matrix D
ss      % Sum of matrix D
Gt      % Push input again wtice
3Y6     % Push [1 1 1; 1 0 1; 1 1 1]
Z+      % 2D convolution, keeping size
*       % Multiply to zero out results for non-curve points. Gives matrix M
tt      % Duplicate twice
1=z     % Number of ones
2=      % Does it equal 2? This is condition 1
wss     % Swap. Sum of matrix
G       % Push input again
zqE     % Number of nonzeros values minus 1, and then multiplied by 2
=       % Are they equal? This is condition 2
*       % Multiply. This is a logical AND of conditions 1 and 2
G       % Push input again
z1=     % Does it contain exactly one nonzero value? This is condition 3
+       % Add. This is a logical OR with condition 3
?}      % If result was false
  _q    %   Negate and subtract 1. This makes sure we get a negative value
]       % End
ss      % Sum of matrix M
y       % Duplicate sum of matrix D from below
-       % Subtract
h       % Concatenate horizontally
2/      % Divide by 2. Implicitly display

_{^{1 La} convolution est la clé du succès .}

Python 3 , 316 315 311 octets

Je pense que cela couvre tous les cas; au moins les cas de test fonctionnent.

De plus, il reste encore beaucoup à jouer, probablement au début où les cas de bord sont traités.

def f(d,R,C):
 s=sum;d=[0]*(C+2),*[[0,*r,0]for r in d],[0]*(C+2);o=-1,0,1;k=[[[(1,0),(0,1)][i*j]for i in o for j in o if d[r+i][c+j]and i|j]for c in range(1,-~C)for r in range(1,-~R)if d[r][c]];w=[x/2for x in map(s,zip(*s(k,[])))]or[0,0];print([w,-1][s(w)!=s([s(z)for z in d])-1or[len(t)for t in k].count(1)>2])

Essayez-le en ligne!

Comment ça fonctionne:

1. d,R,C sont 1. une liste de listes avec 1 comme courbe et 0 comme arrière-plan, 2. nombre de lignes et de colonnes
2. Insérez une ligne de 0 avant et après et une colonne de 0 avant et après dpour ne pas avoir à vous soucier du bord du tableau 2D
3. Pour chaque 1 dans le tableau 2d, scannez le voisinage pour les 1 et ajoutez (1,0) à une liste si la relation est diagonale, sinon ajoutez (0,1)
4. Additionnez tous les tuples, de sorte que (n, m) représente le nombre de voisins diagonaux et non diagonaux, respectivement
5. Vérifiez si le nombre de relations est exactement le nombre de 1 moins un; sinon, pas une courbe.

Merci à @Helka Homba d'avoir signalé un cas manquant. Merci à @TuukkaX et @Trelzevir pour les conseils de golf.

Mathematica, 153 150 octets

Switch[Sort[Join@@BlockMap[If[#[[2,2]]<1,Nothing,Tr[Tr/@#]]&,#~ArrayPad~1,{3,3},1]],{1},0,{2,2,3...},1/.#~ComponentMeasurements~"PolygonalLength",_,]&

Prend un tableau 2D, avec 0s pour .s et 1s pour Xs. Sorties Nullpour les non courbes.

1/.#~ComponentMeasurements~"PolygonalLength"&

Mathematica a une fonction intégrée de 45 octets pour cela, mais il génère des nombres pour les non-courbes et 1 / sqrt (2) pour l'entrée {{1}}. La correction de ces coûts coûte 105 octets (pourrait-on jouer au golf?).