Цель

Целью этой задачи является создание функции, nкоторая вычисляет количество способов разбить n X 1сетку на треугольники, где все вершины треугольников находятся в точках сетки.

пример

Например, существует 14 способов разбиения сетки 2 x 1, поэтому f(2) = 14через следующие разделы, где разделы имеют 2, 2, 2, 2, 4 и 2 разных ориентации соответственно.

счет

Это код-гольф , поэтому выигрывает самый короткий код.

05AB1E , 13 байтов

·LÉœÙεÅγo;P}O

Порт @Bubbler 's Jelly ответа .

Очень медленный из-за встроенных перестановок.

Попробуйте онлайн или проверьте первые четыре входа .

Объяснение:

·                # Double the (implicit) input
 L               # Create a list in the range [1, doubled_input]
  É              # Check for each if they're odd (1 if truthy, 0 is falsey)
                 # We now have a list of n 0s and n 1s (n being the input)
   œ             # Get all permutations of that list
    Ù            # Only leave the unique permutations
     ε     }     # Map each permutation to:
      Åγ         #  Run-length encode the current value (short for `γ€g`)
        o        #  Take 2 to the power for each
         ;       #  Halve each
          P      #  Take the product of the mapped permutation
            O    # Sum all mapped values together (and output implicitly)

Haskell , 60 55 54 52 байта

После рисования и программирования множества примеров мне пришло в голову, что это то же самое, что и проблема ладей:

На шахматной доске $(n+1) \times (n+1)$ сколько путей для ладьи, чтобы перейти от $(0,0)$ к $(n,n)$ , просто двигаясь вправо $+(1,0)$ или вверх$+(0,1)$ ?

В основном у вас есть верхняя и нижняя линия сетки $1 \times n$ . Теперь вам нужно заполнить не горизонтальную линию. Каждый треугольник должен иметь две не горизонтальные линии. Независимо от того, является ли одна из его сторон частью верхней или нижней линии, соответствует направлению и длине, которую вы бы выбрали в задаче о грачах. Это OEIS A051708 . В качестве иллюстрации этого соответствия рассмотрим следующие примеры. Здесь верхняя линия соответствует восходящим движениям, а нижняя соответствует правым движениям.

Спасибо @PeterTaylor за -6 байтов и @PostLeftGarfHunter за -2 байта!

b 0=1
b 1=2
b n=div((10*n-6)*b(n-1)-9*(n-2)*b(n-2))n

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

Haskell , 42 байта

0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n

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

Довольно прямая реализация, которая рекурсивно использует более 2 переменных.

Вот как мы можем получить это решение. Начнем с кода, реализующего прямую рекурсивную формулу:

54 байта

0%0=1
a%b=sum$map(a%)[0..b-1]++map(b%)[0..a-1]
f n=n%n

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

Использование интерпретации ладья перемещения flawr в , a%bэто число путей , которые получают ладью от (a,b)к (0,0), используя только перемещает уменьшение координаты. Первый ход либо уменьшается, aлибо уменьшается b, а другой остается тем же, отсюда и рекурсивная формула.

49 байтов

a?b=sum$map(a%)[0..b-1]
0%0=1
a%b=a?b+b?a
f n=n%n

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

Мы можем избежать повторения map(a%)[0..b-1]++map(b%)[0..a-1], отметив, что две половины одинаковы aи bпоменялись местами. Вспомогательный вызов a?bподсчитывает пути, где уменьшается первый ход a, и, таким образом, b?aподсчитывает пути, где уменьшается первый ход b. Они в целом разные, и они добавляют к a%b.

Суммирование в a?bможет также быть записано как понимание списка a?b=sum[a%i|i<-[0..b-1]].

42 байта

0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n

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

Наконец, мы избавиться %и просто написать рекурсию с точки зрения ?путем замены a%iс a?i+i?aв рекурсивном вызове.

Новый базовый случай приводит ?к тому, что это дает выходные данные вдвое больше, чем ?в 49-байтовой версии, так как с 0?0=1, мы бы получили 0%0=0?0+0?0=2. Это позволяет использовать определение f n=n?nбез деления пополам, что нам нужно для других.

CJam (24 байта)

{2,*e!{e`0f=:(1b2\#}%1b}

Онлайн демо

Это использует подход Bubbler суммирования по перестановкам n0s иn 1.

рассечение

{         e# Define a block
  2,*     e#   Given input n, create an array of n 0s and n 1s
  e!      e#   Generate all permutations of that array
  {       e#   Map:
    e`    e#     Run-length encode
    0f=:( e#     Extract just the lengths and decrement them
    1b    e#     Sum
    2\#   e#     Raise 2 to the power of that sum
  }%
  1b      e#  Sum the mapped values
}

Альтернативный подход (28 байт)

{_1aa{_2$,f{j}@@,f{j}+1b}2j}

Онлайн демо

рассечение

Все треугольники имеют одно горизонтальное ребро и два ребра, которые связывают горизонтальные линии. Пометьте негоризонтальные ребра с помощью кортежа их двух x-координат и отсортируйте лексикографически. Тогда первое ребро (0,0), последнее ребро (n,n), и два последовательных ребра отличаются точно в одном из двух положений. Это делает простую рекурсию, которую я реализовал, используя запомненный оператор рекурсии j:

{            e# Define a block
  _          e#   Duplicate the argument to get n n
  1aa        e#   Base case for recursion: 0 0 => 1
  {          e#   Recursive body taking args a b
    _2$,f{j} e#     Recurse on 0 b up to a-1 b
    @@,f{j}  e#     Recurse on a 0 up to a b-1
    +1b      e#     Combine and sum
  }2j        e#   Memoised recursion with 2 args
}

Заметка

Это не первый раз, когда я хотел fj чтобы меня поддерживали в CJam. Здесь это также уменьшит счет до 24 байтов. Возможно, я должен попытаться написать патч ...

Желе , ₁₅ 14 байт

Ø.xŒ!QŒɠ€’§2*S

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

-1 байт на основе комментария Питера Тейлора.

Использует иллюстрацию flawr напрямую, а не полученную формулу.

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

Ø.xŒ!QŒɠ€’§2*S    Main link (monad). Input: positive integer N.
Ø.x               Make an array containing N zeros and ones
   Œ!Q            All unique permutations
      Œɠ€         Run-length encode on each permutation
         ’§       Decrement and sum each
           2*S    Raise to power of 2 and sum

Возьмите все возможные маршруты по квадратной сетке. Количество способов перемещения L единиц в одном направлении, как ладья 2**(L-1). Примените это к каждому маршруту и ​​суммируйте количество способов прохождения каждого маршрута.

Древесный уголь , 44 31 байт

вычеркнул 44 все еще регулярно 44

Ｆ⊕θ«≔⟦⟧ηＦ⊕θ⊞ηΣ∨⁺ηＥυ§λκ¹⊞υη»Ｉ⊟⊟υ

Попробуйте онлайн! Объяснение: Работает, вычисляя количество способов разбить трапецию противоположных длин сторон m,nна треугольники, которые все лежат на целочисленных смещениях. Это просто общий случай прямоугольника размера nв вопросе. Число разделов дается рекурсивно как суммы номеров разделов для всех сторон m,0..n-1и n,0..m-1. Это эквивалентно обобщенной проблеме ладей, OEIS A035002 . Код просто вычисляет количество рабочих разделов, начиная 0,0с n,nиспользования ранее вычисленных значений.

Ｆ⊕θ«

Цикл по рядам 0..n.

≔⟦⟧η

Начните с пустой строки.

Ｆ⊕θ

Обведите столбцы в строке 0..n.

⊞ηΣ∨⁺ηＥυ§λκ¹

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

⊞υη»

Добавьте готовую строку в список строк.

Ｉ⊟⊟υ

Выведите окончательное значение, рассчитанное.

JavaScript (ES6),  45 44  42 байта

Использует рекурсивную формулу, найденную Питером Тейлором и Flawr .

f=n=>n<2?n+1:(10-6/n)*f(--n)+9/~n*f(--n)*n

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

Пари / ГП , 43 байта

Согласно OEIS , производящей функцией этой последовательности является

n->Vec(sqrt((1-x)/(1-9*x)+O(x^n++))+1)[n]/2

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

Python 3 , 51 байт

lambda n:-~n*(n<2)or(10-6/n)*f(n-1)-(9-18/n)*f(n-2)

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

Порт ответа