Typeset

local args = {...}
if #args < 2 then
  printError("Usage: typset <file> <marginsize>")
  return
end

local function split(str, regex)
  local t = {}
  for n in str:gmatch("[^"..regex.."]+") do
    t[#t + 1] = n
  end
  return t
end

local handle = fs.open(args[1],"r")
local line = handle.readLine()
local words = split(line, "%s")
local n = #words
local M = tonumber(args[2])
local lens = {}
for i=1, n do
  lens[i] = #words[i]
  if lens[i] > M then
    printError("Lzy c0de, 2 big")
    return
  end
end

--compute S_ij
local S = {}
for i = 1, n do
  S[i] = {}
  S[i][i] = M - lens[i]
  for j = i + 1, n do
    S[i][j] = S[i][j - 1] - lens[j] - 1
    if S[i][j] < 0 then
      while j <= n do
        j = j + 1
        S[i][j] = math.huge
      end
    end
  end
end

--compute best_0,...,best_n
local best = {}
local choice = {}
best[0] = 0
choice[0] = 0
for i=1, n do
  local min = math.huge
  local ch = 0
  for j=0, i - 1 do
    local t = best[j] + S[j + 1][i] * S[j + 1][i]
    if t < min then
      min = t
      ch = j
    end
  end
  best[i] = min
  choice[i] = ch
end

--backtrack to output linebreaks
local endc = n
local start = choice[endc]+1
local lines = {}
while endc > 0 do
  local buff = {}
  for j=start, endc do
    buff[#buff + 1] = words[j]
  end
  lines[#lines + 1] = table.concat(buff, " ").."\n"
  endc = start - 1
  start = choice[endc] + 1
end

for j=#lines, 1, -1 do
  write(lines[j])
end