30
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What do you mean by "algebraic"? \$\endgroup\$ – user202729 Feb 9 '18 at 4:27
  • 4
    \$\begingroup\$ @user202729 Like maybe there's some "simple" math formula f(n,x,y) which can directly calculate whether a given coordinate should contain - or |. It might involve modulo operations or bitwise operations. The techniques I've seen so far all involve cutting/joining arrays as shown in the spec. \$\endgroup\$ – PhiNotPi Feb 9 '18 at 4:35
  • 3
    \$\begingroup\$ f(x,y) also works, since if x,y is valid then the result doesn't depend on n \$\endgroup\$ – amara Feb 9 '18 at 4:47
  • 2
    \$\begingroup\$ Can the output be 1-indexed, i.e. input 1 giving |-? \$\endgroup\$ – Zgarb Feb 9 '18 at 11:19
  • 2
    \$\begingroup\$ Is this loss? 🤔 \$\endgroup\$ – qwr Apr 27 '18 at 15:11

15 Answers 15

13
\$\begingroup\$

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 -

\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 102 bytes for your first solution. \$\endgroup\$ – Shaggy Feb 9 '18 at 9:39
  • \$\begingroup\$ 88 bytes for your second. \$\endgroup\$ – Shaggy Feb 9 '18 at 9:41
  • 1
    \$\begingroup\$ Got your second solution working with the correct characters for 95 bytes \$\endgroup\$ – Shaggy Feb 9 '18 at 9:55
  • \$\begingroup\$ ^ 94 bytes \$\endgroup\$ – Shaggy Feb 9 '18 at 10:10
  • \$\begingroup\$ 92 bytes \$\endgroup\$ – Shaggy Apr 26 '18 at 23:30
9
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ You can roll those list comprehensions together for 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)] \$\endgroup\$ – Lynn Feb 9 '18 at 13:24
4
\$\begingroup\$

Perl 5, 72 bytes

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Optimized to 66: $.=map{s/.{$.}$/$&$$/,push@1,$.$&x3}@1for(@1="|-")x<>;say for@1` \$\endgroup\$ – Ton Hospel Feb 11 '18 at 16:34
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 47 46 bytes

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

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

M²↖|-¶¶

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

FENX²ι«

Loop over the first N powers of 2.

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

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

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

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

Alternative solution, also 46 bytes:

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

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

M²→|-

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

FENX²ι«

Loop over the first N powers of 2.

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

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

≦⊗ιJ⊗ιιT⊗ιι

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 25 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.