Statistics

Problem Statement for "Lister"

Problem Statement

A listing of names can be arranged in rows and columns to make it compact. We want our listing to be arranged alphabetically in column major order (e.g. the first column should have all the earliest words in the list). Words should be left justified within their column. Each column has a fixed width, which may differ from the width of other columns. Each row should have a name in each column, except the last row, which may have no names in its final column(s).

Our list will be printed out row by row, with spaces inserted to position the names within each row properly. Each row must contain exactly pageWidth characters (including spaces). In order to avoid run-together, we require that only spaces can appear in the print position just prior to the start of a column. This applies even to the last row (where the final columns may contain no names).

Create a class Lister that contains a method doList that is given pageWidth and a String[] names and that returns the optimal listing as a String[] giving the rows to be printed (in order from top to bottom). Each element in the return should contain exactly pageWidth characters. Use the space character ' ' in your listing to position the names within each row (and to pad each row to pageWidth characters).

A listing is "optimal" if it has as few rows as possible. Among listings with the minimal number of rows, choose the one whose rightmost non-space character is as far to the left as possible. If multiple listings are still equally "optimal" choose the one with the fewest columns.

Definition

Class:
Lister
Method:
doList
Parameters:
int, String[]
Returns:
String[]
Method signature:
String[] doList(int pageWidth, String[] names)
(be sure your method is public)

Constraints

  • pageWidth will be between 10 and 80 inclusive.
  • names will contain between 1 and 50 elements inclusive.
  • Each element of names will contain between 1 and pageWidth characters inclusive.
  • Each element of names will contain only lowercase letters 'a'-'z'.

Examples

  1. 10

    {"bob","abernathy","x"}

    Returns: { "abernathy ", "bob ", "x " }

    Any column containing "abernathy" cannot be adjacent to another column since even a one-character name would be too much to avoid run-together and fit on the page (spaces shown as '.'): abernathy. bob....... x.........

  2. 11

    {"bob","abernathy","x"}

    Returns: { "abernathy x", "bob " }

    There is just enough page width to get abernathy and x on the same row and keep them from running together, producing the following listing (spaces shown as '.'): abernathy.x bob........

  3. 10

    {"bob","a","x"}

    Returns: { "a bob x " }

  4. 10

    {"a","b","a","c","d","ab","e","f","g"}

    Returns: { "a ab c e g", "a b d f " }

  5. 18

    {"a","b","a","c","d","ab","e","f","g"}

    Returns: { "a a ab b c d e f g" }

  6. 17

    {"a","b","a","c","d","ab","e","f","g"}

    Returns: { "a ab c e g ", "a b d f " }

  7. 10

    {"x","teddy","andy"}

    Returns: { "andy x ", "teddy " }

    Note that there are 2 spaces between "andy" and "x" in the listing. It would be illegal to have only 1 space, since then the 'y' in "teddy" would occupy the print position just prior to the second column of names (spaces shown as '.'): andy..x... teddy.....

  8. 10

    {"aaaaaaaaaa","bbbbbbbbbb","cccccccccc","dddddddddd", "eeeeeeeeee","ffffffffff","gggggggggg","hhhhhhhhhh"}

    Returns: { "aaaaaaaaaa", "bbbbbbbbbb", "cccccccccc", "dddddddddd", "eeeeeeeeee", "ffffffffff", "gggggggggg", "hhhhhhhhhh" }

  9. 21

    {"aaaaaaaaaa","bbbbbbbbbb","cccccccccc","dddddddddd", "eeeeeeeeee","ffffffffff","gggggggggg","hhhhhhhhhh"}

    Returns: { "aaaaaaaaaa eeeeeeeeee", "bbbbbbbbbb ffffffffff", "cccccccccc gggggggggg", "dddddddddd hhhhhhhhhh" }

  10. 32

    {"aaaaaaaaaa","bbbbbbbbbb","cccccccccc","dddddddddd", "eeeeeeeeee","ffffffffff","gggggggggg"}

    Returns: { "aaaaaaaaaa dddddddddd ffffffffff", "bbbbbbbbbb eeeeeeeeee gggggggggg", "cccccccccc " }

  11. 32

    {"aaa","baa","caa","daa","eaa","faa","gaa","haa","iaa","jaa", "kaa","laaaaaaa","maaaaaaa","naa","oaa","paa","qaa","raa", "saa","taa","uaa","vaa","waa","xaa","yaa","zaa","zba","zca", "zda","zea","zfa","zga","zha","zia","zja","zka"}

    Returns: { "aaa gaa laaaaaaa qaa vaa zba zga", "baa haa maaaaaaa raa waa zca zha", "caa iaa naa saa xaa zda zia", "daa jaa oaa taa yaa zea zja", "eaa kaa paa uaa zaa zfa zka", "faa " }

  12. 31

    {"aaa","baa","caa","daa","eaa","faa","gaa","haa","iaa","jaa","kaa","laaaaaaa","maaaaaaa","naa","oaa","paa","qaa","raa","saa","taa","uaa","vaa","waa","xaa","yaa","zaa","zba","zca","zda","zea","zfa","zga","zha","zia","zja","zka"}

    Returns: { "aaa iaa paa waa zea ", "baa jaa qaa xaa zfa ", "caa kaa raa yaa zga ", "daa laaaaaaa saa zaa zha ", "eaa maaaaaaa taa zba zia ", "faa naa uaa zca zja ", "gaa oaa vaa zda zka ", "haa " }

  13. 31

    {"aaa","baa","caa","daa","eaa","faa","gaa","haa","iaa","jaa", "kaa","laaaaaa","maaaaaa","naa","oaa","paa","qaa","raa","saa", "taa","uaa","vaa","waa","xaa","yaa","zaa","zba","zca","zda", "zea","zfa","zga","zha","zia","zja","zka"}

    Returns: { "aaa gaa maaaaaa saa yaa zfa", "baa haa naa taa zaa zga", "caa iaa oaa uaa zba zha", "daa jaa paa vaa zca zia", "eaa kaa qaa waa zda zja", "faa laaaaaa raa xaa zea zka" }

  14. 10

    {"a","jj","d","i","g","b","e","hh","f","c"}

    Returns: { "a d g i ", "b e hh jj ", "c f " }

  15. 18

    {"ebfaeff","efaeca","gd","f","dd","agde","dbfdaefadg","gcaddf","fg","gffb","effcg","dcbggaf","bec","dcgefgefg","gee","eeaec","aacfcf","ed","fdecgggf","a","abefeebgdf","bgbggaacfa","abfaabcbgd","dddgcfdb"}

    Returns: { "a ", "aacfcf ", "abefeebgdf ", "abfaabcbgd ", "agde ", "bec ", "bgbggaacfa ", "dbfdaefadg ", "dcbggaf ", "dcgefgefg ", "dd ", "dddgcfdb ", "ebfaeff ", "ed ", "eeaec ", "efaeca ", "effcg ", "f ", "fdecgggf ", "fg ", "gcaddf ", "gd ", "gee ", "gffb " }

  16. 79

    {"fdfcgac","afb","fe","affdecba","cgcg","afdb","fcbcfagae","abdebcbd", "bge","gfedbgaae","d","dfgfdegcc","dcd","fcb","abcbee","fdggcadaa", "caacbd","ebcbcf","bcgcccfae","ddb","cafed","afbabccc","g","ggcfafda", "geegdcfddc","gaaacdedg","gba","gbdaeebea","agefdcgec","fgcg"}

    Returns: { "abcbee afdb bge d dfgfdegcc fcbcfagae fe gaaacdedg geegdcfddc ", "abdebcbd affdecba caacbd dcd ebcbcf fdfcgac fgcg gba gfedbgaae ", "afb agefdcgec cafed ddb fcb fdggcadaa g gbdaeebea ggcfafda ", "afbabccc bcgcccfae cgcg " }

  17. 29

    {"afbbgcgc","ccd","decgdfcgfg","cf","bfcbged","eebbeffd","ga","abaccg","ga"}

    Returns: { "abaccg ccd decgdfcgfg ga ", "afbbgcgc cf eebbeffd ga ", "bfcbged " }

  18. 34

    {"fdaaagecf","ebb","gd","c","d","fde","edcacbcfd","cbcc","bdabaccace"}

    Returns: { "bdabaccace d edcacbcfd fde ", "c ebb fdaaagecf gd ", "cbcc " }

  19. 39

    {"bbffagg","bbbbfccd","eeedcgfg","d","cg","gbc","g","bbf","gb","d","abcebgee","dded","dfcafggfac","abeb","agee","egbadabfbb"}

    Returns: { "abcebgee bbf d dfcafggfac g ", "abeb bbffagg d eeedcgfg gb ", "agee cg dded egbadabfbb gbc ", "bbbbfccd " }

  20. 35

    {"aee","agc","g","fg","bce","bfaa","gcdbagfdag","cafg","ccad","dbcgfbdcd","de","gfc","caefa","cebacce","ccbdgacbb","gbbfd"}

    Returns: { "aee caefa ccbdgacbb de gbbfd ", "agc cafg cebacce fg gcdbagfdag ", "bce ccad dbcgfbdcd g gfc ", "bfaa " }

  21. 33

    {"g","babec","bafffebe","bffaf", "decdgfgcbc","bacfeddea","g","deecgabcg","c"}

    Returns: { "babec bffaf decdgfgcbc g ", "bacfeddea c deecgabcg g ", "bafffebe " }

  22. 12

    {"a","b","c","d","e","ffff","gggg","h","i"}

    Returns: { "a d ffff h ", "b e gggg i ", "c " }

  23. 12

    {"a","b","c","d","e","fff","gggg","h","i"}

    Returns: { "a d gggg ", "b e h ", "c fff i " }

  24. 18

    { "a", "b", "c", "d", "e", "longword", "longerword", "y", "z" }

    Returns: { "a d longerword y ", "b e longword z ", "c " }

  25. 10

    { "aaaaaaaaaa" }

    Returns: { "aaaaaaaaaa" }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: