12
\$\begingroup\$

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

length example

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
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – Greg Martin Mar 13 '17 at 23:50
  • \$\begingroup\$ @Greg Sounds fine. Done \$\endgroup\$ – Calvin's Hobbies Mar 14 '17 at 3:17
  • \$\begingroup\$ [x.x,...,.x.] isn't a valid curve, right? \$\endgroup\$ – Magic Octopus Urn Mar 14 '17 at 14:57
  • \$\begingroup\$ @carusocomputing correct \$\endgroup\$ – Calvin's Hobbies Mar 14 '17 at 14:58
3
\$\begingroup\$

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.

Try it online! Or verify all test cases.

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.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 316 315 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.

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

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?).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.