OCaml 实现代码挑战

Question

我正在做一个允许使用任何语言的日常代码挑战。我最近一直在通过现实世界的OCaml工作。我真的很想知道如何在惯用的OCaml中解决这个特殊的挑战。下面是我的两个 JavaScript 实现。挑战在于识别数学金字塔中的模式：

1 11 21 1211 111221

(模式是一1，两个1，一个2，一个1，三个1，两个2，一个1，数字从下一个"级别"或行读取)

function createNextLevel(previousLevel, currentLevel = 0, finalLevel = 40) {
let sub = '';
let level = '';
// iterate on string
for (let i = 0; i < previousLevel.length; i++) {
// if we don't have an element to the left or it's  equal to current element
if (!previousLevel[i - 1] || previousLevel[i] === previousLevel[i - 1]) {
sub += previousLevel[i]; // sub '2'
} else {
level += String(sub.length) + sub[0]; // ''
sub = previousLevel[i];
}
// if we're at the end
if (i === previousLevel.length - 1) {
level += String(sub.length) + sub[0]; // '21'
}
}
console.log(level);
if (currentLevel < finalLevel) {
createNextLevel(level, currentLevel + 1)
}
}
var firstLevel = '1';
createNextLevel(firstLevel);
// A bit simpler approach
function createNextLevelPlus(str, currentLevel = 0, finalLevel = 10) {
var delimitedStr = '';
var level = '';
for (let i = 0; i < str.length; i++) {
if (!str[i + 1] || str[i] === str[i+1]) {
delimitedStr += str[i];
} else {
delimitedStr += str[i] + '|';
}
}
delimitedStr.split('|').forEach((group, idx, arr) => {
level += `${String(group.length)}${group[0]}`;
});
console.log(level);
if (currentLevel < finalLevel) {
createNextLevelPlus(level, currentLevel+1)
}
}
var firstLevel = '1';
createNextLevelPlus(firstLevel);

我已经思考了一下如何在OCaml中解决这个问题，但我确信我只是重新发明了一种基于C的方法。我考虑过递归地走弦并在头尾上匹配......查看它们是否相等并将结果存储在某种元组或其他东西中......我有点难以将我的思想扭曲成正确的思维。

Answer 1

这是一个高级分解。

你想要一些迭代函数的东西。有一个循环 + 显示部分和一个迭代部分(如何从一个级别转到下一个级别)。

每次迭代中有两个步骤：

数

• 连续数(将 1211 变成">
一一、一二、二一") 将
• 计数列表转换为列表(将"一一、一二、二一"变为111221)

现在，让我们考虑一下类型。我们从不将这些数字用作数字(没有加法等)，因此它们可以被视为整数列表，或在 OCamlint list中。

另一方面，计数也是一个列表，但列表的每个元素都是一对(计数、值)。例如，"一一、一二、二一"可以表示为[(1, 1); (1, 2); (2, 1)]。OCaml 中此类事物的类型是(int * int) list。

换句话说，算法的重要部分将是：

• 对连续元素进行计数的int list -> (int * int) list类型的函数。
• 类型(int * int) list -> int list的函数，用于将这些计数转换为新列表。

一旦你有了这些，你应该能够把这些碎片放在一起。玩得愉快！