^{Esse desafio foi inspirado por uma pergunta no Mathematica.SE .}

Digamos que você tenha uma lista / matriz aninhada de alguma estrutura arbitrária (as listas em cada nível não necessariamente têm o mesmo comprimento). Para simplificar, assumiremos que os nós são números inteiros não negativos ou matrizes vazias. Como um exemplo

[[[1, 3], 2], [1, 4], 12, [[0, [], 0], [5, [7]]]]

Às vezes, é mais conveniente achatar essa lista para executar alguma manipulação dos nós, por exemplo

--> [1, 3, 2, 1, 4, 12, 0, 0, 5, 7]
--> [1, 1, 0, 1, 0, 0, 0, 0, 1, 1]

Mas, no final, você realmente deseja preservar a estrutura original, portanto, deseja transformar isso novamente em

--> [[[1, 1], 0], [1, 0], 0, [[0, [], 0], [1, [1]]]

Sua tarefa é executar o último passo.

Dada uma lista aninhada de números inteiros não negativos arbitrários, que representa a estrutura desejada do resultado, e uma lista simples de números inteiros não negativos, que representam os valores desejados, reformula a lista simples na forma da lista estruturada. Você pode assumir que ambas as listas contêm o mesmo número de números inteiros.

Como de costume, você não precisa lidar com entradas inválidas (por exemplo, a segunda lista não é plana, a entrada está sintaticamente malformada, não possui números inteiros como nós, etc.). Você pode modificar as matrizes de entrada no seu código.

Você pode escrever uma função ou programa, recebendo entradas via STDIN, argumento de linha de comando ou argumento de função, e pode retornar o resultado ou imprimi-lo em STDOUT. Você pode usar qualquer formato conveniente de lista ou sequência para representar entrada e saída (desde que o formato seja inequívoco e a entrada não seja pré-processada). Além disso, o formato de ambas as entradas precisa ser consistente (para que você não possa considerar uma entrada como uma string e a outra como uma lista, por exemplo). Você pode acessar as listas de entrada em qualquer ordem, mas especifique o método exato de entrada em sua resposta.

Mais uma restrição: você não deve usar expressões regulares. Este é um desafio de manipulação de array, não um desafio de manipulação de string.

Isso é código de golfe, então a resposta mais curta (em bytes) vence.

Casos de teste

Structure                             Values                 Result
[[[1,3],2],[1,4],12,[[0,0],[5,[7]]]]  [1,1,0,1,0,0,0,0,1,1]  [[[1,1],0],[1,0],0,[[0,0],[1,[1]]]]
[[[0,0],0],[0,0],0,[[0,0],[0,[0]]]]   [1,1,0,1,0,0,0,0,1,1]  [[[1,1],0],[1,0],0,[[0,0],[1,[1]]]]
[]                                    []                     []
[[]]                                  []                     [[]]
[0,1,2,3]                             [5,1,0,5]              [5,1,0,5]
[[[[[0]]]]]                           [123]                  [[[[[123]]]]]
[0,[1,[]],[[]],[2,3],[]]              [1,6,1,8]              [1,[6,[]],[[]],[1,8],[]]

CJam, 18 16 13 bytes

lA,sNerN%l~]z

Recebe entrada via STDIN no mesmo formato da resposta CJam anterior:

[0 [11 []] [[]] [2 3] []]
[1 6 1 8] 

e gera a sequência de resultados para STDOUT

[1 [6 []] [[]] [1 8] []]

Simplesmente trato a primeira linha como string, converto todos os caracteres de dígito em novas linhas, divido em uma ou mais ocorrências de novas linhas, coloco a segunda linha como uma matriz na pilha, envolvo em uma matriz e compactamos as duas matrizes (linhas). A impressão é automática e, como a primeira linha foi tratada como string, ela mantém seus colchetes.

Expansão de código

lA,sNerN%l~]z
l                     "Read the first line of input. This is the nested array";
 A,s                  "Get array [0,1,2...9] and  convert it to string '012..9'";
    Ner               "Replace all occurrences of 0,1,2,..9 with new line";
       N%             "Split on one or more occurrences of new line";
         l~           "Read the second line as an array";
           ]          "Wrap both the splitted string and the second line array";
                      "in an array";
            z         "Transpose the array, there by placing the numbers from second";
                      "input array in the split holes of first input string";

Obrigado a @ user23013 por salvar 3 bytes.

Experimente online aqui

JavaScript, ES6, 44 bytes

f=(a,b,i=0)=>a.map(x=>x.map?f(x,b,i):b[i++])

Isso cria uma função fque pode ser chamada como

f([0,[1,[]],[[]],[2,3],[]],[1,6,1,8])

ou seja, a matriz aninhada e a matriz de valores como argumentos de entrada. A saída da função é a matriz aninhada convertida.

Essa é uma pergunta muito boa para recursão, é por isso que a resposta é uma função de recursão pura e agradável. Eu crio uma função fque converte o primeiro argumento usando o mapmétodo Para cada elemento, se o elemento for uma matriz, ele chama fnovamente, caso contrário, para números inteiros, obtém o i- ^ésimo item e o retorna, incrementando o valor de i. O valor de ié passado para baixo em cada chamada recursiva, para manter a ordem correta.

A detecção de matriz vs. número inteiro é novamente realizada usando o mapmétodo Para uma variável de matriz, mapé uma função válida, enquanto para variáveis ​​inteiras, não há propriedade ou função chamada mapdefinida para a variável.

Isso funciona em um navegador Firefox mais recente (devido ao ES6).

JavaScript, ES6, 41 bytes

Fiquei realmente impressionado com a resposta do Optimizer , foi muito inteligente e aprendi muito. No entanto, ao examiná-lo, encontrei uma maneira de encurtar um pouco e corrigir um pequeno bug:

f=(a,b)=>a.map(x=>x.map?f(x,b):b.shift())

Peguei a ivariável e a substitui por a shift(). Isso o torna um pouco mais curto e corrige o problema com o fato de iser passado por valor e não por referência, o que fez com que alguns números da matriz final se repetissem e outros no final não fossem usados. Mais uma vez, a resposta do Optimizer foi muito bem pensada, melhor do que eu poderia ter feito, apenas consertei um pouco.

Dyalog APL, 14 caracteres

Este é um acéfalo: (∊a)←b.

Normalmente, ∊asignifica aachatado, mas quando ocorre no lado esquerdo de uma tarefa, ele faz exatamente o que esse problema está pedindo. Para cumprir o requisito de ser uma função, ele precisa de alguns rabiscos extras: {a←⍺⋄(∊a)←⍵⋄a}(chaves para lambda; ⍺e ⍵para argumentos esquerdo e direito; ⋄para separador de instruções).

Teste em tryapl.org. Observe que no APL o vetor numérico vazio é indicado por ⍬("zilde"). Os vetores de um elemento são construídos com (,A)porque (A)significariam um escalar. Na saída, esta coisa:

┌⊖┐
│0│
└~┘

representa um vetor numérico vazio. O 0no centro mostra o "elemento prototípico", que não é um elemento da matriz.

Python, 51

f=lambda a,b:[b.pop(0)if x<[]else f(x,b)for x in a]

Exemplo:

>>> f([0,[1,[]],[[]],[2,3],[]], [1,6,1,8])
[1, [6, []], [[]], [1, 8], []]

Python 2, 50

f=lambda s,v:v.pop(0)if s<[]else[f(x,v)for x in s]

Este foi um problema muito bonito. Enquanto continuava trabalhando, percebi que bits do meu código eram desnecessários e a lógica se desmoronou em uma expressão simples. A maior parte do golfe estava em encontrar o algoritmo certo.

sé a estrutura e vé a lista plana da lista. A idéia é verificar se sé um número inteiro com s<[](o Python 2 trata os números como menores que as listas). Se for, simplesmente pegue e retorne o primeiro elemento de v, removendo-o de v. Caso contrário, recorra para as sublistas de s.

O pop é um pedaço de mágica imperativa no código de estilo muito funcional. Como todos vapontam para a mesma instância, a remoção de um elemento de um remove-o vem toda a árvore de execução; portanto, cada número vé usado apenas uma vez. A compreensão da lista [f(x,v)for x in s]cria uma árvore de chamada que é expandida em profundidade primeiro e da esquerda para a direita, fazendo com que os elementos vsejam colocados na ordem correta.

Eu escrevi isso independentemente da resposta do grc , mas acabou sendo o mesmo para mover um único [(e nomes de variáveis). A mudança salva um caractere devido ao espaçamento. A mudança de colchete significa manipular o caso do nó imediatamente na função, e não como parte da compreensão da lista, que eu não havia considerado.

Podemos salvar um caractere para 49 se esticarmos os requisitos de entrada para obter o valor de STDIN e a estrutura como argumento de função. Isso nos permite usar map.

v=input()
g=lambda s:v.pop(0)if s<[]else map(g,s)

Ruby, 39

f=->a,b{a.map{|d|f[d,b]}rescue b.shift}

Repete-se até que o elemento na lista seja um número inteiro.
Uma vez que chamar Integer.map dá uma exceção,
ele vai para a parte de resgate, que "abre / desloca" o 1º elemento da 2ª lista.

Regex soln ... um pouco mais:

f=->a,b{eval a.to_s.split(/\d+/).zip(b)*''}

Experimente com alguns casos de teste

CJam, 43 37 35 33 bytes

Esta é uma conversão direta da minha resposta JS . Um pouco longo, a maioria dos quais é utilizada pela detecção de tipo.

q~:B;{{_`La`&{F}{;BW):W=}?}%}:F~`

Toma as duas matrizes de entrada em duas linhas de STDIN, como

[[[1 3] 2] [1 4] 12 [] [[0 0] [5 [7]]]]
[1 1 0 1 0 0 0 0 1 1]

e saídas para STDOUT como

[[[1 1] 0] [1 0] 0 "" [[0 0] [1 [1]]]]

Experimente online aqui

Haskell, 113 104 bytes (86 + 18 da declaração de tipo de dados)

data N=I Int|L[N]
L[]!v=(L[],v)
L(a:b)!v|(c,w)<-a!v,(L d,u)<-L b!w=(L$c:d,u)
_!(n:m)=(I n,m)
s#v=fst$s!v

O Haskell não possui um tipo de dados de matriz aninhada interno, então tive que rolar o meu. Por esse motivo, o programa contém apenas correspondência de padrões e recursão estrutural explícita. O último caso de teste lê

L[I 0,L[I 1,L[]],L[L[]],L[I 2,I 3],L[]]#[1,6,1,8]

e avalia para

L[I 1,L[I 6,L[]],L[L[]],L[I 1,I 8],L[]]

Mathematica, 41 bytes

Function[,m[[i++]],Listable][i=1;m=#2;#]&

Essa é uma função sem nome que assume a estrutura como o primeiro argumento e a lista de valores como o segundo argumento (e retorna uma lista).

Esta é uma versão em golfe da resposta aceita na pergunta que inspirou esse desafio. Estou postando isso eu mesmo e não aceitarei essa resposta (na verdade, ela deve permanecer a mais curta, o que duvido). Isso é para impedir que mais alguém vença o desafio, basicamente copiando a resposta.

Como funciona:

• Nós definimos uma Listablefunção pura. As funções listáveis ​​são aplicadas automaticamente aos elementos de um argumento da lista (recursivamente) em vez da própria lista, portanto, chamar fa lista estruturada basicamente retornará uma lista da mesma estrutura com cada número inteiro isubstituído por f[i].
• Armazenamos a lista de valores no global me um contador i.
• Cada vez que chamamos f(independentemente do argumento), retornamos o próximo elemento de m.

Rebol - 87 66 60

f: func[a[block!]b][map-each n a[any[attempt[f n b]take b]]]

Ungolfed:

f: func [a [block!] b] [
    map-each n a [
        any [
            attempt [f n b]  
            take b
        ]
    ]
]

Exemplo:

>> f [0 [1 []] [[]] [2 3] []]   [1 6 1 8]           
== [1 [6 []] [[]] [1 8] []]

C #, 225 + 13 = 239 185 + 35 = 220 172 + 35 = 207 bytes

Requer isto:

using System;using o=System.Object;

Aceita object[]s como argumentos.

o[]u(o[]a,o[]b){var c=a;int i=0;Action<o[],o[]>d=null;d=(e, f)=>{for(int j=0;j<e.Length;j++){if(e[j]is int){f[j]=b[i];i++;}else{d((o[])e[j],(o[])f[j]);}}};d(a,c);return c;}

Código não destruído:

object[] Unflatten(object[] structure, object[] values)
{
    var c = structure;
    int i = 0;
    Action<object[], object[]> recursiveFunc = null;
    recursiveFunc = (e, f) =>
    {
        for (int j = 0; j < e.Length; j++)
        {
            if (e[j] is int)
            {
                f[j] = values[i]; i++;
            }
            else
            {
                recursiveFunc((object[])e[j], (object[])f[j]);
            }
        }
    };
    recursiveFunc(structure, c);
    return c;
}

Python 2, 64 bytes

def g(N,L):f=lambda N:L.pop(0)if`N`<":"else map(f,N);return f(N)

Ouvi dizer que você gosta de listas em listas, por isso coloco funções em funções.

Edit: Olhando para a resposta do grc agora percebo que era completamente desnecessário. Ah bem...

SWI-Prolog 82

f([],A,[],A):-!.
f([H|T],A,[J|U],B):-(is_list(H),!,f(H,A,J,C);A=[J|C]),f(T,C,U,B).

Exemplo de execução:

?- f([[[1,3],2],[1,4],12,[[0,[],0],[5,[7]]]],[1,1,0,1,0,0,0,0,1,1],R,[]).
R = [[[1,1],0],[1,0],0,[[0,[],0],[1,[1]]]].

O último []da consulta é para verificar o número incompatível de elementos, o que não parece ser necessário nesta pergunta.

Erlang, 116 93 bytes

f(R,F)->put(n,F),[g(X)||X<-R].
g([H|T])->[g(H)|g(T)];g([])->[];g(E)->[H|T]=get(n),put(n,T),H.

Usa duas funções impuras fe g. fmanipula o dicionário do processo configurando na lista simples e mapeia cada elemento da lista aninhada g(X). gem seguida, define no final da lista simples toda vez que encontra um valor que não seja da lista e retorna o cabeçalho da lista simples.

Perl 5, 49 bytes

O primeiro argumento é a estrutura do modelo, o segundo são os valores.

sub u{($t,$l)=@_;ref$t?[map{u$_,$l}@$t]:shift@$l}

Programa de teste

use Test::More;
use Test::Deep;

sub u{($t,$l)=@_;ref$t?[map{u$_,$l}@$t]:shift@$l}

cmp_deeply u([[[1,3],2],[1,4],12,[[0,0],[5,[7]]]],[1,1,0,1,0,0,0,0,1,1]),[[[1,1],0],[1,0],0,[[0,0],[1,[1]]]];
cmp_deeply u([[[0,0],0],[0,0],0,[[0,0],[0,[0]]]],[1,1,0,1,0,0,0,0,1,1]),[[[1,1],0],[1,0],0,[[0,0],[1,[1]]]];
cmp_deeply u([], []), [];
cmp_deeply u([[]], []), [[]];
cmp_deeply u([0,1,2,3], [5,1,0,5]), [5,1,0,5];
cmp_deeply u([[[[[0]]]]], [123]), [[[[[123]]]]];
cmp_deeply u([0,[1,[]],[[]],[2,3],[]], [1,6,1,8]), [1,[6,[]],[[]],[1,8],[]];
done_testing;

Powershell: 115

a matriz de entrada é $ i, o mapeamento é $ m, a saída é $ o

$h={if($_.GetType().IsArray){if($_.c -eq 0){,@()}else{,@($_|%{.$h})}}else{$m[$c++]}};$i|%{$o=@();$c=0}{$o+=,(.$h)}

$ h é uma string que contém a função recursiva, e você pode executar o código contido em uma string com. $ h ... E seria 30 bytes mais curto se o powershell não insistisse em achatar matrizes de valor único para escalares e uma matriz com um único valor nulo para nulo

e um visualizador de estrutura de matriz útil para verificar resultados

$j={if($_.GetType().IsArray){write-host '(' -n;($_|%{.$j});write-host ')' -n}else{write-host "$_" -n}};write-host '(' -n;$o|%{(.$j)}; write-host ')' -n;

editar: 149

salve como unflatten.ps1:

$m=[array]$args[1];$h={if($_.GetType().IsArray){if($_.c -eq 0){,@()}else{,@($_|%{.$h})}}else{$m[$c++]}};$args[0]|%{$o=@();$c=0}{$o+=,(.$h)};echo $o;

edit: 136, criação de matriz de saída em linha e saída de gravação

$m=[array]$args[1];$h={if($_.GetType().IsArray){if($_.c -eq 0){,@()}else{,@($_|%{.$h})}}else{$m[$c++]}};echo(,@($args[0]|%{$c=0}{.$h}))

ligue com. \ unflatten.ps1 [matriz de entrada] [matriz de mapeamento]

a saída é gravada no pipeline - execute isso primeiro:

Function View-Array{
Param([Parameter(ValueFromPipeline=$True,ValueFromPipelinebyPropertyName=$True)]
      [array]$o)

    PROCESS{
    $j={if($_.GetType().IsArray){write-host '(' -n;($_|%{.$j});write-host ')' -n}else{write-host "$_" -n}};
    write-host '(' -n;$o|%{(.$j)}; write-host ')' -n;
    }
}

e corra com

.\unflatten.ps1 [input array] [mapping array] | View-Array

C #, (40 + 123) = 163 bytes OR (67 + 81) = 148 bytes

O C # sofre com sua digitação estática e espaços para nome longos aqui.

Método de matriz

Usando instruções:

using o=System.Object;using System.Linq;

Código:

o[] u(o[] x,o[] y){int i=0;Func<o[],o[],o[]> f=null;f=(a,b)=>a.Select(e=>e is int?b[i++]:f((o[])e,b)).ToArray();return f(x,y);}

Método Stack (usa a estrutura Stack em vez de matrizes)

Usando instruções:

using s=System.Collections.Generic.Stack<object>;using System.Linq;

Código:

System.Func<s,s,s>f=null;f=(a,b)=>new s(a.Select(e=>e is int?b.Pop():f((s)e,b)));

Primeiras tentativas, primeiro código de golfe aqui.