Format a list of words

Question

Your challenge is to format a list of words across multiple lines that are no longer than a given number of characters, so that each line contains as many words as possible and no words are unnecessarily cut off.

Input

The input will be a space-separated list of words and then a number that is at least 4.

Output

The output should be the input words grouped into lines so that none of the lines contains more characters than the input number. The words should be output in the order they were input. The words should be separated by a comma and then a space, except at the end of each line, where the space isn't needed. If a word is too long to fit on a line, it should be cut off as little as possible while following the other rules, and "..." should be added to the end.

Test cases

Input:
foo bar baz qux 12

Output:
foo, bar,
baz, qux


Input:
foo bar baz qux 5

Output:
foo,
bar,
baz,
qux


Input:
strength dexterity constitution intelligence wisdom charisma 10

Output:
strength,
dexterity,
consti...,
intell...,
wisdom,
charisma


Input:
quas wex exort 4

Output:
...,
wex,
e...

Answer 1

Unreadable, 2559 bytes

This challenge is eerily suited for Unreadable.

The first version of this was 3379 bytes, just to give you an idea of how much I golfed this.

The program accepts the input exactly as described in the challenge: a space-separated list of words (which may contain digits and punctuation marks, too), followed by a space and an integer that is at least 4 (lower numbers generate infinite loops).

'""""""'""""""""'"""'""'""'""'""'""'""'"""'"""""'""'""""""'""'"""'""""""""""'""""""'""""""'""""""""'"""'""'"""""""'""""""""'"""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'"""""""'""'"""'"""""'"""""""'""""""'""""""""'"""'""""""""'"""""""'""""""""'"""'"""'"""""'"""""""'""""""'""""""""'"""'""'"""""""'""""""""'"""'""""'""""'""""""'""'"""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'""""""""'"""'"""""'""'""""""'""'""'"""'""""""""'"""""""'""'""'"""'""""""'""'"""'""'""'""'""'""'""'""'""'""'""'"""""""'""'"""'""""""'""'""'"""'"""""'""""""'"""""""'""""""""'"""'""""""""'"""""""'"""""""'""""""""'"""'""""""'""'"""'""'"""""""'""'"""'"""""'""""""'""'"""'""""""""'"""""""'""'"""'""""""'""""""'"""'""""""""'"""""""'"""'"""'""""""'""'""'""'""'"""'""'""'""'""'""'""'""'""'""'""'""'""'""""""'""'""'""'""'""'"""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""""""'""'""'"""'""'""'""'""""""'""""""""'"""'""'""'""'""'""'""'""""""'"""'"""'"""""'"""""""'""'"""""""'""""""""'"""'""""'""""'""""'"""""'"""""""'""""""'""""""""'"""'""'"""""""'""""""""'"""'""""""'"""'""""""""'"""""""'"""'"""""""""'""""""'""'"""'"""""""'""'"""""""'""""""""'"""'""""""'"""'""""""""'"""""""'"""'"""'"""""'"""""""'""""""'""""""""'"""'""""""""'"""""""'""""""""'"""'"""'""""""'""'""'""'"""'"""""""""'"""""""'"""""""""'"""""""'""'""'""'"""'""""""'"""'""""""""'"""""""'"""'"""""""'"""'""""'""""'"""""""""'"""""""'""'""'""'"""'"'"""""""'""'""'""'""'""'"""'"""'"""""'"""""""'""""""'""""""""'"""'""'"""""""'""""""""'"""'"'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'"""""""'"""""""'""""""""'"""'"""""""""'"""""""'""'"""'"'"""""""'""'""'""'""'"""'"""'""""'""""'"""""""""'"""""""'""'""'""'"""'"""'""""'""""'""""'""""'"""""'""""""""'"""""""'""""""'"""'""'"""""""'"""'"""'"""""""""'"""""""'""'"""'""""""'"""'""'"""""""'"""'"""'"""""'""'""""""'"""'""'"""""""'"""'"'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'""'"""""""'""""""'""""""""'"""'""'"""""""'""""""""'"""'"'"'"'"""""'"""""""'""""""'""""""""'"""'""'"""""""'""""""""'"""'""'""'"""""""'""'""'""'""'"""'"""""""""'"""""""'""'"""'"'"""""""'""'""'""'""'"""'"""'"'"""""""'""'""'"""'""""""""'""""""'"""'"""

Explanation

I’m going to walk you through how the program processes the input thyme horseradish peppermint 10. The expected output is thyme,\nhorser...,\npeppermint.

First we start at cell #7 and read the entire input, but subtract 32 from every character so that spaces become zeros.

For obvious reasons, this leaves the running pointer (named p here, stored in cell #0) at the end. We use one while loop to find the last gap, which is the beginning of the number that defines the width of the output (cell #36 in this example).

We now want to decode the number (i.e. convert from decimal). The final result will be in both cells t and r. We rely on the fact that they start out at zero.

For every digit in the number, do the following:

• Set t to −15.
• In a while loop, decrement r (which contains the result so far) to −1 (because we need exactly r iterations, but since the decrement happens before it is checked as the while loop’s condition, decrementing to 0 would give one fewer iterations) and for each iteration, add 10 to t. Now t contains 10 times the previous result minus 15.
• Again in a while loop, decrement *p to 0 and for each iteration, add 1 to t. After this t contains the correct intermediate result so far: the characters '0' to '9' have ASCII codes 48–57, so after the earlier subtraction of 32 they are 16–25, so we actually add 15–24 to t, which cancels with the −15 we set it to earlier. It is also important that this zeroes the cells that used to contain the digit characters so that the subsequent code can recognize the end of the list of words.
• Set r to the new intermediate result so that the next iteration finds it in r. (Note we do not need to read from t again, we can just use the last value from the previous while loop because we know that *p can’t be zero, so it has run at least once.)

Finally, we use another simple while loop (decrementing t as the counter) to convert the number we just calculated into unary. We store a string of 1s going leftwards from cell #0. This relies on the fact that cell #1, our running pointer for this (q), starts out at 0. We get one fewer 1s because while loops in Unreadable are like that:

After this, we no longer need the value in r, so we re-use that cell for something else. We reset the pointers p and q and initialize some cells with ASCII codes of characters we need later. I’ve also labeled c and s which we will use later, and we will rely on the fact that s starts out at zero:

Hey, wait a minute. Why is cell #0 colored red?... Well, this is to highlight a sneaky trick. Remember we output one 1 too few? The trick is that we use the cell #0 as an “extension” to correct for that. This works because we know that p will never be 0. This way, the red block is now 10 cells wide, exactly the number we want. It also saves 9 characters to be able to initialize q to 1 instead of 0.

Now we enter the while loop that goes through the words and outputs them all.

Step 1: Find out whether the next word will fit into the current line. We do this by simply moving p to the right and q left with a while loop until p hits the next gap:

Now that p is on the right of the word, we can check whether this is the last word in the list by checking if *(p+1) is zero. We also store that value (which in our example is 72 because it’s the “h” from “horseradish” minus 32) in c because we’ll need it again later. In this case, it isn’t zero, so we will need to output a comma along with the word, so the word is one character longer. Take account of this by decrementing q one more time. Finally, use another while loop to move p back to the beginning of the word.

We now know that the word will fit into the current line because q is pointing at a non-zero value, so all we have to do is:

• Move p forward through the word again, printing each character (plus 32, because all the ASCII codes are off by 32).
• If c is non-zero, print a comma (using the value in cell #5).
• Set s to a non-zero value to indicate to the next iteration that we are no longer at the beginning of a line and therefore need to output a space character before the next word. (We re-use the return value of the above print statement for this, which is 44 for the comma.)

Output so far: thyme,

Then the next iteration of the big loop starts. As before, we check whether the next word fits into the rest of the line by decrementing q as we go through the word from left to right. Note that q is still −5 from the previous iteration, keeping track of how many characters we’ve already printed in the current line. After counting the characters in “horseradish”, plus one for the comma, plus one because s is non-zero indicating that we need to output a space as well, q will have overshot the end of the block of 1s:

Now q points at a zero cell, which means that “horseradish” will not fit into the current line. What we do now depends on whether s is non-zero. In our case it is, which means we need to wrap to the next line. All we have to do for that is:

• Print a newline (using cell #3)
• Set q back to 1
• Set s to 0

Output so far: thyme,\n

For the next iteration, p is in the same place as before, so we will be looking at the same word again. As before, we count the characters in “horseradish”, set c to 80 again when we notice there’s another word after this one, decrement q for the comma, and rewind p back to the beginning of the word:

As in the previous iteration, we find that “horseradish” still doesn’t fit because q ends up on a cell that is zero. However, this time s is zero, which means we do something different than last time. We need to output some of the word, three dots and a comma. Our width is 10, so we need to output 6 characters of the word. Let’s see where we end up if we:

• Find the beginning of the red block of 1s. We can do this by going right because we know that q must be left of it.
• Increment q once more if we also need to output a comma (c ≠ 0).

The tape now looks like this:

I’ve marked a span of 6 cells here. As you can see, we need to output characters until q = −1. This is very code-efficient to check (basically, while ((++q)+1) { ... }). So:

• Print those characters (plus 32, because all the ASCII codes are off by 32) until q reaches −1. p will then be at cell 19, in the middle of the word “horseradish”.
• Print three dots. Since the print command returns its own argument, we can code-efficiently nest it (essentially, print(print(print('.')))). We take the ASCII value from cell #5 and add 2 to it to get the ASCII code of the dot.
• Move p to the end of the word. Since we know we can’t have already reached the end of the word (because the word was too long, and we had to remove at least 3 characters from it to fit the dots), this loop definitely has at least one iteration, so it’s shorter in code to have the body of the while loop calculate the ASCII value for the dot and then pass the return value of the while loop to the print functions.
• Print a comma if c is non-zero.

After all of this, we also print a newline (using cell #3) and set q back to 1. We can also set s to 0 even though it’s already 0, which makes this the same that we did previously when we wrapped to the next line (when s was non-zero), so to avoid repeating the code, we do it after the conditional that checks s.

Output so far: thyme,\nhorser...,\n

There is only one iteration left. This time, after counting the letters of the word, we get this:

This time, there is nothing after p, so we set c to 0 to indicate “no comma”, and accordingly we do not decrement q a further time. Since q now points at a non-zero cell, we know the word will fit, so the same code is executed as in the first iteration, except that this time c is zero, so it will simply not print the comma.

Output: thyme,\nhorser...,\npeppermint

In this walkthrough I did not include a case where the code would actually print a space, but I think it should be fairly clear now. If the code finds that the word fits (*q ≠ 0) and s is non-zero, it will simply output a space before the word.

Answer 2

JavaScript (ES6), 171

As an anonymous function returning the output as an array

(as this is generally allowed unless explicitly forbidden: meta meta)

s=>(s=s.split` `,n=s.pop()-1,t='',o=[],s.map((w,i)=>(w=w[n+=!s[i+1]]?w.slice(0,n-3)+'...':w,(t+w)[n-2]&&(t&&o.push(t.slice(1)),t=''),t+=` ${w},`)),o.push(t.slice(1,-1)),o)

f=s=>(s=s.split` `,n=s.pop()-1,t='',o=[],s.map((w,i)=>(w=w[n+=!s[i+1]]?w.slice(0,n-3)+'...':w,(t+w)[n-2]&&(t&&o.push(t.slice(1)),t=''),t+=` ${w},`)),o.push(t.slice(1,-1)),o)

// Less golfed
U=s=>(
  s=s.split` `,
  n=s.pop()-1,
  t='', // current line
  o=[], // output
  s.map( (w,i)=>(
    w=w[
      n+=!s[i+1] // space for 1 more char on the last line
    ]?w.slice(0,n-3)+'...':w, // change w if it is too long
    (t+w)[n-2]&& ( // if current line + w is too long, ouput t and reset current line
      t&&o.push(t.slice(1)),t=''
    ),
    t+=` ${w},`
  )),
  o.push(t.slice(1,-1)), // remove tailing comma on last line
  o
)

console.log=x=>O.textContent+=x+'\n\n';
  
console.log(f("foo bar baz qux 12").join`\n`)
console.log(f("foo bar baz qux 5").join`\n`)
console.log(f("strength dexterity constitution intelligence wisdom charisma 10").join`\n`)
console.log(f("quas wex exort 4").join`\n`)

<pre id=O></pre>

Answer 3

Python 2, 206 bytes

i=input().split()
l=int(i.pop())
i=[[w[:l-4]+'...',w][len(w)<l]+','for w in i][:-1]+[[w,w[:l-3]+'...'][len(w)>l]]
r=[i.pop(0)]
for w in i:
 if len(r[-1])+len(w)<l:r[-1]+=' '+w
 else:r+=[w]
print'\n'.join(r)