Un desafío simple para su lunes por la noche (bueno, o martes por la mañana en la otra mitad del mundo ...)
Se le da como entrada una matriz anidada, potencialmente desigual, de enteros positivos:
[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]
Su tarea es determinar su profundidad, que es la mayor profundidad de anidamiento de cualquier número entero en la lista. En este caso, la profundidad de 11
es 6
, que es mayor.
Puede suponer que ninguna de las matrices estará vacía.
Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).
La entrada puede tomarse en cualquier lista conveniente o formato de cadena que admita matrices no rectangulares (con matrices anidadas de diferentes profundidades), siempre que la información real no esté preprocesada.
No debe utilizar ninguna función integrada relacionada con la forma de las matrices (incluidas las integradas que resuelven este desafío, que le dan las dimensiones de una matriz anidada). La única excepción a esto es obtener la longitud de una matriz.
Aplican reglas estándar de código de golf .
Casos de prueba
[1] -> 1
[1, 2, 3] -> 1
[[1, 2, 3]] -> 2
[3, [3, [3], 3], 3] -> 3
[[[[1], 2], [3, [4]]]] -> 4
[1, [[3]], [5, 6], [[[[8]]]], 1] -> 5
[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14] -> 6
[[[[[[[3]]]]]]] -> 7
fuente
≡
es la primitiva incorporada de APL para exactamente esto .\
en las entradas? EDITAR: no importa solo lo intenté así. Eso ni siquiera funciona. Maldición, ¿no puedo usar args CMD?Respuestas:
K, 4 bytes
En K,
,/
unirá todos los elementos de una lista. El idioma común,//
itera a un punto fijo, allanando por completo una lista anidada arbitrariamente.,/\
iterará a un punto fijo de manera similar, pero reunirá una lista de resultados intermedios. Al contar cuántos resultados intermedios visitamos antes de llegar al punto fijo (#
), obtenemos la respuesta que queremos: la profundidad máxima de anidación."Conteo de unión sobre exploración de punto fijo".
En acción:
fuente
Retina , 10
Aquí el formato de entrada es un poco artificial: los
_
caracteres se usan para los separadores de listas, por lo que una entrada se vería así{1_{{2_3_{{4}_5}_6_{7_8}}_9_{10_{{{11}}}}_12_13}_14}
}{
y todos los demás\w
personajes. Esto tiene el efecto de a) hacer que todas las listas en todos los niveles consistan en un solo elemento yb) eliminar todos los caracteres no estructurales de la lista.{
. Esto proporciona el nivel más profundo de anidación.Pruébalo en línea.
Si eso es demasiado, la respuesta anterior fue:
Retina , 13
Asume que las listas están contenidas entre llaves
{}
.Pruébalo en línea .
fuente
_
lugar de,,
pero eso podría ser un poco exagerado._
separadores pueden ser demasiado artificiales. Así que dejo ambas versiones en la respuestaPython 2, 33 bytes
Define recursivamente la profundidad diciendo que la profundidad de un número es 0 y que la profundidad de una lista es uno más que la profundidad máxima de sus elementos. El número frente a la lista se verifica comparándolo con el diccionario vacío
{}
, que está por encima de los números pero debajo de las listas en el ordenamiento arbitrario de Python 2 de los tipos incorporados.fuente
Pyth -
11107 bytes1 bytes guardados gracias a @Dennis
4 bytes guardados gracias a @Thomas Kwa
Pruébelo en línea aquí .
Sigue sumando la matriz hasta que deja de cambiar, lo que significa que es solo un número, lo hace de forma acumulativa para guardar todos los resultados intermedios y obtiene longitud haciendo un urange con la misma longitud que la lista y tomando el último elemento.
fuente
m!!d
puede llegar a ser&R1
.l
no está permitido en OP.Haskell, 43 bytes
Ejemplo de uso:
maximum.scanr(#)0 $ "[1, [[3]], [5, 6], [[[[8]]]], 1]"
->5
.Haskell no tiene listas mixtas (
Integer
mezcladas conList of Integer
), por lo que no puedo explotar algunas funciones de detección de listas y tengo que analizar la cadena.Estoy comenzando por la derecha con
0
y sumo 1 por cada]
, reste 1 por cada[
y mantenga el valor de lo contrario.scanr
mantiene todos los resultados intermedios, por lo quemaximum
puede hacer su trabajo.fuente
JavaScript (ES6), 35 bytes
Explicación
Función recursiva que devuelve la profundidad máxima de una matriz, o
0
si se pasa un número.fuente
MATL , 11
14 15bytesLas llaves se usan en MATL para este tipo de matrices. De todos modos, la entrada se toma y procesa como una cadena, por lo que los corchetes podrían usarse igualmente, modificando los dos caracteres en el código.
Pruébalo en línea!
fuente
Octava, 29 bytes
Se asigna
[
a 1 y]
a -1, luego toma el máximo de la suma acumulativa.La entrada es una cadena de la forma
Ejecución de muestra en ideone .
fuente
{
,}
? La octava equivalente a las matrices en el OP son las matrices de celdas, creoJulia,
5526 bytesEsta es una función recursiva que acepta una matriz unidimensional con contenido de tipo
Any
y devuelve un entero. Al pasar una matriz a la función, prefije todos los corchetes conAny
, es decirf(Any[1,Any[2,3]])
.El enfoque es bastante simple. Para una entrada a , multiplicamos a por 0 y verificamos si el resultado es el escalar 0. Si no, sabemos que a es una matriz, por lo que aplicamos la función a cada elemento de a , tomamos el máximo y sumamos 1.
¡Ahorró 29 bytes gracias a Dennis!
fuente
Ruby, 53 bytes
Entrada de STDIN, salida a STDOUT.
fuente
Jalea,
107 bytesPruébalo en línea! o verificar todos los casos de prueba .
Cómo funciona
Actualizar
Mientras escribía esta respuesta, noté que Jelly se comporta de manera bastante extraña para las listas irregulares, porque calculé la profundidad de una lista como el mínimo incrementado de profundidades de sus elementos.
Esto se ha abordado en la última versión, por lo que el siguiente código ( 6 bytes ) funcionaría ahora.
Esto suma las filas de la matriz en lugar de concatenarlas.
fuente
ŒḊ
es más nuevo que el desafío?Mathematica, 18 bytes
fuente
Mathematica,
2720 bytesFunción recursiva simple.
fuente
If
, ahorrando 7 bytes. (Avísame si quieres una pista.)Replace
solución basada en al menos es tan larga como esta ...Map
de ping más de un número entero es un no-op:Max[#0/@#]+1&[0#]-1&
. El-1
también puede ir dentro de la llamada interna como...&[0#-1]&
.PHP, 61 bytes
función recursiva que se utiliza a sí misma como una función de mapeo para reemplazar cada elemento con su profundidad.
fuente
PHP,
8472646360 bytesNota: requiere PHP 7 para el operador de comparación combinado. También usa la codificación IBM-850
Corre así:
[
y]
$i
a un int. Las compensaciones de cadena se convierten a un int implícitamentefuente
C,
9869 bytes29 bytes de descuento gracias @DigitalTrauma !!
Toma una cadena como entrada y devuelve el resultado como entero.
Ejemplo en vivo en: http://ideone.com/IC23Bc
fuente
Python 3,
4239 bytes-3 bytes gracias a Sp3000
Esto es esencialmente un puerto de la solución Python 2 de xnor :
Desafortunadamente,
[] > {}
devuelve ununorderable types
error, por lo que ese truco inteligente particular de xnor no se puede usar. En su lugar,-0123456789
son más bajos en valor ASCII queA
, que es más bajo que[]
, por lo tanto, la comparación de cadenas funciona.fuente
CJam (15 bytes)
Demostración en línea
Disección
Por la misma longitud pero bastante más en territorio de hack feo,
fuente
s/ugly/beautiful/
'[,-
quitar la cadena[]
, lo que depende de que el contenido sea limitado. El enfoque que aplana funciona independientemente del contenido de la matriz.Sed, 40 caracteres
(Código de 39 caracteres + opción de línea de comando de 1 carácter).
Entrada: cadena, salida: número unario.
Ejecución de muestra:
Sed, 33 caracteres
(Código de 32 caracteres + opción de línea de comando de 1 carácter).
Si se permiten espacios finales en la salida.
Entrada: cadena, salida: número unario.
Ejecución de muestra:
fuente
Hexagonía , 61 bytes.
Editar : ¡Gracias @Martin Ender ♦ por salvarme 1 byte del maravilloso truco -1!
¡Pruébelo en línea para verificar casos de prueba!
Las imágenes a continuación no se modifican, pero el flujo es básicamente el mismo. También tenga en cuenta que esto volverá
-1
si la entrada no es una matriz (es decir, sin[]
).Tengo un montón de no-operaciones dentro del Hexágono ... Supongo que definitivamente se puede jugar más.
Explicación
En resumen, agrega
-1
cuando encuentra a[
y agrega1
cuando encuentra a]
. Finalmente imprime el máximo que tiene.Ejecutemos el caso de prueba 5 para ver su comportamiento cuando se ejecuta a lo largo de la cadena
[1, [[3]], [5, 6], [[[[8]]]], 1]
:Comienza al principio y toma su entrada en la esquina W:
Como todavía hay entrada (no el carácter nulo
\0
o EOL), se ajusta a la parte superior e inicia la ruta carmesí.Esto es lo que sucede cuando desde allí hasta lindo
><
:,
lee[
en la memoria tampón, y{
yZ
establece el Z constante para ser 90.'
mueve a Dif y-
calcula la diferencia. Para[
y]
la diferencia será1
y3
respectivamente. Para números, espacios y comas será negativo.Luego corremos
(
dos veces (una al final del camino carmesí, una al comienzo después de envolver en el camino verde) para obtener-1
y1
resp para[
y]
. Aquí cambiamos el nombre deDiff
aValue
. Agregue este valor a la profundidad. (SolíaZ&
asegurarme de que copiara al vecino correcto). Luego calculamoslastMin - Depth
y obtuvimos un número en el borde de la memoriaminLR
.Luego aplicamos
&
(al final del camino verde) aminLR
: Si el número es <= 0, copia el valor izquierdo (es decirlastMin - Depth <= 0 => lastMin <= Depth
), de lo contrario toma el valor correcto.Envolvemos el camino azul horizontal y vemos de
Z&
nuevo qué copia elminLR
. Luego nosotros"&
e hicimos una copia del min calculado. Se supone que los corchetes están equilibrados, por lo que el mínimo debe ser <= 0. Después de ajustar, el camino azul va a la izquierda y golpea(
, haciendo que la copia sea1
menor que el mínimo real. Reutilizando el-
, creamos una copia única más como vecino de Buffer:Nota:
copy
se renombra como1-off
Cuando el camino azul golpea
\
y obtiene un bonito"
y lo<
atrapa de vuelta al circuito principal.Cuando los éxitos de bucle
1
,,
ou otros números como entrada:
El Diff se volverá negativo y se reflejará nuevamente en el bucle principal para la próxima entrada.
Cuando todo ha pasado por el bucle principal, llegamos a EOL que hace Buffer
-1
y finalmente va al borde inferior:'
mueve el MP hacia el1-off copy
y lo)
incrementa, y con la~
negación obtuvo el valor correcto de Profundidad Máxima que se imprime con!
Y la historia termina con a
@
.Supongo que debo haber complicado un poco las cosas. Si solo hubiera tenido que "retroceder" e "imprimir" sin incrementar y negar, habría guardado bien 2 bytes sin usar el hexágono completo.
¡ Muchas gracias a Timwi por IDE Esotérico y Hexagony Colorer !
fuente
-1
desde,
cambiando la última fila a:@!-".
(aunque estoy de acuerdo en que probablemente sea posible recortar mucho más o incluso ajustar esto en la longitud lateral 4 con algo de reestructuración).Z
de usarZ&
. Y debería haber mejores formas de iniciar el programa con el if implícito.brainfuck, 48 bytes
Formateado:
Toma la entrada formateada como
(1, ((3)), (5, 6), ((((8)))), 1)
y emite un valor de byte .Pruébalo en línea.
Esto almacena la profundidad por ubicación de memoria, moviendo el puntero hacia la derecha
(
y hacia la izquierda)
e ignorando otros caracteres. Las celdas visitadas están marcadas con una1
bandera, por lo que al final del bucle principal habrádepth + 1
banderas a la derecha de la celda actual. Estos se agregan para imprimir el resultado final.Una solución anterior de 69 bytes que utiliza un enfoque diferente:
En esta versión, la profundidad y la profundidad máxima se almacenan explícitamente en celdas.
fuente
Pyth,
1513 bytes-2 bytes por @Maltysen
Cuenta la diferencia entre los recuentos acumulativos de
[
y]
, y toma el máximo.Y
es la matriz vacía, y su representación de cadena (`
) es conveniente[]
.Probarlo aquí .
fuente
CJam, 19
22 23bytesIdea similar a mi respuesta MATL.
Gracias a Peter Taylor por eliminar 3 bytes
Pruébalo aquí
fuente
Perl 5, 34 bytes
32, más dos para
-p
Robados de Digital Trauma 's Retina respuesta ... que es un 26% más corto que esto.
:-)
O, igualmente:
fuente
]
no necesita escapar, excepto entre paréntesis.s&...&...&g
es el operador de sustitución. Ver perldoc.perl.org/perlop.htmlRuby, 51 caracteres
(Comenzó como una sugerencia de mejora para la respuesta Ruby de Doorknob , pero terminó de manera diferente. Así que la publiqué como respuesta separada. Los votos a favor de la idea de contar en profundidad ( descendiendo de ) deberían ir a la respuesta original).
?\\<=>$&
'] ['.index(c)
Entrada: cadena, salida: número.
Ejecución de muestra:
fuente
Perl 6, 53 bytes
El cierre:
Necesita un argumento, por ejemplo:
Explicación:
fuente
Minkolang 0.15 ,
312924 bytes¡Revisé mi algoritmo inspirado por la respuesta CJam de Luis Mendo y ahorré 5 bytes!
Pruébalo aquí!
Explicación
Esencialmente, lo que hace este código es mantener un total acumulado con +1 para cada uno
[
y -1 para cada uno]
, haciendo un seguimiento del valor máximo alcanzado, generando ese máximo al final. El bucle se maneja por la naturaleza toroidal de la caja de códigos de Minkolang.fuente
Ruby, 41 caracteres
Parámetro: matriz, retorno: número.
Ejecución de muestra:
fuente
Oracle SQL 11.2, 133 bytes
Sin golf
CONNECT BY crea una fila por carácter en la cadena de entrada.
El SUBSTR aísla el carácter correspondiente al número de fila.
El DECODE traduce cada '[' a 1, cada ']' a -1 y todos los demás caracteres a 0.
El SUM analítico suma cada 1, -1 y 0 de las filas anteriores, incluida la fila actual;
Las sumas máximas son la profundidad.
fuente
Java 8, 95
Esta es una expresión lambda para a
ToIntFunction<String>
. La entrada se toma como aString
en el formato de ejemplos del OP.bastante directo Divida la cadena usando
[
como delimitador. Para cada uno de ellos, incremente el contadore
y compárelo con el contadord
, manteniendo el más grande adentrod
. Luego divida la cadena de la iteración actual usando]
como delimitador esta vez y reste el número de divisiones adicionales dee
.fuente