/**
 * paragraph.c
 *   Attempts "ideal" wrapping of a paragraph, using dynamic programming.
 */

// +---------+-------------------------------------------------------
// | Headers |
// +---------+

#include <stdio.h>
#include <string.h>
#include <limits.h>

// +-----------+-----------------------------------------------------
// | Constants |
// +-----------+

/** The maximum length of a line. */
#define MAXLEN 14

// +---------+-------------------------------------------------------
// | Helpers |
// +---------+

/**
 * Display the greedy formatting.  Return its cost.
 */
int
greedy (char *paragraph[], int words)
{
  int len = 0;          // Length of current line
  int newlen;
  int badness = 0;      // "badness" of this format
  int i;                // Word iterator

  while (i < words)
    {
      // No words on the line: Take the first
      if (len == 0)
        {
          printf ("%s", paragraph[i]);
          len = strlen(paragraph[i]);
          ++i;
        }
      // Room for next word: Add it
      else if ((newlen = len + strlen(paragraph[i]) + 1) <= MAXLEN)
        {
          printf (" %s", paragraph[i]);
          len = newlen;
          i++;
        }
      // No room for next word.  Move to the next line.
      else
        {
          printf ("\n");
          badness += (MAXLEN - len) * (MAXLEN - len);
          len = 0;
        } // no room
    } // while
  if (len != 0)
    printf ("\n");

  return badness;
} // greedy

/**
 * Compute the orientation of a paragraph starting at position start.
 */
int
dpr_helper (char *paragraph[], int words, int badness[], int breaks[], int start)
{
  int len = 0;
  if (badness[start] != INT_MAX)
    return badness[start];
  len = strlen (paragraph[start]);
  // First guess: Break after the first word.
  badness[start] = dpr_helper (paragraph, words, badness, breaks, start+1) + 
                   (MAXLEN - len) * (MAXLEN - len);
  breaks[start] = start;
  // Try the other guesses
  int i = start + 1;
  while ((i < words) && ((len = len + strlen (paragraph[i]) + 1) <= MAXLEN))
    {
      int nextguess = dpr_helper(paragraph, words, badness, breaks, i+1) + 
                                (MAXLEN - len) * (MAXLEN - len);
      if (nextguess < badness[start])
        {
          badness[start] = nextguess;
          breaks[start] = i;
        }
      ++i;
    } // while
  if (i == words)
    {
      badness[start] = 0;
      breaks[start] = words;
    }
  return badness[start];
} // dpr_helper

/**
 * Compute the orientation of a paragrpah using dynamic programming.
 */
int
dpr (char *paragraph[], int words)
{
  int i;
  int badness[words];
  int breaks[words];
  for (i = 0; i < words; i++)
    {
      badness[i] = INT_MAX;
      breaks[i] = i;
    } // for
  dpr_helper (paragraph, words, badness, breaks, 0);

  int start = 0;
  for (i = 0; i < words; i++)
    {
      if (i == breaks[start])
        {
          printf("%s\n", paragraph[i]);
          start = i + 1;
        }
      else
        printf ("%s ", paragraph[i]);
    } // for
  printf ("\n");

  return badness[0];
} // dp

int
dp (char *paragraph[], int words)
{
  int badness[words];
  int breaks[words];

  // Compute the tables
  int start;
  badness[words-1] = 0;
  for (start = words-2; start >= 0; start--)
    {
      int len = strlen (paragraph[start]);
      // First guess: Break after the start.
      badness[start] = badness[start+1] + (MAXLEN - len) * (MAXLEN - len);
      breaks[start] = start;
      // Try the other guesses
      int i = start + 1;
      while ((i < words) && ((len = len + strlen (paragraph[i]) + 1) <= MAXLEN))
        {
          int nextguess = badness[i+1] + (MAXLEN - len) * (MAXLEN - len);
          if (nextguess < badness[start])
            {
              badness[start] = nextguess;
              breaks[start] = i;
            }
          ++i;
        } // while
      if (i == words)
        {
          badness[start] = 0;
          breaks[start] = words;
        } // if (i == words)
    } // for

  // Print it out
  start = 0;
  int i;
  for (i = 0; i < words; i++)
    {
      if (i == breaks[start])
        {
          printf("%s\n", paragraph[i]);
          start = i + 1;
        }
      else
        printf ("%s ", paragraph[i]);
    } // for
  printf ("\n");

  return badness[0];
} // dp

// +------+----------------------------------------------------------
// | Main |
// +------+

int
main (int argc, char *argv[])
{
  int cost;
  printf ("------ GREEDY -----\n");
  cost = greedy (argv+1, argc-1);
  printf ("\nCOST: %d\n\n", cost);

  printf ("---- RECURSIVE ----\n");
  cost = dpr (argv+1, argc-1);
  printf ("\nCOST: %d\n\n", cost);

  printf ("-------- DP -------\n");
  cost = dp (argv+1, argc-1);
  printf ("\nCOST: %d\n\n", cost);

  return 0;
} // main