Magnetic Sculptures... in Space!

Question

Background

This is a continuation of my earlier challenge, where the task was to compute the shape of a sculpture obtained by dropping magnets into a huge pile.

Good news: the eccentric artist liked your work, and has another project for you. He still works with magnetic sculptures, but has decided to expand his art studio -- into space! His current method is to blast a single cube-shaped magnet into the orbit, and shoot other magnets at it to create a huge magnetic satellite.

Input

Your input is a finite list of 0s and 1s, given either in the native list format of your language, or a string. It is interpreted as a "blueprint" of a work of art, and is processed in order from left to right as follows.

You start with a single magnet floating at some integer coordinate of the 2D plane, and keep adding more magnets as per the directives. The directive 0 rotates the entire sculpture 90 degrees in the counter-clockwise direction. In the case of the directive 1, the artist finds the leftmost column of the sculpture, and shoots a new magnet to it from below. The new magnet sticks to the bottom-most existing magnet in the column, and becomes a part of the sculpture. Note that the magnet does not stick to other magnets in the neighboring column, unlike in the earlier challenge; its speed is now astronomical!

Output

The artist wants to know whether the complete sculpture will fit into his garage (how he'll get it down from the orbit remains unclear). Thus, your output is the width and height of the sculpture, ordered from lower to higher. They can be given as a two-element list, a pair, or as a string separated by a comma.

Example

Consider the input sequence

[1,0,1,1,0,1,0,0,1,1]

To process it, we start with one magnet floating in space:

#

The first directive is 1, so we shoot a new magnet from below:

#
#

The next directive is 0, so we rotate the sculpture:

##

The next two directives are 1,1, which means we'll shoot two magnets to the leftmost column:

##
#
#

Then, we rotate again and shoot once, as directed by 0,1:

#
###
#

Finally, we rotate twice and shoot twice:

  #
###
# #
#

The resulting sculpture has width 3 and height 4, so we output [3,4].

Rules

You can give either a function or a full program. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

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

Answer 1

Pyth: 34 33 bytes

Sml{dCuS?+G,hhGtehGHm,_ekhkGQ],ZZ

Input is a list of ones and zeros, like in the question. Try it online: Pyth Compiler/Executor

Explanation:

It's a one-on-one translation of the following Python 2 code (126 bytes).

print sorted(map(len,map(set,zip(*reduce(lambda s,i:([[-b,a]for a,b in s],s+[[min(s)[0],min(s)[1]-1]])[i],input(),[[0,0]])))))

I create a list of coordinates of the single magnets. This is initialized with the magnet [0,0]. Then for each of the integers of the blueprint I manipulate the list in the following way. If the next integer is 0, I rotate the sculpture by changing the coordinates for each magnet [a,b] to [-b,a] (basically multiplying with a rotation matrix). If the next integer is a 1, I search for the minimal piece [a,b] (which is automatically the lowest magnet of the leftmost column) and append the magnet [a,b-1] to the list.

After all the input is processed, I create 2 sets (for removing duplicates), one for the x-values and one for the y values, and print the sizes of them in sorted order.

Sml{dCuS?+G,hhGtehGHm,_ekhkGQ],ZZ
                             ],ZZ  starting list G=[(0,0)]
      u                     Q],ZZ  for H in input(): manipulate G
       S                              Sort G after each manipulation
        ?          H                  G = ... if H==1 else ...
                    m,_ekhkG            [(-b,a) for a,b in G)] (rotate)
         +G,hhGtehG                     G+[(G[0][0],G[0][1]-1)]
                                        (G[0] is the lowest magnet in the leftmost column)
     C                             Zip the coords together
                                    (creates 2 lists, x- and y-coords)
 ml{d                              for each of those list compute number of unique values
S                                  sort and print

An idea for improvement: Using complex numbers as coords for the magnets. A rotation is just a multiplication by j and subtracting j from the lowest magnet in the leftmost column. Sadly finding this lowest leftmost magnet takes way too many chars in Python, not even talking of finding the rectangle.

Answer 2

CJam, 48 bytes

S]l~{{)S/);Sa+S*a+_z,f{_N*@\+<}}{zW%}?}/_,\z,]$p

Test it here.

Expects input as a CJam-style array (i.e. spaces instead of commas) and will present the output similarly. If you want to use the test cases from the question directly, copy them straight into the input field (include the -> and results) and use this test harness, which converts the lines to the correct input format (and discards the results):

qN/{S/0=","Ser}%{[

S]\~{{)S/);Sa+S*a+_z,f{_N*@\+<}}{zW%}?}/_,\z,]$p

}/

Explanation

I'm just implementing the rules very literally. I'm keeping a grid with the current sculpture (as an array of strings), and then for each instruction I either rotate the grid, or I add a new block. The main tricks to save bytes are:

• Add to the bottom row from the right. This is completely equivalent. I'm just one rotation ahead, and since the grid starts out rotationally invariant, that doesn't matter.
• Use a space to represent occupied blocks and a newline character to represent empty blocks. So if you actually printed out the grid you wouldn't see a whole lot and it wouldn't even look rectangular. I'm doing this, because most array-based operators only do what you want if the grid element in question is wrapped in an array. And with S and N I have access to strings containing the space and newline character (i.e. the character wrapped in an array), instead of having to use, say, 1a and 0a to get an array containing a number.

Let's go through the code:

"Overall program structure:";
S]l~{{...}{...}?}/_,\z,]$p
S]                         "Push a string with a space and wrap it in an array.
                            This is the initial grid containing a single block.";
  l~                       "Read the input and evaluate it.";
    {           }/         "For each instruction in the input...";
     {...}{...}?           "Execute the first block if it's 1, the second if it's 0.";
                  _,       "Duplicate the resulting grid and get its length. This
                            is one of the dimensions.";
                    \      "Swap with the other copy of the grid.";
                     z,    "Zip/transpose it and get its length. This is the other
                            dimension of the grid.";
                       ]$p "Wrap both in an array, sort them, and print the result.";

"The rotation block is simple. A rotation is equivalent to two reflection operations
 along different axes. The simplest ones available are to transpose the grid (which
 is a reflection about the diagonal) and reversing the rows (which is a reflection
 about the horizontal). In CJam these are z for zip/tranpose and W% for reversing
 an array. So I simply put these together in the right order to get a counter-
 clockwise rotation:";
zW%

"Now the interesting part, adding new blocks and growing the grid. This part consists
 of two steps: appending a block to the rightmost block in the bottom row (allowing
 for empty blocks after it). And then potentially padding the rest of the grid with
 new empty cells if the bottom row got longer.";
)S/);Sa+S*a+_z,f{_N*@\+<}
)                         "Split off the bottom row.";
 S/                       "Split the row on occupied blocks.";
   );                     "Split off the final substring - this discards trailing
                           empty cells.";
     Sa+                  "Add a new substring containing an occupied block to the row.";
        S*                "Join all substrings together with spaces, putting back in
                           all the occupied blocks.";
          a+              "Wrap it in an array to add the row back onto the grid.";

 "At this point we need to make sure the grid is still rectangular. The easiest way
  (I found) is to find the maximum row length, add that many empty blocks to each 
  line and then truncate the lines to that length.";

            _             "Duplicate the grid.";
             z,           "Zip/transpose it and get the length. This is the length
                           of the longest row in a ragged array.";
               f{       } "Map this block onto each row, passing in the target length.";
                 _N*      "Duplicate the target length and get a string of that many
                           empty cells.";
                    @\    "Pull up the row and then swap it with those empty cells.";
                      +   "Add the empty cells to the end of the row.";
                       <  "Truncate to the target length.";

Answer 3

Matlab (92)

S=1;for d=input(''),if d,S(find(S(:,1),1,'last')+1,1)=1;else,S=rot90(S);end;end,sort(size(S))

Standard input is used. Data should be introduced in the form [1,0,1,1,0,1,0,0,1,1].

Ungolfed:

S = 1; %// initial magnet
for d = input('') %// get directives, and pick them sequentially
    if d %// if directive is 1
        S(find(S(:,1),1,'last')+1,1) = 1; %// add 1 after lowest 1 in column 1. Grow if needed
    else %// if directive is 0
        S = rot90(S); %// rotate counterclockwise. Handy Matlab built-in function
    end
end
sort(size(S)) %// display size sorted

Example run:

>> clear all
>> S=1;for d=input(''),if d,S(find(S(:,1),1,'last')+1,1)=1;else,S=rot90(S);end;end,sort(size(S))
[1,0,1,1,0,1,0,0,1,1]
ans =
     3     4

Answer 4

Python - 211

import numpy as n
p=input()
q=len(p)
a=n.zeros([2*q+1]*2)
a[q,q]=1
for i in p:
 if i:x=a[:,n.where(a.any(0))[0][0]];x[len(x)-n.where(x[::-1])[0][0]+1]=1
 else:a=n.rot90(a)
z=a[:,a.any(1)]
print z[a.any(0)].shape

Answer 5

CJam, 47 bytes

1]]q~{{0f+(W%_1#(1tW%a\+z{1b},}{W%}?z}/),\,)]$p

This takes CJam styled (space separated instead of comma) array input from STDIN and prints the result to STDOUT.

Example:

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

gives

[3 3]

output.

Explanation to follow after I am convinced that this cannot be golfed further.

Try it online here