Codegolf — Сетки Могут Быть Изогнутыми. Сколько Времени У Тебя?

Рассмотрите возможность изображения простой, открыть, двумерная кривая на текстовой сетке шириной W и высотой H, где

 
 
 
 
 
 
 
 
 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
 
 
 
 
 
 
 
 
 

Каждое пространство сетки имеет 8 соседних ячеек сетки. Район Мур. Пространства сетки за пределами границ считаются пустыми.

Сетка содержит изгиб если он имеет ровно один . ИЛИ если у него более одного X where:

• Ровно два Null s have only one neighboring -1 . Это конечные точки кривой.
• Каждый . besides the endpoints neighbors exactly two X с. Они составляют основную часть кривой.

Например, эта сетка, где W = 9 и H = 4, содержит кривую:

X

Аналогично, эти сетки (W = 4, H = 3) имеют кривые:

XXX. ...X ..X.

Однако эти сетки не содержат кривой:

.X X.

Длину кривой можно найти, просуммировав расстояния между всеми соседними парами X. .X s:

• Расстояние между двумя ортогонально соседними X s is 1 unit.

  X X XX

• Расстояние между двумя соседними по диагонали X s is √2 единицы.

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

Например, длина кривой в сетке

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

можно визуализировать как

Итак, мы видим, что это 1 + 1 + √2 + √2 = 4,828427...

Длина кривой только с одним ....X.... .X.X.X.X. X..X..X.X .XX.....X is zero.

Если сетка не образует кривую, ее длина не определена четко.

Испытание

Учитывая сетку текста X s and X s, выведите длину содержащейся в ней кривой или же выведите что-то вроде X or X чтобы указать, что сетка не имеет кривой.

Для ввода вы можете использовать другие символы, кроме X and X при желании, а H и W могут быть приняты в качестве входных данных, если необходимо. Ввод в виде вложенного списка или матрицы, заполненной единицами и нулями вместо строки, также подойдет.

Вы можете вывести число с плавающей запятой для длины кривой или, альтернативно, два целых числа A и B, где . .

Выигрывает самый короткий код в байтах.

Тестовые случаи

#код-гольф #арифметика #геометрия #сетка #теория графов

МАТЛ, 52 51 байт

 
 
 
 
 {{1}} 
 
 
 
 

Входные данные представляют собой матрицу нулей и единиц.

Выход: 1/.#~ComponentMeasurements~"PolygonalLength"& , then Null . Некривые дают отрицательный результат X .

Попробуйте онлайн! Или проверить все тестовые случаи.

Объяснение

Вычисление длины кривой использует две 2D-свертки¹: один с маской Мура, а другой с маской, содержащей только соседей по диагонали. Результатом являются две матрицы с одинаковым размером входных данных, которые будут обозначаться как М и Д соответственно. М дает общее количество соседей для каждой точки, тогда как Д дает количество соседей по диагонали.

Результаты в М и Д необходимо фильтровать для исключения точек, не принадлежащих кривой. Кроме того, их необходимо разделить на 2, поскольку отношение «быть соседом» является симметричным, поэтому каждая точка кривой учитывается дважды.

Определение того, действительна ли кривая оказался более громоздким, чем я ожидал. Для этого код проверяет три условия:

1. Количество единиц в М равный 1 ? (That is, are thre exactly two points with a single neighbour?)
2. Общая сумма М равно количеству точек на входной кривой, умноженной на . minus 0 ? (Вместе с условием 1 это проверяет, все ли ненулевые значения в М кроме двух из них равных Switch[Sort[Join@@BlockMap[If[#[[2,2]]<1,Nothing,Tr[Tr/@#]]&,#~ArrayPad~1,{3,3},1]],{1},0,{2,2,3...},1/.#~ComponentMeasurements~"PolygonalLength",_,]& )
3. Содержит ли входная кривая одну точку?

Кривая действительна, если выполняются условия 1 и 2 или условие 3.

_{¹ Свертка – ключ к успеху.}

Питон 3, 316 315 311 байт

Я думаю, что это охватывает все случаи; по меньшей мере тестовые случаи работа.

Кроме того, конечно, еще многое предстоит сделать, возможно, на начальном этапе, когда будут рассмотрены крайние случаи.

Попробуйте онлайн!

Как это работает:

1. 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]) are 1. a list of lists with 1 as curve and 0 as background, 2. row and column count
2. Вставьте строку с нулями до и после и столбец с нулями до и после. 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 so we don't have to worry about the edge of the 2d array
3. Для каждой единицы в массиве 2d просканируйте окрестности на наличие единиц и добавьте (1,0) в список, если отношение диагональное, иначе добавьте (0,1)
4. Суммируйте все кортежи так, чтобы (n,m) представляло количество диагональных и недиагональных соседей соответственно.
5. Проверьте, равно ли количество отношений числу единиц минус один; если нет, то не кривая.

Спасибо @Helka Homba за указание на пропавший кейс.

Математика, 153 150 байт 2 s for 2 Принимает 2D-массив с 2 s for A песок A for non-curves.

с. Выходы t2Y6~Z+*ssGt3Y6Z+*tt1=z2=wssGzqE=*Gz1=+?}_q]ssy-h2/ . Correcting these cost 105 bytes (could be golfed?).