Formattazione delle stringhe in triangoli in Haskell

Question

Ho una lista di liste di stringhe e ho bisogno di formattarle in un triangolo usando periodi tali che ogni lista è sulla sua stessa riga, e le stringhe di ogni lista sono separate da almeno una periodo. Inoltre, ogni personaggio deve avere punti sopra e sotto. Questo è probabilmente meglio spiegato con l'esempio:

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

dovrebbe restituire

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

Infine, è opportuno utilizzare il minor numero di periodi possibili, cioè l'approccio di imbottitura su ogni parola alla lunghezza massima la parola è troppo dispendiosa; cioè dell'esempio non deve restituire

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

posso facilmente scrivere la funzione che fa il mettere periodi entrambi i lati per farne una forma triangolare, il problema è con i periodi tra le parole.

Ho una funzione che funziona fintanto che la lunghezza della parola è 1, che è ovviamente piuttosto inutile per l'attività. Tuttavia, la mia funzione dots:

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

Questo è un esercizio compiti a casa, in modo da sentori sarebbe preferibile, ma ho cercato di fare questo per ore senza fortuna.

Answer 1

prima cosa è necessario una funzione, che aggiunge segnaposto a una lista come questa:

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

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

Ora è necessario riempire questi punti "" con punti. Così si può scrivere una funzione ausiliaria, che aggiunge i punti a un elenco:

addDots ["test", "", "random", ""] 

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

e poi fill è semplicemente

fill = transpose . map addDots . transpose 

E la vostra funzione è solo

triangle = map concat . fill . addPlaceholders 

Answer 2

Vorrei affrontare il problema come segue.

Innanzitutto, trascurare la lunghezza di ogni parola. Pensa a una m di scacchiera e piazza ogni parola in un quadrato in modo che le parole finiscano solo in quadrati neri. Ora, il numero di righe n è il numero di elenchi di parole che hai. Scopri cosa dovrebbe essere.

Si consiglia di "centrare" l'assegnazione in ogni riga, in modo da ottenere un triangolo alla fine.

Quindi, considerare la lunghezza della parola. Quanto è ampio (in caratteri) ogni colonna m? Per ogni colonna, calcola la sua larghezza. Riempi ogni quadrato di punti in modo da raggiungere la larghezza desiderata.

faccio alcuna pretesa questo è l'approccio più semplice - è solo il primo che è venuto da me :)

Answer 3

In primo luogo, un po 'di terminologia : per una data riga, ad es ["some", "more", "random", "words"], chiameremo l'indice di una determinata parola nella riga "colonna logica". Pertanto, "more" ha la colonna logica 1 in quella riga; e "words" ha la colonna logica 3.Una volta che abbiamo scelto una posizione per ogni parola, avremo anche una "colonna fisica" che dice quanti caratteri (punti o altri caratteri di parole) devono comparire prima di quando si esegue il rendering della riga.

Facciamo un'ipotesi semplificativa (il problema è abbastanza difficile anche semplificata): nel layout finale, una parola alla riga r, colonna logico c deve essere tra le parole alla riga r+1, colonne logiche c e c+1.

Un'idea per affrontare questo problema è aggiungere un terzo tipo di colonna, chiamiamola una "colonna a scacchiera", come passaggio intermedio. Le righe di un numero pari di passi dal basso avranno tutte le loro parole in colonne pari a scacchiera e le righe di un numero dispari di passi dal basso avranno tutte le loro parole in colonne a scacchiera dispari. Si può quindi scegliere una larghezza per ogni colonna a scacchiera e impostare la colonna fisica di una parola come la somma delle larghezze delle colonne a scacchiera più piccole di quella.

Tuttavia, questo ha un leggero problema; considerare questo scacchiera, dove ho segnato in modo esplicito i confini delle colonne a scacchiera:

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

perché abbiamo scelto una larghezza per ogni colonna scacchiera, parole diverse colonne a scacchiera non possono mai sovrapporsi. Questo esclude soluzioni come la seguente, che sono leggermente più stretta:

aa 
    b c 
d e f 
g hh i j 

noti che aa e hh si sovrappongono - anche se non sono su file adiacenti, quindi questo è bene.

Un'altra soluzione è quella di tracciare le parole in questo ordine:

4 
    3 7 
2 6 9 
1 5 8 10 

Durante la posa fuori una data parola, possiamo poi semplicemente scegliere la colonna fisico più piccolo per questo che non viola le regole, cercando nella posizione e lunghezza delle parole sopra/a sinistra e sotto/a sinistra di esso (che sarà già stato calcolato). Ho un'implementazione di questo algoritmo, che aggiungerò a questa risposta tra qualche giorno (secondo le linee guida del sito sui compiti a casa), ma questo suggerimento dovrebbe essere sufficiente per riprodurre qualcosa di molto simile a te stesso. L'interessante bit algoritmico della mia implementazione è una funzione a dieci righe di tipo Map (Row, LogicalColumn) String -> Map (Row, PhysicalColumn) String e ti consiglio di eseguire un tentativo con una funzione tipizzata in modo simile. Dovrebbe essere possibile farlo con una intelligente traversata degli elenchi di input direttamente (eliminando quindi qualsiasi costo di indicizzazione della mappa), ma non riuscivo a capirlo. Possiamo dimostrare per induzione (dove la variabile su cui stiamo inducendo è l'ordine in cui disponiamo le parole) che questo approccio produce la soluzione con una larghezza minima.

Come promesso, il codice mi si avvicinò con:

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 k m = maybe empty pure (Data.Map.lookup k m) 
    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