> import Array

> min_waste :: String -> Int -> Int
> min_waste t l = c n
>     where n   = length ws
>           ws  = words t
>           c 0 = 0
>           c i = minimum [max (waste (n-i) (n-j-1) l ws) (c j) | j <- [0..i-1]]

> waste :: Int -> Int -> Int -> [String] -> Int
> waste i j l ws = if length (unwords segment) > l then l
>                  else l - length (concat segment)
>  where segment = take (j+1-i) (drop i ws)



> fe :: String -> Int -> IO()
> fe t l             = putStr (concat ["\n[",text,"~~ waste: ",ans'," ~~]\n"])
>   where (ans,text) = min_waste' t l
>         ans'       = if ans < l then show ans else "<FAILED>"

> min_waste' :: String -> Int -> (Int, String)
> min_waste' t l   = c n
>   where n        = length ws
>         ws       = words t
>         c 0      = (0,"")
>         c i      = foldr1 min' [max' (waste' (n-i) (n-j-1) l ws) (c j)
>                    | j <- [0..i-1]]
>         min' x y = if fst x < fst y then x else y
>         max' x y = (max (fst x) (fst y),snd x ++ "]\n[" ++ snd y)

> waste' :: Int -> Int -> Int -> [String] -> (Int, String)
> waste' i j l ws = if length seg' > l then (l,seg')
>                   else (l - length (concat seg),take l (seg' ++ repeat ' '))
>      where seg  = take (j+1-i) (drop i ws)
>            seg' = unwords seg



> mw_array :: String -> Int -> Int
> mw_array t l = c!n
>     where n  = length ws
>           ws = words t
>           c  = array (0,n) ([(0,0)] ++ 
>                [(i,minimum [max (a!(i,j)) (c!j) | j <- [0..i-1]]) | i <- [1..n]])
>           a  = array ((1,0),(n,n-1)) ([((i,i-1),getw i (i-1)) | i <- [1..n]] ++
>                [((i,j),if (a!(i,j+1)) == l then l else getw i j) 
>                | i <- [1..n], j <- [0..i-2]])
>           getw i j = waste (n-i) (n-j-1) l ws


> fe_array :: String -> Int -> IO()
> fe_array t l       = putStr (concat ["\n[",text,"~~ waste: ",ans'," ~~]\n"])
>   where (ans,text) = mw_array' t l
>         ans'       = if ans < l then show ans else "<FAILED>"

> mw_array' :: String -> Int -> (Int,String)
> mw_array' t l = c!n
>      where n  = length ws
>            ws = words t
>            c  = array (0,n) ([(0,(0,""))] ++ [(i,foldr1 min'
>                 [max' (a!(i,j)) (c!j) | j <- [0..i-1]]) | i <- [1..n]])

>            a  = array ((1,0),(n,n-1)) ([((i,i-1),getw i (i-1)) | i <- [1..n]] ++
>                [((i,j),if fst (a!(i,j+1)) == l then (l,"") else getw i j) 
>                | i <- [1..n], j <- [0..i-2]])
>            getw i j = waste' (n-i) (n-j-1) l ws
>            min' x y = if fst x < fst y then x else y
>            max' x y = (max (fst x) (fst y),snd x ++ "]\n[" ++ snd y)



> ex = "This is the best"

> ex0 = "Wagner has beautiful moments but awful quarter hours."

> ex1 = unwords [ex0, ex0, ex0, ex0]

> ex2 = unwords [ex1, ex1]

> ex3 = unwords ["Kathleen Robertson of Austin, Texas, was awarded",
>       "$780,000 by a jury of her peers after breaking her ankle tripping",
>       "over a toddler who was running amok inside a furniture store. The",
>       "owners of the store were understandably surprised at the verdict,",
>       "considering the child was Ms. Robertson's son. Jerry Williams of",
>       "Little Rock, Arkansas, was awarded $14,500 and medical expenses",
>       "after being bitten on the buttocks by his next door neighbor's",
>       "beagle. The beagle was on a chain in its owner's fenced-in yard with",
>       "Mr. Williams. The award was less than sought because the jury felt",
>       "the dog may have been provoked by Mr. Williams who, at the time, was",
>       "shooting it repeatedly with a pellet gun. A Philadelphia restaurant",
>       "was ordered to pay Amber Carson of Lancaster, Pennsylvania, $113,500",
>       "after she slipped on soft drink and broke her coccyx. The beverage",
>       "was on the floor because Ms. Carson had thrown it at her boyfriend",
>       "30 seconds earlier during an argument."]

> ex4 = unwords ["January: now is here, a fine new start for a whole new year.",
>       "In January, when there's snow we get our sleds and away we go.",
>       "January sparkles. January's bold. January huffs and puffs. January's",
>       "cold."]

[hugs Main]$ map (mw_array ex3) [100..140]
[24,25,26,27,28,29,30,31,32,26,27,28,29,30,28,29,30,31,32,33,22,23,24,25,26] ++
[27,28,29,30,31,32,33,34,35,36,37,38,27,28,28,29]
(2549466802 reductions, 3382146380 cells, 9668 garbage collections)