12
\$\begingroup\$

Everybody loves nested lists! However, sometimes it's hard to make a nested list. You have to decide if you want to nest it deeper, or if you need to nest it shallower. So for your challenge, you must "Autonest" a list. To autonest a list, compare every pair of items in the list.

  • If the second item is smaller, separate the two elements by inserting closing and opening brackets between them, like this:

      } {
    {2 , 1}
    

    For example, {2, 1} becomes {2}, {1}, and {3, 2, 1} becomes {3}, {2}, {1}

  • If the second item is the same, then change nothing. For example, {1, 1, 1} stays the same, and {2, 1, 1, 1} would become {2}, {1, 1, 1}.

  • If the second item is larger, then nest every following item one level deeper. For example, {1, 2} would become {1, {2}} and {1, 2, 3} would become {1, {2, {3}}}

The Challenge

You must write a program or function that takes in a list of numbers, and returns the same list after being autonested. Take this input in your languages native list format (or the closest alternative) or as a string. You do not have to use curly braces like I did in my examples. You can use whichever type of brackets are most natural in your language, as long as this is consistent. You can safely assume the list will only contain integers. You can also assume the list will have at least 2 numbers in it. Here is some sample IO:

{1, 3, 2}                         -->   {1, {3}, {2}}
{1, 2, 3, 4, 5, 6}                -->   {1, {2, {3, {4, {5, {6}}}}}}
{6, 5, 4, 3, 2, 1}                -->   {6}, {5}, {4}, {3}, {2}, {1}
{7, 3, 3, 2, 6, 4}                -->   {7}, {3, 3}, {2, {6}, {4}}
{7, 3, 1, -8, 4, 8, 2, -9, 2, 8}  -->   {7}, {3}, {1}, {-8, {4, {8}, {2}, {-9, {2, {8}}}}}

Standard loopholes apply, and the shortest answer in bytes wins!

\$\endgroup\$
  • 2
    \$\begingroup\$ Can we take the input in our language's string format? \$\endgroup\$ – Downgoat Jun 28 '16 at 1:49
  • \$\begingroup\$ What is the max size of the integer? \$\endgroup\$ – thepiercingarrow Jun 28 '16 at 4:00
  • \$\begingroup\$ @thepiercingarrow I don't really care too much. It won't be anything ridiculous. You should be able to at least handle [-100, 100] but I'm not planning on giving gigantic inputs. \$\endgroup\$ – DJMcMayhem Jun 28 '16 at 4:59
  • \$\begingroup\$ "If the second item is smaller, then nest all following elements one level higher, by inserting a closing bracket. Then, to make sure all the brackets stay matched, insert an opening bracket. For example, {2, 1} becomes {2}, {1}" How is that one level higher? One level higher would be {2}, 1. What you have is the same level. \$\endgroup\$ – msh210 Jun 28 '16 at 7:30
  • \$\begingroup\$ @msh210 Yeah, that was a poor explanation. Is the current phrasing better? \$\endgroup\$ – DJMcMayhem Jun 28 '16 at 7:45
1
\$\begingroup\$

MATL, 48 43 bytes

YY_XKx"@K<?93]44@K-?91]@XKV]v93Gd0>sQY"h4L)

This uses square brackets in input and output. The output has commas without spaces as separators.

Note that the output would not be interpreted as a nested list in MATL. It would in other languages, and it satisfies the output specification in the challenge.

Try it online!

Explanation

YY_XKx   % Push -inf. Copy to clipboard K (represents previous input entry). Delete
"        % Take numerical array implicitly. For each entry:
  @K<    %   Is current entry less than the previous one?
  ?93]   %   If so, push 93 (ASCII for ']')
  44     %   Push 44 (ASCII for comma)
  @K-    %   Is current entry different from the previous one?
  ?91]   %   If so, push 91 (ASCII for '[')
  @XKV   %   Push current entry, copy into clipboard K, convert to string
]        % End for each
v        % Concat vertically all stack contents, converting to char
93       % Push 93 (ASCII for ']') (to be repeated the appropriate number of times)
Gd0>sQ   % Determine how many times the input increases, plus 1
Y"       % Repeat 93 that many times
h        % Concat horizontally with previous string. Gives a row array, i.e. string
4L)      % Remove first char, which is an unwanted comma. Display implicitly
\$\endgroup\$
3
\$\begingroup\$

Haskell, 96 bytes

a#b|a<b=",{"|a>b="},{"|1<2=","
f(a:b:c)=show a++a#b++f(b:c)++['}'|a<b]
f[x]=show x++"}"
('{':).f

Usage example: ('{':).f $ [7,3,3,2,6,4] -> "{7},{3,3},{2,{6},{4}}".

As Haskell doesn't have nested lists, I return the result as a string. The nesting algorithm is easy: a) print number, b) if the next number is greater (less, equal), print ,{ ( },{, ,), c) make a recursive call with the rest of the list, d) print } if the number is less than the next one, e) enclose everything in { and }.

\$\endgroup\$
  • \$\begingroup\$ Sorry, I miscount \$\endgroup\$ – Akangka Jun 29 '16 at 11:54
3
\$\begingroup\$

Python 3, 98 bytes

p,*i=eval(input())
c=[p]
a=b=[c]
for x in i:
 if x>p:b=c
 if x!=p:c=[];b+=[c]
 c+=[x];p=x
print(a)

Example:

$ python3 autonest.py <<< "[7, 3, 1, -8, 4, 8, 2, -9, 2, 8]"
[[7], [3], [1], [-8, [4, [8], [2], [-9, [2, [8]]]]]]
\$\endgroup\$
2
\$\begingroup\$

Java 8 197 187 193 192 bytes


Thanks to all the commenters who worked with me on this monstrosity. It was golfed down to 187 bytes until I found a costly bug. However due to the power of Black Magic the "runs down to" operator "-->" the byte count is at a healthy 192 bytes.


String a(int[]b){int l=b.length,d=1,i=0;String c="{";for(;i<l-1;i++)if(b[i]>b[i+1])c+=b[i]+"},{";else if(b[i]<b[i+1]){d++;c+=b[i]+",{";}else c+=b[i]+",";c+=b[l-1];while(d-->0)c+="}";return c;}
\$\endgroup\$
  • \$\begingroup\$ Sorry coming right up @Blue \$\endgroup\$ – Rohan Jhunjhunwala Jun 28 '16 at 1:58
  • \$\begingroup\$ Also, a couple of tips: 1. You can take the input as an array, rather than a sequence: (int[]b) 2. You can define multiple ints at the same time using commas (int l=b.length,d=1,i=0). 3. You should remove as much whites pace as you can (ex. between variable assignments). Hope this helps! \$\endgroup\$ – Blue Jun 28 '16 at 2:07
  • \$\begingroup\$ Hello, and welcome to PPCG! Snippets are meant for javascript code that are meant to be executed in the browser, not challenge submissions. Also, you forgot a space after length, \$\endgroup\$ – Maltysen Jun 28 '16 at 2:19
  • \$\begingroup\$ Oh ok my apologies @Maltysen I will embed it into a full java program. I was just going off of the op saying "function or program" which "returns". So should I refactor this to print my output \$\endgroup\$ – Rohan Jhunjhunwala Jun 28 '16 at 2:21
  • 1
    \$\begingroup\$ @RohanJhunjhunwala sorry, should have been more clear. When I said "snippet", I wasn't talking about your code, but rather your formatting. When trying to put code into a post, don't click the "snippet" button, but instead put it in a code block(4 spaces or ctrl-k) \$\endgroup\$ – Maltysen Jun 28 '16 at 3:41
2
\$\begingroup\$

C, 145 138 bytes

Thanks to Giacomo for 7 bytes!

#define P printf(
n;main(c,v,p,t)char**v;{p=-101;for(v++;*v;v++){t=atoi(*v);if(t<p)P"}{");if(t>p)P"{",n++);P"%d ",p=t);}for(;n--;)P"}");}

Input is taken through command line arguments and output is given though stdout.

sample run:

$ ./autonest 7 3 1 -8 4 8 2 -9 2 8
{7 }{3 }{1 }{-8 {4 {8 }{2 }{-9 {2 {8 }}}}}
\$\endgroup\$
  • 1
    \$\begingroup\$ Try use t=atoi(*v); instead of sscanf(*v,"%d",&t); Source \$\endgroup\$ – Giacomo Garabello Jul 1 '16 at 15:13
  • \$\begingroup\$ Use for(;*++v;) for save the first 4 and then insted of if(t<p)P"}{");if(t>p)P"{",n++); use t>p?P"}{"):P"{",n++); for 10 more. \$\endgroup\$ – Giacomo Garabello Jul 11 '16 at 13:20
1
\$\begingroup\$

CJam, 51 49 48 46 bytes

Exploits the fact that the number of last bracket is one more than number of adjacent pair that is increasing in array.

And I don't know ew operator before that I had to reimplement.

The input is space separated list delimited by square brackets.

'[q~_W=\2ew_{~\_@-g)["["S"]["]=}%@@{~>M']?}%']

Explanation

'[q~_W=\2ew_{~\_@-g)["["S"]["]=}%@@{~>M']?}%']
'[                                             e# Opening bracket
  q~                                           e# Read the input
    _W=\2ew                                    e# Save the last item and turn array into array of pair of next item and the item itself.
            _                                  e# We need two copies of that item                                       
             {~\_@-g)["["S"]["]=}%             e# Build the "body" that consist of the item and the suitable delimiter, space if equal, opening brace if the first item is the smallest, otherwise, closing bracket and opening bracket.
                                  @@           e# Put in the last item. (It was omitted in previous phase)
                                    {~<']""?}% e# Create the closing bracket as many as the number of increasing adjacent pair
                                               '] e# And one more bracket.

I will find out how to do this with actual nested array instead of relying on prettyprinting.

Finally, at par with beaten MATL's answer.

\$\endgroup\$
  • \$\begingroup\$ Finally, beaten MATL's answer Not now :-P \$\endgroup\$ – Luis Mendo Jul 1 '16 at 14:36
  • \$\begingroup\$ @LuisMendo Ugh. \$\endgroup\$ – Akangka Jul 1 '16 at 15:01
1
\$\begingroup\$

Retina, 71 70 bytes

Lists are space separated, with curly braces: {1 2 3}. Negative numbers are not supported, so if that's a problem, I'll just delete my answer. Retina + negative numbers = not worth it.

\d+
$*
+`\b(1+) (1+\1\b.*)
$1 {$2}
+`\b(1(1+)1*) (\2)\b
$1} {$2
1+
$.0

Try it online

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

JavaScript (ES6), 73 bytes

a=>a.map(r=>l-r?(n=l<r?m:n).push(m=[l=r]):m.push(l),l=a[0],o=n=[m=[]])&&o

Explanation: The case of consecutive equal items is easy; the item is just added to the innermost array (here represented by the m variable; n is the array that contains m as its last element, while o is the output). For the case of different items, the item always goes in a new innermost array, the only difference being whether that array is a sibling or a child of the previous innermost array. For extra golfiness I set up the arrays so that the initial item counts as a consecutive equal item.

\$\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.