Фибоначчи черепица домино

11

Классический комбинаторный результат состоит в том, что число способов разбить 2*nполосу 1*2домино - это n- е число Фибоначчи. Ваша цель состоит в том, чтобы напечатать все элементы мозаичного изображения, заданные nштрихами и вертикальными линиями, как эти 8 элементов мозаичного изображения для n=5:

|————
|————

——|——
——|——

|||——
|||——

————|
————|

||——|
||——|

|——||
|——||

——|||
——|||

|||||
|||||

Вы должны предоставить программу или именованную функцию, которые принимают в nкачестве входных данных и распечатывают требуемые выходные данные. Побеждает несколько байтов.

вход

Число nмежду 1и 10включительно через STDIN или функциональный вход.

Выход

Напечатайте все возможные фрагменты домино 2*nполосы, нарисованные горизонтально. Повороты могут быть в любом порядке, но каждый должен появляться ровно один раз. Они должны быть отделены пустой строкой.

Вертикальное домино состоит из двух вертикальных полос ( |), а горизонтальное домино состоит из двух черточек ( ). Вы можете использовать дефисы ( -) вместо тире, чтобы остаться в ASCII.

Вы можете делать что-либо с пробелами, если вывод на печать выглядит одинаково.

XNOR
источник
Будет ли дополнительный перевод строки после последней плитки попадать под что-либо с пробелами ?
Деннис
@ Денис Да, дополнительные пустые строки в порядке.
xnor
Я действительно удивлен, увидев так много разных подходов к решению одной и той же проблемы. Вы ожидали этого?
Уровень Река
@steveverrill Нет, я полностью не сделал, и рад видеть разнообразие! А твой берет торт за неожиданность. В основном я имел в виду рекурсию в стиле Фибоначчи, так как большинство используемых решений я использовал. Я не ожидал , что фильтрация , чтобы быть эффективным, и в той степени , которую я сделал, я хотя бы фильтровать строки ——и |от длины , как Деннис, а не длина- nстроки и |фильтруется появляются парами. И для последнего я бы ожидал, что это будет с помощью регулярных выражений или строковых операций над созданной строкой, например s.split('——), а не с помощью арифметического подхода, подобного вашему.
xnor
Я думаю, что «1x2 домино» является излишним.
SuperJedi224

Ответы:

5

С, 106

Гольф версия

f(n){
  for(int i,h=n*2<<n;h--;(i/3|i/3*2)-i||(putchar(i>>h%n&1?45:124),h%n||puts(h%(n*2)?"":"\n")))
    i=h/2/n;
}

Оригинальная версия

i,j,n;
main(){
  scanf("%d",&n);
  for(i=1<<n;i--;)if((i/3|i/3*2)==i){
    for(j=1<<n;j/=2;)printf("%c",i&j?'-':'|');puts("");
    for(j=1<<n;j/=2;)printf("%c",i&j?'-':'|');puts("\n");
  }
}

Как это работает

Переменная iработает от 1<<n-10 до 0, создавая все возможные двоичные числа с nцифрами. 0 кодирует для |и 1 кодирует для -. Нас интересуют числа, которые содержат 1 в парах. Очевидно, что такие числа делятся на 3.

Когда число делится на 3, исходное число можно восстановить, умножив результат на 2 и добавив его к себе (эффективно умножая на 3). Большинство чисел потребует перенос, но когда процесс выполняется на числах проценты, перенос не требуется, поэтому в этих случаях вместо дополнения можно использовать только ИЛИ. Это используется для проверки интересующих чисел, поскольку они являются единственными, где выражение i/3|i/3*2возвращает исходное значение i. Смотрите пример ниже.

1111= 15 ---> 0101= 5 ---> 1111= 15 (действует, 0101|1010== 0101+1010)

1001= 9 ---> 0011= 3 ---> 0111= 7 (неверно 0011|0110,! = 0011+0110)

Тестовое значение всегда равно или меньше исходного значения. Поскольку числа, не кратные 3, также возвращают число, меньшее оригинала, при делении на 3 и затем умножении на 3, тест также дает желаемое значение FALSE для этих чисел.

В оригинальной версии пара циклов jиспользуется для сканирования битов iи вывода. В версии для гольфа используется единственная forпетля, в которой hпробегаются все числа от (n*2)*(1<<n)-1нуля до 0. Значения iгенерируются с помощью h/2/n. Переменная jбольше не используется, поскольку эквивалентное количество получается из h%n. Использование n*2позволяет печатать обе строки из одного и того же цикла, при этом в putsоператоре используется несколько мультиплексоров для печати одной или двух новых строк в конце строки.

Обратите внимание , что мясо это в положении приращения for()кронштейна и , следовательно , запускается на выполнение послеi=h/2/h .

Пример вывода n = 6:

$ ./a
6
------
------

----||
----||

--|--|
--|--|

--||--
--||--

--||||
--||||

|----|
|----|

|--|--
|--|--

|--|||
|--|||

||----
||----

||--||
||--||

|||--|
|||--|

||||--
||||--

||||||
||||||
Уровень реки St
источник
i/3|i/3*2Трюк гениален! Я не ожидал арифметического выражения для грамматики.
xnor
3

CJam, 33 27 байтов

LN{_'|f+@"——"f++}ri*\;{_N}/

Спасибо @ jimmy23013 за удаление 6 байтов!

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

Фон

Это итеративная реализация рекурсивного алгоритма:

Возможные значения для n могут быть получены путем добавления вертикального домино к возможным значениям для n - 1 и двух горизонтальных домино для возможных значений для n - 2 .

Таким образом, число мозаичных чисел для n является суммой чисел мозаичных чисел для n - 1 и n - 2 , то есть n- го числа Фибоначчи.

Как это работает

LN                                " A:= [''] B:= ['\n']                         ";
  {             }ri*              " Repeat int(input()) times:                  ";
   _'|f+                          "   C = copy(B); for T ∊ C: T += '|'          ";
              @                   "   Swap A and B.                             ";
               "——"f+             "   for T ∊ B: T += "——"                      ";
                     +            "   B = C + B                                 ";
                        \;        " Discard A.                                  ";
                          {_N}/   " for T ∊ B: print T, T + '\n'                ";

Пример запуска

$ alias cjam='java -jar cjam-0.6.2.jar'

$ cjam domino.cjam <<< 3
|||
|||

——|
——|

|——
|——

$ for i in {1..10}; do echo $[$(cjam domino.cjam <<< $i | wc -l) / 3]; done1
2
3
5
8
13
21
34
55
89
Деннис
источник
LNli{_'|f\@"——"f\+2/}*\;{_N}/,
jimmy23013
f\еще не был реализован в 0.6.2, но я смог объединить наши подходы. Благодаря!
Деннис
2

Haskell, 89 байт

f(-1)=[]
f 0=[""]
f n=map('|':)(f$n-1)++map("--"++)(f$n-2)
g=unlines.(>>= \x->[x,x,""]).f

fявляется функцией, которая с заданным числом возвращает список из одной строки всех возможных значений Фибоначчи длины n возможных. не имеет значения, что он возвращает одну строку, потому что обе строки всех значений одинаковы.

fработает рекурсивно, вызывая n-1и n-2и добавляя "|"и "--"(соответственно) к строкам.

gэто функция, которая отвечает на вопросы. он в основном вызывает fвходные данные, удваивает каждую строку, чтобы показать две строки, и соединяет их все символами новой строки.

пример вывода:

*Main> putStrLn $ g 5
|||||
|||||

|||--
|||--

||--|
||--|

|--||
|--||

|----
|----

--|||
--|||

--|--
--|--

----|
----|
гордый хаскеллер
источник
2

CJam, 42 37 байт

3li:L#,{3b"——|"2/f=s}%{,L=},_&{N+_N}/

Я посчитал тире как один байт каждый, так как вопрос позволяет заменить их дефисами ASCII.

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

Как это работает

Чтобы получить все возможные значения в 2 × L , мы перебираем все неотрицательные целые числа I <3 L , чтобы четные цифры в основании 3 соответствовали горизонтальным домино, а нечетные - вертикальным.

Поскольку у каждого I есть L или меньше цифр в основании 3, это генерирует все возможные способы покрытия полосы 2 × L. Осталось только отфильтровать покрытия, которые больше или меньше 2 × L, и распечатать остальные покрытия.

3li:L#,      " Read an integer L from STDIN and push A := [ 0 1 ... (3 ** N - 1) ].       ";
{            " For each integer I in A:                                                   ";
  3b         " Push B, the array of I's base 3 digits.                                    ";
  "——|"2/    " Push S := [ '——' '|' ].                                                    ";
  f=         " Replace each D in B with S[D % 2] (the modulus is implicit).               ";
  s          " Flatten B.                                                                 ";
}%           " Collect the result in an array R.                                          ";
{,L=},       " Filter R so it contains only strings of length L.                          ";
_&           " Intersect R with itself to remove duplicates.                              ";
{N+_N}/      " For each string T in B, push (T . '\n') twice, followed by '\n'.           ";

Пример запуска

$ cjam domino.cjam <<< 3
|——
|——

——|
——|

|||
|||

$ for i in {1..10}; do echo $[$(cjam domino.cjam <<< $i | wc -l) / 3]; done
1
2
3
5
8
13
21
34
55
89
Деннис
источник
Здорово. Мне просто интересно, почему вы не использовали базу 2, например, edc65 вместо базы 3. Это избавило бы вас от дубликатов. Я предполагаю, что это потому, что ведущие нули, вероятно, усекаются в шаге 3b. Это правильно?
Уровень Река
1
@steveverrill: Да, именно в этом причина. На самом деле, ведущие нули не соответствуют никакому домино. Но отсутствие дубликатов позволило бы мне заменить три блока на один. Я должен подумать об этом еще немного.
Деннис
@steveverrill: мне не удалось заставить работать базу 2, но рекурсивный подход кажется еще короче.
Деннис
2

JavaScript (E6) 102

Генерация конфигураций из битовых последовательностей, 0 -> '-' и 1 -> '|'.

F=n=>{
  for(i=0;(j=++i)<2<<n;s.length==1+n&&console.log('\n'+s+s))
    for(s='\n';j>1;j>>=1)s+=j&1?'|':'--';
}

Test In firefox / консоль firebug

F(5)

Выход

|----
|----

--|--
--|--

----|
----|

|||--
|||--

||--|
||--|

|--||
|--||

--|||
--|||

|||||
|||||
edc65
источник
1

Haskell: 109 байт

Это перевод известной однострочности Хаскеля для ленивого вычисления последовательности чисел Фибоначчи:

b=map.map.(++)
w=zipWith
z=w(++)
s=["\n"]:["|\n"]:z(b"--"s)(b"|"$tail s)
f=sequence_.map putStrLn.(w z s s!!)

Основная последовательность плиточных нитей, не разглаженных:

dominos = [""] : ["|"] : zipWith (++) ("--" `before` dominos) ("|" `before` tail dominos)
    where before = map . map . (++)

И однострочник Фибоначчи для сравнения:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Пример использования:

$ ghci fibtile
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( fibtile.hs, interpreted )
Ok, modules loaded: Main.
*Main> f 5
----|
----|

--|--
--|--

--|||
--|||

|----
|----

|--||
|--||

||--|
||--|

|||--
|||--

|||||
|||||

*Main>
Мэтт Нунан
источник
1

Кобра - 176

Не могу дождаться, пока я закончу с коброй.

def m(n)
    for t in.f(n),print t+t
def f(n,x='')as String*
    if x.length<n,for i in.f(n,x+'-').toList+.f(n,x+'|').toList,yield i
    else if not'-'in x.replace('--',''),yield x+'\n'
Οurous
источник
1

J - 54 символа

Функция принимает в nкачестве аргумента справа.

0{::(];'--'&,"1@[,'|',"1])&>/@[&0&((1 2$,:)&.>'';,'|')

Основным корнем этого гольфа является (];'--'&,"1@[,'|',"1])&>/. Это берет список значений длины (N-2) и (N-1) и возвращает список значений длины (N-1) и N. Это стандартное повторение Фибоначчи, как линейная алгебра. ];возвращает правый список как новый левый (поскольку изменений нет). '--'&,"1@[добавляет --плитки в левый список, в то время как '|',"1]добавляет |плитки в правый список, и они вместе являются новым правым списком.

Мы повторяем это много nраз (это @[&0) и начинаем с пустого тайлинга и одиночного тайлинга длины 1. Затем мы возвращаем первый из пары с 0{::. То есть, если мы запустим его ноль раз, мы просто вернем первый, то есть пустой лист. Если мы запустим его nраз, мы вычислим до пары nи ( n+1), но отбросим последнюю. Это дополнительная работа, но меньше персонажей.

Это (1 2$,:)то, что J должен сделать, чтобы элементы в списках легко расширялись. Мы делаем левый начальный список одним списком из 2-х рядных символов, каждая строка имеет длину 0. Правый начальный список такой же, но строки длиной 1 заполнены |. Затем мы добавляем новые плитки в каждую строку и добавляем списки матриц, когда мы соединяем два набора мозаичных элементов вместе. Это простое применение концепции, которую J называет «рангом»: по сути, манипулирование размерностью своих аргументов и неявное зацикливание при необходимости.

   0{::(];'--'&,"1@[,'|',"1])&>/@[&0&((1 2$,:)&.>'';,'|')5
----|
----|

--|--
--|--

--|||
--|||

|----
|----

|--||
|--||

||--|
||--|

|||--
|||--

|||||
|||||

Попробуйте сами на tryj.tk .

algorithmshark
источник
1

Python 3: 70 байт

f=lambda n,s="\n":n>0and f(n-1,"|"+s)==f(n-2,"--"+s)or n or print(s*2)

Рекурсивно строит все возможные строки, sпредставляющие один ряд домино, которые дублируются и печатаются. Начиная sс символа новой строки, автоматически появляется пустая строка.

==Между двумя вызовами для fтолько для выполнения обеих вызовов функций. Они обычно возвращаются, Noneпотому что они просто печатают, и ==это один из немногих операторов, определенных для None.

В ands и ors являются произвести правильное поведение короткое замыкание , чтобы воспроизвести ifс и elseх годов ungolfed кода.

Ungolfed:

def f(n,s="\n"):
 if n==-1:pass
 elif n==0: print(s*2)
 else: f(n-1,"|"+s);f(n-2,"--"+s)
XNOR
источник
1

Сетчатка , 44 байта

Примечание: сетчатка моложе, чем этот вызов.

+`([-|]*)11(1*#)
$1|1$2$1--$2
1
|
.*?#
$0$0#

Принимает ввод в унарном виде с завершающим переводом строки.

Каждая строка должна идти в свой собственный файл и #должна быть заменена на новую строку в файле. Это нецелесообразно, но вы можете запускать код как один файл с -sфлагом, сохраняя #маркеры (и изменяя символ новой строки на также #во входных данных). При желании вы можете изменить #обратно на новые строки в выходных данных. Например:

> echo 1111# | retina -s fib_tile | tr # '\n'
||||
||||

||--
||--

|--|
|--|

--||
--||

----
----

Метод:

  • Начиная со ввода мы меняем каждую строку двумя другими: одна с первым 1изменением на |и одна с первыми двумя 1, замененными на --. Мы делаем это до тех пор, пока не получим строки, по крайней мере, с двумя 1.
  • Когда остались только синглы 1, мы изменили их на |s.
  • Мы удваиваем каждую строку и добавляем к ней дополнительную новую строку, и мы получаем желаемый результат.
randomra
источник
Трейлинг новой строки в порядке.
xnor