火柴棍压缩

今日不肯埋头，明日何以抬头！每日一句努力自己的话哈哈~哈喽，今天我将给大家带来一篇《火柴棍压缩》，主要内容是讲解等等，感兴趣的朋友可以收藏或者有更好的建议在评论提出，我都会认真看的！大家一起进步，一起学习！

每周挑战 296

穆罕默德·s·安瓦尔 (mohammad s. anwar) 每周都会发出“每周挑战”，让我们所有人都有机会为两周的任务提出解决方案。我的解决方案首先用python编写，然后转换为perl。这对我们所有人来说都是练习编码的好方法。

挑战，我的解决方案

任务 1：字符串压缩

任务

您将获得一串字母字符，$chars。

编写一个脚本，使用游程编码来压缩字符串，如示例所示。

压缩单元可以是单个字符，也可以是计数后跟一个字符。

奖励：编写一个解压缩函数。

我的解决方案

由于正则表达式的强大功能，这是一项非常简单的任务。 python 和 perl 都允许替换值是一个函数。因此，我有一个名为 sc 的函数，它将多个字母转换为数字和字母。例如如果输入是aaa，它将返回3a。

def sc(match):
    m = match.group(0)
    return str(len(m)) + m[0]

然后就是根据需要调用这个函数了。

def string_compress(s: str) -> str:
    return re.sub(r'(([a-z])\2+)', sc, s)

解压缩函数（仅限python）以类似的方式工作。它采用数字后跟字母的模式，并将其更改为重复指定次数的字母。

def usc(match):
    m = match.group(0)
    return m[-1] * int (m[:-1])

def string_decompress(s: str) -> str:
    return re.sub(r'(\d+[a-z])', usc, s)

为了从命令行执行，我使用 argparse 模块来查看是否指定了 --decompress 选项。

def main():
    parser = argparse.argumentparser()
    parser.add_argument("--decompress", help="decompress the input", action='store_true')
    parser.add_argument("str", help="the string to compress/decompress")
    args = parser.parse_args()

    if args.decompress:
        result = string_decompress(args.str)
    else:
        result = string_compress(args.str)
    print(result)

示例

$ ./ch-1.py abbc
a2bc

$ ./ch-1.py aaabccc
3ab3c

$ ./ch-1.py abcc
ab2c

$ ./ch-1.py --decompress a2bc
abbc

$ ./ch-1.py --decompress 3ab3c
aaabccc

$ ./ch-1.py --decompress ab2c
abcc

任务2：火柴方

任务

给你一个整数数组，@ints。

编写一个脚本来查找是否可以使用给定数组 @ints 中的棍子制作一个正方形，其中 $ints[ì] 是第 i 根棍子的长度。

我的解决方案

这会有点长，所以请系好安全带。我检查的第一件事是木棍的总和是否能被四整除。如果不是，没有可能的解决方案，我可以返回 false

我还可以检查没有一根棍子比一侧长。如果发生这种情况，我也会返回 false。

通过这两项检查，所有示例都会给出正确的结果。然而，它会错误地报告 4 3 3 3 3 为真，而实际上并非如此。

尝试二

查看示例和我自己的想法，我认为解决方案是匹配一对值来匹配每一侧。因此，对于示例 3 4 1 4 3 1，我们有两对 3 和 1 棍子，组成四根棍子。这将解决 4 3 3 3 3 问题，因为 3 没有匹配的。

但是如果棍子是 4 4 3 1 2 1 1，这将不起作用，因为一侧使用三根棍子（一根 2 和两根 1）

尝试三

所以我的下一次尝试有点复杂，我认为这是一个很好的解决方案......直到它不是。对于这次尝试，我从最长的棍子开始。如果不是边的长度，我就拿完成边所需的下一根最长的棍子，然后重复，直到没有可能的解决方案。使用此方法，以下解决方案是正确的。

• 4 4 3 1 2 1 1
• 9 5 4 3 3 3 3 3 3
• 9 6 3 5 4 3 3 3
• 9 6 3 5 4 3 3 2 1

我以为这就是解决方案，直到我意识到 9 5 3 1 5 2 2 3 3 3 不起作用。第一条边是 9，下一条边是 5 3 1，第三条边会失败，只有 5 3 而没有 1。

尝试四

此时，我开始怀疑是否有可能想出一个不涉及暴力的解决方案。所以我就睡在上面，在平板电脑上写下了很多东西（我正在度假，所以不能使用我的白板），然后又睡在上面。我的结论是使用递归函数是唯一的解决方案。

也许我只是想太多了，或者也许有一个我刚刚想到的真正简单的解决方案（就像上周的情况）。

最终代码

还在读书吗？干得好:)

对于这个任务，我有一个名为 make_side 的递归函数。它需要一个剩余棍棒的列表（perl 中的 arrayref）以及所需的长度。然后它会遍历剩余的棍子（首先是最高的）。然后发生以下三件事之一：

• 如果棍子比要求的长度长，我会跳过它。
• 如果是需要的长度，我就返回。
• 如果它很短，我会使用它并再次调用该函数以使用另一根棍子。该调用会删除已使用的棍子，并根据已使用的棍子的长度减少所需的长度。

该函数将返回所使用的棍子列表，如果未找到有效的棍子组合，则返回 none （perl 中的 undef）。

def make_side(sticks: list, l: int) -> list:
    pieces = sorted(set(sticks), reverse=true)
    for piece in pieces:
        if piece > l:
            continue

        if piece == l:
            return [piece]

        sticks_copy = sticks.copy()
        sticks_copy.remove(piece)
        result = make_side(sticks_copy, l - piece)
        if result:
            # we have a solution. send it upstream
            return [piece, *result]

    return false

拼图的最后一块，我执行第一部分中提到的检查（总和可以被四整除，不超过边长），然后调用上面的函数。如果返回 none，我返回 false。如果所有的棍子都被使用，我返回true。

def matchstick_square(sticks: list) -> str:
    if sum(sticks) % 4:
        return false

    side_length = sum(sticks) // 4

    if any(i > side_length for i in sticks):
        return false

    while sticks:
        side = make_side(sticks, side_length)
        if not side:
            return false
        for stick in side:
            sticks.remove(stick)

    return true

示例

$ ./ch-2.py 1 2 2 2 1
True

$ ./ch-2.py 2 2 2 4
False

$ ./ch-2.py 2 2 2 2 4
False

$ ./ch-2.py 3 4 1 4 3 1
True

$ ./ch-2.py 9 5 3 1 5 2 2 3 3 3
True

终于介绍完啦！小伙伴们，这篇关于《火柴棍压缩》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布文章相关知识，快来关注吧！