Sample solution and discussion for Perl "Easy" Quiz #2005-3, print_list [posted as 2005-2]

The problem was originally stated as follows:

 - - -

Write a subroutine called print_list that takes a number indicating
the width of the display as a number of characters, and a list of
strings, and prints the strings in a sorted columnar display, using as
many columns that will fit in the display for the given list.

The longest string in one column should appear exactly two spaces away
from the beginning of the next column.  (The columns are not
necessarily the same width.)

Each column should include consecutive elements in the sorted list,
such that the item following the last item in column 1 appears at the
top of column 2, and similarly for the remaining columns.

For example, given:

 @strings = qw(Jonathan Sam Abby Daniel Julia Terrence Constance Al);

print_list(30, @strings) prints:

 Abby       Daniel    Sam
 Al         Jonathan  Terrence
 Constance  Julia

print_list(40, @strings) prints:

 Abby  Constance  Jonathan  Sam
 Al    Daniel     Julia     Terrence

print_list(80, @strings) prints:

 Abby  Al  Constance  Daniel  Jonathan  Julia  Sam  Terrence

And print_list(1, @strings) prints:

 Abby
 Al
 Constance
 Daniel
 Jonathan
 Julia
 Sam
 Terrence

For a real world example of a similar display, see the Unix/Linux
command, 'ls'.  For an example of how to determine the actual width of
a terminal window in characters, see the Perl Cookbook, 1st or 2nd
edition, recipe 15.4.

 - - -

If the columns were to be of equal size, the algorithm for printing a list
of strings in columns would be mostly straightforward: determine the
length of the longest string, add a couple of spaces for a gap, divide the
column width into the display width (and round down) to determine the
number of columns, then divide that number into the number of items (and
round up) to determine the number of rows.  For each row, print a value
for each column, if there is one: $item[column * colheight + row]  Here's
ten items in three columns:

 1  5  9
 2  6  10
 3  7
 4  8

This quiz included a requirement that a given column be only two spaces
wider than its widest element, so the columns are not necessarily the same
width.  This means we have to be a bit more thorough about how we fit our
strings into columns, because how the strings are distributed among the
columns affects the column widths and the number of columns that can fit
in the display.

The following solution tries to fit strings to columns starting with the
fewest possible number of columns, then re-calculating column widths
adding one column at a time until the total width exceeds the display
width.  There's a special case we have to deal with using this approach,
when the number of items cannot fill all of the requested columns in an
iteration, even though the ideal fit may require additional columns.  For
example, an attempt to fill 5 columns with 8 elements inevitably uses a
column length of 2, which leaves the fifth column empty.  It may still be
possible to fit all 8 elements on one row, so the loop skips column counts
that leave columns empty but continues adding columns.

 1  3  5  7  ?? ?? ??
 2  4  6  8  ?? ?? ??

 1  2  3  4  5  6  7  8

 - - -

#!/usr/bin/perl

use warnings;
use strict;

sub print_list {
    my ($width, @strings) = @_;

    # Treat zero elements and one element as special cases.
    return if (!@strings);
    if (scalar(@strings) == 1) {
        print $strings[0], "\n";
        return;
    }

    # Sort.  I chose alphabetical sort for this implementation.
    @strings = sort { lc($a) cmp lc($b) } @strings;

    # Precalculate the lengths of the items, because we'll be referring to
    # them frequently.
    my @lengths = map { length($_) } @strings;

    # Determine the number of columns and their widths.
    my $colcount;
    my @last_colwidths = ();

    # The loop considers possible column counts from 2 to the width of the
    # display divided by 3 (the most possible columns if all strings are
    # one character and our column gap is two spaces).  If the length of
    # the longest item (plus 2) is wider than half the display, the loop
    # exits immediately and a one-column list is treated as a special case.
    for ($colcount = 2; $colcount < int($width/3); $colcount++) {

        # Calculate the maximum column length for the given column count.
        my $collength = int(scalar(@strings) / $colcount)
            + (scalar(@strings) % $colcount > 0);

        # Catch a special case where filling the columns with the items
        # leaves a column empty, which is possible even if the ideal fit
        # requires more columns.
        next if !defined($lengths[($colcount-1) * $collength]);

        # Determine the column widths for this configuration, based on the
        # element lengths.
        my @colwidths = ();
        my $linelength = 0;
        for (my $col = 0; $col < $colcount; $col++) {
            my $longest = 0;
            for (my $row = 0; $row < $collength; $row++) {
                 $longest = $lengths[$col * $collength + $row]
                    if (defined($lengths[$col * $collength + $row])
                        && $lengths[$col * $collength + $row] > $longest);
            }
            $colwidths[$col] += $longest;
            # Include a 2-space gap if this is not the rightmost column.
            $colwidths[$col] += 2
                if ($col != $colcount - 1);
            $linelength += $colwidths[$col];
        }

        if ($linelength > $width) {
            # We've outgrown the display with too many columns, go back
            # one and exit the loop.  Our previous column widths are
            # either stored in @last_colwidths, or two columns was too
            # much and we're using only one column (a special case).
            $colcount--;
            last;

        } elsif ($colcount == scalar(@strings)) {
            # Quit early if every element has its own column (all the
            # elements fit on one row).
            @last_colwidths = (@colwidths);
            last;

        } else {
            # We have a fit, so remember these widths and see if we can do
            # better with one more column.
            @last_colwidths = (@colwidths);
        }
    }

    if (!@last_colwidths) {
        # If the loop quit on its first iteration without remembering
        # column widths, then only one column would fit.  Print the list,
        # one item to a line.
        print join("\n", @strings), "\n";

    } else {
        # Print the columnar list using the widths we calculated.
        my $collength = int(scalar(@strings) / $colcount)
            + (scalar(@strings) % $colcount > 0);
        for (my $row = 0; $row < $collength; $row++) {
            for (my $col = 0; $col < $colcount; $col++) {
                my $i = $col * $collength + $row;
                if ($i <= $#strings) {
                    print $strings[$i];
                    print ' ' x ($last_colwidths[$col] - $lengths[$i])
                        if ($col != $colcount-1);
                }
            }
            print "\n";
        }
    }
}

# A few simple tests.
my @strings = qw(Jonathan Sam Abby Daniel Julia Terrence Constance Al);
print_list(1, @strings);
print_list(30, @strings);
print_list(40, @strings);
print_list(80, @strings);

print_list(10, ());
print_list(10, ("Hello"));
print_list(10, ("Hello there my friend"));
print_list(10, ("Hello there my friend", "How are you?", "I am fine thanks"));
print_list(40, ("Hello there my friend", "How are you?", "I am fine thanks"));

__END__

-- Dan