You are given an array `@A`

of items (integers say, but they can be anything).

Your task is to pack that array into an `MxN`

matrix spirally counterclockwise, as tightly as possible.

‘Tightly’ means the absolute value `|M-N|`

of the difference has to be as small as possible.

## Examples

### Example 1

```
Input: @A = (1, 2, 3, 4)
Output:
4 3
1 2
```

Since the given array is already a 1×4 matrix on its own, but that’s not as tight as possible. Instead, you’d spiral it counterclockwise into the given output.

### Example 2

```
Input: @A = (1 .. 6)
Output:
6 5 4
1 2 3
or
5 4
6 3
1 2
```

### Example 3

```
Input: @A = (1 .. 12)
Output:
9 8 7 6
10 11 12 5
1 2 3 4
or
8 7 6
9 12 5
10 11 4
1 2 3
```

## Notes

The challenge defines tightly purely based on size of the initial array — lengths of the elements do not have to be taken into account. This is clear from the third example, the first solution takes an area of 30 characters (3 lines of 10 characters), the second takes an area of 28 characters (4 lines of 7 characters), yet both are acceptable.

# Solution

## Overview

The task can be broken down into various parts:

- Read in the data, and parse it into individual elements.
- Determine the width and height of the resulting matrix.
- Fill in the resulting matrix
- Print the resulting matrix.

### Read in data

The first sub task is pretty easy. It’s not given how we will be given the array `@A`

; therefore, we assume elements are on the first line of standard input, separated by white space.

### Determine width and height

To determine the width and height, we have to factor `N`

, where `N`

is the number of elements. This typically is a hard problem, exponential in the number of bits of `N`

. But the size of the input is exponential in the number of bit of `N`

anyway — which means that if we use a simple try-everything method, we still don’t exceed linear time (in the size of the input).

What we will do is start with and decrement until . At that moment will be the height of the resulting matrix, and be the width.

### Fill in the matrix

The fill in the matrix, we use a couple of variables: `min_x`

, `max_x`

, `min_y`

, `max_y`

, `x`

, `y`

, and `direction`

. The first four keep track of the minimum/maximum rows and columns of the matrix with have to filled in. `min_x`

and `min_y`

will start off as 0 (or 1 for languages where array indices start at 1). `max_x`

and `max_y`

start off as the height and width (minus 1 for languages where array indices start at 0) of the resulting matrix.

`x`

and `y`

are the coordinates to be filled in next; we start off with `x = max_x`

and `y = min_y`

— the bottom left of the matrix. We head off to the right (for which we use `direction`

to keep track). We now fill in the bottom row of the matrix with the first `W`

elements (where `W`

is the width of the matrix). Each time we fill in an element, we increment `y`

— until we hit the corner. At that moment, our new direction becomes up, and we will now start decrementing `y`

(while keeping `x`

constant). And since we have filled in the bottom row, we decrement `max_x.

We continue this process, filling the matrix one row and column at a time, turning at each corner, until we have filled in the matrix.

### Print the matrix

We will first make a pass over the matrix to determine the width of each column. For each column, we look at each row, and determine the width of the element on that position. We keep track of the maximum of those widths for each column.

Given the widths, it’s easy to print out the matrix, so each column is aligned.

## Perl

We start off by setting some constants for directions:

```
my $RIGHT = 0;
my $UP = 1;
my $LEFT = 2;
my $DOWN = 3;
```

Reading data is easy.

```
my @elements = split ' ' => scalar <>;
```

We can now calculate the necessary height and width:

```
my $h = int sqrt @elements;
for (;@elements % $h;) {
$h --;
}
my $w = @elements / $h;
```

Filling in the matrix, as described above:

```
my $matrix;
my ($min_x, $max_x, $min_y, $max_y) = (0, $h - 1, 0, $w - 1);
my $x = $max_x;
my $y = $min_y;
my $direction = $RIGHT;
foreach my $element (@elements) {
$$matrix [$x] [$y] = $element;
my $turn = 0;
if ($direction == $RIGHT) {
if ($y >= $max_y) {$turn = 1; $x --; $max_x --}
else {$y ++}
}
if ($direction == $UP) {
if ($x <= $min_x) {$turn = 1; $y --; $max_y --}
else {$x --}
}
if ($direction == $LEFT) {
if ($y <= $min_y) {$turn = 1; $x ++; $min_x ++}
else {$y --}
}
if ($direction == $DOWN) {
if ($x >= $max_x) {$turn = 1; $y ++; $min_y ++}
else {$x ++}
}
if ($turn) {
$direction ++;
$direction %= 4;
}
}
```

Find out the width of each column:

```
my @widths = map {my $y = $_;
max map {length $$matrix [$_] [$y]} 0 .. $h - 1}
0 .. $w - 1;
```

Print the matrix:

```
foreach my $row (@$matrix) {
for (my $y = 0; $y < @$row; $y ++) {
my $width = $widths [$y];
printf "%s%${width}s" => $y ? " " : "", $$row [$y];
}
print "\n";
}
```

Find the complete program on GitHub.

## AWK

The AWK solution is very similar to the Perl solution — except that AWK doesn’t have support for 2-D arrays. So, we introduce a method which takes an x and a y coordinate, the width and height of the matrix, and which then returns a single coordinate.

```
function idx (x, y, h, w) {
return x * w + y + 1
}
```

The rest is a straight translation of our Perl solution:

```
BEGIN {
RIGHT = 0
UP = 1
LEFT = 2
DOWN = 3
}
{
#
# Get the data; we're assuming it's one a single line,
# seperated by white space.
#
split ($0, elements)
#
# Find optimal sizes: width w and height h
# We start at the square root, and count downwards till we
# have a divider.
#
n = length (elements)
h = int (sqrt (n))
for (;n % h;) {
h --
}
w = n / h
#
# Fill the matrix, starting from the bottom left
#
min_x = 0
max_x = h - 1
min_y = 0
max_y = w - 1
x = max_x
y = 0
direction = RIGHT
for (i = 1; i <= length (elements); i ++) {
matrix [idx(x, y, h, w)] = elements [i]
turn = 0
if (direction == RIGHT) {
if (y >= max_y) {turn = 1; x --; max_x --}
else {y ++}
}
if (direction == UP) {
if (x <= min_x) {turn = 1; y --; max_y --}
else {x --}
}
if (direction == LEFT) {
if (y <= min_y) {turn = 1; x ++; min_x ++}
else {y --}
}
if (direction == DOWN) {
if (x >= max_x) {turn = 1; y ++; min_y ++}
else {x ++}
}
if (turn) {
direction ++
direction %= 4
}
}
#
# Find the max widths for each columns.
#
for (y = 0; y < w; y ++) {
max = 0;
for (x = 0; x < h; x ++) {
l = length (matrix [idx(x, y, h, w)])
if (l > max) {
max = l
}
}
widths [y + 1] = max
}
#
# Print the matrix, with each column outlined
#
for (x = 0; x < h; x ++) {
for (y = 0; y < w; y ++) {
width = widths [y + 1]
format = "%s%" width "s"
printf (format, y == 0 ? "" : " ", matrix [idx(x, y, h, w)])
}
printf ("\n")
}
}
```

Find the complete program on GitHub.

## Bash

Bash does not have 2-D arrays either, so we use an index function like we did with AWK:

```
function idx () {
index=$(($1 * $4 + $2))
}
```

Note that in Bash, functions don’t return anything, so we use a global variable, `index`

to return the index. Bash function also don’t use parameter names — instead it uses positional variables for the input parameter.

Another thing Bash lacks is arithmetic for floating point numbers, so we lack a `sqrt`

method. Instead of counting down, we count up, and keep track of the largest proper divisor of the size of the input array:

```
read -a elements
height=1
n=${#elements[*]}
for ((h = 2; h <= n / h; h ++))
do if ((!(n % h)))
then height=$h
fi
done
width=$((n / height))
```

Note the use of `(( ))`

and `$(( ))`

; this is how we do arithmetic in Bash.

We can now fill in the matrix:

```
RIGHT=0
UP=1
LEFT=2
DOWN=3
declare -a matrix
min_x=0
max_x=$((height - 1))
min_y=0
max_y=$((width - 1))
x=$max_x
y=$min_y
direction=$RIGHT
for ((i = 0; i < n; i ++))
do idx $x $y $height $width
matrix[$index]=${elements[$i]}
turn=0
if ((direction == RIGHT))
then if ((y >= max_y))
then turn=1; ((x --)); ((max_x --))
else ((y ++))
fi
fi
if ((direction == UP))
then if ((x <= min_x))
then turn=1; ((y --)); ((max_y --))
else ((x --))
fi
fi
if ((direction == LEFT))
then if ((y <= min_y))
then turn=1; ((x ++)); ((min_x ++))
else ((y --))
fi
fi
if ((direction == DOWN))
then if ((x >= max_x))
then turn=1; ((y ++)); ((min_y ++))
else ((x ++))
fi
fi
if ((turn == 1))
then ((direction ++))
((direction %= 4))
fi
done
```

Finding the columns widths and printing the results:

```
declare -a widths
for ((y = 0; y < width; y ++))
do max=0
for ((x = 0; x < height; x ++))
do idx $x $y $height $width
element=${matrix[$index]}
if ((max < ${#element}))
then max=${#element}
fi
done
widths[$y]=$max
done
```

```
for ((x = 0; x < height; x ++))
do for ((y = 0; y < width; y ++))
do idx $x $y $height $width
if ((y))
then printf " "
fi
printf %${widths[$y]}s ${matrix[$index]}
done
echo
done
```

Find the complete program on GitHub.

## C

C requires more work, as we need to do the memory allocation ourselves. While we can read in our array of data and have it split on whitespace in a single line of code in many languages, we need a lot more code in C:

```
int main (void) {
char * line = NULL;
size_t len = 0;
size_t line_len;
while ((line_len = getline (&line, &len, stdin)) != -1) {
/*
* Count the number of elements, so we know how much to allocate.
*/
size_t count = 0;
for (size_t i = 1; i <= line_len; i ++) {
if (isspace (line [i]) && !isspace (line [i - 1])) {
count ++;
}
}
/*
* Allocate memory for elements
*/
char ** elements;
if ((elements = (char **) malloc (count * sizeof (char *))) == NULL) {
perror ("Failed to malloc 'elements'");
exit (1);
}
/*
* Iterate over the string again; now find the beginning
* of all the 'words', and allocate them to the elements
* array; make every space a NUL character, so each element
* is terminated.
*/
size_t c = 0;
for (size_t i = 0; i < line_len; i ++) {
if (!isspace (line [i]) && (!i || !line [i - 1])) {
elements [c ++] = line + i;
}
if (isspace (line [i])) {
line [i] = '\0';
}
}
```

Calculate the size of the resulting matrix, and allocate memory for it:

```
/*
* Determine the width and height of the resulting matrix
*/
size_t height = (size_t) floor (sqrt (count));
for (;count % height;) {
height --;
}
size_t width = count / height;
/*
* Allocate memory for the resulting matrix
*/
char *** matrix;
if ((matrix = (char ***) malloc (height * sizeof (char **))) == NULL) {
perror ("Failed to malloc 'matrix'");
exit (1);
}
for (size_t x = 0; x < height; x ++) {
if ((matrix [x] = (char **) malloc
(width * sizeof (char *))) == NULL) {
perror ("Failed to malloc row for 'matrix'");
exit (1);
}
}
```

Filling in the matrix:

```
# define RIGHT 0
# define UP 1
# define LEFT 2
# define DOWN 3
short direction = RIGHT;
size_t min_x = 0;
size_t max_x = height - 1;
size_t min_y = 0;
size_t max_y = width - 1;
size_t x = max_x;
size_t y = min_y;
for (size_t i = 0; i < count; i ++) {
matrix [x] [y] = elements [i];
bool turn = false;
if (direction == RIGHT) {
if (y >= max_y) {turn = true; x --; max_x --;}
else {y ++;}
}
if (direction == UP) {
if (x <= min_x) {turn = true; y --; max_y --;}
else {x --;}
}
if (direction == LEFT) {
if (y <= min_y) {turn = true; x ++; min_x ++;}
else {y --;}
}
if (direction == DOWN) {
if (x >= max_x) {turn = true; y ++; min_y ++;}
else {x ++;}
}
if (turn) {
direction ++;
direction %= 4;
}
}
```

Determine width of each column, and print the matrix:

```
/*
* Determine the width of each column.
*/
size_t * widths;
if ((widths = (size_t *) malloc (width * sizeof (size_t))) == NULL) {
perror ("Failed to malloc 'widths'");
exit (1);
}
for (size_t y = 0; y < width; y ++) {
size_t max = 0;
for (size_t x = 0; x < height; x ++) {
if (max < strlen (matrix [x] [y])) {
max = strlen (matrix [x] [y]);
}
}
widths [y] = max;
}
/*
* Print out the matrix
*/
char format [15]; /* We can safely assume no element from the
* input is longer than 2^32 characters wide.
* (And (size_t) -1 on our box is 2^32 - 1 anyway.)
* '%s%Ws' is hence at most 15 characters, if
* W does not exceed 10 characters, and there is
* a terminating NUL character */
for (size_t x = 0; x < height; x ++) {
for (size_t y = 0; y < width; y ++) {
sprintf (format, "%%s%%%zus", widths [y]);
printf (format, y ? " " : "", matrix [x] [y]);
}
printf ("\n");
}
```

As this is C, we need to free up the memory we allocated:

```
free (widths);
for (size_t x = 0; x < height; x ++) {
free (matrix [x]);
}
free (matrix);
free (elements);
}
free (line);
```

Find the complete program on GitHub.

## Lua

```
local line = io . read ()
local elements = {}
for element in line : gmatch ("%S+") do
elements [#elements + 1] = element
end
--
-- Calculate the optimal width and height
--
local height = math . floor (math . sqrt (#elements))
while #elements % height > 0 do
height = height - 1
end
local width = #elements / height
--
-- Fill the matrix, starting from the bottom left
--
local min_x = 1
local max_x = height
local min_y = 1
local max_y = width
local x = max_x
local y = min_y
local direction = RIGHT
--
-- Initialize the matrix
--
local matrix = {}
for x = 1, height do
matrix [x] = {}
end
for i = 1, #elements do
matrix [x] [y] = elements [i]
local turn = 0
if direction == RIGHT
then if y >= max_y
then turn = 1
x = x - 1
max_x = max_x - 1
else y = y + 1
end
end
if direction == UP
then if x <= min_x
then turn = 1
y = y - 1
max_y = max_y - 1
else x = x - 1
end
end
if direction == LEFT
then if y <= min_y
then turn = 1
x = x + 1
min_x = min_x + 1
else y = y - 1
end
end
if direction == DOWN
then if x >= max_x
then turn = 1
y = y + 1
min_y = min_y + 1
else x = x + 1
end
end
if turn > 0
then direction = (direction + 1) % 4
end
end
--
-- Find the maximum widths in each column
--
local widths = {}
for y = 1, width
do local max = 0
for x = 1, height
do if max < #matrix [x] [y]
then max = #matrix [x] [y]
end
end
widths [y] = max
end
--
-- Pretty print the matrix
--
for x = 1, height
do for y = 1, width
do if y > 1
then io . write (" ")
end
local format = "%" .. widths [y] .. "s"
io . write (string . format (format, matrix [x] [y]))
end
io . write ("\n")
end
```

Find the complete program on GitHub.

## Node.js

Find the complete program on GitHub.

## Python

Find the complete program on GitHub.

## Ruby

Find the complete program on GitHub.