Una matriz de desafíos # 2: separar una matriz anidada

36

Nota: Este es el # 2 en una serie de desafíos de de . Para el desafío anterior, haga clic aquí .

Separar listas anidadas

Para separar los valores en una lista anidada, aplánelo y luego ajuste cada valor para que tenga la misma profundidad anidada que antes.

Es decir, esta lista:

[1, [2, 3], [4, 4, [5, 2], 1]]

Se convertiría:

[1, [2], [3], [4], [4], [[5]], [[2]], [1]]

El reto

Su tarea es escribir un programa que tome cualquier lista anidada de enteros positivos (dentro de los límites de su idioma) y realice esta operación de separación.

Puede enviar una función que tome la lista como argumento o un programa completo que realice E / S.

Como se trata de , ¡el envío más corto (en bytes) gana! *

* Las lagunas de golf estándar están prohibidas. Ya sabes que hacer.


Casos de prueba

Las listas de entrada solo contendrán enteros en el tamaño entero estándar de su idioma. Para evitar las restricciones de los idiomas que les impiden competir, los valores no se anidarán a profundidades de más de 10.

Puede suponer que la entrada no tendrá sublistas vacías: por ejemplo [[5, []]], no se dará. Sin embargo, la lista principal podría estar vacía.

[]            ->  []

[[1, 2]]      ->  [[1], [2]]
[3, [4, 5]]   ->  [3, [4], [5]]
[3, [3, [3]]] ->  [3, [3], [[3]]]
[[6, [[7]]]]  ->  [[6], [[[7]]]]
[[5, 10], 11] ->  [[5], [10], 11]

No dude en dejar un comentario si me he perdido un caso de esquina.

Ejemplo

Tiré juntos una solución rápida Python (ungolfed) 3 como ejemplo - se puede probarlo en repl.it .

FlipTack
fuente
Agregue un caso de prueba con números mayores que un solo dígito para respuestas basadas en cadenas.
orlp
@orlp buena idea.
FlipTack
2
¿Podemos asumir una cierta profundidad máxima? Digamos 16?
orlp
@orlp Voy a decir que sí, la profundidad máxima anidada será 10, ya que estoy más interesado en la ejecución de su algoritmo y método que las restricciones de su idioma. Actualizará el hilo ahora.
FlipTack
¿Puedo mostrar como una cadena?
Rohan Jhunjhunwala

Respuestas:

4

Brachylog , 16 bytes

:{##:0&:ga|g}ac|

Pruébalo en línea!

Explicación

Example input: [1:[2:3]]

:{          }a     Apply the predicate below to each element of the list: [[1]:[[2]:[3]]]
              c    Concatenate: Output = [1:[2]:[3]]
               |   Or: Input = Output = []

  ##                 Input is a list: e.g. Input = [2:3]
    :0&              Call recursively the main predicate with this input: [2:3]
       :ga           Group each element in a list: Output = [[2]:[3]]
          |          Or (not a list): e.g. Input = 1
           g         Group into a list: Output = [1]
Fatalizar
fuente
¿Qué hace el Zargumento sobre TIO? Sin él, esto parece salir con verdadero / falso, lo que hace que parezca Znecesario en el recuento de bytes.
FlipTack
@FlipTack Zle dice a Brachylog que el argumento de salida es una variable. Esta es esta variable que se unifica con la salida resultante. Cuando lo elimina, le indica a Brachylog que la salida es una variable anónima y, en cambio, imprimirá si el predicado principal tiene éxito o falla. Esto es lo mismo que en Prolog, donde el resultado se "pone" en una variable.
Fatalize
Ok :) buena respuesta!
FlipTack
19

Mathematica, 24 21 bytes

##&@@List/@#0/@#&/@#&

o uno de estos:

##&@@List/@#&/@#0/@#&
##&@@List@*#0/@#&/@#&
##&@@List/@#&@*#0/@#&

Explicación

La razón por la que esto es tan breve es que es básicamente una recursión que no requiere un caso base explícito.

Aquí hay mucha azúcar sintáctica, así que comencemos por desvelar esto. &denota una función sin nombre a la izquierda, cuyo argumento se escribe como #. Dentro de esta función se #0refiere a la función misma, que le permite a uno escribir funciones recursivas sin nombre. Pero comencemos dando un nombre a la función interna y sacándola:

f[x_] := ##& @@ List /@ f /@ x
f /@ # &

El otro azúcar sintáctico importante es el f/@xque es la abreviatura de, Map[f, x]es decir, invoca ftodos los elementos de x. La razón f[x_] := ... f /@ xno conduce a una recursión infinita es que mapear algo sobre un átomo deja el átomo sin cambios sin realmente llamar a la función. Por lo tanto, no necesitamos verificar el caso base (el elemento actual es un entero) explícitamente.

Entonces, la función frecurre primero a la lista más profunda dentro x, en cuyo punto se f/@convierte en un no-op. Luego llamamos al uso ##& @@ List /@de eso. La asignación Listsobre la lista simplemente envuelve cada elemento en una lista separada, por lo que se {1, 2, 3}convierte {{1}, {2}, {3}}. Luego lo aplicamos ##& , lo que significa que la cabeza (es decir, la lista externa) se reemplaza por ##&, por lo que esto se convierte en ##&[{1}, {2}, {3}]. Pero ##&simplemente devuelve sus argumentos como un Sequence(que se puede considerar como una lista sin envolver, o una especie de operador "splat" en otros idiomas).

Por lo tanto, ##& @@ List /@convierte una lista {1, 2, 3}en {1}, {2}, {3}(más o menos, esa última cosa está realmente envuelta en la cabeza Sequence, pero desaparece tan pronto como usamos el valor en cualquier lugar).

Eso deja la pregunta de por qué fya no es la solución al desafío. El problema es que la lista más externa debe tratarse de manera diferente. Si tenemos aportes {{1, 2}, {3, 4}}queremos {{1}, {2}, {3}, {4}}y no {{1}}, {{2}}, {{3}}, {{4}} . Mi solución original fijado esto pasando el resultado final como una lista de argumentos para Joinque restaurar el nivel externo de las listas, pero éste sólo se salta el nivel externo mediante el uso de f sí mismo en un mapa en la salida. Por flo tanto, solo se aplica a los elementos individuales de la lista más externa y nunca toca esa lista.

En cuanto a las otras tres soluciones, la primera simplemente aplica la recursión fuera de la fcual funciona igual de bien. Las otras dos soluciones evitan una Mapoperación repetida componiendo primero dos funciones y luego mapeando el resultado solo una vez.

Martin Ender
fuente
8

J , 19 18 bytes

(<@]/@,~>)S:0 1{::

Este es un verbo anónimo que toma y devuelve matrices en caja, que son la versión J (bastante engorrosa) de matrices anidadas. Véalo pasar todos los casos de prueba.

Explicación

Esto utiliza las operaciones algo exóticas {::( mapa ) y S:( propagación ), que operan en matrices en caja. {::reemplaza cada hoja con el camino encuadrado a esa hoja. S:aplica un verbo dado a una profundidad de anidamiento dada, luego divide los resultados en una matriz.

(<@]/@,~>)S:0 1{::  Input is y.
(        )          Let's look at this verb first.
        >           Open the right argument,
      ,~            append the left argument to it,
    /               then reduce by
 <@]                boxing. This puts the left argument into as many nested boxes
                    as the right argument is long.
                    This verb is applied to y
               {::  and its map
            0 1     at levels 0 and 1.
                    This means that each leaf of y is paired with its path,
                    whose length happens to be the nesting depth of y,
                    and the auxiliary verb is applied to them.
          S:        The results are spread into an array.
Zgarb
fuente
3

R, 199 bytes

function(l){y=unlist(l);f=function(x,d=0){lapply(x,function(y){if(class(y)=='list'){f(y,d=d+1)}else{d}})};d=unlist(f(l));lapply(1:length(d),function(w){q=y[w];if(d[w]){for(i in 1:d[w])q=list(q)};q})}

Esta pregunta fue DURA. Las listas de R son un poco extrañas y no es absolutamente sencillo recorrer todos los elementos de las sublistas. Tampoco es sencillo determinar la profundidad de esa lista. Luego, el desafío es recrear la lista con todos los elementos separados, por lo que también necesitamos una forma de crear adaptativamente una lista de cierta profundidad.

La solución consta de dos grandes partes. Una función recursiva que recorre todas las listas y registra la profundidad:

  f=function(x,d=0){
    lapply(x,function(y){
      if(class(y)=='list'){
        f(y,d=d+1)
      } else {
        d
      }})
  }

Cuando tenemos las profundidades de cada entrada del vector unlist(l), almacenadas d, creamos implícitamente una lista lapplyy la llenamos con la siguiente función:

  lapply(1:length(d),function(w){
    q=y[w]
    if(d[w]){
      for(i in 1:d[w]){
        q=list(q)
      }
    }
    q
  })

En esta llamada de solicitud, creamos un objeto qcon el valor de la entrada en la lista, verificamos su profundidad y vemos si no es cero. Si es cero, podemos dejarlo como un valor numérico. Si no es cero, debemos anidarlo en esa cantidad de listas. Entonces llamamos a dtiempos for-loop y repetidamente llamamos q=list(q).

lapplyluego pone todos estos valores qen una lista, creando la salida deseada.

Programa completo con espaciado adecuado y tal:

function(our.list){
  values <- unlist(our.list)
  f <- function(part.list, depth = 0){
    lapply(part.list, function(y){
      if(class(y)=='list'){
        f(y, depth <- depth + 1)
      } else {
        return(depth)
      }})
  }
  depths <- unlist(f(our.list))
  new.list <- lapply(1:length(depths), function(w){
    q <- values[w]
    if(depths[w] != 0){
      for(i in 1:depths[w]){
        q <- list(q)
      }
    }
    return(q)
  })
  return(new.list)
}
JAD
fuente
Bonito, este es el método que utilicé con mi solución inicial de Python para los casos de prueba :)
FlipTack
is.list(y)en lugar de class(y)=='list'? no puedo verificar que eso realmente funcione.
Giuseppe
180 bytes
Giuseppe
3

Retina , 34 bytes

+`(.(?>()\[|(?<-2>)]|.)+)\2,
$1],[

Pruébalo en línea!

Martin Ender
fuente
¿Cómo funciona el (?<-2>)trabajo?
Kritixi Lithos
@KritixiLithos Es un grupo equilibrado . Aparece de la pila de captura 2, lo que me permite realizar un seguimiento de la profundidad de anidación actual.
Martin Ender
2

C (gcc), 147 bytes

d=0,l,i;
P(n,c){for(;n--;)putchar(c);}
main(c){for(;~(c=getchar());l=i)i=isdigit(c),P((l<i)*d,91),P(i,c),P((l>i)*d,93),P(l>i,32),d+=(92-c)*(c>90);}

Entrada de ejemplo:

1 [23 3] [40 4 [5 2] 1]

Salida de ejemplo:

1 [23] [3] [40] [4] [[5]] [[2]] [1]
orlp
fuente
2

apilada , no competitiva, 25 bytes

{e d:e$wrap d 1-*}cellmap

Esta es una función porque modifica el miembro superior de la pila. Si desea una función de buena fe, simplemente agregue [y ]al principio y al final. Pruébalo aquí!

Aquí hay una versión legible:

{ arr :
  arr { ele depth :
    ele   $wrap depth 1- * (* execute wrap n times, according to the depth *)
  } cellmap (* apply to each cell, then collect the results in an array *)
} @:a2
(1 (2 3) (4 4 (5 2) 1)) a2 out

Caso de prueba:

(1 (2 3) (4 4 (5 2) 1))    (* arg on TOS *)
{e d:e$wrap d 1-*}cellmap
out                        (* display TOS *)

Salida sin líneas nuevas:

(1 (2) (3) (4) (4) ((5)) ((2)) (1))
Conor O'Brien
fuente
¿Es *como argumento para bloquear el código?
Downgoat
@Downgoat en este caso envuelve los d-1tiempos de discusión . $funcEs una función que puede ser manipulada.
Conor O'Brien
2

PHP, 101 94 bytes

ahorré 1 byte gracias a @Christoph, salvé otros 6 inspirados por eso.

function s($a){foreach($a as$b)if($b[0])foreach(s($b)as$c)$r[]=[$c];else$r[]=$b;return$r?:[];}

función recursiva, bastante sencilla

Descompostura

function s($a)
{
    foreach($a as$b)                // loop through array
        if($b[0])                       // if element is array
            foreach(s($b)as$c)$r[]=[$c];    // append separated elements to result
        else$r[]=$b;                    // else append element to result
    return$r?:[];                   // return result, empty array for empty input
}
Titus
fuente
¿Dónde se inicializa el resultado?
Neil
@Neil: PHP no requiere una inicialización explícita. O $robtiene elementos en el bucle o la función devuelve una matriz vacía. Puede generar avisos, pero estos no se imprimen con la configuración predeterminada.
Titus
¿No significa eso que solo podrás llamarlo una vez?
Neil
1
Es lo mismo que volverse locos: !cos(). cos()devuelve nullpara cada matriz y un flotante! = 0 para cada entero positivo. Quiero decir ... ¿a quién le importan las advertencias?
Christoph
1
@ Christoph: las advertencias se imprimen, los avisos no (en la configuración predeterminada). ¡Pero es una gran idea! On is_int: invertir la condición no guarda nada; Necesito un espacio entre elsey foreach. PERO: $b[0]para un entero es NULL.
Titus
2

Python 2, 122106 bytes

Puntaje bastante terrible, solo una implementación sencilla.

¡Gracias a @Zachary T por ayudar a ahorrar 16 bytes!

def x(l,a=[],d=0):
 n=lambda b:b and[n(b-1)]or l
 if'['in`l`:[x(e,a,d+1)for e in l];return a
 else:a+=n(d)

Llame xcon un argumento para ejecutar. Por alguna razón, solo se puede ejecutar una vez.

Azul
fuente
Puede cambiar a+=[n(l,d)]a a+=n(l,d),(tenga en cuenta la coma final)
FlipTack
¿Incluso necesitas asignar t?
Zacharý
¿Funciona esto cuando lo llamas más de una vez?
Zacharý
Puede pasar na la función y eliminar el primer argumento, ya que siempre será así l.
Zacharý
repl.it/EwPz
Zacharý
2

JavaScript (Firefox 30-57), 53 bytes

f=a=>[for(e of a)for(d of e.map?f(e):[e])e.map?[d]:d]

La mejor respuesta de ES6 que tengo hasta ahora es de 76 bytes:

f=(a,r=[],d=0)=>a.map(e=>e.map?f(e,r,d+1):r.push((n=d=>d?[n(d-1)]:e)(d)))&&r
Neil
fuente
2
En ambos bloques de código, creo que omitiste el inicio f=.
Conor O'Brien
@ ConorO'Brien Una vez más ...
Neil
1

Perl 6 , 60 47 bytes

sub f{[$_~~List??|([$_] for .&f)!!$_ for |$^a]}

( Pruébelo en línea )

Explicación:

  1. [... for |$^a]: Itere sobre la matriz de entrada y construya una nueva matriz a partir de ella.
  2. $_ ~~ List ?? ... !! ...: Para cada elemento, verifique si es en sí mismo una matriz.
  3. |([$_] for .&f): Si el elemento es una matriz, aplíquele recursivamente la función, repita los elementos de la nueva matriz devuelta por esa llamada recursiva, ajuste cada elemento en una matriz propia y deslícelos en la lista externa.
  4. $_: Si el elemento no es una matriz, pásalo como está.
smls
fuente
1

Haskell, 71 bytes

data L=N Int|C[L] 
d#C l=((C .pure.d)#)=<<l
d#n=[d n]
f(C l)=C$(id#)=<<l

Nuevamente, tengo que definir mi propio tipo de lista, porque las listas nativas de Haskell no se pueden anidar arbitrariamente. Este nuevo tipo Lse puede devolver desde una función pero no se puede imprimir de forma predeterminada, por lo que para ver un resultado defino una showinstancia para L:

instance Show L where
  show (N n)=show n
  show (C l)=show l

Ahora podemos hacer alguna prueba en el REPL:

*Main> f $ C[N 1, C[N 2, N 3], C[N 4, N 4, C[N 5, N 2], N 1]]
[1,[2],[3],[4],[4],[[5]],[[2]],[1]]

*Main> f $ C[C[N 6, C[C[N 7]]]]
[[6],[[[7]]]]

Cómo funciona: una recursión simple que pasa el nivel de anidación en función de los Cconstructores. Comenzamos con la función de identidad idy cada vez que hay una lista (-> coincidencia de patrón d#C l=) agregamos una capa adicional de C(-> C .pure.d) a la llamada recursiva de #todos los elementos de la lista. Si encontramos un número, simplemente aplicamos la función de nivel de anidamiento dal número.

nimi
fuente
0

APL (Dyalog) , 44 bytes *

Función de prefijo tácito anónimo. Toma la lista APL anidada como argumento y devuelve una matriz APL anidada.

∊{⊃⊂⍣⍵,⍺}¨{⊃¨(j∊⎕D)⊆+\-'[]'∘.=j←⎕JSON⍵}

Pruébalo en línea!

{} Aplique la siguiente función explícita donde el argumento está representado por :

⎕JSON⍵ convertir el argumento a JSON

j← almacenar en j

'[]'∘.= tabla donde jes igual a los corchetes abiertos (fila superior) y cerrados (fila inferior)

-⌿ fila superior menos fila inferior (reducción de diferencia vertical)

+\ suma acumulativa (esto da el nivel de anidación para cada personaje)

(... )⊆ partición, comenzando una nueva partición siempre que un 1 no esté precedido por un 1 en ...

  j∊⎕D donde cada personaje de jes un miembro del conjunto de D igits

⊃¨ elija el primero de cada uno (esto proporciona un nivel de anidación por número de varios dígitos)

∊{...  aplique la siguiente función a cada nivel de anidamiento ( ), utilizando el elemento correspondiente del argumento ϵ nistado (aplanado) como argumento izquierdo ( ):

,⍺ descifrar (enumerar) el número (porque los escalares no se pueden encerrar)

⊂⍣⍵ adjuntar tiempos

 revelar (porque la lista más interna es en sí misma un recinto)


* Uso de Dyalog Classic con ⎕ML←3(predeterminado en muchos sistemas), sustituyendo por y para . Tio!

Adán
fuente