44
\$\begingroup\$

This challenge was inspired by a question on Mathematica.SE.

Say you've got a nested list/array of some arbitrary structure (the lists at each level don't necessarily have the same length). For simplicity, we'll assume that the nodes are non-negative integers or empty arrays. As an example

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

Sometimes it's more convenient to flatten that list to perform some manipulation of the nodes, e.g.

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

But in the end you actually want to preserve the original structure, so you want to turn this back into

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

Your task is to perform that last step.

Given a nested list of arbitrary non-negative integers, which represents the desired structure of the result, and a flat list of non-negative integers, which represent the desired values, reshape the flat list into the form of the structured list. You may assume that both lists contain the same number of integers.

As usual you don't have to deal with invalid input (e.g. the second list not being flat, the input being syntactically malformed, not having integers as nodes, etc.). You may modify the input arrays in your code.

You may write a function or program, taking input via STDIN, command-line argument or function argument, and you may return the result or print it to STDOUT. You may use any convenient list or string format to represent input and output (as long as the format is unambiguous and the input is not preprocessed). Also, the format of both inputs needs to be consistent (so you can't take one input as a string and the other as a list, for instance). You may take the input lists in either order, but please specify the exact input method in your answer.

One more restriction: you must not use regular expressions. This is an array manipulation challenge, not a string manipulation challenge.

This is code golf, so the shortest answer (in bytes) wins.

Test Cases

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],[]]
\$\endgroup\$
5
  • \$\begingroup\$ Is it allowed if the values in the Structure array get changed? \$\endgroup\$
    – ProgramFOX
    Jan 3, 2015 at 10:00
  • \$\begingroup\$ @ProgramFOX yes. "You may modify the input arrays in your code." \$\endgroup\$ Jan 3, 2015 at 11:05
  • \$\begingroup\$ Ironically, one of the submissions here is in Mathematica. \$\endgroup\$ Jan 5, 2015 at 19:50
  • 1
    \$\begingroup\$ @impinball That is mine, which I posted along with the question, in order to prevent anyone else from stealing the answer from the linked question (and in fact, it's merely a golfed down version of that answer). \$\endgroup\$ Jan 5, 2015 at 20:31
  • \$\begingroup\$ @MartinBüttner Oh. Nice. It's actually one of the shorter answers, too. \$\endgroup\$ Jan 5, 2015 at 23:30

21 Answers 21

26
\$\begingroup\$

JavaScript, ES6, 44 bytes

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

This creates a function f which can be called like

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

i.e. the nested array and the values array as input arguments. The output of the function is the converted nested array.

This question is a very nice question for recursion, that is why the answer is a neat and sweet recursion function. I create a function f which converts the first argument using the map method. For each element, if the element is an array, it calls f again, otherwise, for integers, it gets the ith item and returns that, incrementing the value of i. The value of i is passed down in each recursive call, so as to maintain the order correct.

Array vs. Integer detection is yet again done using the map method. For an array variable, map is a valid function, while for integer variables, there is no property or function called map defined for the variable.

This works in a latest Firefox browser (due to ES6).

\$\endgroup\$
5
  • 4
    \$\begingroup\$ I know I should avoid comments like "+1" and "thanks", but damn this is one sweet ES6 function! I can look at this code line for hours :) \$\endgroup\$
    – Jacob
    Dec 31, 2014 at 14:08
  • \$\begingroup\$ I se that there's 2 .map existed in the code. Is there any way to further shorten it? Anyway, nice code! \$\endgroup\$ Dec 31, 2014 at 18:39
  • \$\begingroup\$ Whoa, when did ES add that lambda syntax? \$\endgroup\$
    – fluffy
    Dec 31, 2014 at 20:42
  • \$\begingroup\$ @fluffy in ES6 ;) \$\endgroup\$
    – Optimizer
    Dec 31, 2014 at 21:20
  • \$\begingroup\$ @Derek朕會功夫 unfortunetely no. map is tied to the context, so the first map belongs to a while the next map belongs to each x in the iteration. There is no other shorter way to refer map either, nor to differentiate array from integers \$\endgroup\$
    – Optimizer
    Dec 31, 2014 at 21:22
19
\$\begingroup\$

JavaScript, ES6, 41 bytes

I was really impressed by Optimizer's answer, it was very cleverly done and I learned a lot. However on looking it over I found a way of shortening it slightly and fixing a small bug:

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

I took out the i variable and replaced it with a shift(). This makes it slightly shorter and fixes the problem with the fact that i is passed by value and not by reference, witch caused some numbers from the final array to repeat and some at the end not to be used. Again, Optimizer's answer was really well thought out, better than I could have done, I just fixed it a little.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Nice golf! A bit sad that I did not catch that :P \$\endgroup\$
    – Optimizer
    Dec 31, 2014 at 22:01
18
\$\begingroup\$

Dyalog APL, 14 characters

This is a no-brainer: (∊a)←b.

Normally, ∊a means a flattened, but when it occurs on the left-hand side of an assignment, it does precisely what this problem is asking for. To comply with the requirement of being a function, it needs a few extra squiggles: {a←⍺⋄(∊a)←⍵⋄a} (curly braces for lambda; and for left and right argument; for statement separator).

Test on tryapl.org. Note that in APL the empty numeric vector is denoted by ("zilde"). One-element vectors are constructed with (,A) because (A) would mean a scalar. In the output, this thing:

┌⊖┐
│0│
└~┘

represents an empty numeric vector. The 0 in the centre shows the "prototypical element" which is not an element of the array.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Does that graphical representation not distinguish (,1) and (1) or why is the final bit just presented as [1|1] instead of [1|[1]]? \$\endgroup\$ Dec 31, 2014 at 15:47
  • \$\begingroup\$ The graphical representation that tryapl uses (known as ]box on) doesn't distinguish between them. There's another function in Dyalog (display from dfns.dws) that does make a distinction, but unfortunately tryapl restricts the loading of additional workspaces (i.e. libraries). :( \$\endgroup\$
    – ngn
    Dec 31, 2014 at 15:52
  • 1
    \$\begingroup\$ To see the result in square-bracketed form, try this: ∊{0=⍴⍴⍵:⍕⍵ ⋄ '['(∇¨⍵)']'}a. Or this: ∊{0=⍴⍴⍵:⍕⍵ ⋄ '['(1↓,'|',[1.5]∇¨⍵)']'}a if you insist on the separator, |. \$\endgroup\$
    – ngn
    Dec 31, 2014 at 15:55
  • \$\begingroup\$ Oh, you can also use ]display a in tryapl. It gives complete information about the structure. Sorry, I didn't realize this at first. \$\endgroup\$
    – ngn
    Dec 31, 2014 at 17:06
  • \$\begingroup\$ Fair point. I turned it into a function at the cost of 2 extra bytes. \$\endgroup\$
    – ngn
    Dec 31, 2014 at 18:50
12
\$\begingroup\$

Python 2, 50

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

This was a very beautiful problem. As I kept working on it, I kept realizing that bits of my code were unnecessary, and the logic collapsed into a simple expression. Most of the golfing was in finding the right algorithm.

s is the structure and v is the flat list of list. The idea is to check whether s is an integer with s<[] (Python 2 treats numbers as smaller than lists). If it is, simply take and return the first element of v, removing it from v. Otherwise, recurse down onto the sublists of s.

The pop is a piece of imperative magic in very functional-style code. Because all v point to the same instance, popping an element from one removes it from v in the whole execution tree, so each number in v is only used once. The list comprehension [f(x,v)for x in s] creates a call tree that is expanded depth-first and left-to-right, causing the elements of v to be slotted in the correct order.

I wrote this independently of grc's answer, but it turned out to the same up to moving a single [ (and variable names). The move saves a char due to spacing. The bracket move means handling the node case immediately in the function, rather than as part of the list comprehension, which I hadn't considered.

We can save a char for 49 if we stretch the input requirements to take the value from STDIN and the structure as a function argument. This lets us use map.

v=input()
g=lambda s:v.pop(0)if s<[]else map(g,s)
\$\endgroup\$
10
\$\begingroup\$

Ruby, 39

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

Recurses till the element in the list is an integer.
Since calling Integer.map gives an exception,
it goes to the rescue portion, which "pops/shift" the 1st element out of the 2nd list.

Regex soln... a bit longer:

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

Try it with some test cases

\$\endgroup\$
1
  • \$\begingroup\$ Just for reference, regex solutions aren't allowed. ;) \$\endgroup\$ Dec 31, 2014 at 14:01
10
\$\begingroup\$

Python, 51

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

Example:

>>> f([0,[1,[]],[[]],[2,3],[]], [1,6,1,8])
[1, [6, []], [[]], [1, 8], []]
\$\endgroup\$
9
\$\begingroup\$

CJam, 18 16 13 bytes

lA,sNerN%l~]z

Takes input via STDIN in the same format as the previous CJam answer:

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

and outputs the result string to STDOUT

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

I simply treat the first line as string, convert all digit characters to newlines, split on one or more occurrences of newlines, put the second line as an array on stack, wrap in an array and zip together the two arrays (rows). Printing is automatic and as the first row was treated as string, it retains its brackets.

Code expansion

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

Thanks to @user23013 for saving 3 bytes.

Try it online here

\$\endgroup\$
5
  • \$\begingroup\$ From the OP, "This is an array manipulation challenge, not a string manipulation challenge." \$\endgroup\$
    – atk
    Jan 2, 2015 at 2:05
  • \$\begingroup\$ @atk: It is arguable since OP only explicitly disallow regular expression. \$\endgroup\$ Jan 2, 2015 at 2:35
  • 1
    \$\begingroup\$ Short for /La-: %. \$\endgroup\$
    – jimmy23013
    Jan 2, 2015 at 6:00
  • \$\begingroup\$ @user23013 Wow, never bothered to realize that % is for split too, and it splits across multiple occurrences too! \$\endgroup\$
    – Optimizer
    Jan 2, 2015 at 6:52
  • \$\begingroup\$ @atk Yes, since only regex were banned, I used this technique. \$\endgroup\$
    – Optimizer
    Jan 2, 2015 at 6:55
5
\$\begingroup\$

Mathematica, 41 bytes

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

This is an unnamed function which takes the structure as the first argument and the list of values as the second argument (and returns a list).

This is a golfed version of the accepted answer on the question that inspired this challenge. I'm posting this myself, and will not accept this answer (should it actually remain the shortest, which I doubt). This is in order to prevent any one else from winning the challenge by basically copying the answer.

How it works:

  • We define a Listable pure function. Listable functions are automatically applied to the elements of a list argument (recursively) instead of the list itself, so calling f on the structured list will basically return a list of the same structure with each integer i replaced by f[i].
  • We store the value list in the global m and a counter in i.
  • Each time we call f (regardless of the argument) we return the next element of m.
\$\endgroup\$
5
\$\begingroup\$

CJam, 43 37 35 33 bytes

This one is a direct conversion of my JS answer. A bit long, most of which is taken up by type detection.

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

Takes the two input arrays on two lines of STDIN like

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

and outputs to STDOUT like

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

Try it online here

\$\endgroup\$
5
\$\begingroup\$

Haskell, 113 104 bytes (86 + 18 from datatype declaration)

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

Haskell does not have a built-in nested array datatype, so I had to roll my own. For this reason, the program contains only pattern matching and explicit structural recursion. The last test case reads

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

and evaluates to

L[I 1,L[I 6,L[]],L[L[]],L[I 1,I 8],L[]]
\$\endgroup\$
4
\$\begingroup\$

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
        ]
    ]
]

Example:

>> f [0 [1 []] [[]] [2 3] []]   [1 6 1 8]           
== [1 [6 []] [[]] [1 8] []]
\$\endgroup\$
4
\$\begingroup\$

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

Requires this:

using System;using o=System.Object;

Accepts object[]s as arguments.

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

Ungolfed code:

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;
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ You can shorten it a bit more by using using o=System.Object and replacing all instances of object with simply o. msdn.microsoft.com/en-us/library/sf0df423.aspx \$\endgroup\$
    – Kroltan
    Jan 2, 2015 at 18:41
  • 1
    \$\begingroup\$ @Kroltan Great tip, thanks! \$\endgroup\$
    – ProgramFOX
    Jan 2, 2015 at 18:47
  • \$\begingroup\$ Clone is shallow. If modification of the inputs is allowed, you don't need to clone at all. If it's not allowed, you need proper cloning. \$\endgroup\$ Jan 2, 2015 at 19:28
  • \$\begingroup\$ @CodesInChaos I see. As modifying the input array is allowed, I removed the clone. Thanks! \$\endgroup\$
    – ProgramFOX
    Jan 3, 2015 at 11:07
3
\$\begingroup\$

Python 2, 64 bytes

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

I heard you like lists in lists so I put functions in functions.

Edit: Looking at grc's answer now I realise that was completely unnecessary. Oh well...

\$\endgroup\$
3
\$\begingroup\$

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).

Sample run:

?- 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]]]].

The last [] in the query is for checking for mismatched number of elements, which doesn't seem to be necessary in this question.

\$\endgroup\$
2
  • \$\begingroup\$ What makes the cuts (and, by extension, the expensive is_list) necessary? \$\endgroup\$ Jul 7, 2019 at 12:25
  • 1
    \$\begingroup\$ @UnrelatedString: Feel free to edit the answer directly if you found them unnecessary to get the right answer. My Prolog was bad back then (I use library and cuts extensively) and even more rusty these days. \$\endgroup\$ Jul 7, 2019 at 17:29
3
\$\begingroup\$

Jelly, 1 byte

Try it online!

Jelly's mold builtin does this exactly. Takes input in reversed order (i.e. the flat list first)


Jelly, 7 bytes

ßḢ}ŒḊ?€

Try it online!

Non-builtin is still pretty short. Takes input in normal order (flat list second)

How it works

ßḢ}ŒḊ?€ - Main link. Takes l on the left and r on the right
      € - Over each element k in l:
     ?  -   If statement:
   ŒḊ   -   Condition: Depth. This yields 0 for integers and non-zero for lists
ß       -   Then: Recurse with k on the left and r on the right
 Ḣ}     -   Else: Pop and return the first element of r
\$\endgroup\$
2
\$\begingroup\$

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.

Uses two impure functions f and g. f manipulates the process dictionary by setting n to the flat list and maps each element of the nested list to g(X). g then sets n to the tail of the flat list every time it encounters a non-list value and returns the head of the flat list.

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 49 bytes

First argument is the template structure, second is the values.

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

Test Program

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;
\$\endgroup\$
1
\$\begingroup\$

Powershell: 115

the input array is $i, the mapping is $m, output is $o

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

$h is a string containing the recursive function, and you can execute code contained in a string with .$h... And it would be 30 bytes shorter if powershell didn't insist on flattening single value arrays to scalars, and an array with a single null value to null

and a handy array structure viewer for verifying results

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

edit: 149

save as 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, inline output array creation and write-output

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

call with .\unflatten.ps1 [input array] [mapping array]

the output is written to the pipeline- so run this first:

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

and run with

.\unflatten.ps1 [input array] [mapping array] | View-Array
\$\endgroup\$
0
1
\$\begingroup\$

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

C# suffers from its static typing and long namespaces here.

Array method

Using statements:

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

Code:

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

Stack method (uses the Stack structure instead of arrays)

Using statements:

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

Code:

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

First attempts, first code golf here.

\$\endgroup\$
0
\$\begingroup\$

Appleseed, 136 bytes

(def M(q((S D)(if S(if(type?(head S)Int)(cons(head D)(M(tail S)(tail D)))(cons(M(head S)D)(M(tail S)(drop(length(flatten(head S)))D))))(

Defines a recursive function that takes two lists. Try it online!

Ungolfed/commented

; Define mold
(def mold
  ; as a function of two arguments, the nested list representing the structure
  ; and the flat list containing the data
  (lambda (shape data)
    ; If the shape list is nonempty:
    (if shape
      ; If its first element is an int:
      (if (type? (head shape) Int)
        ; Construct the result list from
        (cons
          ; the first element of the data list
          (head data)
          ; followed by a recursive call with all but the first element of both lists
          (mold (tail shape) (tail data)))
      ; Else, its first element is a list:
        ; Construct the result list from
        (cons
          ; a recursive call with the first element of the shape list
          (mold (head shape) data)
          ; followed by a recursive call with
          (mold
            ; all but the first element of the shape list
            (tail shape)
            ; and all but the first N elements of the data list, where N is the number
            ; of data elements used in unflattening the head of the shape list
            (drop (length (flatten (head shape))) data))))
    ; Else, the shape list is empty:
      ; Return the empty list
      nil)))
\$\endgroup\$
0
\$\begingroup\$

R, 6 bytes

relist

Try it online!

relist performs the exact operation described here; and has been included since R 2.6.0 (released Oct. 3, 2007).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.