Algorithm - Python - 帽子を全員で揃える(ランレングス符号化(RLE(Run Length Encoding)、連長圧縮)、圧縮、復号化、1パス)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple
• Emacs (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の1章(帽子を全員で揃える)、練習問題、パズル問題4.を取り組んでみる。

コード(Emacs)

#!/usr/bin/env python3
import unittest
from run_length_encoding import encode, decode


class Test(unittest.TestCase):
    s1 = ''
    s2 = 'B'
    s3 = 'BWWWWBWWWW'
    s4 = 'WWWWBWWWWB'
    s5 = 'WWWWWWWWWWWWWBBWWWWWWWWWWWWBBBBB'

    def sefUp(self):
        pass

    def tearDown(self):
        pass

    def test_empty(self):
        encoded = encode(Test.s1)
        self.assertEqual(encoded, '')

    def test_one(self):
        encoded = encode(Test.s2)
        self.assertEqual(encoded, '1B')

    def test_s3(self):
        encoded = encode(Test.s3)
        self.assertEqual(encoded, '1B4W1B4W')

    def test_s4(self):
        encoded = encode(Test.s4)
        self.assertEqual(encoded, '4W1B4W1B')

    def test_s5(self):
        encoded = encode(Test.s5)
        self.assertEqual(encoded, '13W2B12W5B')

    def test_decode_empty(self):
        decoded = decode(encode(Test.s1))
        self.assertEqual(decoded, Test.s1)

    def test_decode_one(self):
        decoded = decode(encode(Test.s2))
        self.assertEqual(decoded, Test.s2)

    def test_decode_s3(self):
        decoded = decode(encode(Test.s3))
        self.assertEqual(decoded, Test.s3)

    def test_decode_s4(self):
        decoded = decode(encode(Test.s4))
        self.assertEqual(decoded, Test.s4)

    def test_decode_s5(self):
        decoded = decode(encode(Test.s5))
        self.assertEqual(decoded, Test.s5)


if __name__ == '__main__':
    unittest.main()

#!/usr/bin/env python3

s1 = ''
s2 = 'B'
s3 = 'BWWWWBWWWW'
s4 = 'WWWWBWWWWB'
s5 = 'WWWWWWWWWWWWWBBWWWWWWWWWWWWBBBBB'
str_list = [s1, s2, s3, s4, s5]


def encode(s: str) -> str:
    encoded = ''
    str_len = len(s)
    if str_len == 0:
        return encoded
    start = 0
    character = s[0]
    for i in range(1, str_len):
        if character != s[i]:
            encoded += f'{i - start}{character}'
            character = s[i]
            start = i
    encoded += f'{str_len - start}{character}'

    return encoded


def decode(s: str) -> str:
    decoded = ''
    str_len = len(s)
    if str_len == 0:
        return decoded
    start = 0
    num_str = s[0]
    for i in range(1, len(s)):
        if s[i].isdigit():
            num_str += s[i]
        else:
            decoded += s[i] * int(num_str)
            num_str = '0'

    return decoded


if __name__ == '__main__':
    for s in str_list:
        encoded = encode(s)
        decoded = decode(encoded)
        for a, b in zip(['文字列', '符号化', '復号化', '比較'],
                        [s, encoded, decoded, s == decoded]):
            print(f'{a}: {b}')
        print()

入出力結果(Terminal, Jupyter(IPython))

$ ./run_length_encoding_test.py 
..........
----------------------------------------------------------------------
Ran 10 tests in 0.000s

OK
$ ./run_length_encoding.py 
文字列: 
符号化: 
復号化: 
比較: True

文字列: B
符号化: 1B
復号化: B
比較: True

文字列: BWWWWBWWWW
符号化: 1B4W1B4W
復号化: BWWWWBWWWW
比較: True

文字列: WWWWBWWWWB
符号化: 4W1B4W1B
復号化: WWWWBWWWWB
比較: True

文字列: WWWWWWWWWWWWWBBWWWWWWWWWWWWBBBBB
符号化: 13W2B12W5B
復号化: WWWWWWWWWWWWWBBWWWWWWWWWWWWBBBBB
比較: True

$