Raggedy, Raggedy

Introduction

This asks you to format monospaced text by splitting it across lines of max length L such that the sum of squares of the difference between the actual line lengths and L is mininal.

Solutions

DP

Dimensions

• word you're on

Values

• the minimum sum of squares
• length of the last line (for path recovery)

Relation For each word you attempt to add word N to the end of the paragraph, you must iterate over all possible lines ending with N ("N-1 N", "N-2 N-1 N"...), up until you hit max line length L. The value is the minimum of(L-length(candidate last line) + dp(N-<words on candidate last line>). Ensure you record the line length when you find a minimum so you can actually build the paragraph later.

Construct the paragraph backwards, storing the correct number of words for each line, and then print them out in the correct order.

Code

Solution - Java

import java.util.*;
public class b {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new b().go();
	}
	private void go() {
		while(true){
			int n=in.nextInt();
			if(n==0)break;
			in.nextLine();
			ArrayList<String> words=new ArrayList<String>();
			while(true){
				String line=in.nextLine();
				if(line.equals(""))break;
				Scanner s=new Scanner(line);
				while(s.hasNext())words.add(s.next());
			}
			int[] lengths=new int[words.size()];
			for(int i=0;i<words.size();i++)lengths[i]=words.get(i).length();
			int[][] dp=new int[words.size()+1][2];
			for(int i=0;i<=words.size();i++)dp[i][0]=Integer.MAX_VALUE;
			dp[0][0]=0;
			for(int i=0;i<words.size();i++){
				int len=0;
				for(int j=1;j<=i+1;j++){
					len+=lengths[i-j+1]+1;
					if(len-1>n)break;
					int r=dp[i-j+1][0];
					if(i<dp.length-2)r+=(n-len+1)*(n-len+1);
					if(r<dp[i+1][0]){
						dp[i+1][0]=r;
						dp[i+1][1]=j;
					}
				}
			}
			ArrayList<Integer> lens=new ArrayList<Integer>();
			for(int on=words.size()-1;on>=0;){
				lens.add(dp[on+1][1]);
				on-=dp[on+1][1];
			}
			Collections.reverse(lens);
			Queue<String> q=new LinkedList<String>(words);
			for(int i:lens){
				String out="";
				for(int j=0;j<i;j++)out+=" "+q.poll();
				System.out.println(out.substring(1));
			}
			System.out.println("===");
		}
	}
}