Сетки могут быть соблазнительными. Как долго у тебя?

12

Подумайте об изображении простой , открытой двумерной кривой на сетке текста шириной W и высотой H, где она Xпредставляет часть кривой и .представляет пустое пространство, а другие символы не используются.

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

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

  • Ровно два человека Xимеют только одного соседа X. Это конечные точки кривой.
  • Каждая, Xкроме конечных точек, соседствует ровно с двумя Xs. Они составляют основную часть кривой.

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

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

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

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

Эти сетки, однако, не содержат кривую:

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

Мы можем найти длину кривой, суммируя расстояния между всеми соседними парами Xs:

  • Расстояние между двумя ортогонально соседними Xs составляет 1 единицу.

    XX
    X
X

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

    X.
.X
    .X
X.

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

XXX.
...X
..X.

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

пример длины

так что мы можем видеть, что это 1 + 1 + √2 + √2 = 4.828427 ...

Длина кривой только с одним Xравна нулю.

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

Вызов

Если задана сетка текста Xs и .s, выведите длину кривой, которую она содержит, либо выведите что-то вроде -1или, Nullчтобы указать, что сетка не имеет кривой.

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

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

Самый короткий код в байтах побеждает.

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

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
code-golf arithmetic geometry grid graph-theory Кальвин Хобби
источник
Я рекомендую разрешить решающему устройству выбирать выходной формат для сеток, у которых нет кривых (любое непротиворечивое значение, которое не имеет форму m + n * sqrt (2) для любого m, n≥0).
Грег Мартин
@ Грег Звучит хорошо. Готово
Увлечения Кэлвина
[x.x,...,.x.]не правильная кривая, верно?
Волшебная Осьминог Урна
@carusocomputing правильно
Хобби Calvin

Ответы:

3

MATL , 52 51 байт

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

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

Выход есть B, тогда A. Не кривые дают негатив A.

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

объяснение

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

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

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

  1. Имеет ли число единиц в M равно 2? (То есть есть ли ровно две точки с одним соседом?)
  2. Соответствует ли общая сумма M количеству точек на входной кривой раз 2минус 2? (Вместе с условием 1 это проверяет, все ли ненулевые значения в M, кроме двух, равны 2)
  3. Входная кривая содержит одну точку?

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

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 Свертка - ключ к успеху .

Луис Мендо
источник
1

Python 3 , 316, 315, 311 байт.

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

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

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

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

Как это устроено:

  1. d,R,C 1. список списков с 1 в качестве кривой и 0 в качестве фона, 2. количество строк и столбцов
  2. Вставьте строку с 0 до и после и столбец с 0 до и после, dчтобы нам не пришлось беспокоиться о крае массива 2d
  3. Для каждого 1 в массиве 2d просканируйте окрестности на наличие 1 и добавьте (1,0) в список, если отношение диагонально, иначе добавьте (0,1)
  4. Суммируйте все кортежи, чтобы (n, m) представляло число диагональных и недиагональных соседей соответственно
  5. Проверьте, точно ли число отношений равно числу 1 минус один; если нет, то не кривая.

Спасибо @Helka Homba за указание на пропущенное дело. Спасибо @TuukkaX и @Trelzevir за советы по игре в гольф.

Нил
источник
Похоже d=[[1,0,1],[0,1,0],[1,0,1]], здесь произойдет сбой (добавлен тестовый пример).
Увлечения Кельвина,
@HelkaHomba Вы правы, я наблюдал за этим. Спасибо! Исправлено (теперь, к сожалению, с большим количеством байтов).
Нил
1
s=sumэкономит 4 байта.
Трелзевир,
0

Mathematica, 153 150 байт

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

Принимает двумерный массив с 0s для .s и 1s для Xs. Выходы Nullдля не кривых.

1/.#~ComponentMeasurements~"PolygonalLength"&

Mathematica имеет 45-байтовую встроенную для этого, но она выводит некоторые числа для не-кривых и 1 / sqrt (2) для ввода {{1}}. Исправление этих стоило 105 байт (может быть в гольфе?).

Юнг Хван Мин
источник