# Grids can be curvy. How long is yours?

Consider depicting a simple, open, two-dimensional curve on a W wide by H high grid of text where X represents part of the curve and . represents empty space and no other characters are used.

Every grid space has 8 neighboring grid spaces, its Moore neighborhood. Grid spaces beyond the borders are considered empty.

A grid contains a curve if it has exactly one X OR if it has more than one X where:

• Exactly two Xs have only one neighboring X. These are the curve's endpoints.
• Every X besides the endpoints neighbors exactly two Xs. These form the bulk of the curve.

For example, this grid where W = 9 and H = 4 contains a curve:

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


Likewise, these grids (W = 4, H = 3) have curves:

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


These grids, however, do not contain a curve:

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


We can find the length of a curve by summing the distances between all neighboring pairs of Xs:

• The distance between two orthogonally neighboring Xs is 1 unit.

XX
X
X
• The distance between two diagonally neighboring Xs is √2 units.

X.
.X
.X
X.

For example, the length of the curve in the grid

XXX.
...X
..X.


can be visualized as

so we can see it is 1 + 1 + √2 + √2 = 4.828427...

The length of a curve with only one X is zero.

When a grid does not form a curve its length is not well defined.

# Challenge

Given a grid of text of Xs and .s, output the length of the curve it contains, or else output something such as -1 or Null to indicate the grid has no curve.

For input you may use other characters than X and . if desired, and H and W may be taken as input if needed. Input as a nested list or matrix filled with 1s and 0s instead of a string is also fine.

You may output a float for the curve length or alternatively two integers A and B where length = A + B*√2.

The shortest code in bytes wins.

# Test Cases

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

• I recommend allowing the solver to choose their output format for grids that have no curves (any consistent value that's not of the form m + n*sqrt(2) for any m,n≥0). – Greg Martin Mar 13 '17 at 23:50
• @Greg Sounds fine. Done – Calvin's Hobbies Mar 14 '17 at 3:17
• [x.x,...,.x.] isn't a valid curve, right? – Magic Octopus Urn Mar 14 '17 at 14:57
• @carusocomputing correct – Calvin's Hobbies Mar 14 '17 at 14:58

# MATL, 52 51 bytes

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


Input is a matrix of zeros and ones.

Output is B, then A. Non-curves give a negative A.

### Explanation

Computing the length of the curve uses two 2D convolutions1: one with the Moore mask, and another with a mask containing only the diagonal neighbours. The results are two matrices with the same size of the input, which will be denoted as M and D respectively. M gives the total number of neighbours for each point, whereas D gives the number of diagonal neighbours.

The results in M and D must be filtered to discard points that don't belong to the curve. Also, they must be divided by 2, because "being neighbour of" is a a symmetric relation, so each point in the curve is counted twice.

Determining if the curve is valid is more cumbersome than I expected. To do this, the code tests three conditions:

1. Does the number of ones in M equal 2? (That is, are thre exactly two points with a single neighbour?)
2. Does the total sum of M equal the number of points in the input curve times 2 minus 2? (Together with condition 1, this tests if all non-zero values in M except two of them equal 2)
3. Does the input curve contain a single point?

The curve is valid if conditions 1 and 2 are true, or if condition 3 is.

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 Convolution is the key to success.

# Python 3, 316315 311 bytes

I think this covers all cases; at least the test cases work.

Also, there surely is still a lot to golf down, probably in the beginning where the edge cases are handled.

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


Try it online!

How it works:

1. d,R,C are 1. a list of lists with 1 as curve and 0 as background, 2. row and column count
2. Insert a row of 0's before and after and a column of 0's before and after d so we don't have to worry about the edge of the 2d array
3. For every 1 in the 2d array, scan the neighbourhood for 1's and add (1,0) to a list if the relation is diagonal, else add (0,1)
4. Sum all tuples, so that (n,m) represents the number of diagonal and non-diagonal neighbours, respectively
5. Check if the number of relations is exactly the number of 1's minus one; if not, not a curve.

Thanks to @Helka Homba for pointing out a missing case. Thanks to @TuukkaX and @Trelzevir for the golfing tips.

• Looks like d=[[1,0,1],[0,1,0],[1,0,1]] will fail here (added testcase). – Calvin's Hobbies Mar 14 '17 at 3:26
• @HelkaHomba You're right, I oversaw that. Thanks!Fixed it (now unfortunately with more bytes). – nile Mar 14 '17 at 4:12
• s=sum saves 4 bytes. – Trelzevir Mar 14 '17 at 6:22

# Mathematica, 153 150 bytes

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


Takes a 2D array, with 0s for .s and 1s for Xs. Outputs Null for non-curves.

1/.#~ComponentMeasurements~"PolygonalLength"&


Mathematica has a 45-byte built-in for this, but it outputs some numbers for non-curves and 1/sqrt(2) for input {{1}}. Correcting these cost 105 bytes (could be golfed?).