Вызов
Учитывая заданную двоичную матрицу и двоичную строку, определите, можно ли найти эту двоичную строку, начиная с любой точки матрицы и двигаясь в любом направлении в любой последующей точке, чтобы сформировать двоичную строку. То есть можно ли найти строку в сложенном виде внутри матрицы?
Струну можно сложить только под углом 90 или 180 градусов (соединения по краям; расстояние до Манхэттена 1), и она не может перекрывать себя в любой точке.
пример
Давайте возьмем следующий пример:
Matrix:
010101
111011
011010
011011
Snake: 0111111100101
Это правдивый контрольный пример. Мы видим змею, сложенную в следующей позиции:
0-1 0 1 0 1
|
1 1 1-0 1 1
| | | |
0 1 1 0-1-0
| |
0 1-1 0 1 1
правила
- Стандартные лазейки применяются
- Вы можете взять длину строки, ширину и высоту матрицы в качестве входных данных, если хотите
- Вы можете взять двоичную матрицу и двоичную строку как многострочную строку / массив строк / строку с новой строкой / строку с чем-либо еще и строку
- Вы можете взять измерения как плоский массив вместо нескольких аргументов
- Ваша программа должна завершиться для любой матрицы 5 x 5 с любой строкой длиной до 10 в течение минуты
Ограничения
- Матрица не обязательно квадратная
- Строка будет непустой
- Строка может быть длиной 1
- Строка не будет содержать больше квадратов, чем доступно (то есть
len(string) <= width(matrix) * height(matrix)
Тестовые случаи
Truthy
01010
10101
01010
10101
01010
0101010101010101010101010
01110
01100
10010
10110
01101
011111000110100
0
0
10
01
1010
100
010
001
100010001
Falsy
00000
00000
00000
00000
00000
1
10101
01010
10101
01010
10101
11
100
010
001
111
10001
01010
00100
01010
10001
1000100010001000101010100
code-golf
decision-problem
binary-matrix
HyperNeutrino
источник
источник
Ответы:
Python 2 ,
275271264249 байт-1
наH
и удаления одной операции нарезки ([:]
).[:]
), используя назначение нескольких целей, чтобы дать посещенной записи значениеv not in "01"
(S=S[1:];M[y][x]=H;
->S=M[y][x]=S[1:];
), и переключаясь с троичной функции if / else на простую логическую или (any(...)if S else 1
->not S or any(...)
).ZeroDivisionError
), когда змея найдена, и возвращает пустой список ([]
), когда змея не найдена, что является двумя различными типами поведения.not S or
доS<[1]or
~S==[]or
.Попробуйте онлайн!
объяснение
Лямбда-функция, которая принимает матрицу в виде двумерного списка строк (либо,
"0"
либо"1"
), змею - как одномерный список, а размеры матрицы - как два целых числа.Лямбда-функция ищет в матрице записи, соответствующие первому элементу змеи. Для каждого найденного совпадения он вызывает
H
глубокую копию матрицы, без копии змеи, размеров матрицы и позиции совпадения.Когда
H
вызывается, он удаляетS
первую запись и устанавливает запись матрицы данной позиции в нечто иное, чем"0", "1"
. ЕслиS
длина равна нулю, возвращаетсяTrue
; как он называет себя рекурсивно, змея была найдена где-то в матрице.Если
S
длина не равна нулю, он проходит по четырем основным направлениям, проверяет, находится ли эта позиция в матрице, сравнивает элемент матрицы в этой позиции с первым элементомS
и, если он совпадает, вызывает себя рекурсивно.H
Возвращаемые значения направляются в стековые фреймы, всегда проверяя, обнаружила ли хотя бы одна функция возможную змею.Форматированный вывод
Я дополнил свою программу, чтобы также вывести путь, по которому скользит змея (если он есть). Он использует тот же дизайн вывода ASCII, что и вопрос. Ссылка TIO .
источник
m[:]for
~>m*1for
? Может работать.JavaScript (ES6),
138134Не очень отличается от @ Neil's, но что еще это может быть?
Ввод: матрица в виде многострочной строки, двоичная строка, ширина (не считая новой строки)
Примечание: логика в рекурсивной функции
r
несколько инвертирована, чтобы сохранить пару байтовМеньше гольфа
Тест
источник
JavaScript (ES6), 149 байт
Принимает матрицу в виде строки, разделенной новой строкой, змею в виде строки и ширину (в виде целого числа). Свободно основано на ответе @ JonathanFrech.
источник
Mathematica,
180156141153138136104 байтаПример ввода
объяснение
GridGraph@{##4}
являетсяGraph
объектом для сетки вершин со смежными вершинами, соединенными ребрами, с размерами{##4}
- то есть{#4,#5}
или{width,height}
.x
(пронумерованные1
до1##4 = width*height
), все конечные вершиныy
и все путиp
длины не более#3
отx
доy
.""<>Part[Join@@#,p]
извлекает соответствующие символы матрицы и помещает их в строку.s
, выполняя поиск на всех уровнях, потому что это очень многомерный список, который мы создали.Примечание. Замена
#3
на{#3-1}
inFindPath
, так что мы находим только пути точно правильной длины, является огромным улучшением с точки зрения скорости, но стоит еще 4 байта.-24 байта: принимая размеры вещей в качестве входных данных
-15 байт: используя
StringPart
иStringJoin
правильно+12 байт: исправление длины в 1 случае
-15 байт: ...
-2 байта: принимая размер матрицы в качестве входных данных в качестве массива
-32 байта: использование
Table
для итерации по пути позволяет нам избегать использованияFunction
, а использованиеMemberQ[...,s,All]
позволяет просто прикрепить матрицу к таблице при работе со змеями длины 1.источник
C # (.NET Core) ,
346341336302297 байтПопробуйте онлайн!
5 байт спасены игра в гольф на
p
приращении5 байтов сохраняются, если брать длину змеи, начинать с хвоста и удалять ненужное пространство
34 байта сохранены, если правильно прочитать задачу и посмотреть, как я могу взять высоту и ширину матрицы
5 байтов сохранено, тестовый случай с одним элементом не пройден, и исправление было полезным
Ungolfed
источник
if(...)return true;
->return ...;
.b[y,x]
должен быть сброшен в какой-то момент. (Также извините за неправильное написание вашего имени в моем ответе.)if(N(x,y,0)>0)return 0<1;
; первое появлениеreturn
.Котлин , 413 байт
украшенный
Тест
источник