Напишите функцию (используя как можно меньше байтов), которая принимает двумерный массив любого числа столбцов и строк, в котором:
0
представляет пустой блок,1
представляет собой змеиный блок.
Функция должна возвращать количество возможных путей, пройденных змеей.
Пример 1:
Входные данные:
[
[1,1,1,1,1],
[0,0,0,0,1],
[0,0,0,0,1],
]
Выход: 2
В приведенном выше примере функция вернется, 2
потому что ответ является одним из:
Пример 2:
Входные данные:
[
[1,1,1,1],
[0,0,1,1],
[0,0,1,1],
]
Выход: 6
В этом примере функция вернется, 6
потому что ответ может быть одним из:
Заметка:
Оценивая вклад, вы можете предположить, что:
- Массивы, представляющие столбцы, всегда будут иметь одинаковые размеры (поэтому массивы имеют прямоугольную форму);
- Существует как минимум 1 действительный путь;
- Змея не может пройти через края (как это может случиться в некоторых версиях змеи);
- У змеи всегда будет как минимум 2 блока;
- Змея не может двигаться по диагонали;
- Пути направлены. (таким образом, два пути, заканчивающиеся в разных позициях, но в остальном выглядящие одинаково, не являются одним и тем же путем, это в сумме составит)
code-golf
grid
binary-matrix
Аделин
источник
источник
[[0,0,1,1],[0,0,1,1],[0,0,1,1]]
. Большинство ответов дают 16, но один дает 15.Ответы:
Wolfram Language (Mathematica) , 16 + 83 = 99 байт
Оператор импорта библиотеки (16 байт):
Фактическое тело функции (83 байта):
Попробуйте онлайн!
Обратите внимание, что в вопросе просто задайте номер гамильтонова пути в графе.
Однако (по некоторым причинам)
HamiltonianPath
функция не работает с ориентированным графом ( пример ). Итак, я использовал обходной путь, описанный в этом вопросе Mathematica.SE :True
), которая связана со всеми остальными вершинами.Граф строится с использованием
MakeGraph
(досадно, что прямо эквивалентных встроенных функций нет), используя булеву функцию##||Norm[#-#2]==1&
, которая возвращаетTrue
тогда и только тогда, когда один из аргументов равенTrue
или расстояние между двумя вершинами равно1
.Tr[1^x]
не может использоваться вместоLength@x
и<2
не может использоваться вместо==1
.HamiltonianPath
может использоваться, если график не направлен, причем тело функции занимает 84 байта (ровно на 1 байт больше, чем текущая отправка):Попробуйте онлайн!
источник
JavaScript (ES6),
154134 байтаПопробуйте онлайн!
Как?
метод
Начиная с каждой возможной ячейки, мы заполняем матрицу, очищая все ячейки на нашем пути. Всякий раз, когда матрица не содержит больше 1 , мы увеличиваем число n возможных путей.
Каждый действительный путь считается 4 раза из-за направления, выбранного в последней ячейке, что на самом деле не имеет значения. Следовательно, конечный результат n / 4 .
Рекурсивная функция
Вместо вызова рекурсивной функции g () из обратного вызова второго map (), как это ...
... мы определим рекурсивную функцию г () непосредственно в качестве обратного вызова из карты () :
Несмотря на довольно длинную формулу,
y=1/y?y:Y
которая необходима для установки начального значения y , в целом это экономит 2 байта.Код комментария
источник
Желе ,
1211 байтПопробуйте онлайн!
Объяснение.
источник
§ỊML
того,§ỊP€S
чтобы вместо того, чтобы сохранить байт - я думаю, что это должно работать?§ÐṂL
что немного быстрее.Python 2 ,
257246241234233227214210 байтПопробуйте онлайн!
Сохраненный
источник
w
иh
Python 2, 158 байт
Попробуйте онлайн!
источник
Haskell ,
187155 байтовПопробуйте онлайн!
источник