Um desafio simples para sua segunda-feira à noite (ou terça-feira de manhã na outra metade do mundo ...)

Você recebe como entrada uma matriz aninhada e potencialmente irregular de números inteiros positivos:

[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]

Sua tarefa é determinar sua profundidade, que é a maior profundidade de aninhamento de qualquer número inteiro na lista. Nesse caso, a profundidade de 11é 6, qual é a maior.

Você pode assumir que nenhuma das matrizes estará vazia.

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e emitindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

A entrada pode ser obtida em qualquer formato conveniente de lista ou sequência que suporte matrizes não retangulares (com matrizes aninhadas de diferentes profundidades), desde que as informações reais não sejam pré-processadas.

Você não deve usar nenhum componente interno relacionado à forma das matrizes (incluindo os internos que resolvem esse desafio, que fornecem as dimensões de uma matriz aninhada). A única exceção é obter o comprimento de uma matriz.

Aplicam-se as regras padrão de código de golfe .

Casos de teste

[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

K, 4 bytes

#,/\

Em K, ,/juntará todos os elementos de uma lista. O idioma comum ,//itera para um ponto fixo, nivelando completamente uma lista arbitrariamente aninhada. ,/\iterará para um ponto fixo de maneira semelhante, mas reunirá uma lista de resultados intermediários. Contando quantos resultados intermediários visitamos antes de atingir o ponto fixo ( #), obtemos a resposta que queremos: a profundidade máxima de aninhamento.

"Contagem de junção sobre verificação de ponto fixo".

Em ação:

 (#,/\)'(,1
        1 2 3
        ,1 2 3
        (3;(3;,3;3);3)
        ,((,1;2);(3;,4)))
1 1 2 3 4

Retina , 10

• Guardado 1 byte graças a @ ӍѲꝆΛҐӍΛПҒЦꝆ
• Guardou 14 bytes adicionais graças a @ MartinBüttner

+ `\ w |} {

{

Aqui, o formato da entrada é um pouco artificial - os _caracteres são usados ​​para separadores de lista, portanto, uma entrada se pareceria com esta{1_{{2_3_{{4}_5}_6_{7_8}}_9_{10_{{{11}}}}_12_13}_14}

• Etapa 1 - remova repetidamente }{e todos os outros \wcaracteres. Isso tem o efeito de: a) tornar todas as listas em todos os níveis consistidas em apenas um elemento eb) remover todos os caracteres não estruturais da lista.
• Etapa 2 - contagem restante {. Isso fornece o nível mais profundo de aninhamento.

Experimente online.

Se isso for muito exagerado, a resposta anterior foi:

Retina , 13

Assume que as listas estão contidas em chaves {}.

+ `[^} {] |} {

{

Experimente online .

Python 2, 33 bytes

f=lambda l:l>{}and-~max(map(f,l))

Define recursivamente a profundidade dizendo que a profundidade de um número é 0 e a profundidade de uma lista é uma a mais que a profundidade máxima de seus elementos. A lista de números versus é verificada comparando-se com o dicionário vazio {}, que fica acima dos números, mas abaixo das listas na ordenação arbitrária de tipos internos do Python 2.

Pitão - 11 10 7 bytes

1 bytes salvos graças a @Dennis

4 bytes salvos graças a @Thomas Kwa

eU.usNQ

Experimente online aqui .

Continua somando a matriz até que ela pare de mudar, o que significa que é apenas um número, faz isso cumulativamente para salvar todos os resultados intermediários e obtém comprimento criando um intervalo com o mesmo comprimento da lista e obtendo o último elemento.

Haskell, 43 bytes

'['#x=x-1
']'#x=x+1
_#x=x
maximum.scanr(#)0

Exemplo de uso: maximum.scanr(#)0 $ "[1, [[3]], [5, 6], [[[[8]]]], 1]"-> 5.

Haskell não tem listas mistas ( Integermisturadas com List of Integer), portanto, não posso explorar algumas funções de detecção de lista e preciso analisar a string.

Estou começando à direita com 0e adicione 1 para cada ], subtraia 1 para cada [e mantenha o valor caso contrário. scanrmantém todos os resultados intermediários, para que maximumpossa fazer seu trabalho.

JavaScript (ES6), 35 bytes

f=a=>a[0]?Math.max(...a.map(f))+1:0

Explicação

Função recursiva que retorna a profundidade máxima de uma matriz ou 0se passou um número.

var solution =

f=a=>
  a[0]?                   // if a is an array
    Math.max(...a.map(f)) // return the maximum depth of each element in the array
    +1                    // add 1 to increase the depth
  :0                      // if a is a number, return 0

// Test cases
result.textContent =
`[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`
.split`\n`.map(t=>(c=t.split`->`.map(p=>p.trim()),c[0]+" == "+c[1]+": "+(solution(eval(c[0]))==c[1]?"Passed":"Failed"))).join`\n`

<input type="text" id="input" value="[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]" />
<button onclick="result.textContent=solution(eval(input.value))">Go</button>
<pre id="result"></pre>

MATL , 11 14 15 bytes

'}{'!=dYsX>

Chaves entre dentes são usadas no MATL para esse tipo de matrizes. De qualquer forma, a entrada é obtida e processada como uma sequência, de modo que colchetes podem ser usados ​​igualmente, modificando os dois caracteres no código.

Experimente online!

          % implicitly take input as a string (row array of chars)
'}{'!     % 2x1 (column) char array with the two curly brace symbols
=         % 2-row array. First / second row contains 1 where '}' / '{' is found
d         % second row minus first row
Ys        % cumulative sum of the array
X>        % maximum of the array
          % implicitly display result

Oitava, 29 bytes

@(a)max(cumsum(92-(a(a>90))))

Mapeia [para 1 e ]para -1 e, em seguida, obtém o máximo da soma acumulada.

Entrada é uma sequência do formulário

S6 = '[1, [[3]], [5, 6], [[[[8]]]], 1]';

Amostra executada em ideone .

Julia, 55 26 bytes

f(a)=0a!=0&&maximum(f,a)+1

Esta é uma função recursiva que aceita uma matriz unidimensional com conteúdo do tipo Anye retorna um número inteiro. Ao passar um array para a função, prefixe todos os colchetes com Any, ie f(Any[1,Any[2,3]]).

A abordagem é bastante simples. Para uma entrada a , multiplicamos a por 0 e verificamos se o resultado é o escalar 0. Caso contrário, sabemos que a é uma matriz, portanto aplicamos a função a cada elemento de a , aproveite o máximo e adicione 1.

Economizou 29 bytes graças a Dennis!

Ruby, 53 bytes

i=0;p gets.chars.map{|c|i+=('] ['.index(c)||1)-1}.max

Entrada de STDIN, saída para STDOUT.

i=0;                 initialize counter variable
p                    output to STDOUT...
gets                 get line of input
.chars               enumerator of each character in the input
.map{|c|             map each character to...
i+=                  increment i (and return the new value) by...
('] ['.index(c)||1)  returns 0 for ], 2 for [, 1 for anything else
-1                   now it's -1 for ], 1 for [, 0 for anything else
                     therefore: increment i on increase in nesting, decrement i
                       on decrease, do nothing otherwise
}.max                find the highest nesting level that we've seen

Geléia, 10 7 bytes

¬;/SпL

Experimente online! ou verifique todos os casos de teste .

Como funciona

¬;/SпL  Main link. Input: A (list)

¬        Negate all integers in A. This replaces them with zeroes.
    п   Cumulative while loop.
   S       Condition: Compute the sum of all lists in A.
                      If the sum is an integer, it will be zero (hence falsy).
 ;/        Body:      Concatenate all lists in A.
      L  Count the number of iterations.

Atualizar

Ao escrever esta resposta, notei que Jelly se comporta de maneira estranha para listas irregulares, porque calculei a profundidade de uma lista como o mínimo incrementado de profundidade de seus itens.

Isso foi resolvido na versão mais recente; portanto, o código a seguir ( 6 bytes ) funcionaria agora.

¬SSпL

Isso soma as linhas da matriz em vez de concatená-las.

Mathematica, 18 bytes

Max@#+1&//@(0#-1)&

Mathematica, 27 20 bytes

Max[#0/@#]+1&[0#]-1&

Função recursiva simples.

PHP, 61 bytes

function d($a){return is_array($a)?1+max(array_map(d,$a)):0;}

função recursiva que se usa como uma função de mapeamento para substituir cada elemento por sua profundidade.

PHP, 84 72 64 63 60 bytes

Nota: requer PHP 7 para o operador de comparação combinada. Também usa a codificação IBM-850

for(;$c=$argv[1][$i++];)$c>A&&$t=max($t,$z+=~ú<=>$c);echo$t;

Execute assim:

php -r 'for(;$c=$argv[1][$i++];)$c>A&&$t=max($t,$z+=~ú<=>$c);echo$t;' "[1, [[3]], [5, 6], [[[[8]]]], 1]"

• Salva 12 bytes apenas contando chaves da representação de sequência
• Economizou 8 bytes simplificando as comparações de cadeias e usando o número ordinal do caractere no caso de [e]
• Salvou um byte por não transmitir $i para um int. Os deslocamentos de sequência são convertidos para um int implicitamente
• Economizou 3 bytes usando o operador de comparação combinada em vez do número ordinal

C, 98 69 bytes

29 bytes de desconto, graças @DigitalTrauma !!

r,m;f(char*s){for(r=m=0;*s;r-=*s++==93)r+=*s==91,m=r>m?r:m;return m;}

Pega uma string como entrada e retorna o resultado como inteiro.

Exemplo ao vivo em: http://ideone.com/IC23Bc

Python 3, 42 39 bytes

-3 bytes graças ao Sp3000

Esta é essencialmente uma porta da solução Python 2 do xnor :

f=lambda l:"A"<str(l)and-~max(map(f,l))

Infelizmente, [] > {}retorna um unorderable typeserro, de modo que um truque específico do xnor não pode ser usado. Em seu lugar, -0123456789são mais baixos no valor ASCII que A, que é menor que [], portanto, a comparação de cadeias funciona.

CJam (15 bytes)

q~{__e_-M*}h],(

Demonstração online

Dissecação

q~      e# Read line and parse to array
{       e# Loop...
  _     e#   Leave a copy of the array on the stack to count it later
  _e_-  e#   Remove a flattened version of the array; this removes non-array elements from
        e#   the top-level array.
  M*    e#   Remove one level from each array directly in the top-level array
}h      e# ...until we get to an empty array
],(     e# Collect everything together, count and decrement to account for the extra []

Pelo mesmo comprimento, mas um pouco mais em território feio,

q'[,-{:~_}h],2-

Sed, 40 caracteres

(Código de 39 caracteres + opção de linha de comando de 1 caractere.)

s/[^][]+//g
:;s/]\[//;t
s/]//g
s/\[/1/g

Entrada: sequência, saída: número unário.

Exemplo de execução:

bash-4.3$ sed -r 's/[^][]+//g;:;s/]\[//;t;s/]//g;s/\[/1/g' <<< '[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]'
111111

Sed, 33 caracteres

(Código de 32 caracteres + opção de linha de comando de 1 caractere.)

Se espaços à direita forem permitidos na saída.

s/[^][]+//g
:;s/]\[//;t
y/[]/1 /

Entrada: sequência, saída: número unário.

Exemplo de execução:

bash-4.3$ sed -r 's/[^][]+//g;:;s/]\[//;t;y/[]/1 /' <<< '[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]'
111111      

Hexagonia , 61 bytes

Edit : Obrigado @Martin Ender ♦ por me salvar 1 byte do maravilhoso truque -1!

|/'Z{>"-\..(.."/'&<'..{>-&,=+<$.{\$._{..><.Z=/...({=Z&"&@!-"

Experimente online para verificar os casos de teste!

As imagens abaixo não são modificadas, mas o fluxo é basicamente o mesmo. Observe também que isso retornará -1se a entrada não for uma matriz (ou seja, sem[] ).

Tenho muitas no-ops dentro do Hexagon ... acho que definitivamente pode ser mais jogado.

Explicação

Em resumo, ele adiciona -1quando encontra um [e adiciona 1quando encontra um] . Finalmente, imprime o máximo que conseguiu.

Vamos executar o Caso de Teste 5 para ver seu comportamento ao executar a String [1, [[3]], [5, 6], [[[[8]]]], 1] :

Começa no início e leva sua entrada no canto W:

Como ainda existe entrada (não o caractere nulo \0 ou EOL), ela é colocada no topo e inicia o caminho carmesim.

Aqui está o que acontece quando de lá até fofo ><:

,lê [em Buffer {e Zdefine a constante Z como 90. 'move-se para Dif e -calcula a diferença. Para [e ]a diferença será 1e 3respectivamente. Para números, espaços e vírgulas, será negativo.

Em seguida, corremos (duas vezes (uma vez no final do caminho carmesim, um no início após o empacotamento no caminho verde) para obter -1e 1resp [e e ]. Aqui, alteramos o nome de Diffpara Value. Adicione este valor à profundidade. (Eu costumava Z&garantir que ele copiasse o vizinho certo). Então calculamoslastMin - Depth e obtivemos um número na borda da memóriaminLR .

Em seguida, aplicamos &(no final do caminho verde) a minLR: Se o número for <= 0, ele copia o valor esquerdo (ou seja,lastMin - Depth <= 0 => lastMin <= Depth ), caso contrário, recebe o valor correto.

Nós envolvemos o caminho azul horizontal e vemos Z&novamente o que copia o arquivo minLR. Então nós "&e fizemos uma cópia do min calculado. Os colchetes são assumidos como balanceados, portanto, o mínimo deve ser <= 0. Após o empacotamento, o caminho azul vai para a esquerda e pressiona (, tornando a cópia 1menor que o mínimo real. Reutilizando -, criamos mais uma cópia única como um vizinho do Buffer:

Nota: copy é renomeado como1-off

Quando o caminho azul atinge \e tem uma boa "e< pega de volta para o loop principal.

Quando o loop atinge 1, ,ou ou outros números como entrada:

O Diff ficará negativo e será refletido de volta ao loop principal para a próxima entrada.

Quando tudo passa pelo loop principal, chegamos ao EOL, que faz o Buffer, -1e finalmente chega ao limite inferior:

'move o MP para 1-off copye o )incrementa, e com ~negação, obtém o valor correto de Profundidade máxima, impresso com!

E a história termina com um @.

Acho que devo ter complicado um pouco as coisas. Se eu tivesse que apenas "retroceder" e "imprimir" sem aumentar e negar, teria economizado 2 bytes sem usar o Hexagon completo.

Muito obrigado a Timwi por Esoteric IDE e Hexagony Colorer !

brainfuck, 48 bytes

,[<++[>-<------]>++[+[<]>>[-]]+<,]-[<[>+<-]>>]<.

Formatado:

,
[
  <++[>-<------]>++
  [
    not close paren
    +
    [
      not open paren
      <
    ]
    >>[-]
  ]
  +<,
]
-[<[>+<-]>>]
<.

Pega entrada formatada como (1, ((3)), (5, 6), ((((8)))), 1)e gera um valor de byte .

Experimente online.

Isso armazena a profundidade por localização da memória, movendo o ponteiro para a direita (e para a esquerda )e ignorando outros caracteres. As células visitadas são marcadas com um 1sinalizador, portanto, no final do loop principal, haverá depth + 1sinalizadores à direita da célula atual. Estes são adicionados para imprimir o resultado final.

Uma solução anterior de 69 bytes usando uma abordagem diferente:

,
[
  >>++[<<->>------]<-<++
  [
    not close paren
    >++<+
    [
      not open paren
      >-<[-]
    ]
  ]
  <
  [
    [>+>]
    <[<-<]
    >
  ]
  >>[<+> >+<-]
  ,
]
<.

Nesta versão, a profundidade e a profundidade máxima são armazenadas explicitamente nas células.

Pitão, 15 13 bytes

-2 bytes por @Maltysen

eSm-F/Ld`Y._z

Conta a diferença entre as contagens cumulativas de [e ], e leva o máximo. Yé a matriz vazia e sua representação de string ( `) é convenientemente[] .

Experimente aqui .

CJam, 19 22 23 bytes

0l{_91=\93=-+_}%:e>

Idéia semelhante à minha resposta MATL.

Agradecimentos a Peter Taylor por remover 3 bytes

Experimente aqui

0                            push a 0
l                            read line as string
{            }%              map this block on the string
  _91=\93=-                  1 if it's an opening bracket, -1 if closing
           +_                cumulative sum
               :e>           fold maximum function

Perl 5, 34 bytes

32, mais dois para -p

{s&]\[|[^][]&&g&&redo}$_=@a=/]/g

Roubado do Trauma Digital 's resposta Retina ... o que é 26% menor do que isso.:-)

Ou, igualmente:

{s&]\[|[^][]&&g&&redo}$_=y///c/2

Ruby, 51 caracteres

(Começou como sugestão de melhoria para a resposta Ruby da maçaneta da porta , mas terminou de forma diferente. Então, eu a publiquei como resposta separada. Voto a favor da idéia de contagem de profundidade ( , descendente de?\\<=>$&'] ['.index(c) ) devem ir para a resposta original.)

m=i=0
gets.gsub(/\[|\]/){m=[m,i+=?\\<=>$&].max}
p m

Entrada: string, saída: número.

Exemplo de execução:

bash-4.3$ ruby -e 'm=i=0;gets.gsub(/\[|\]/){m=[m,i+=?\\<=>$&].max};p m' <<< '[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]'
6

Perl 6, 53 bytes

O encerramento:

{my ($m,$d);/[\[{$d++;$m=max $m,$d}|\]{$d--}|.]*/;$m}

Precisa de um argumento, por exemplo:

{my ($m,$d);/[\[{$d++;$m=max $m,$d}|\]{$d--}|.]*/;$m}("[[[3]][2]]")
3

Explicação:

{ my ($m,$d);                 # start closure, declare variables    

  /                           # start regex match

   [                          # start (non-capturing) group

     \[ {$d++;$m=max $m,$d} | # match [ and track depth; OR

     \] {$d--}              | # match ] and track depth; OR

     .                        # match one character

   ]*                         # repeat group

  /;                          # end regex

  $m                          # return max depth
}

Minkolang 0,15 , 31 29 24 bytes

Revisou meu algoritmo inspirado na resposta CJam de Luis Mendo e salvou 5 bytes!

od5&j$ZN.d"["=$r"]"=~++d

Experimente aqui!

Explicação

Essencialmente, o que esse código faz é manter um total contínuo com +1 para cada um [e -1 para cada ], mantendo o controle do valor máximo atingido, produzindo esse valor máximo no final. O loop é tratado pela natureza toroidal do codebox de Minkolang.

od           Take character from input and duplicate it (0 if input is empty)
  5&         Pop top of stack and skip the following five spaces if 0
    j$Z      Push the maximum value of the stack
       N.    Output as number and stop.

  d                  Duplicate top of stack for character tests
   "["=              +1 if the character is [
       $r            Swap top two items of stack
         "]"=~       -1 if the character is ]
              ++     Add twice
                d    Duplicate top of stack for the running total

Ruby, 41 caracteres

f=->a,d=1{a.map{|e|f[e,d+1]rescue d}.max}

Parâmetro: matriz, retorno: número.

Exemplo de execução:

2.1.5 :001 > f=->a,d=1{a.map{|e|f[e,d+1]rescue d}.max}
 => #<Proc:0x0000000214d258@(irb):1 (lambda)> 

2.1.5 :002 > f[[1, [[2, 3, [[4], 5], 6, [7, 8]], 9, [10, [[[11]]]], 12, 13], 14]]
 => 6 

Oracle SQL 11.2, 133 bytes

SELECT MAX(d)FROM(SELECT SUM(DECODE(SUBSTR(:1,LEVEL,1),'[',1,']',-1,0))OVER(ORDER BY LEVEL)d FROM DUAL CONNECT BY LEVEL<=LENGTH(:1));

Sem golfe

SELECT MAX(d)
FROM   (
         SELECT SUM(DECODE(SUBSTR(:1,LEVEL,1),'[',1,']',-1,0))OVER(ORDER BY LEVEL) d 
         FROM   DUAL 
         CONNECT BY LEVEL<=LENGTH(:1)
       );

O CONNECT BY cria uma linha por caractere na cadeia de entrada.

O SUBSTR isola o caractere correspondente ao número da linha.

O DECODE traduz cada '[' para 1, cada ']' para -1 e todos os outros caracteres para 0.

O SUM analítico soma cada 1, -1 e 0 das linhas anteriores, incluindo a linha atual;

A soma MAX é a profundidade.

Java 8, 95

Esta é uma expressão lambda para a ToIntFunction<String>. A entrada é tomada como a Stringno formato de exemplos do OP.

s->{int d=e=-1;for(String t:s.split("[")){d=++e>d?e:d;e-=t.split("]",-1).length()-1;}return d;}

bastante direto. Divida a sequência usando [como delimitador. Para cada um deles, aumente o contador ee compare-o com o contador d, mantendo o maior dentro d. Em seguida, divida a sequência da iteração atual usando ]como delimitador dessa vez e subtraia o número de divisões extras e.