hw6.py

"""
Created on  Oct 23, 2025
@author(s): Hajin Lim and Evan Su
Pledge:     I pledge my honor that I have abided by the Stevens Honor System.

CS115 - Hw 6
"""

# Number of bits for data in the run-length encoding format.
# The assignment refers to this as k.
COMPRESSED_BLOCK_SIZE = 5

# Number of bits for data in the original format.
MAX_RUN_LENGTH = 2**COMPRESSED_BLOCK_SIZE - 1

# Do not change the variables above.
# Write your functions here. You may use those variables in your code.
# You may write helpers if you see fit. Remember: do not
# import anything, and do not use loops.


def numToBinary(n):
    """Precondition: integer argument is non-negative.
    Returns the string with the binary representation of non-negative integer n.
    If n is 0, the empty string is returned."""
    if n == 0:
        return ""
    else:
        return numToBinary(n // 2) + str(n % 2)


def binaryToNum(s):
    """Precondition: s is a string of 0s and 1s.
    Returns the integer corresponding to the binary representation in s.
    Note: the empty string represents 0."""
    if s == "":
        return 0
    else:
        return binaryToNum(s[:-1]) * 2 + int(s[-1])


def invert_bit(n: str):
    """Inverts a single bit string '0' to '1' and '1' to '0'."""
    return "1" if n == "0" else "0"


def pad_start(s: str, total_length: int, pad_char: str) -> str:
    """Pads the start of string s with pad_char to reach total_length."""
    if len(s) >= total_length:
        return s
    else:
        return pad_char + pad_start(s, total_length - 1, pad_char)


def compress(S):
    """compresses a 64-bit binary image (represented as 1's
    and 0's) using a run-length encoding"""

    def count_consecutive(S, value):
        """Counts how many consecutive letters match value from the start of S"""

        if S == "" or S[0] != value:
            return 0

        return 1 + count_consecutive(S[1:], value)

    def compress_helper(S, current_bit):
        """Recursively compresses S, starting with current_bit = '0'"""

        if S == "":
            return ""

        run_length = min(count_consecutive(S, current_bit), MAX_RUN_LENGTH)
        next_bit = invert_bit(current_bit)

        result = pad_start(numToBinary(run_length), COMPRESSED_BLOCK_SIZE, "0")

        return result + compress_helper(S[run_length:], next_bit)

    return compress_helper(S, "0")


def uncompress(C):
    """uncompresses a run-length encoding to its original
    64-bit binary image"""

    def uncompress_helper(C, current_bit, step):
        if C == "" or step * COMPRESSED_BLOCK_SIZE >= len(C):
            return ""

        start = COMPRESSED_BLOCK_SIZE * step
        end = COMPRESSED_BLOCK_SIZE * (step + 1)

        target = C[start:end]

        uncompressed_block = current_bit * binaryToNum(target)

        return uncompressed_block + uncompress_helper(
            C, invert_bit(current_bit), step + 1
        )

    return uncompress_helper(C, "0", 0)