TextEditor
SRM 171 · 2003-11-12 · by Running Wild
SRM 171 · 2003-11-12 · by Running Wild · String Manipulation
Problem Statement
Problem Statement
You have a page of text that is nicely formatted in the usual fashion (like this text), but you wanted it formatted in two columns, like a magazine. Given a String[] text, and an int width, return a String[] which is the same text but formatted such that every element contains as many words as possible without being more than width characters long. Begin by putting as many words as possible in the first line of the first column without using more than width characters, then continue this for each subsequent line. The elements of the return value should be organized such that every pair of elements corresponds to one line of text, spread over two columns. Thus element 2*i and 2*i+1 (with i starting at 0) of the output will represent the i-th line of the first and second columns, respectively. If the last line of the second column has no text, do not include it as part of the return value (see example 0). Do not hyphenate words to fit them on two lines. Also, there should only be a single space between adjacent words, and there should be no leading or trailing spaces in the lines. A 'word' is a sequence of non-space characters that does not have non-space characters immediately before or after it. Punctuation marks should be treated the same as other characters. For example, "Hello,Fred", "Hello,I'mFred", and "...!?!?" are all considered to be single words, and should not be broken apart in any way.
For example, if text={"This text is now ","in two columns."} and width=7, the output would be {"This", "two", "text is", "columns.", "now in"}. Making the first element of the return value the first line of the first column, the next element the first line of the second column, and then continuing in the same way for subsequent rows, the text looks like this:
For example, if text={"This text is now ","in two columns."} and width=7, the output would be {"This", "two", "text is", "columns.", "now in"}. Making the first element of the return value the first line of the first column, the next element the first line of the second column, and then continuing in the same way for subsequent rows, the text looks like this:
"This" "two" "text is" "columns." "now in"
Constraints
- text will contain between 1 and 50 elements, inclusive.
- width will contain between 1 and 50, inclusive.
- Each element of text will be between 1 and 50 characters, inclusive.
- Each element of text will contain only upper and lower-case letters ('a'-'z','A'-'Z'), digits ('0'-'9'), spaces, and the characters ".,;:?!". Quotes and parentheses in all cases are for clarity only.
- No element of text will contain a string of non-space characters longer than width.
Examples
0)
{"The quick brown fox jumps over the lazy dog. "}
7
Returns: { "The", "over", "quick", "the", "brown", "lazy", "fox", "dog.", "jumps" }
Only one word can fit per line. Making two columns with this output looks like this: "The", "over", "quick","the", "brown","lazy", "fox", "dog.", "jumps"
1)
{" WOLF, meeting with a Lamb astray from the fold,","resolved not to lay violent hands on him, but to","find some plea to justify to the Lamb the Wolfs","right to eat him. He thus addressed him: Sirrah,","last year you grossly insulted me. Indeed,","bleated the Lamb in a mournful tone of voice, I","was not then born. Then said the Wolf, You feed","in my pasture. No, good sir, replied the Lamb,","I have not yet tasted grass. Again said the","Wolf, You drink of my well. No, exclaimed the","Lamb, I never yet drank water, for as yet my","mothers milk is both food and drink to me. Upon","which the Wolf seized him and ate him up, saying,","Well! I wont remain supperless, even though you","refute every one of my imputations. The tyrant","will always find a pretext for his tyranny."}
35
Returns: { "WOLF, meeting with a Lamb astray", "Again said the Wolf, You drink of", "from the fold, resolved not to lay", "my well. No, exclaimed the Lamb, I", "violent hands on him, but to find", "never yet drank water, for as yet", "some plea to justify to the Lamb", "my mothers milk is both food and", "the Wolfs right to eat him. He thus", "drink to me. Upon which the Wolf", "addressed him: Sirrah, last year", "seized him and ate him up, saying,", "you grossly insulted me. Indeed,", "Well! I wont remain supperless,", "bleated the Lamb in a mournful tone", "even though you refute every one of", "of voice, I was not then born. Then", "my imputations. The tyrant will", "said the Wolf, You feed in my", "always find a pretext for his", "pasture. No, good sir, replied the", "tyranny.", "Lamb, I have not yet tasted grass." }
2)
{" AN ASTRONOMER used to go out at night to observe","the stars. One evening, as he wandered through the","suburbs with his whole attention fixed on the sky,","he fell accidentally into a deep well. While he","lamented and bewailed his sores and bruises, and","cried loudly for help, a neighbor ran to the well,","and learning what had happened said: Hark ye, old","fellow, why, in striving to pry into what is in","heaven, do you not manage to see what is on","earth?"}
35
Returns: { "AN ASTRONOMER used to go out at", "sores and bruises, and cried loudly", "night to observe the stars. One", "for help, a neighbor ran to the", "evening, as he wandered through the", "well, and learning what had", "suburbs with his whole attention", "happened said: Hark ye, old fellow,", "fixed on the sky, he fell", "why, in striving to pry into what", "accidentally into a deep well.", "is in heaven, do you not manage to", "While he lamented and bewailed his", "see what is on earth?" }
3)
{" The Law of the Jungle, which never orders","anything without a reason, forbids every beast to","eat Man except when he is killing to show his","children how to kill, and then he must hunt","outside the huntinggrounds of his pack or tribe.","The real reason for this is that mankilling","means, sooner or later, the arrival of white men","on elephants, with guns, and hundreds of brown men","with gongs and rockets and torches. Then everybody","in the jungle suffers. The reason the beasts give","among themselves is that Man is the weakest and","most defenseless of all living things, and it is","unsportsmanlike to touch him. They say too and","it is true that maneaters become mangy, and","lose their teeth."}
15
Returns: { "The Law of the", "hundreds of", "Jungle, which", "brown men with", "never orders", "gongs and", "anything", "rockets and", "without a", "torches. Then", "reason, forbids", "everybody in", "every beast to", "the jungle", "eat Man except", "suffers. The", "when he is", "reason the", "killing to show", "beasts give", "his children", "among", "how to kill,", "themselves is", "and then he", "that Man is the", "must hunt", "weakest and", "outside the", "most", "huntinggrounds", "defenseless of", "of his pack or", "all living", "tribe. The real", "things, and it", "reason for this", "is", "is that", "unsportsmanlike", "mankilling", "to touch him.", "means, sooner", "They say too", "or later, the", "and it is true", "arrival of", "that maneaters", "white men on", "become mangy,", "elephants, with", "and lose their", "guns, and", "teeth." }
4)
{" The Law of the Jungle, which never orders","anything without a reason, forbids every beast to","eat Man except when he is killing to show his","children how to kill, and then he must hunt","outside the huntinggrounds of his pack or tribe.","The real reason for this is that mankilling","means, sooner or later, the arrival of white men","on elephants, with guns, and hundreds of brown men","with gongs and rockets and torches. Then everybody","in the jungle suffers. The reason the beasts give","among themselves is that Man is the weakest and","most defenseless of all living things, and it is","unsportsmanlike to touch him. They say too and","it is true that maneaters become mangy, and","lose their teeth."}
35
Returns: { "The Law of the Jungle, which never", "of brown men with gongs and rockets", "orders anything without a reason,", "and torches. Then everybody in the", "forbids every beast to eat Man", "jungle suffers. The reason the", "except when he is killing to show", "beasts give among themselves is", "his children how to kill, and then", "that Man is the weakest and most", "he must hunt outside the", "defenseless of all living things,", "huntinggrounds of his pack or", "and it is unsportsmanlike to touch", "tribe. The real reason for this is", "him. They say too and it is true", "that mankilling means, sooner or", "that maneaters become mangy, and", "later, the arrival of white men on", "lose their teeth.", "elephants, with guns, and hundreds" }
13)
{"Such a preposterous use of !punctuation! !!!","Who would write ... something like this ???"}
17
Returns: { "Such a", "write ...", "preposterous use", "something like", "of !punctuation!", "this ???", "!!! Who would" }
Remember not to treat punctuation marks any differently than other characters.
19)
{" Forsaking monastic tradition, twelve jovial",
" friars gave up their vocation for a questionable",
" existence on the flying trapeze. "}
25
Returns: { "Forsaking monastic", "vocation for a", "tradition, twelve jovial", "questionable existence on", "friars gave up their", "the flying trapeze." }
All leading, trailing, and extra whitespace is ignored.
Submissions are judged against all 34 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TextEditor with a public method vector<string> twoColumn(vector<string> text, int width) · 34 test cases · 2 s / 256 MB per case