Perl Weekly Challenge 101: Pack a Spiral

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:

  1. Read in the data, and parse it into individual elements.
  2. Determine the width and height of the resulting matrix.
  3. Fill in the resulting matrix
  4. 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 h = \lfloor \sqrt{N}\rfloor and decrement h until N \mod h = 0. At that moment h will be the height of the resulting matrix, and N / h 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s