Greedy Text Justification

March 30, 2021

Today’s exercise would make a good interview question, though I don’t know of anyone doing that; you should answer as if you are standing at a whiteboard explaining your code as you go:

Given a string and a line width, split the string into words (a maximal run of characters excluding spaces) and write the words onto successive lines with spaces added between the words so that each line is the requested width. Words should be added to lines greedily (as many words as will fit) and extra spaces should be assigned to the left of the output string. The last line should not have spaces added, so it may be shorter than the other lines.

For example, the string “This is an example of text justification” is written with a line width of 16 like this:

    ----+----+----+-
    This    is    an
    example  of text
    justification.
    ----+----+----+-

Your task is to write a program that greedily justifies text. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

6 Responses to “Greedy Text Justification”

  1. chaw said

    Here is a solution in standard R7RS Scheme plus a few well-known
    helpers. It focuses more on clarity than on low-level efficiency.

    (import (scheme base)
            (scheme write)
            (only (srfi 1)
                  fold split-at drop first second cons*)
            (only (srfi 13)
                  string-tokenize string-join))
    
    ;; Using the (chibi fmt) library or the similar (srfi 166) we could
    ;; probably just do something like the following, but that probably is
    ;; not in the spirit of the question:
    
    ;; (define (greedy-text-justify width str)
    ;;   (fmt #f (with-width width (justify str))))
    
    (define (assert p)
      (unless p (error "assertion failed")))
    
    (define samples ; ((input . output) ...)
      '(((16 "This is an example of text justification.")
         .
         "\
    This    is    an
    example  of text
    justification.")
        ((80 "This is an example of text justification.")
         .
         "This is an example of text justification.")
        ((80 "")
         .
         "")
        ((5 "This is an example of text justification.")
         .
         "\
    This
    is an
    example
    of
    text
    justification.")
        ((5 "OK") . "OK")
        ((5 "fits.") . "fits.")
        ((5 "fits doesn't.") . "fits\ndoesn't.")
        ((5 "doesn't.") . "doesn't.")))
    
    (define (greedy-line-justify width words)
      (let ((nwords (length words))
            (nspaces (- width (apply + (map string-length words)))))
        (if (or (< nwords 2)
                (< nspaces 1))
            (string-join words " ") ; TODO something better?
            (let*-values (((quot rem) (floor/ nspaces (- nwords 1)))
                          ((pfx sfx) (split-at words rem))
                          ((sep-short) (make-string quot #\space))
                          ((sep-long) (string-append sep-short " ")))
              (string-append (string-join pfx sep-long)
                             (if (zero? rem) "" sep-long)
                             (string-join sfx sep-short))))))
    
    (define (greedy-text-justify width str)
      (let ((r (fold (lambda (word s)
                       (let* ((wlen (string-length word))
                              (cwds (second s))
                              (wrem (- (first s) (if (null? cwds) 0 1)))
                              (prev (cddr s)))
                         (if (or (>= wrem wlen) (null? cwds))
                             (cons* (- wrem wlen)
                                    (cons word cwds)
                                    prev)
                             (cons* (- width wlen)
                                    (list word)
                                    (greedy-line-justify width (reverse cwds))
                                    prev))))
                     ;; (remaining-width curr-line-words . previous-lines):
                     (list width '())
                     (string-tokenize str))))
        (string-join (reverse (cons (string-join (reverse (second r)))
                                    (drop r 2)))
                     "\n")))
    
    (define (test)
      (assert (equal? (map cdr samples)
                      (map (lambda (args) (apply greedy-text-justify args))
                           (map car samples)))))
    
    (test)
    

  2. Ramakrishna akumarthi said

    #include<graphics.h>
    #include<stdio.h>
    #include<string.h>
    #include<conio.h>
    void main()
    {
    char* str;
    int x=0,y,i,l,j,e=34,gd=DETECT,gm;
    clrscr();
    initgraph(&gd,&gm,”c:\turboc3\bgi”);
    setbkcolor(GREEN);
    printf(“Enter the data:\n”);
    gets(str);
    l=strlen(str);
    if(l<e)
    puts(str);
    else
    {
    for(i=0;i<(l/e);i++)
    {
    for(j=0;j<e;j++)
    {
    printf(“%c”,str[x]);
    x++;
    }
    printf(“\n”);
    }
    y=l%e;
    while(y)
    { printf(“%c”,str[x]);
    x++;
    y–;
    }
    }
    getch();
    closegraph();
    }

  3. Kevin said

    A solution in Racket:

    ; assumptions:
    ; given text is a non-empty string.
    ; given width is big enough to hold longest word in text.
    
    (define (gj-guide width)
      (for ((n (in-range 1 (add1 width))))
        (display (if (zero? (remainder n 5)) "+" "-")))
      (displayln ""))
               
    (define (gj-result width lines)
      (gj-guide width)
      (for-each displayln lines)
      (gj-guide width))
    
    (define (gj-line words width)
      (let* ((diff (- width (foldl (λ (v i) (+ i (string-length v))) 0 words))) (gaps (sub1 (length words))) (sz (quotient diff gaps)))
        (let loop ((in words) (line "") (pad (remainder diff gaps)))
          (cond
            ((null? in) line)
            ((or (string=? line "") (equal? #\space (last (string->list line)))) (loop (cdr in) (string-append line (car in)) pad))
            ((zero? pad) (loop in (string-append line (make-string sz #\space)) pad))
            (else (loop in (string-append line (make-string (add1 sz) #\space)) (sub1 pad)))))))
    
    (define (greedy-justify text width)
      (let loop ((in (string-split text)) (len 0) (txtlen 0) (words '()) (lines '()))
        (if (null? in)
            (if (null? words)
                (gj-result width (reverse lines))
                (loop in 0 0 '() (cons (string-join (reverse words)) lines)))
            (let* ((word (car in)) (wordlen (string-length word)) (temp (+ len (if (null? words) 0 1) wordlen)))
              (cond
                ((< temp width) (loop (cdr in) temp (+ txtlen wordlen) (cons word words) lines))
                ((= temp width) (loop (cdr in) 0 0 '() (cons (string-join (reverse (cons word words))) lines)))
                (else (loop in 0 0 '() (cons (gj-line (reverse words) width) lines))))))))
    

    Examples:

    > (greedy-justify "This is an example of text justification." 16)
    ----+----+----+-
    This    is    an
    example  of text
    justification.
    ----+----+----+-
    > (greedy-justify "Happy families are all alike; every unhappy family is unhappy in its own way." 25)
    ----+----+----+----+----+
    Happy  families  are  all
    alike;    every   unhappy
    family  is unhappy in its
    own way.
    ----+----+----+----+----+
    > (greedy-justify "Call me Ishmael." 16)
    ----+----+----+-
    Call me Ishmael.
    ----+----+----+-
    > (greedy-justify "Call me Ishmael." 12)
    ----+----+--
    Call      me
    Ishmael.
    ----+----+--
    > (greedy-justify "Call me Ishmael." 8)
    ----+---
    Call  me
    Ishmael.
    ----+---
    
  4. Daniel said

    Here’s a solution in Python.

    def justify(string, width=16):
        words = list(reversed(string.split()))
        result = []
        while words:
            line = [words.pop()]
            count = len(line[0])
            while words and count + len(words[-1]) + 1 <= width:
                line.append(words.pop())
                count += len(line[-1]) + 1
            if len(line) == 1 or not words:
                result.extend(' '.join(line))
            else:
                num_spaces = width - sum(len(word) for word in line)
                q, r = divmod(num_spaces, len(line) - 1)
                pads = [0 if idx == 0 else q if idx > r else q + 1 for idx in range(len(line))]
                result.extend(' ' * pad + word for pad, word in zip(pads, line))
            result.append('\n')
        return ''.join(result)
    
    print(justify('This is an example of text justification'))
    

    Output:

    This    is    an
    example  of text
    justification
    
  5. V said
    const sep = " ";
    
    function justify(str, width) {
      if (sep.length != 1) { 
        throw "ERROR: sep must be one char long."
      }
      
      let buf = []
      let lines = []
      const words = str.split(/\s+/)
      
      words.forEach(word => {
        // Does word fits in buf?
        const wordFitsInLine = buf.concat([word]).join(sep).length <= width
    
        if (wordFitsInLine) {
          buf.push(word)
        } else {
          lines.push(makeLine(buf, width))
          buf = [word]
        }
      })
    
      lines.push(makeLine(buf, width))
      
      return lines.join("\n")
    }
    
    function makeLine(words, width) {
      if (words.length == 0) {
        return ""
      }
      
      if (words.length == 1) {
        return words[0]
      }
    
      const wordsInit = words.slice(0, words.length-1)
      const wordsLast = words[words.length-1]
      let pads = (new Array(words.length-1)).fill(sep)
      
      while (true) {
        for (let i = 0; i < pads.length; i++) {
          pads[i] = pads[i] + sep
       
          line = wordsInit
            .flatMap((w, j) => [w, pads[j]])
            .concat([wordsLast])
            .join('')
       
          if (line.length == width) {
            return line
          }
        }
      }
    }
    const s1 = "This is an example of text justification."
    const s2 = "Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua."
    
    console.log(justify(s1, 16))
    console.log("---")
    console.log(justify(s2, 40))
    

    Out:

    This    is    an
    example  of text
    justification.
    ---
    Lorem  ipsum dolor sit amet, consectetur
    adipisicing  elit, sed do eiusmod tempor
    incididunt  ut  labore  et  dolore magna
    aliqua.
    
  6. faisi said

    // This is not the exact answeer. it is written in c++ your comments please to improve it so that output matches

    #include
    #include
    using namespace std;

    int main()
    {
    int i = 0;
    int del = 0;
    int del2;
    string delim = ” “;
    int strlength;
    int linewidth = 16;
    string s;
    s = “This is a justified text below”;
    string* sub = new string[s.length()];
    while (true)
    {
    del2 = s.find(delim, del);
    //cout << del2 << endl;
    //cout << del << endl;
    if (del2 == -1) {
    sub[i] = s.substr(del, s.length());
    break;
    }
    else
    {
    sub[i] = new char[s.substr(del, del2).length() + 1];
    sub[i] = s.substr(del, del2 – del);
    del = del2 + delim.length();
    //cout <<sub[i] << endl;
    i++;
    }
    }
    cout << i << endl;
    i = i+1 ;
    int j;
    int lengths = 0;
    int k = 0;
    int m=0;
    for (int y = 0; y < 5; y++)
    {
    lengths = 0;

        for ( j = k; j < i; j++)
        {
            if (lengths + 1+sub[j].length() > 16)
                break;
            else
                lengths = lengths + sub[j].length();
    
    
        }
        lengths = 0;
    
        m = k;
        k = j;
    
        for (int y = m; y < j; y++)
        {
    
    
            if (y == j-1) {
    
                cout << string(16 - lengths, ' ') << sub[y] << endl;
            }
            else {
                lengths = lengths + sub[y].length() + 1;
                cout << sub[y] << " ";
            }
        }
    
    }
    

    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: