OCaml实现代码挑战

Question

我正在进行每日代码挑战，允许使用任何语言。我最近一直在使用Real-World 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）

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

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

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

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

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