Haskell 秒差距 - 解析两个列表

Question

我以 Advent of Code part 16 作为学习如何使用 Parsec 的借口，但我对如何处理这种特定情况感到困惑。

输入格式如下：

Before: [3, 2, 3, 0]
2 3 1 1
After:  [3, 2, 3, 0]

Before: [1, 0, 2, 1]
7 0 1 1
After:  [1, 1, 2, 1]

...

Before: [0, 0, 2, 1]
6 2 3 1
After:  [0, 6, 2, 1]



5 0 2 3
5 1 3 1
...
5 3 2 2

换句话说，首先解析成一个结构的多组三行，由空行分隔，然后是三个空行，然后是一些四位数字的行。

我有每个结构的工作解析器 - Sample 和 MaskedOperation，解析器分别为 sample 和 maskedOp¹ - 但我无法弄清楚如何将它们放在一起以将其解析为 ([Sample], [MaskedOperation]).

我尝试了以下方法：

parseInput :: GenParser Char st ([Sample], [MaskedOperation])
parseInput = do
  samples <- sample `sepBy` (count 2 newline) <* count 3 newline
  operations <- maskedOp `sepBy` newline
  return (samples, operations)

但是当它到达三个换行符时它失败了，期待另一个样本：

(line 3221, column 1):
unexpected "\n"
expecting "Before:"

我如何告诉 parsec 我想要尽可能多地获取，然后使用分隔符（额外的换行符），然后开始阅读其他内容？

¹ 阅读 Advent of Code 问题了解上下文；名字并不重要。

Answer 1

恐怕你不能在这里使用sepBy。

让我们将其简化为将 'a' 解析为样本，将 'b' 解析为换行符。您将解析像

这样的字符串

a b b a b b b c b c b c b

那么解析器在遍历这样一个字符串时是怎么想的呢？让我们来看看：

Parsing a or an empty sequence

[a] b b a b b b c b c b c b

Oh, an a. The sequence is non empty, so I will parse many "bb" >> "a" from now.

a [b b a] b b b c b c b c b

Success! Let's get some more or finish

a b b a [b b] b c b c b c b

Okay, I have found another bb, so the sequence continues. Parsing a

a b b a b b [b] c b c b c b

wat

问题是 解析器不会回滚，除非明确要求这样做。要赋予解析器回滚能力，您必须使用 try 组合器对其进行标记，否则它将无法 "unconsume" 消耗输入。

目前我没有看到比重写 sepBy 组合器更好的方法，让它知道在解析每个分隔符之后它可能需要 return 它回到缓冲区，如果解析 separator >> target 失败：

sepTry a sep = sepTry1 a sep <|> pure []
sepTry1 a sep = liftA2 (:) a (many (try $ sep *> a))

请注意，解析 a 必须包含在 try 部分 - 这是实际触发失败的地方。

为了形象化差异，让我们看一下相同的场景，但使用 sepTry 代替：

...

a [b b a] b b b c b c b c b

Success! Let's try to get one more if possible

a b b a ![b b] b c b c b c b

Okay, I have found another bb, so the sequence continues. Parsing a

a b b a !b b [b] c b c b c b

Not what I expected. Return failure and move cursor to back exclamation mark.

a b b a ![]b b b c b c b c b

Failed parsing bba, parsing sequence finished. Parse bbb

a b b a [b b b] c b c b c b

Success!

在你的情况下，在每个 Sample 之后，这个解析器将尝试读取 2 个换行符，在它们之后有 Sample，或者在失败的情况下读取 3 个换行符并继续 MaskedOperations

Answer 2

我所做的是先运行标记化步骤，然后使用 Parser String ([Sample], [Instruction]) 而不是 Parser Char ([Sample], [Instruction])。列表已经标记化使得忽略空格和其他不相关的标点符号变得容易得多。

solve = parse . tokenize 
  where tokenize = concatMap words . lines . filter (not . (`elem` ",:[]"))
        parse = (,) <$> many sample <*> many instr
        sample = -- ...
        instr = -- ...

不需要回溯，因为示例和说明仅从它们的第一个标记就可以区分。

Haskell 秒差距 - 解析两个列表

Haskell Parsec - parsing two lists of stuff

haskell

parsec