Codegolf — Abaa/Abbb: Создайте Этот Рекурсивный 2D-Шаблон.

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

 
 
 
 N = 0
|-

N = 1
|-||
|---

N = 2
|-|||-|-
|---|-|-
|-||||||
|-------

N = 3
|-|||-|-|-|||-||
|---|-|-|---|---
|-|||||||-|||-||
|-------|---|---
|-|||-|-|-|-|-|-
|---|-|-|-|-|-|-
|-||||||||||||||
|---------------

N = 4
|-|||-|-|-|||-|||-|||-|-|-|||-|-
|---|-|-|---|---|---|-|-|---|-|-
|-|||||||-|||-|||-|||||||-||||||
|-------|---|---|-------|-------
|-|||-|-|-|-|-|-|-|||-|-|-|||-|-
|---|-|-|-|-|-|-|---|-|-|---|-|-
|-|||||||||||||||-|||||||-||||||
|---------------|-------|-------
|-|||-|-|-|||-|||-|||-|||-|||-||
|---|-|-|---|---|---|---|---|---
|-|||||||-|||-|||-|||-|||-|||-||
|-------|---|---|---|---|---|---
|-|||-|-|-|-|-|-|-|-|-|-|-|-|-|-
|---|-|-|-|-|-|-|-|-|-|-|-|-|-|-
|-||||||||||||||||||||||||||||||
|-------------------------------
 
 
 
 

Ширина каждого экземпляра этого узора в два раза превышает высоту. Чтобы перейти с одного уровня паттерна на другой, вы разбиваете этот прямоугольник на два подблока (каждый из которых представляет собой квадрат NxN):

Эти половинки затем дублируются и переставляются по следующему шаблону:

Испытание

Напишите программу/функцию, которая по заданному числу ABAA ABBB giving |-|||-|- |---|-|- |-|||||| |------- , outputs the AB = |-|| |--- so A = |- |- and B = || -- итерация этого рекурсивного дизайна. Это гольф.

Формат ввода-вывода относительно мягок: вы можете вернуть одну строку, список строк, двумерный массив символов и т. д. Допускаются произвольные конечные пробелы. Вы также можете использовать индексацию 0 или 1.

Примеры

Первые несколько итераций шаблона следующие:

Интересно, есть ли какой-нибудь короткий алгебраический способ вычислить эту структуру?

#код-гольф #ascii-art

АПЛ (Диалог Классик), 29 25 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 SubstitutionSystem[{"|"->{i={"|","-"},i},"-"->{i,i}},{i},{#}]&
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

{"|-"x{x,'|+|~x:x,x}/,!2} is the vector matrix

function(n,k=cbind){o=matrix(c("|","-"),1,2) if(n>0)for(i in 1:n)o=rbind(k(a<-o[,x<-1:(2^(i-1))],b<-o[,-x],a,a),k(a,b,b,b)) o} turns it into a 2x1 matrix

≦⊗ιＪ⊗ιιＴ⊗ιι transposes it, so it becomes 1x2

Ｆ432Ｃ×Ｉκι׳ιＦ245Ｃ×Ｉκι⊗ι evaluated input

N ＦＥＮＸ²ι« применить функцию, которая много раз

э²→|- concatenate the argument on top of itself - a 2x2 matrix

э²→|-ＦＥＮＸ²ι«Ｆ432Ｃ×Ｉκι׳ιＦ245Ｃ×Ｉκι⊗ι≦⊗ιＪ⊗ιιＴ⊗ιι remember as ≦⊗ιэ±ι±ιＴ⊗ιι

Ｆ²Ｃ±ι⁰Ｃ⁰ιＣ⊗ι±ιＣ׳ι±ι negate

N transpose

ＦＥＮＸ²ι« reverse horizontally

э²↖|-¶¶ reverse vertically

э²↖|-¶¶ＦＥＮＸ²ι«Ｆ²Ｃ±ι⁰Ｃ⁰ιＣ⊗ι±ιＣ׳ι±ι≦⊗ιэ±ι±ιＴ⊗ιι concatenate with f=.3 :'''|-''{~((,.[:|.[:|."1[:|:-.)@,~)^:y,:0 1' слева

unzip (%)=zipWith(++) f 0=["|-"] f n|(a,b)<-unzip$splitAt(2^(n-1))<$>f(n-1)=a%b%a%a++a%b%b%b использовать матрицу в качестве индексов в строке import StdEnv $0=[['|-']] $n#z=map(splitAt(2^n/2))($(n-1)) =[u++v++u++u\\(u,v)<-z]++[u++v++v++v\\(u,v)<-z] , i.e. turn 0 into ----------------- ;"/;`,Ẏ;`€$ Monadic link. Value = [A, B] ;"/ Accumulate vectorized concatenate. Calculates (A ;" B). Represented as a matrix, it's |AB| (concatenated horizontally) ;` Concatenate with self. |AB| Value = |AB| (concatenate vertically) , $ Pair with ... Ẏ Tighten. |A| (concatenate vertically) Value = |B| ;`€ Concatenate each with self. |AA| Value = |BB| (duplicate horizontally) и 1 в ZY

JavaScript (Node.js), 130...106 94 92 байт

Гольф из моего альтернативного метода и исправления символов, -14 байт Спасибо @Shaggy

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

Мой оригинальный подход (106 102 байт)

-4 байта Спасибо @Shaggy

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

Объяснение и отсутствие гольфа:

Мой оригинальный альтернативный метод, если ["|","-"] is allowed, 105 104 bytes:

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

Только что придумал какой-то алгебраический метод решения этой проблемы.

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

(наконец-то функция, длина которой сопоставима с моим первоначальным ответом)

!¡§z+DȯṁmDTm½;"|- Implicit input: a number n. "|- The string "|-". ; Wrap in a list: ["|-"] ¡ Iterate this function on it: Argument is a list of lines, e.g. L = ["|-||","|---"] m½ Break each line into two: [["|-","||"],["|-","--"]] T Transpose: [["|-","|-"],["||","--"]] ȯṁ Map and concatenate: mD Map self-concatenation. Result: ["|-|-","|-|-","||||","----"] z+ Zip using concatenation § D with L concatenated to itself: ["|-|||-|-","|---|-|-","|-||||||","|-------"] Result is the infinite list [["|-"],["|-||","|---"],["|-|||-|-","|---|-|-","|-||||||","|-------"],... ! Take n'th element, implicitly display separated by newlines. calculates the block type at (x, y) block at !¡§z+DȯṁmDTm½;"|- итерация следующей замены:

где f=lambda x:x<1and['|-']or[n+2*n[i:i+2**x/2]for i in(0,2**x/2)for n in f(x-1)] , starting from ω .

Затем, α calculates the symbol at (x, y) of the original pattern.

Стакс, 24 17 15 байты

Запустите и отладьте его

Вот ascii-представление той же программы.

Основная идея — начать с сетки нулевого поколения, а затем повторить блок, расширяющий сетку.

Холст, 17 16 байты

Попробуйте здесь!

Пояснение, показывающее стек для ввода 1:

Обновлено до 16 байт путем исправления ошибки, из-за которой значения, установленные для g(x)(y) / f(0, 0, 0) = 0 для работы не были скопированы должным образом (Canvas должен быть полностью неизменяемым, но, увы, это не так).

Питон 2, 88 77 байт

^{-11 байт благодаря Линн}

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

Перл 5, 72 байта

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

Шелуха, 17 байт

1-индексированный. Попробуйте онлайн!

Объяснение

Желе, 21 19 байт

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

Объяснение:

Первоначально значение f=n=>n?f(n-1).replace(/[12]+/g,x=>(g=(y,i)=>y.replace(/1|2/g,p=>[,i?11:22,21][p]))(x,0)+` `+g(x,1)):"21" , that is "|"->"2", "-"->"1" .

Последняя ссылка( function f(n) { // Main Function if (n != 0) { // If n != 0: (i.e. not the base case) return [0, 1].map( // Separate the pattern into 2 parts function(j) { // For each part: return f(n - 1).split("\n") // Split the next depth into lines .map(function(x) { // For each line in the result: return x // The common part: "AB" + x.substr( (i = x.length / 2) * j // Take A if j == 0, B if j == 1 , i // Take half the original length ).repeat(2); // Double this part }).join("\n"); // Join all lines together }).join("\n"); // Join the two parts together } else return "|-"; // If not (base case): return "|-"; } ), given f=n=>n?[0,1].map(j=>f(n-1).split` `.map(x=>x+(y=x.substr((i=x.length/2)*j,i))+y).join` `).join` `:"|-" , вернется

. f=n=>n?f(n-1).replace(/.+/g,x=>(g=i=>x.replace(/./g,p=>p<i?s[i]+s[i]:s))`0`+` `+g`1`):s="|-" repeatedly apply the last link (input) number of times, and - форматирует его.

Пояснение к последней ссылке:

Чистый, 121 106 байт

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

Хаскелл, 86 байт

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

Довольно просто. Вывод представляет собой список строк. Мы берем предыдущую версию и разделяем каждую строку пополам, а затем собираем их в два новых списка, используя '|-'[ . Then it's simply a matter of combining the arrays together the right way

Дж, 49 байт

Неуклюжий перевод решения APL от ngn. У меня были проблемы с тем, чтобы сделать это молчаливым - я буду признателен за любой совет.

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

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

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

Чтобы получить согласованную позицию курсора для следующего цикла, мне нужно напечатать шаг 0 в позиции (-2, -2) и оставить курсор в позиции (-2, 0). (Это может быть связано с ошибкой в ​​Charcoal.)

Перебрать первый ⍉ powers of 2.

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

Переместитесь в положение этого прямоугольника и обрежьте холст.

Альтернативное решение, тоже 46 байт:

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

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

Перебрать первый { powers of 2.

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

Переместитесь в положение этого прямоугольника и обрежьте холст.

Р, 126 байт

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

Возвращает 0 1 . There's a bit of code in the TIO link to get it to print nicely for ease of verification.

К (нгн/к), 25 байт

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

Язык Wolfram (Математика), 67 65 байт

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

Простая реализация рекурсии. Возвращает массив символов, заключенный в список.