Unix ls Column Formatting

Time limit1sMemory limit128 MB

Summary

Sort filenames by ASCII value and lay them out in column-major order with fixed-width padding, as few rows as fit in 60 characters.

Level: Easy3 of 10
Topics: Sorting, Implementation, Simulation, String
Solved: No attempts yet

Problem

You are given a list of filenames. Sort the list in ascending order by ASCII character value, then, like the Unix ls command, arrange and print the names in several columns.

Each filename is between 1 and 60 characters long. Let $L$ be the length of the longest filename. The output follows these rules:

Every column is left-justified.
Each filename is printed left-justified in a field of width $L+2$ . This padding applies to every column, including the last one, so each output line ends with trailing spaces.
The number of columns $C$ that fit on a line is the largest value satisfying $(C-1)\times(L+2) + L \le 60$ ; that is, even the last column's actual content width $L$ must fit within 60 characters.
Use as few rows $R$ as possible. The sorted filenames fill each column from top to bottom: names $1$ through $R$ go down column 1, names $R+1$ through $2R$ down column 2, and so on.

Input

The input consists of several filename lists. Each list begins with a line containing the count $N$ ( $1 \le N \le 100$ ), followed by $N$ lines that each contain one filename. The entire content of a line is a single filename, 1 to 60 characters long. The only allowed characters are letters (a–z, A–Z), digits (0–9), and ., _, -. There are no illegal characters and no empty lines. Immediately after the last filename comes either the $N$ of the next list or the end of the input. Read and process every list until the input ends.

Output

For each filename list, first print a line of exactly 60 dashes (-), then print the filenames arranged in columns as described above. Filling is column-major: sorted names $1$ through $R$ are listed down column 1, names $R+1$ through $2R$ down column 2, and so on.

Examples3

Example 1

Input

10
long-file-name
the
longest
file
name
short
tiny
abc
mid-length
88888888.333
10
longer_filename
2short4me
another
long
name
12
Weaser
Alfalfa
Stimey
Buckwheat
10
Porky
Joe
Darla
Cotton
Butch
Froggy
Mrs_Crabapple
P.D.
Mr._French
19
10
Buffy
Danny
Jody
Lori
Shirley
Chris
Jan
Keith
Marsha
Sissy
10
Alice
Carol
Greg
Peter
Shirley
Bobby
Cindy
Mike
Ruben
Sissy

Expected output

------------------------------------------------------------
88888888.333    longest         the             
abc             mid-length      tiny            
file            name            
long-file-name  short           
------------------------------------------------------------
12               Stimey           longer_filename  
2short4me        Weaser           name             
Alfalfa          another          
Buckwheat        long             
------------------------------------------------------------
19             Darla          Mr._French     Porky          
Butch          Froggy         Mrs_Crabapple  
Cotton         Joe            P.D.           
------------------------------------------------------------
Buffy    Danny    Jody     Lori     Shirley  
Chris    Jan      Keith    Marsha   Sissy    
------------------------------------------------------------
Alice    Carol    Greg     Peter    Shirley  
Bobby    Cindy    Mike     Ruben    Sissy

Example 2

Input

1
readme.txt

Expected output

------------------------------------------------------------
readme.txt

Example 3

Input

5
beta
alpha
delta
charlie
echo
3
z
y
x

Expected output

------------------------------------------------------------
alpha    beta     charlie  delta    echo     
------------------------------------------------------------
x  y  z