Разбиение сетки на треугольники

18

Цель

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

пример

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

счет

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

Питер Кейджи
источник
10
Некоторые дополнительные тестовые примеры будут полезны, поэтому мы можем проверить правильность наших представлений.
AdmBorkBork
8
Вы можете указать невырожденные треугольники.
Арно
1
Я внес изменения в последовательность OEIS A051708, чтобы отразить эту интерпретацию.
Питер Кейджи

Ответы:

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)
Кевин Круйссен
источник
19

Haskell , 60 55 54 52 байта

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

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

В основном у вас есть верхняя и нижняя линия сетки 1×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

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

flawr
источник
Я нашел последовательность OEIS, выполнив поиск по первым нескольким значениям. Хорошее объяснение того, почему это соответствует. Вы хотите отредактировать его, чтобы добавить комментарий об этой альтернативной комбинаторной интерпретации? Если нет, я мог бы.
Питер Тейлор
Кстати, вам нужно настроить индексирование, потому что правильный ответ здесь A051708(n+1). Поэтому я отправил первый правильный ответ :-P
Питер Тейлор
Я так понимаю, карта ладьи перемещает карту в треугольники, делая треугольники с верхним и нижним краями соответствующими движениям вверх или вправо?
Нил
@PeterTaylor Черт, спасибо, что указал на мою ошибку :)
flawr
5
@Neil Я добавил графическое объяснение.
августа
8

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без деления пополам, что нам нужно для других.

XNOR
источник
Ваше 49-байтовое решение использует ту же рекурсию, что и мой ответ, но я еще не определил 42-байтовую. Объяснение было бы хорошо.
Питер Тейлор
Я думаю, что использовал один и тот же подход в одной из моих предыдущих программ: идея состоит в том, чтобы генерировать (или считать) все разделы, генерируя не горизонтальные линии справа налево. Вы начинаете с вертикальной линии. Затем вы можете выполнить возврат: возьмите один из конечных узлов предыдущей строки и подключите его к узлу на противоположной горизонтальной линии, которая находится слева от всех предыдущих узлов этой линии.
Flawr
Оператор a%b подсчитывает количество секций, используя узлы 0,1,...,aв верхней строке, и кивает 0,1,..,bв нижней строке. Оператор a?bподсчитывает количество способов добавить новую строку из верхнего узла, aесли нижний узел bуже используется. (Вы можете подключиться aко всем узлам [0,1,...,b-1], но затем вам придется выполнить повторение для каждого из них.)
flawr
@flawr, это 49-байтовый, который я понимаю. Это ?из 42 байтов, которые я не делаю, и что особенно любопытно, это то, что это не симметрично.
Питер Тейлор
@PeterTaylor Извините за путаницу, я как-то перепутал два решения. Я думаю, что мы можем довольно легко преобразовать два решения друг в друга: на первом шаге мы можем заменить map...понимание списка, на втором шаге мы просто добавим определение %:a?b=sum$map(a%)[0..b-1], a%b=a?b+b?a a?b=sum[a%i|i<-[0..b-1]], a%b=a?b+b?a a?b=sum[a?i+i?a|i<-[0..b-1]]
flawr
7

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 байтов. Возможно, я должен попытаться написать патч ...

Питер Тейлор
источник
Да, я побил тебя на 10 секунд, я не думаю, что когда-либо был так близко :)
flawr
@flawr, я подумал о публикации, прежде чем писать рассечение, но я подумал, что у меня есть время, чтобы быстро его отключить. Затем я увидел «Новый ответ», поэтому я удалил свое письменное вскрытие, опубликовал и отредактировал.
Питер Тейлор
1
Спасибо за -5 байт между прочим: D
flawr
4

Желе , 15 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). Примените это к каждому маршруту и ​​суммируйте количество способов прохождения каждого маршрута.

фонтанчик для питья
источник
Хороший подход. Когда я перенес его в CJam, было короче уменьшить длину, сумму, а затем повысить 2 до суммы; вместо увеличения на 2, деления пополам, а затем умножения. Не знаю, может ли это сэкономить вам байт.
Питер Тейлор
3

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

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

F⊕θ«≔⟦⟧ηF⊕θ⊞ηΣ∨⁺ηEυ§λκ¹⊞υη»I⊟⊟υ

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

F⊕θ«

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

≔⟦⟧η

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

F⊕θ

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

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

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

⊞υη»

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

I⊟⊟υ

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

Нил
источник
2

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

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

12(1-Икс1-9Икс+1)

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

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

alephalpha
источник