ABAA / ABBB: genera este patrón 2D recursivo

30

Estaba jugando con redes de resistencia infinita (larga historia) cuando me encontré con el siguiente patrón recursivo interesante:

|-||
|---

Cada instancia de este patrón es dos veces más ancha que alta. Para pasar de un nivel del patrón al siguiente, divide este rectángulo en dos subbloques (cada uno de los cuales es un cuadrado NxN):

AB =
|-||
|---

so A = 
|-
|-

and B = 
||
--

Estas mitades se duplican y reorganizan de acuerdo con el siguiente patrón:

ABAA
ABBB

giving

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

Reto

Escriba un programa / función que, dado un número N, produzca la Niteración de este diseño recursivo. Esto es golf.

El formato de E / S es relativamente indulgente: puede devolver una sola cadena, una lista de cadenas, una matriz 2D de caracteres, etc. Se permite un espacio en blanco al final arbitrario. También puede usar 0 o 1 indexación.

Ejemplos

Las primeras varias iteraciones del patrón son las siguientes:

N = 0
|-

N = 1
|-||
|---

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

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

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

Me pregunto si hay alguna forma algebraica corta de calcular esta estructura.

PhiNotPi
fuente
¿Qué quieres decir con "algebraico"?
user202729
44
@ user202729 Como tal vez hay alguna fórmula matemática "simple" f(n,x,y)que puede calcular directamente si una determinada coordenada debe contener -o |. Puede implicar operaciones de módulo u operaciones bit a bit. Las técnicas que he visto hasta ahora implican cortar / unir matrices como se muestra en la especificación.
PhiNotPi
3
f(x,y)también funciona, ya que si x,yes válido, entonces el resultado no depende den
amara
2
¿Se puede indexar la salida 1, es decir, dar entrada 1 |-?
Zgarb
2
¿Es esta pérdida? 🤔
qwr

Respuestas:

13

APL (Dyalog Classic) , 29 25 bytes

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

Pruébalo en línea!

⍳2 es el vector 0 1

lo convierte en una matriz 2x1

lo transpone, por lo que se convierte en 1x2

entrada evaluada

{ }⍣⎕ aplicar una función que muchas veces

⍪⍨⍵ concatenar el argumento encima de sí mismo: una matriz de 2x2

a← recuerda como a

~ negar

transponer

revertir horizontalmente

revertir verticalmente

a,concatenar con aa la izquierda

'|-'[ ]usa la matriz como índices en la cadena '|-', es decir, convierte 0 en |y 1 en-

ngn
fuente
10

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

Golfé desde mi método alternativo y arreglé los caracteres, -14 bytes Gracias @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="|-"

Pruébalo en línea!

Mi enfoque original ( 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 Gracias @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`
`:"|-"

Pruébalo en línea!

Explicación y sin golf:

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

Mi método alternativo original, si "|"->"2", "-"->"1"está permitido, 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"

Pruébalo en línea!

Acabo de descubrir algún método algebraico para este problema.

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]

Pruébalo en línea!

(Finalmente una función cuya longitud es comparable a mi respuesta original)

f(n, x, y)calcula el tipo de bloque en el bloque (x, y) en nla iteración de la siguiente sustitución:

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

de donde 0 = "|-", 1 = "||", 2 = "--", a partir de f(0, 0, 0) = 0.

Luego, g(x)(y)calcula el símbolo en (x, y) del patrón original.

Shieru Asakoto
fuente
102 bytes para su primera solución.
Shaggy
88 bytes para su segundo.
Shaggy
1
Tu segunda solución funciona con los caracteres correctos para 95 bytes
Shaggy
^ 94 bytes
Shaggy
92 bytes
Shaggy
9

Stax , 24 17 15 bytes

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

Ejecutar y depurarlo

Aquí está la representación ascii del mismo programa.

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

La idea básica es comenzar con la cuadrícula de generación 0 y luego repetir un bloque que expande la cuadrícula.

'|'-                    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
recursivo
fuente
8

Lienzo , 17 16 bytes

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

Pruébalo aquí!

Explicación, que muestra la pila para la entrada de 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       "|-||¶|---"

Se actualizó a 16 bytes corrigiendo un error en el que los valores establecidos para α/ ωpara trabajar no se copiaron correctamente (se supone que Canvas es totalmente inmutable, pero, por desgracia, no lo fue).

dzaima
fuente
6

Python 2 , 88 77 bytes

-11 bytes thansk a 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)]

Pruébalo en línea!

Barra
fuente
Puede agrupar esas comprensiones de listas para 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

Pruébalo en línea!

Xcali
fuente
1
Optimizado para 66: $.=map{s/.{$.}$/$&$$ /,push@1,$. $ & X3} @ 1for (@ 1 = "| -") x <>; digamos para @ 1`
Ton Hospel
4

Casco , 17 bytes

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

1 indexado. Pruébalo en línea!

Explicación

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

Jalea , 21 19 bytes

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

Pruébalo en línea!


Explicación:

Inicialmente, el valor es ⁾|-, es decir ["|","-"].

El último enlace ( Ç), dado [A, B], regresará

   AB     AA
[  AB  ,  BB  ]

. El ¡aplican repetidamente el último número de enlace (entrada) de veces, y ZYlo formatea.

Explicación del último enlace:

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

Limpio , 121106 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]

Pruébalo en línea!

Οurous
fuente
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

Pruébalo en línea!

Bastante simple. La salida es una lista de cadenas. Tomamos la versión anterior y dividimos cada línea por la mitad, luego las recopilamos en dos listas nuevas usando unzip. Entonces es simplemente una cuestión de combinar las matrices juntas de la manera correcta

usuario1472751
fuente
1

J , 49 bytes

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

Una traducción torpe de la solución APL de ngn. Tuve problemas para hacerlo tácito. Apreciaré cualquier consejo.

Pruébalo en línea!

Galen Ivanov
fuente
1

Carbón , 47 46 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

M²↖|-¶¶

Para obtener una posición consistente del cursor para el siguiente ciclo, tengo que imprimir el paso 0 en la posición (-2, -2) y dejar el cursor en (-2, 0). (Esto podría deberse a un error en el carbón).

FENX²ι«

Recorre los primeros Npoderes de 2.

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

Haga copias de la salida anterior con varios desplazamientos que den como resultado un lienzo que contenga el siguiente paso deseado en un rectángulo dentro de él.

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

Muévase a la posición de ese rectángulo y recorte el lienzo.

Solución alternativa, también 46 bytes:

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

M²→|-

Esta vez, el paso 0 debe imprimirse en la posición (2, 0), pero al menos la posición del cursor no importa.

FENX²ι«

Recorre los primeros Npoderes de 2.

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

Haga copias de la salida anterior con varios desplazamientos que den como resultado un lienzo que contenga el siguiente paso deseado en un rectángulo dentro de él.

≦⊗ιJ⊗ιιT⊗ιι

Muévase a la posición de ese rectángulo y recorte el lienzo.

Neil
fuente
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}

Pruébalo en línea!

Devuelve a matrix. Hay un poco de código en el enlace TIO para que se imprima bien y facilitar la verificación.

Giuseppe
fuente
110
Robin Ryder