ABAA / ABBB: Generieren Sie dieses rekursive 2D-Muster

30

Ich habe mit unendlichen Widerstandsnetzwerken herumgespielt (lange Geschichte), als ich auf folgendes interessantes rekursives Muster stieß:

|-||
|---

Jedes Exemplar dieses Musters ist doppelt so breit wie hoch. Um von einer Ebene des Musters zur nächsten zu gelangen, zerlegen Sie dieses Rechteck in zwei Unterblöcke (von denen jeder ein NxN-Quadrat ist):

AB =
|-||
|---

so A = 
|-
|-

and B = 
||
--

Diese Hälften werden dann dupliziert und nach folgendem Muster neu angeordnet:

ABAA
ABBB

giving

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

Herausforderung

Schreiben Sie ein Programm / eine Funktion, die unter Angabe einer Zahl Ndie NIteration dieses rekursiven Entwurfs ausgibt . Das ist Golf.

Das E / A-Format ist relativ nachgiebig: Sie können eine einzelne Zeichenfolge, eine Liste von Zeichenfolgen, ein 2D-Array von Zeichen usw. zurückgeben. Beliebig nachgestellte Leerzeichen sind zulässig. Sie können auch die Indexierung 0 oder 1 verwenden.

Beispiele

Die ersten Iterationen des Musters lauten wie folgt:

N = 0
|-

N = 1
|-||
|---

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

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

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

Ich frage mich, ob es eine kurze algebraische Methode gibt, um diese Struktur zu berechnen.

PhiNotPi
quelle
Was meinst du mit "algebraisch"?
user202729
4
@ user202729 Vielleicht gibt es eine "einfache" mathematische Formel, mit f(n,x,y)der direkt berechnet werden kann, ob eine bestimmte Koordinate enthalten soll -oder nicht |. Es kann sich um Modulo-Operationen oder bitweise Operationen handeln. Die Techniken, die ich bisher gesehen habe, umfassen alle das Schneiden / Verbinden von Arrays, wie in der Spezifikation gezeigt.
PhiNotPi
3
f(x,y)funktioniert auch, da wenn x,ygültig, dann das Ergebnis nicht abhängtn
amara
2
Kann der Ausgang 1-indiziert sein, dh Eingang 1 geben |-?
Zgarb
2
Ist das ein Verlust? 🤔
qwr

Antworten:

13

APL (Dyalog Classic) , 29 25 Bytes

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

Probieren Sie es online!

⍳2 ist der Vektor 0 1

verwandelt es in eine 2x1 Matrix

transponiert es, so wird es 1x2

ausgewertete Eingabe

{ }⍣⎕ wende eine Funktion so oft an

⍪⍨⍵ Verketten Sie das Argument auf sich selbst - eine 2x2-Matrix

a← erinnere mich als a

~ negieren

transponieren

horizontal umkehren

vertikal umkehren

a,verketten mit aauf der linken Seite

'|-'[ ]Verwenden Sie die Matrix als Indizes in der Zeichenfolge '|-', dh drehen Sie 0 in |und 1 in-

ngn
quelle
10

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

Golf von meiner alternativen Methode und die Festsetzung der Zeichen, -14 Bytes Danke @ 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="|-"

Probieren Sie es online!

Mein ursprünglicher Ansatz ( 106 102 Bytes)

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 Bytes Danke @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`
`:"|-"

Probieren Sie es online!

Erklärung & Ungolfed:

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

Meine ursprüngliche alternative Methode, falls "|"->"2", "-"->"1"zulässig, 105 bis 104 Byte:

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"

Probieren Sie es online!

Ich habe gerade eine algebraische Methode für dieses Problem herausgefunden.

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]

Probieren Sie es online!

(Endlich eine Funktion, deren Länge mit meiner ursprünglichen Antwort vergleichbar ist)

f(n, x, y)berechnet den Blocktyp am (x, y) Block bei nder Iteration der folgenden Ersetzung:

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

woher 0 = "|-", 1 = "||", 2 = "--", ausgehend von f(0, 0, 0) = 0.

Dann g(x)(y)berechnet das Symbol bei (x, y) des ursprünglichen Muster.

Shieru Asakoto
quelle
102 Bytes für Ihre erste Lösung.
Shaggy
88 Bytes für Ihre Sekunde.
Shaggy
1
Ihre zweite Lösung sollte mit den richtigen Zeichen für 95 Bytes arbeiten
Shaggy
^ 94 Bytes
Shaggy
92 Bytes
Shaggy
9

Stax , 24 17 15 Bytes

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

Führen Sie es aus und debuggen Sie es

Hier ist die ASCII-Darstellung des gleichen Programms.

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

Die Grundidee ist, mit dem Gitter der Generation 0 zu beginnen und dann einen Block zu wiederholen, der das Gitter erweitert.

'|'-                    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
rekursiv
quelle
8

Canvas , 17 16 Bytes

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

Probieren Sie es hier aus!

Erklärung, die den Stack für die Eingabe von 1 zeigt:

|∙-               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       "|-||¶|---"

Auf 16 Bytes aktualisiert, indem ein Fehler behoben wurde, bei dem die für α/ ωto work festgelegten Werte nicht richtig kopiert wurden (Canvas soll vollständig unveränderlich sein, war es aber leider nicht).

dzaima
quelle
6

Python 2 , 88 77 Bytes

-11 Bytes als 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)]

Probieren Sie es online!

Stange
quelle
Sie können diese Listenverständnisse für 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 Bytes

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

Probieren Sie es online!

Xcali
quelle
1
Optimiert auf 66: $.=map{s/.{$.}$/$&$$ /,push@1,$. $ & X3} @ 1für (@ 1 = "| -") x <>; sagen wir für @ 1`
Ton Hospel
4

Schale , 17 Bytes

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

1-indiziert. Probieren Sie es online!

Erläuterung

!¡§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
quelle
3

Jelly , 21 bis 19 Bytes

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

Probieren Sie es online!


Erläuterung:

Der Wert ist anfangs ⁾|-also ["|","-"].

Der letzte angegebene link ( Ç) [A, B]wird zurückgegeben

   AB     AA
[  AB  ,  BB  ]

. Die ¡letzte Verknüpfung (Eingabe) wird wiederholt angewendet und ZYformatiert.

Erklärung für den letzten Link:

-----------------
;"/;`,Ẏ;`€$  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)
user202729
quelle
2

Haskell , 86 Bytes

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

Probieren Sie es online!

Ziemlich einfach. Die Ausgabe ist eine Liste von Zeichenfolgen. Wir nehmen die vorherige Version und teilen jede Zeile in zwei Hälften, dann sammeln wir diese mit in zwei neue Listen unzip. Dann geht es einfach darum, die Arrays richtig zu kombinieren

user1472751
quelle
1

J , 49 Bytes

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

Eine ungeschickte Übersetzung der APL-Lösung von ngn. Ich hatte Probleme, es stillschweigend zu machen - ich werde jeden Rat zu schätzen wissen.

Probieren Sie es online!

Galen Ivanov
quelle
1

Kohle , 47 46 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

M²↖|-¶¶

Um eine konsistente Cursorposition für die folgende Schleife zu erhalten, muss Schritt 0 an Position (-2, -2) gedruckt und der Cursor an Position (-2, 0) belassen werden. (Dies könnte an einem Fehler in Charcoal liegen.)

FENX²ι«

Schleife über die ersten NPotenzen von 2.

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

Erstellen Sie Kopien der vorherigen Ausgabe mit verschiedenen Offsets, sodass eine Zeichenfläche entsteht, die den gewünschten nächsten Schritt in einem Rechteck enthält.

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

Bewegen Sie sich an die Position dieses Rechtecks ​​und schneiden Sie die Leinwand.

Alternative Lösung, auch 46 Bytes:

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

M²→|-

Dieser Zeitschritt 0 muss an Position (2, 0) gedruckt werden, aber zumindest die Cursorposition spielt keine Rolle.

FENX²ι«

Schleife über die ersten NPotenzen von 2.

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

Erstellen Sie Kopien der vorherigen Ausgabe mit verschiedenen Offsets, sodass eine Zeichenfläche entsteht, die den gewünschten nächsten Schritt in einem Rechteck enthält.

≦⊗ιJ⊗ιιT⊗ιι

Bewegen Sie sich an die Position dieses Rechtecks ​​und schneiden Sie die Leinwand.

Neil
quelle
1

R , 126 Bytes

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}

Probieren Sie es online!

Gibt a zurück matrix. Der TIO-Link enthält ein bisschen Code, damit er gut gedruckt werden kann, um die Überprüfung zu vereinfachen.

Giuseppe
quelle
110
Robin Ryder