ABAA / ABBB: Wygeneruj ten rekurencyjny wzór 2D

30

Gawędziłem z nieskończonymi sieciami rezystorów (długa historia), kiedy natknąłem się na następujący interesujący wzorzec rekurencyjny:

|-||
|---

Każde wystąpienie tego wzoru jest dwa razy szersze niż wysokie. Aby przejść z jednego poziomu wzoru na następny, należy rozbić ten prostokąt na dwa podbloki (z których każdy jest kwadratem NxN):

AB =
|-||
|---

so A = 
|-
|-

and B = 
||
--

Połówki te są następnie powielane i układane zgodnie z następującym wzorem:

ABAA
ABBB

giving

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

Wyzwanie

Napisz program / funkcję, która przy danej liczbie Nwyświetli Niterację tego rekurencyjnego projektu. To jest golf.

Format we / wy jest względnie łagodny: możesz zwrócić pojedynczy ciąg, listę ciągów, tablicę znaków 2D itp. Dozwolona jest dowolna końcowa spacja. Możesz także użyć indeksowania 0 lub 1.

Przykłady

Pierwsze kilka iteracji wzoru jest następujące:

N = 0
|-

N = 1
|-||
|---

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

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

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

Zastanawiam się, czy istnieje jakiś krótki algebraiczny sposób obliczenia tej struktury.

PhiNotPi
źródło
Co rozumiesz przez „algebraiczny”?
user202729,
4
@ user202729 Być może istnieje „prosta” formuła matematyczna, f(n,x,y)która może bezpośrednio obliczyć, czy dana współrzędna powinna zawierać -lub |. Może to obejmować operacje modulo lub operacje bitowe. Techniki, które do tej pory widziałem, obejmują wycinanie / łączenie tablic, jak pokazano w specyfikacji.
PhiNotPi
3
f(x,y)działa również, ponieważ jeśli x,yjest poprawny, wynik nie zależy odn
amara
2
Czy dane wyjściowe mogą być indeksowane 1, to znaczy dane wejściowe 1 dają |-?
Zgarb
2
Czy to strata? 🤔
qwr

Odpowiedzi:

13

APL (Dyalog Classic) , 29 25 bajtów

'|-'[{a,⊖⌽⍉~a←⍪⍨⍵}⍣⎕⍉⍪⍳2]

Wypróbuj online!

⍳2 jest wektorem 0 1

zamienia to w macierz 2x1

transponuje go, więc staje się 1x2

oceniane wejście

{ }⍣⎕ zastosuj funkcję wiele razy

⍪⍨⍵ połącz argument na wierzchu - macierz 2x2

a← pamiętaj jak a

~ negować

transponować

odwrócić w poziomie

odwrócić w pionie

a,konkatenuj z apo lewej stronie

'|-'[ ]użyj macierzy jako wskaźników w ciągu '|-', tzn. zamień 0 na |1 na-

ngn
źródło
10

JavaScript (Node.js) , 130 ... 106 94 92 bajty

Grałem w golfa z mojej alternatywnej metody i ustalania znaków, -14 bajtów Dzięki @Shaggy

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="|-"

Wypróbuj online!

Moje oryginalne podejście ( 106 102 bajtów)

f=n=>n?[0,1].map(j=>f(n-1).split`
`.map(x=>x+x.substr((i=x.length/2)*j,i).repeat(2)).join`
`).join`
`:"|-"

-4 bajty Dzięki @Shaggy

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`
`:"|-"

Wypróbuj online!

Wyjaśnienie i nieprzygotowany:

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 "|-";
}

Moja oryginalna metoda alternatywna, jeśli "|"->"2", "-"->"1"jest dozwolona, 105 104 bajtów:

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"

Wypróbuj online!

Właśnie wymyśliłem jakąś metodę algebraiczną dotyczącą tego problemu.

x=>y=>"|-||--"[(f=(x,y,t=0,m=2**30,i=!(y&m)*2+!(x&m)<<1)=>m?f(x^m,y^m,([18,0,90][t]&3<<i)>>i,m>>1):t)(x>>1,y)*2+x%2]

Wypróbuj online!

(wreszcie funkcja o długości porównywalnej z moją pierwotną odpowiedzią)

f(n, x, y)oblicza typ bloku w bloku (x, y) przy niteracji następującego podstawienia:

0 => 0 1      1 => 0 0      2 => 1 1
     0 2           0 0           2 2

skąd 0 = "|-", 1 = "||", 2 = "--", począwszy od f(0, 0, 0) = 0.

Następnie g(x)(y)oblicza symbol w (x, y) oryginalnego wzoru.

Shieru Asakoto
źródło
102 bajty dla twojego pierwszego rozwiązania.
Kudłaty
88 bajtów na sekundę.
Kudłaty
1
Twoje drugie rozwiązanie działa z poprawnymi znakami dla 95 bajtów
Kudłaty
^ 94 bajty
Kudłaty
92 bajty
Kudłaty
9

Stax , 24 17 15 bajtów

╛ä├¼àz[{╧↑;ε╖>╠

Uruchom i debuguj

Oto reprezentacja ascii tego samego programu.

'|'-{b\2*aa+c\}N\m

Podstawową ideą jest rozpoczęcie od siatki 0 generacji, a następnie powtórzenie bloku, który rozszerza siatkę.

'|'-                    Push "|" and "-"
     {         }N       Get input and repeat block that many times.
      b                 Copy two top stack values
       \2*              Zip two parts, and double the height
          aa            Roll the top of the stack down to 3rd position.
            +           Concatenate two grids vertically
             c\         Copy result and zip horizontally
                  \     Zip the two parts horizontally
                   m    Output each row
rekurencyjny
źródło
8

Płótno , 17 16 bajtów

|∙-╶[∔αω+:∔;:+}+

Wypróbuj tutaj!

Objaśnienie, pokazując stos dla danych wejściowych 1:

|∙-               push "|" and "-" - the initial halves  "|", "-"
   ╶[         }   repeat input times                     
     ∔              add the two parts vertically         "|¶-"
      αω            get the original arguments to that   "|¶-", "|", "-"
        +           and add those horizontally           "|¶-", "|-"
         :∔         and add to itself vertically         "|¶-", "|-¶|-"
           ;        get the vertically added parts       "|-¶|-", "|¶-"
            :+      and add to itself horizontally       "|-¶|-", "||¶--"
               +  finally, add the halves together       "|-||¶|---"

Zaktualizowano do 16 bajtów, naprawiając błąd, w wyniku którego wartości ustawione dla α/ ωdo działania nie zostały poprawnie skopiowane (Canvas ma być w pełni niezmienny, ale, niestety, nie był).

dzaima
źródło
6

Python 2 , 88 77 bajtów

-11 bajtów Thansk do Lynn

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)]

Wypróbuj online!

Pręt
źródło
Możesz przetłumaczyć te zestawienia razem dla 77: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)]
Lynn
4

Perl 5 , 72 bajtów

@1='|-';$l=@1,map{/.{$l}/;push@1,$_.$' x2;$_.=$&x2}@1for 1..<>;say for@1

Wypróbuj online!

Xcali
źródło
1
Zoptymalizowany do 66: $.=map{s/.{$.}$/$&$$ /,push@1,$. $ & X3} @ 1for (@ 1 = "| -") x <>; powiedzmy dla @ 1`
Ton Hospel
4

Łuska , 17 bajtów

!¡§z+DȯṁmDTm½;"|-

1-indeksowany. Wypróbuj online!

Wyjaśnienie

!¡§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.
Zgarb
źródło
3

Galaretka , 21 19 bajtów

;"/;`,Ẏ;`€$
⁾|-Ç¡ZY

Wypróbuj online!


Wyjaśnienie:

Początkowo wartość wynosi ⁾|-, to znaczy ["|","-"].

Ostatni Çpodany link ( ) [A, B]powróci

   AB     AA
[  AB  ,  BB  ]

. ¡Wielokrotnie zastosować ostatnie ogniwo (wejście) liczbę razy i ZYformaty to.

Objaśnienie ostatniego linku:

-----------------
;"/;`,Ẏ;`€$  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)
użytkownik202729
źródło
2

Czysty , 121 106 bajtów

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]

Wypróbuj online!

Obrzydliwe
źródło
2

Haskell , 86 bajtów

(%)=zipWith(++)
f 0=["|-"]
f n|(a,b)<-unzip$splitAt(2^(n-1))<$>f(n-1)=a%b%a%a++a%b%b%b

Wypróbuj online!

Dość proste. Dane wyjściowe to lista ciągów znaków. Bierzemy poprzednią wersję i dzielimy każdą linię na pół, a następnie zbieramy je na dwie nowe listy za pomocą unzip. Następnie wystarczy po prostu połączyć tablice we właściwy sposób

użytkownik 1472751
źródło
1

J , 49 bajtów

f=.3 :'''|-''{~((,.[:|.[:|."1[:|:-.)@,~)^:y,:0 1'

Niezdarne tłumaczenie rozwiązania APL firmy ngn. Miałem problemy z dorozumieniem - docenię każdą radę.

Wypróbuj online!

Galen Iwanow
źródło
1

Węgiel drzewny , 47 46 bajtów

M²↖|-¶¶FENX²ι«F²C±ι⁰C⁰ιC⊗ι±ιC׳ι±ι≦⊗ιM±ι±ιT⊗ιι

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

M²↖|-¶¶

Aby uzyskać spójną pozycję kursora dla następnej pętli, muszę wydrukować krok 0 w pozycji (-2, -2) i pozostawić kursor w pozycji (-2, 0). (Może to być spowodowane błędem w Charcoal.)

FENX²ι«

Pętla nad pierwszymi Npotęgami 2.

F²C±ι⁰C⁰ιC⊗ι±ιC׳ι±ι

Wykonaj kopie poprzedniego wydruku z różnymi przesunięciami, w wyniku czego płótno zawiera żądany następny krok w prostokącie.

≦⊗ιM±ι±ιT⊗ιι

Przejdź do pozycji tego prostokąta i przytnij płótno.

Alternatywne rozwiązanie, również 46 bajtów:

M²→|-FENX²ι«F432C×Iκι׳ιF245C×Iκι⊗ι≦⊗ιJ⊗ιιT⊗ιι

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

M²→|-

Ten krok czasowy 0 musi być wydrukowany w pozycji (2, 0), ale przynajmniej pozycja kursora nie ma znaczenia.

FENX²ι«

Pętla nad pierwszymi Npotęgami 2.

F432C×Iκι׳ιF245C×Iκι⊗ι

Wykonaj kopie poprzedniego wydruku z różnymi przesunięciami, w wyniku czego płótno zawiera żądany następny krok w prostokącie.

≦⊗ιJ⊗ιιT⊗ιι

Przejdź do pozycji tego prostokąta i przytnij płótno.

Neil
źródło
1

R , 126 bajtów

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}

Wypróbuj online!

Zwraca a matrix. W linku TIO jest trochę kodu, który pozwala ładnie wydrukować i ułatwić weryfikację.

Giuseppe
źródło
110
Robin Ryder