在Haskell中将字符串格式化为三角形

我有一个字符串列表的列表，我需要将它们格式化为三角形，使用句点，以便每个列表都在自己的行上，并且每个列表的字符串至少用一个期。此外，每个角色的上下都必须有点。这例如可能是最好的解释：在Haskell中将字符串格式化为三角形

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

应该返回

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

最后，应该尽可能使用时间最少的，即每一个字填充到最大长度的方法这个词太浪费了;那是上面的例子不应该返回

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

我可以随便写，做了把周期两侧，使之变成一个三角形的一个功能，我的问题是，在字与字之间的周期。

我有一个函数，只要字长度为1，这显然是非常无用的任务。然而，我的功能dots：

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

这是一个课外练习，所以提示将是首选，但我一直在努力的，没有运气小时做到这一点。

来源

2014-12-20 b3036667

也许例子稍有不正确的？在世界的下方有一个米，根据规则，这应该是不允许的。另外还有一整列可能被删除的点。（和+1清除它是作业） – chi

是的，这是错误的，谢谢指出。我编辑过它。 – b3036667

这个问题令人惊讶地微妙！例如，[[“aa”]，[“b”，“c”]，[“d”，“e”，“ff”]'的一个正确答案是“.... aa \ nbc。 \ nd.e ... \ n .... FF“'。注意'aa'是'c'的*右边*和答案'“..aa ... \ nb.c .. \ nd.e .... \ n ..... ff”'将'aa'放在'b'和'c'之间的点数更多（因此根据您的规格不正确）。这是故意的吗？ –

首先你需要一个功能，即增加了占位符像这样的列表：

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

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

现在你需要用点填充这些""。所以，你可以写一个辅助功能，即增加点到列表：

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

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

然后fill简直是

fill = transpose . map addDots . transpose

而且你的功能仅仅是

triangle = map concat . fill . addPlaceholders

来源

2014-12-20 05:06:50 user3237465

此方法不会给出[[“aa”]，[“b”，“c”]，[“d”，“e”，“f”]，[“g”，“ HH”， “I”， “J”]]'。请参阅我的答案，了解为什么。 –

@Daniel Wagner，我认为你太过复杂了。这只是一项家庭作业，所以我认为，重叠是不允许的。 – user3237465

我认为问题很复杂，值得讨论原因。 –

我会按如下方式处理问题。

首先，忽略每个单词的长度。想象一个由m棋盘组成的n，并将每个单词放在一个正方形中，这样单词只能以黑色方块结束。现在，行数n是您拥有的单词列表数。找出m应该是什么。

您可能希望在每行中“分配”分配，以便最终获得三角形。

然后，考虑字长。 m列应该有多宽（以字符表示）？对于每列，计算其宽度。用圆点填充每个正方形，以达到预期的宽度。

我并没有要求这是更简单的方法 - 它只是向我走过来:)第一个

来源

2014-12-20 01:08:44 chi

注意：本解决方案存在上述评论中关于规范中的细微之处（或者至少不讨论如何解决它）的问题。 –

事实上，情况变得更糟。这个解决方案可以处理上面我的评论中提出的问题，并适当地实现了“将每个单词放在一个正方形中，以便单词只在黑色方块中结束”。但是它不能得到正确的答案，即[[“aa”]，[“b”，“c”]，[“d”，“e”，“f”]，[“g”，“ hh“，”i“，”j“]]'，其中一个正确的解决方案必须在同一个文本列中有'aa'中的第一个'a'和'hh'中的最后'h'。 –

首先，一些术语：对于给定的行，例如["some", "more", "random", "words"]，我们将在行的“逻辑列”中调用给定单词的索引。因此"more"在该行中具有逻辑列1;并且"words"具有逻辑列3。一旦我们为每个单词选择了一个位置，我们还会有一个“物理列”，表示在渲染行时应该出现多少个字符（点或其他单词字符）。

让我们做一个简单的假设（的问题是够硬，甚至简化）：在最后的布局，在r行字，逻辑列c必须在r+1行，逻辑列c和c+1是在字与字之间。

解决此问题的一个想法是添加第三种列，我们称之为“棋盘列”作为中间步骤。从底部开始的偶数步骤将在偶数棋盘列中包含所有单词，而从底部开始奇数个步骤的行将具有奇数棋盘列中的所有单词。然后可以为每个棋盘列选择一个宽度，并将单词的物理列设置为棋盘列的宽度小于它的总和。

但是，这有一个小问题;考虑这个棋盘，在那里我已经明确地标示出棋盘列边界：

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

因为我们选择每个棋盘列的宽度，在不同的棋盘格列说出的话不能重叠。这排除了类似下面的一个解决方案，这是略窄：

aa 
    b c 
d e f 
g hh i j

注意aa和hh重叠 - 尽管他们不在相邻行，所以这是好的。

另一种解决方案是顺序进行布局的话：

当设计一个给定的话，我们就可以简单地选择最小物理列它不看违反规则在上面/左边和下面/左边的文字的位置和长度（已经计算出来）。我有一个这种算法的实现，我将在几天内添加到这个答案中（根据关于作业的网站指南），但这个提示应该足以让你重现自己喜欢的东西。我实现的有趣算法位是Map (Row, LogicalColumn) String -> Map (Row, PhysicalColumn) String类型的十行函数，我建议您尝试使用类似函数。应该可以通过直接巧妙地遍历输入列表来完成此操作（因此可以消除任何映射索引成本），但我无法完全理解它。我们可以通过归纳法证明（我们引入的变量是我们布置文字的顺序），这种方法产生最小宽度的解。

正如所承诺的，我想出了代码：

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

来源

2014-12-20 05:48:30

在Haskell中将字符串格式化为三角形

回答

相关问题