#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

void read_words(const char* fileName,vector<string>& words)
{
  ifstream in;
  in.open(fileName);
  string nextWord;
  while(in >> nextWord) words.push_back(nextWord);
  in.close();
}

/* We will work only with the lengths of the words, so count those 
   lengths and store them in the vector lengths. */
void count_lengths(const vector<string>& words,vector<int>& lengths)
{
  lengths.resize(words.size());
  for(int n = 0;n < words.size();n++) 
  {
    lengths[n] = words[n].length();
  }
}

int cube(int x) 
{
  return x*x*x;
}

/* Here is a sketch of the original recursive version
that this dynamic programming version is based on.

The recursive function min_badness looks at the block
of text starting at word n and determines the minimum
badness possible for that block of text. It does this
by finding the optimal number of words to put on the
first line of the text block such that the badness of
that first line added to the optimal badness of the 
following lines is as low as possible.

int min_badness(int n,const vector<int>& lengths,int max_line)
{
// Find the index of the last word that that will fit
// on the line starting with word n.
int last_word = computeWords(n,lengths,max_line);
// Base case - if the last word that will fit on this line
// is the last word in the text, we are one the last line
// of the text. By definition, the last line always has a 
// badness of 0.
if(last_word == lengths.size() - 1)
	return 0;

// Now, for each choice of k, compute the badness that results
// from putting words n through k on the first line of the block.
int lowestBadness = cube(max_line - line_width(n,n,lengths)) + min_badness(n+1,lengths,max_line);
int bestK = n;

for(int k = n+1;k <= last_word;k++)
{
// Try putting the words n .. k on the first line
// and all subsequent words on following lines.
// Measure the badness of that configuration and see if it
// beats the best so far.
int badness = cube(max_line - line_width(n,k,lengths)) + min_badness(k+1,lengths,max_line);
if(badness < lowestBadness)
	{
	lowestBadness = badness;
	bestK = k;
	}
}

  return lowestBadness;
}
*/

// Now the dynamic programming version of the recursive algorithm.
void build_lines(const vector<int>& lengths,vector<int>& badnesses,vector<int>& breaks,int line_width)
{
  // badness[k] contains the minimum badness of a line that starts
  // with word k.
  badnesses.resize(lengths.size());
  // breaks[k] contains the index of the word that starts the
  // next line after the optimal line starting in position k.
  breaks.resize(lengths.size());

  // First, we build in the base cases. The base case is that
  // all words that will fit on the last line have a badness of 0.
  int z = lengths.size() - 1;
  int last_line_width = lengths[z];
  badnesses[z] = 0;
  breaks[z] = lengths.size();
  while(last_line_width + 1 + lengths[z-1] <= line_width)
  {
    z--;
    badnesses[z] = 0;
    breaks[z] = lengths.size();
    last_line_width += 1 + lengths[z];
  }
  
  // Now do the dynamic programming filling in the
  // values of the badness and break arrays.
  for(int n = z-1;n >= 0;n--)
  {
    int width = lengths[n];
    int k = n + 1;
    int bestBadness = badnesses[k] + cube(line_width - width);
    int bestK = k;
    while(k < lengths.size() && width <= line_width)
    {
      int currentBadness = badnesses[k] + cube(line_width - width);
      if(currentBadness < bestBadness)
      {
        bestBadness = currentBadness;
        bestK = k;
      }
      width += 1 + lengths[k];
      k++;
    }
    badnesses[n] = bestBadness;
    breaks[n] = bestK;
  }
}

void save_words(const char* fileName,vector<string>& words,vector<int>& breaks)
{
  ofstream out;
  out.open(fileName);
  int nextBreak = breaks[0];
  for(int n = 0;n < words.size();n++)
  {
    out << words[n];
    cout << words[n];
    // Put the line breaks before the nextBreak position.
    if(n == nextBreak-1) 
    {
      out << endl;
      cout << endl;
      if(nextBreak < breaks.size())
        nextBreak = breaks[nextBreak];
    }
    else 
    {
      out << ' ';
      cout << ' ';
    }
  }
  out.close();
}

int main()
{
  vector<string> words;
  vector<int> lengths;
  vector<int> badnesses;
  vector<int> breaks;
  
  int line_width;
  cout << "Enter the line width you would like to use: ";
  cin >> line_width;
  cout << endl;
  
  read_words("text.txt",words);
  count_lengths(words,lengths);
  build_lines(lengths,badnesses,breaks,line_width);
  save_words("output.txt",words,breaks);
  	
	return 0;
}