Formatting strings in triangles in Haskell

Question

I have a list of line lists, and I need to format them into a triangle, using such periods so that each list is on a separate line, and the lines of each list are separated by at least one period. In addition, each character must have dots above and below. This is probably best explained by an example:

> dots [["test"], ["hello", "world"], ["some", "random", "words"], ["even", "more", "random", "words"]] 

must return

 ............test..................... .......hello.......world............. ...some......random......words....... not....really......random.....anymore 

Finally, he must use the least number of periods, that is, the approach of putting each word to the length of the maximum word is too wasteful; i.e. the above example should not return

 .....................test........................ ..............hello.........world................ .......some..........random........words......... not...........really........random........anymore 

I can easily write a function a, which puts the periods on each side in the shape of a triangle, my problem is with the periods between words.

I have a function that works as long as the word length is 1, which is clearly useless for the task. However, my dots function:

 dots :: [[String]] -> [[String]] dots xss = map dots' xss where dots' (x:[]) = [x] dots' (x:xs) = [x] ++ ["."] ++ dots' xs 

This is homework, so hints would be preferable, but I tried to do it for hours without any luck.

Answer 1

First you need a function that adds placeholders to a list like this:

 addPlaceholders [ ["test"] , ["hello", "world"] , ["some", "random", "words"] , ["not", "really", "random", "anymore"] ] ==> [ ["" , "" , "" , "test" , "" , "" , "" ] , ["" , "" , "hello" , "" , "world" , "" , "" ] , ["" , "some", "" , "random", "" , "words", "" ] , ["not", "" , "really", "" , "random", "" , "anymore"] ] 

Now you need to fill these "" dots. So you can write a helper function that adds points to the list:

 addDots ["test", "", "random", ""] ==> ["test..","......","random","......"] 

and then fill just

 fill = transpose . map addDots . transpose 

And your function is just

 triangle = map concat . fill . addPlaceholders 

Answer 2

First, some terminology: for a given line, for example. ["some", "more", "random", "words"] , we will call this index of a word in a row its "logical column". Thus, "more" has a logical column 1 on this line; and "words" has a logical column of 3 . Once we have selected a position for each word, we will also have a “physical column” that indicates how many characters (dots or other word characters) should appear in front of it when rendering the string.

Let's make a simplifying assumption (the problem is quite complicated and even simplified): in the final layout, the word in row r , the logical column c must be between the words in row r+1 , the logical columns c and c+1 .

One idea to solve this problem is to add a third type of column, let's call it a “chessboard column” as an intermediate step. Lines of an even number of steps below will have all the words in the columns of the checkerboard, and lines with an odd number of steps below will have all their words in the columns of the odd chessboard. You can then select the width for each column of the chessboard and set the physical column of the word as the sum of the width of the columns of the chessboard is less than it.

However, this has a slight problem; look at this chessboard, where I clearly marked the borders of the columns of the chessboard:

  | | |aa| | | | | b| |c| | |d| |e | |f| g| |hh| |i| |j 

Since we selected a width for each column of a chessboard, words in different columns of a chessboard can never overlap. This eliminates solutions such as the following, which are slightly narrower:

  aa bc def g hh ij 

Note that aa and hh overlap - although they are not on adjacent lines, so this is normal.

Another solution is to lay out the words in the following order:

  4 3 7 2 6 9 1 5 8 10 

When highlighting a given word, we can simply select the smallest physical column for it, which does not violate the rules, if we look at the position and length of words above / to the left and below / to the left of it (which will already be calculated). I have an implementation of this algorithm that I will add to this answer in a few days (in accordance with the recommendations of the site about homework), but this hint should be enough so that you can reproduce something very similar to it. An interesting algorithmic bit of my implementation is a ten-line function of type Map (Row, LogicalColumn) String -> Map (Row, PhysicalColumn) String , and I recommend that you try a similar typed function. It should be possible to do this by cleverly traversing the input lists directly (hence, excluding any costs for indexing the map), but I could not completely wrap myself around it. We can prove by induction (where the variable on which we induce is the order, we spell out the words) that this approach gives a solution with a minimum width.

As promised, the code I came up with:

 import Control.Applicative import Data.List import Data.Map hiding (empty, map) import Data.Ord type Row = Int type PhysicalColumn = Int type LogicalColumn = Int layout :: Map (Row, LogicalColumn) [a] -> Map (Row, PhysicalColumn) [a] layout m = munge answer where answer = mapWithKey positionFor m positionFor (r, c) as = maximumBy (comparing snd) . concat $ [ [(as, 0)] , addLength as <$> lookup (r+1, c ) answer , addLength as <$> lookup (r-1, c-1) answer ] addLength as (v, p) = (as, p + length v) lookup km = maybe empty pure (Data.Map.lookup km) munge = fromAscList . map (\((r, _), (w, c)) -> ((r, c), w)) . toAscList parse :: String -> Map (Row, LogicalColumn) String parse = fromList . enumerate . map words . lines enumerate :: [[a]] -> [((Row, LogicalColumn), a)] enumerate xss = concat . zipWith (\i xs -> [((i, j), x) | (j, x) <- xs]) [0..] . map (zip [0..]) $ xss groups :: Eq b => (a -> (b, c)) -> [a] -> [(b, [c])] groups f = map (\pairs -> (fst . head $ pairs, map snd pairs)) . groupBy ((==) `on` fst) . map f flatten :: Map (Int, Int) [a] -> [(Int, [(Int, [a])])] flatten = map (\(r, pairs) -> (r, map (concat <$>) (groups id pairs))) . groups (\((r, c), a) -> (r, (c, a))) . toAscList pad :: a -> [(Int, [a])] -> [a] pad blank = go 0 where go n ((target, v):rest) = replicate (target-n) blank ++ v ++ go (target+length v) rest go _ [] = [] pprint = unlines . map (pad ' ' . snd) . flatten allTogetherNow = putStr . pprint . layout . parse 

Answer 3

I would approach the problem as follows.

First, neglect the length of each word. Think about the nm chessboard, and put each word in a square so that the words appear only in black squares. Now the number of lines n is the number of word lists you have. Find out what should be m.

You may want to “center” the distribution in each row to get a triangle at the end.

Then consider the length of the word. How wide (in characters) should each of the columns m be? For each column, calculate its width. Fill each square with dots to achieve the desired width.

I do not claim that this is a simpler approach - this is only the first one that came up to me :)