ABAA/ABBB: Generate this recursive 2D pattern

Question

I was messing around with infinite resistor networks (long story) when I came across the following interesting recursive pattern:

|-||
|---

Each instance of this pattern is twice as wide as it is tall. To go from one level of the pattern to the next, you break up this rectangle into two sub-blocks (each of which is a NxN square):

AB =
|-||
|---

so A = 
|-
|-

and B = 
||
--

These halves are then duplicated and rearranged according to the following pattern:

ABAA
ABBB

giving

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

Challenge

Write a program/function which, given a number N, outputs the Nth iteration of this recursive design. This is golf.

I/O format is relatively lenient: you may return a single string, a list of strings, a 2D array of characters, etc. Arbitrary trailing whitespace is allowed. You may also use either 0 or 1 indexing.

Examples

The first several iterations of the pattern are as follows:

N = 0
|-

N = 1
|-||
|---

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

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

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

I wonder if there is some short algebraic way to compute this structure.

Answer 1

APL (Dyalog Classic), 29 25 bytes

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

Try it online!

⍳2 is the vector 0 1

⍪ turns it into a 2x1 matrix

⍉ transposes it, so it becomes 1x2

⎕ evaluated input

{ }⍣⎕ apply a function that many times

⍪⍨⍵ concatenate the argument on top of itself - a 2x2 matrix

a← remember as a

~ negate

⍉ transpose

⌽ reverse horizontally

⊖ reverse vertically

a, concatenate with a on the left

'|-'[ ] use the matrix as indices in the string '|-', i.e. turn 0 into | and 1 into -

Answer 2

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

Golfed from my alternative method and fixing the characters, -14 bytes Thanks @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="|-"

Try it online!

My original approach (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 Thanks @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`
`:"|-"

Try it online!

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

My original alternative method, if "|"->"2", "-"->"1" is allowed, 105 104 bytes:

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"

Try it online!

Just figured out some algebraic method towards this problem.

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]

Try it online!

(finally a function which length's comparable to my original answer)

f(n, x, y) calculates the block type at (x, y) block at nth iteration of the following substitution:

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

where 0 = "|-", 1 = "||", 2 = "--", starting from f(0, 0, 0) = 0.

Then, g(x)(y) calculates the symbol at (x, y) of the original pattern.

Answer 3

Stax, 24 17 15 bytes

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

Run and debug it

Here's the ascii representation of the same program.

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

The basic idea is start with the 0-generation grid, and then repeat a block that expands the grid.

'|'-                    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

Answer 4

Canvas, 17 16 bytes

|∙-╶［∔αω＋：∔；：＋｝＋

Try it here!

Explanation, showing the stack for the input of 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       "|-||¶|---"

Updated to 16 bytes by fixing a bug where the values set for α/ω to work weren't copied properly (Canvas is supposed to be fully immutable, but, alas, it wasn't).

Answer 5

Python 2, 88 77 bytes

^{-11 bytes thansk to 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)]

Try it online!

Answer 6

Perl 5, 72 bytes

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

Try it online!

Answer 7

Husk, 17 bytes

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

1-indexed. Try it online!

Explanation

!¡§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.

Answer 8

Jelly, 21 19 bytes

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

Try it online!

---

Explanation:

Initially, the value is ⁾|-, that is ["|","-"].

The last link (Ç), given [A, B], will return

   AB     AA
[  AB  ,  BB  ]

. The ¡ repeatedly apply the last link (input) number of times, and ZY formats it.

Explanation for last 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)

Answer 9

Clean, 121 106 bytes

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]

Try it online!

Answer 10

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

Try it online!

Pretty simple. Output is a list of strings. We take the previous version and split each line in half then collect those into two new lists using unzip. Then it's simply a matter of combining the arrays together the right way

Answer 11

Charcoal, 47 46 bytes

Ｍ²↖|-¶¶ＦＥＮＸ²ι«Ｆ²Ｃ±ι⁰Ｃ⁰ιＣ⊗ι±ιＣ׳ι±ι≦⊗ιＭ±ι±ιＴ⊗ιι

Try it online! Link is to verbose version of code. Explanation:

Ｍ²↖|-¶¶

In order to get a consistent cursor position for the following loop, I have to print step 0 at position (-2, -2) and leave the cursor at (-2, 0). (This might be due to a bug in Charcoal.)

ＦＥＮＸ²ι«

Loop over the first N powers of 2.

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

Make copies of the previous output with various offsets resulting in a canvas that contains the desired next step in a rectangle within it.

≦⊗ιＭ±ι±ιＴ⊗ιι

Move to the position of that rectangle and trim the canvas.

Alternative solution, also 46 bytes:

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

Try it online! Link is to verbose version of code. Explanation:

Ｍ²→|-

This time step 0 has to be printed at position (2, 0), but at least the cursor position doesn't matter.

ＦＥＮＸ²ι«

Loop over the first N powers of 2.

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

Make copies of the previous output with various offsets resulting in a canvas that contains the desired next step in a rectangle within it.

≦⊗ιＪ⊗ιιＴ⊗ιι

Move to the position of that rectangle and trim the canvas.

Answer 12

J, 49 bytes

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

A clumsy translation of ngn's APL solution. I had problems making it tacit - I'll apreciate any advice.

Try it online!

Answer 13

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}

Try it online!

Returns a matrix. There's a bit of code in the TIO link to get it to print nicely for ease of verification.

Answer 14

K (ngn/k), 25 bytes

{"|-"x{x,'|+|~x:x,x}/,!2}

Try it online!

Answer 15

Wolfram Language (Mathematica), 67 65 bytes

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

Try it online!

Straightforward implementation of the recursion. Returns an array of characters wrapped in a list.