Куда идет эта змея?

35

Напишите функцию (используя как можно меньше байтов), которая принимает двумерный массив любого числа столбцов и строк, в котором:

  • 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 блока;
  • Змея не может двигаться по диагонали;
  • Пути направлены. (таким образом, два пути, заканчивающиеся в разных позициях, но в остальном выглядящие одинаково, не являются одним и тем же путем, это в сумме составит)
Аделин
источник
13
Добро пожаловать в PPCG! Хороший первый вызов.
Лайкони
5
Небольшое примечание: «Всегда будет по крайней мере одна строка и один столбец» является избыточным, учитывая, что змея всегда будет иметь по крайней мере 2 блока.
Стьюи Гриффин
2
Предлагаемые тестовые случаи: тот, который предоставлен @StewieGriffin и [[0,0,1,1],[0,0,1,1],[0,0,1,1]]. Большинство ответов дают 16, но один дает 15.
Кевин Круйссен
2
Кажется, что все до сих пор (включая меня) сделали предположение, что 2 пути, заканчивающиеся в разных позициях, но в остальном выглядящие одинаково, не являются одним и тем же путем. Я думаю, что это должно быть явно указано.
Арно
2
@Arnauld - это верно. Два пути, заканчивающиеся в разных положениях, но в остальном выглядящие одинаково , не являются одним и тем же путем , это будет суммироваться с итогом. В вашем примере общее число должно быть 16, если я не ошибаюсь - я не могу точно рассчитать прямо сейчас, но вы получите точку
Аделин

Ответы:

11

Wolfram Language (Mathematica) , 16 + 83 = 99 байт

Оператор импорта библиотеки (16 байт):

<<Combinatorica`

Фактическое тело функции (83 байта):

Length@HamiltonianCycle[MakeGraph[#~Position~1~Join~{1>0},##||Norm[#-#2]==1&],All]&

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


Обратите внимание, что в вопросе просто задайте номер гамильтонова пути в графе.

Однако (по некоторым причинам) HamiltonianPathфункция не работает с ориентированным графом ( пример ). Итак, я использовал обходной путь, описанный в этом вопросе Mathematica.SE :

  • Добавьте вершину (называемую True), которая связана со всеми остальными вершинами.
  • Подсчитайте количество гамильтоновых циклов на результирующем графе.

Граф строится с использованием MakeGraph(досадно, что прямо эквивалентных встроенных функций нет), используя булеву функцию ##||Norm[#-#2]==1&, которая возвращает Trueтогда и только тогда, когда один из аргументов равен Trueили расстояние между двумя вершинами равно 1.


Tr[1^x]не может использоваться вместо Length@xи <2не может использоваться вместо ==1.


HamiltonianPathможет использоваться, если график не направлен, причем тело функции занимает 84 байта (ровно на 1 байт больше, чем текущая отправка):

Length@HamiltonianPath[MakeGraph[#~Position~1,Norm[#-#2]==1&,Type->Undirected],All]&

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

user202729
источник
10

JavaScript (ES6), 154 134 байта

m=>m.map((r,Y)=>r.map(g=(_,x,y,r=m[y=1/y?y:Y])=>r&&r[x]&&[-1,0,1,2].map(d=>r[r[x]=0,/1/.test(m)?g(_,x+d%2,y+~-d%2):++n,x]=1)),n=0)|n/4

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

Как?

метод

Начиная с каждой возможной ячейки, мы заполняем матрицу, очищая все ячейки на нашем пути. Всякий раз, когда матрица не содержит больше 1 , мы увеличиваем число n возможных путей.

Каждый действительный путь считается 4 раза из-за направления, выбранного в последней ячейке, что на самом деле не имеет значения. Следовательно, конечный результат n / 4 .

Рекурсивная функция

Вместо вызова рекурсивной функции g () из обратного вызова второго map (), как это ...

m=>m.map((r,y)=>r.map((_,x)=>(g=(x,y,r=m[y])=>...g(x+dx,y+dy)...)(x,y)))

... мы определим рекурсивную функцию г () непосредственно в качестве обратного вызова из карты () :

m=>m.map((r,Y)=>r.map(g=(_,x,y,r=m[y=1/y?y:Y])=>...g(_,x+dx,y+dy)...))

Несмотря на довольно длинную формулу, y=1/y?y:Yкоторая необходима для установки начального значения y , в целом это экономит 2 байта.

Код комментария

m =>                           // given the input matrix m[][]
  m.map((r, Y) =>              // for each row r[] at position Y in m[][]:
    r.map(g = (                //   for each entry in r[], use g() taking:
      _,                       //     - the value of the cell (ignored)
      x,                       //     - the x coord. of this cell
      y,                       //     - either the y coord. or an array (1st iteration),
                               //       in which case we'll set y to Y instead
      r = m[y = 1 / y ? y : Y] //     - r = the row we're currently located in
    ) =>                       //       (and update y if necessary)
      r && r[x] &&             //     do nothing if this cell doesn't exist or is 0
      [-1, 0, 1, 2].map(d =>   //     otherwise, for each direction d,
        r[                     //     with -1 = West, 0 = North, 1 = East, 2 = South:
          r[x] = 0,            //       clear the current cell
          /1/.test(m) ?        //       if the matrix still contains at least one '1':
            g(                 //         do a recursive call to g() with:
              _,               //           a dummy first parameter (ignored)
              x + d % 2,       //           the new value of x
              y + ~-d % 2      //           the new value of y
            )                  //         end of recursive call
          :                    //       else (we've found a valid path):
            ++n,               //         increment n
          x                    //       \_ either way,
        ] = 1                  //       /  do r[x] = 1 to restore the current cell to 1
      )                        //     end of map() over directions
    ),                         //   end of map() over the cells of the current row
    n = 0                      //   start with n = 0
  ) | n / 4                    // end of map() over the rows; return n / 4
Arnauld
источник
10

Желе , 12 11 байт

ŒṪŒ!ạƝ€§ÐṂL

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


Объяснение.

ŒṪ               Positions of snake blocks.
  Œ!             All permutations.
                 For each permutation:
    ạƝ€             Calculate the absolute difference for each neighbor pair
       §            Vectorized sum.
                 Now we have a list of Manhattan distance between snake
                    blocks. Each one is at least 1.
        ÐṂL      Count the number of minimum values.
                    Because it's guaranteed that there exists a valid snake,
                    the minimum value is [1,1,1,...,1].
user202729
источник
Новые функции оказываются чрезвычайно полезными.
user202729
Как насчет §ỊMLтого, §ỊP€Sчтобы вместо того, чтобы сохранить байт - я думаю, что это должно работать?
Джонатан Аллан
... или §ÐṂLчто немного быстрее.
Джонатан Аллан
@JonathanAllan Работает, только если результат ненулевой.
user202729
@JonathanAllan Так что на самом деле все работает.
user202729
8

Python 2 , 257 246 241 234 233 227 214 210 байт

lambda b:sum(g(b,i,j)for j,l in e(b)for i,_ in e(l))
e=enumerate
def g(b,x,y):d=len(b[0])>x>-1<y<len(b);c=eval(`b`);c[d*y][d*x]=0;return d and b[y][x]and('1'not in`c`or sum(g(c,x+a,y)+g(c,x,y+a)for a in(1,-1)))

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


Сохраненный

  • -8 байт, благодаря Кевину Круйссену
  • -14 байт, спасибо пользователю 202729
TFeld
источник
1
249 байт, удалив wиh
Кевин Круйссен
1
Правильный язык для работы?
Нил