マッチ棒圧縮

ウィークリーチャレンジ 296

Mohammad S. Anwar は毎週、毎週 2 つのタスクに対する解決策を全員が考え出すチャンスであるウィークリー チャレンジを送信します。私のソリューションは最初に 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 番目のスティックの長さ) のようにスティックを使用して 1 つの正方形を作成できるかどうかを確認するスクリプトを作成します。

私の解決策

これは少し長くなりますので、しっかりと理解してください。最初にチェックするのは、スティックの合計が 4 で割り切れるかどうかです。そうでない場合、考えられる解決策はなく、 false を返すことができます

一本の棒が一辺よりも長いものがないことも確認できます。このような場合も false を返します。

これら 2 つのチェックを行うと、すべての例で正しい結果が得られます。ただし、実際にはそうでない場合でも、4 3 3 3 3 が true であると誤って報告されます。

2 回試してみる

例と私自身の考えを見て、解決策は、それぞれの側に一致する値のペアを一致させることであると考えました。したがって、例 3 4 1 4 3 1 では、3 と 1 のスティックが 2 組あり、4 になります。これにより、3 には一致するものが存在しないため、4 3 3 3 3 の問題が解決されます。

しかし、スティックが 4 4 3 1 2 1 1 の場合、片側が 3 本のスティック (2 が 1 つと 1 が 2 つ) を使用するため、これは機能しません

3 回目の試行

それで、私の次の試みはもう少し複雑で、良い解決策だと思っていましたが、そうではありませんでした。今回は一番長い棒から始めてみました。辺の長さが合わない場合は、辺を完成させるのに必要な次に長い棒を取り、解決策がなくなるまで繰り返しました。この方法を使用すると、次の解決策が当てはまります。

• 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、3 面目は 5 3 で 1 がないと失敗します。

4 回の試行

この時点で、私は力技を使わない解決策を考え出すことは可能なのかと考え始めました。そこで私はその上で寝て、タブレットにたくさんのことを走り書きし（休暇中なのでホワイトボードは使えません）、またその上で寝ました。私の結論は、再帰関数を使用することが唯一の解決策であるということです。

もしかしたら、私がこれらすべてを考えすぎているだけかもしれません。あるいは、私がたった今思いついた本当に簡単な解決策があるのか​​もしれません (先週の場合と同様)。

最終的なコード

まだ読んでいますか?よくやった:)

このタスクには、make_side という再帰関数を使用します。残りのスティックのリスト (Perl では arrayref) と必要な長さを受け取ります。次に、残りのスティックを通過します（最初に最も高いスティック）。その後、次の 3 つのうちの 1 つが起こります:

• スティックが必要な長さより長い場合はスキップします。
• ご希望の長さでしたら返品させていただきます。
• 短い場合は、それを使用し、もう一度関数を呼び出して別のスティックを使用します。この呼び出しにより、使用済みのスティックが削除され、使用済みのスティックの長さだけ必要な長さが減ります。

関数は使用されているスティックのリストを返します。スティックの有効な組み合わせが見つからない場合は None (Perl では undef) を返します。

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

パズルの最後のピースとして、最初の部分で説明したチェックを実行し (合計は 4 で割り切れる、スティックは 1 辺より長くない)、その後、上記の関数を呼び出します。 None が返された場合は false を返します。すべてのスティックを使用した場合は true を返します。

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

例

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)

以上がマッチ棒圧縮の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。