SeaCanal

你是否曾经参加过那些测试，给你一个整数序列，然后你必须说出序列中的下一个数字？例如，你可能看到这样的东西

# Which number fits into the blank spot?
7 1 3 9 3 5 25 19 _

在这个例子中，模式是先减去六，然后加二，然后平方，这意味着正确的答案是 21。

显然，人们在尝试解决这类问题时会有不同的体验，从“哦，这很有趣”到“不了，我宁愿把钉子放进搅拌机里听一会儿”。然而，我想我们都可以同意，无论你认为这些有多容易或多难，它们都如此抽象和毫无意义，我们还有更好的事情可以做，而不是参加这样的测试。这就是 SeaCanal 的想法来源。

什么是 SeaCanal？

SeaCanal 是用 Rust 编写的“序列分析器”（“[seq]uence [anal]ysis” -> “SeqAnal”...你懂了吗？看，如果你不想处理那些糟糕的双关语，你可能不应该读我的 GitHub 上的东西）。基本上，你给它一个数字序列，它会告诉你它能在其中找到任何模式。理论上，如果你要参加那种愚蠢的测试，并且你有电脑，你可以输入序列，SeaCanal 会告诉你模式是什么（但实际不要这么做，作弊是不好的）。

安装

库

SeaCanal 发布在 crates.io 上，所以你可以像使用任何其他 Cargo 包一样使用它。

将以下内容添加到您的 Cargo.toml 中的 [dependencies] 部分

sea-canal = "0.2"

将以下内容添加到您的项目根目录下

extern crate sea_canal;

下次您运行 cargo build 时，该软件包将为该项目安装。

独立 CLI

只需运行 cargo install sea-canal。

用法

库

首先，导入 Analyzer

use sea_canal::Analyzer;

创建一个分析您想要分析的任何序列的分析器

let analyzer = Analyzer::from_seq(&[7, 1, 3, 9, 3, 5, 25, 19]);

然后调用任一 find_patterns 方法来查找所有模式，或调用任一 find_any_pattern 方法来查找单个模式（根据方法的不同，可以是最大长度或精确长度）。

println!("{:?}", analyzer.find_any_pattern(7))

独立 CLI

假设你已经正确设置了 cargo install 的路径，你可以使用 scnl 运行 SeaCanal。然后只需输入一个（以空白分隔的）整数序列，然后按“Enter”键。

或者，为了查看 SeaCanal 分析一些预设序列的（非常小的）样本，运行 scnl --sample。

SeaCanal 是如何工作的？

（这真的很详细，所以你可以随意跳过，尤其是如果你觉得基本的算术很无聊）。

首先，SeaCanal 会查看序列中每对相邻数字，并计算可能从一数变到另一数的操作。你可以查看它在 操作类型 中支持的操作。例如，上述第一个序列的分析看起来像这样

7 -> 1:   =1,  -6,  /7
1 -> 3:   =3,  +2,  *3
3 -> 9:   =9,  +6,  *3, ^2
9 -> 3:   =3,  -6,  /3, root 2
3 -> 5:   =5,  +2
5 -> 25:  =25, +20, *5, ^2
25 -> 19: =19, -6

为了更容易讨论，我们将序列中的相邻数字称为“转换”，将描述转换的可能操作的集合称为“选择”。

然后 SeaCanal 开始尝试找到操作最少的模式。这意味着它首先尝试找到只有一个操作的模式；如果找不到合适的模式，它就尝试找到两个操作的模式。这个过程会一直重复，直到找到匹配的模式或达到用户指定的上限（这是通过用户传入的）。这是为了确保它不会生成无用的模式。这通常很有帮助；对于这个例子，模式 [/7, *3, *3, /3, +2, *5, -6] 虽然这些数字在技术上可以是该模式描述的序列的第一个迭代，但这个模式并没有什么意义。

为了识别给定长度 n 的模式，SeaCanal 将转换分成大小为 n 的切片（最后一个切片可能更小，这没关系），然后将出现在切片相同位置的转换组合在一起。最后，SeaCanal 尝试在给定组中的所有转换中找到一个共同的选择。

以我们的例子为例，当 n = 1 时，切片将只是每个转换自己的切片，所以所有转换都会组合在一起。找到长度为 1 的模式意味着尝试找到一个在每个转换中都出现的选项。显然，在这种情况下，没有这样的选项。

# There is no operation that appears in each of the lists below
7 -> 1:   -6,  /7
1 -> 3:   =3,  +2,  *3
3 -> 9:   =9,  +6,  *3, ^2
9 -> 3:   =3,  -6,  /3, root 2
3 -> 5:   =5,  +2
5 -> 25:  =25, +20, *5, ^2
25 -> 19: =19, -6

我们继续到 n = 2。切片看起来像这样

Slice 1: 7 -> 1,  1 -> 3
Slice 2: 3 -> 9,  9 -> 3
Slice 3: 3 -> 5,  5 -> 25
Slice 4: 25 -> 19

并且组会是这样的

Group 1: 7 -> 1, 3 -> 9, 3 -> 5, 25 -> 19
Group 2: 1 -> 3, 9 -> 3, 5 -> 25

（如果你在行中均匀地分布每个切片，那么组就是单独的列）。

在第一个组中，我们的选择列表是

7 -> 1:   =1,  -6,  /7
3 -> 9:   =9,  +6,  *3, ^2
3 -> 5:   =5,  +2
25 -> 19: =19, -6

我们仍然没有在任何选择中出现的操作，这意味着没有长度为 2 的模式。

当 n = 3 时，切片会是

Slice 1: 7 -> 1,  1 -> 3, 3 -> 9
Slice 2: 9 -> 3,  3 -> 5, 5 -> 25
Slice 3: 25 -> 19

而组会是

Group 1: 7 -> 1, 9 -> 3, 25 -> 19
Group 2: 1 -> 3, 3 -> 5
Group 3: 3 -> 9, 5 -> 25

观察第一个组，我们发现共同操作 -6

7 -> 1:   =1,  -6,  /7
9 -> 3:   =3,  -6,  /3, root 2
25 -> 19: =19, -6

在第二个组中，我们发现 +2

1 -> 3:   =3,  +2,  *3
3 -> 5:   =5,  +2

最后，在最后一个组中，我们发现 ^2，这完成了模式

3 -> 9:   =9,  +6,  *3, ^2
5 -> 25:  =25, +20, *5, ^2

(注意，每个转换的共同操作实际上不必像这三个组那样位于相同的“列”；我只是这样放置，以便更直观地注意到)

操作类型

内置

基本算术

• *
• /

注意：模运算尚未实现

指数

• 平方
• 平方根
• 立方
• 立方根

常量

序列中的常量元素。例如，序列 2 6 8 4 12 8 4 可以用以下模式描述：*3, =8, -4（其中 =8 表示常量值 8）。

单独使用常量模式并不很有趣，因为它们在第二次迭代之后往往会开始重复。然而，当与 元模式 结合使用时，这种情况并不一定发生。

自定义操作

您可以通过创建 CustomPatternElem 结构体的实例来定义自定义操作。这样做需要定义一个类型为 (i32, i32) -> bool 的函数，该函数作为测试来确定序列中给定相邻数字是否可以用该操作来描述。例如，以下代码测试了一个使用自定义操作的第四次幂序列

#[macro_use]
extern crate sea_canal;

use sea_canal::{Analyze, Analyzer};
use sea_canal::pattern::{CustomPatternElem, Pattern};
use sea_canal::pattern::PatternElem::*;

fn pow4(i: i32, j: i32) -> bool {
    i * i * i * i == j
}

let pow4_pattern = CustomPatternElem::new(pow4, "^4");
let slice = &[2, 16, 3, 81, 68];
let analyzer = Analyzer::with_custom_patterns(slice, vec![pow4_pattern.clone()]);

assert_eq!(Some(pat![Custom(pow4_pattern), Minus(13)]), analyzer.find_any_pattern(4));

元模式

当操作不是常量但本身遵循模式时，发生“元模式”。例如，考虑以下序列

1 2 4 7 11...

注意，每个转换都是一个比上一个多 1 的加法操作（+1，+2，+3...）。我们无法用我们上面定义的方式用模式描述这个序列，但我们仍然可能想要一种方法来识别此类序列的行为。

元模式不必描述序列中的每个操作数；就像常规操作数一样，它们只需要描述给定的选择。例如，以下序列符合以下模式：[+1, +2, +3, +4 ...], =10

10 11 10 12 10 13

元模式也不一定只能有一个操作数类型。例如，我们可以修改上面的序列以匹配以下模式：[+1, *2, +3, *4...], =10

10 11 10 20 10 13 10 40

元模式通过分析选择操作数的序列，看是否有模式出现来实现。要成为有效的元模式，每个操作数必须有一个数值参数（例如，/ 是有效的，但 root 2 是无效的）并且操作数的类型必须是重复的。

请注意，在搜索操作数的数值中的模式时，不会考虑元模式。例如，如果一个序列由操作 [+1, +2, +4, +7, +11] 描述，它将不会报告找到元模式。

发现元模式

要发现元模式，请使用 with_meta 构造函数

let slice = &[10, 11, 10, 12, 10, 13];
let analyzer = Analyzer::with_meta(slice);

assert_eq!(pat!(Meta(pat!(Plus(1), Plus(2), Plus(3))), Const(10)), analyzer.find_any_pattern(4));

要在搜索元模式时使用自定义操作，请使用 with_options 构造函数。