火柴棍压缩
每周挑战 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])+)', 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
以上就是火柴棍压缩的详细内容，更多请关注硕下网其它相关文章！