# ENCODING PROCESS:
# The encoding process involve creating a polynomial that represents the message to be encoded and then evaluating that polynomial at different points to create the encoded message. In my code:
#    1. I start by defining the finite field 'GF(256)' with a primitive element 'alpha'. This field has 256 elements and is suitable for byte-sized data operations.
#    2. I assert that the multiplicative order of 'alpha' is 255, ensuring it's a primitive element and can generate all non-zero elements of the field.
#    3. I convert the message, which is in bytes, to field elements. These elements become the coefficients of the Lagrange polynomial i'll create.
#    4. Using the points "(alpha^i, message_element[i]) for i in the range k", I create the Lagrange polynomial 'g'.
#    5. I evaluate this polynomial at 'n' consecutive powers of 'alpha' to form the encoded message. These evaluations are the encoded elements.
#    6. I convert the encoded elements back to bytes to get the final encoded message.

#/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/

# DECODING PROCESS:
# The decoding process is designed to handle the detection and correction of errors in the received message:
#    1. The received message is converted to field elements.
#    2. I will use a voting system to find the correct polynomial representing the original message. For every combination of 'k' elements from the received message (which has 'n' elements after encoding), I:
#        - Create a Lagrange polynomial using the 'k' elements.
#        - Evaluate this polynomial at 'k' consecutive powers of 'alpha'.
#        - Form an identifier for this polynomial from these evaluations.
#        - Tally a vote for each polynomial identifier.
#    3. After all combinations are processed, I determine which polynomial has the majority of votes. This polynomial is considered the correct representation of the original message.
#    4. If a polynomial with a majority is found, I use it to reconstruct the original message by converting its coefficients back to bytes.
#    5. If no majority is found, which indicates that the errors are uncorrectable with the given setup, I raise an 'UnrecoverableMessage' exception.

F.<alpha> = GF(256, 'a', modulus='primitive')
assert alpha.multiplicative_order() == 255

# conversion between field elements and integers/bytes
assert F.from_integer(123).to_integer() == 123


R.<s> = F['s'] # for creating Lagrangre polynomial in this polynomial ring, consult ?R.lagrange_polynomial

n = 10
k = 8

# Your task is to complete these functions
def baby_rs_encode(message: bytes) -> bytes:
    assert len(message) == k
    message_elements = [F.from_integer(b) for b in message]

    points = [(alpha^i, message_elements[i]) for i in range(k)]

    g = R.lagrange_polynomial(points)

    encoded_elements = [g(alpha^i) for i in range(n)]

    encoded_message = bytes([e.to_integer() for e in encoded_elements])
    return encoded_message

class UnrecoverableMessage(Exception):
    pass

# if the message cannot be decoded, UnrecoverableMessage shall be raised
# Decoding function with error correction
def baby_rs_decode(encoded_message: bytes) -> bytes:
    assert len(encoded_message) == n

    encoded_elements = [F.from_integer(b) for b in encoded_message]

    polynomial_votes = {}

    for indices in itertools.combinations(range(n), k):
        points = [(alpha**i, encoded_elements[i]) for i in indices]
        g = R.lagrange_polynomial(points)

        poly_id = tuple(g(alpha**i) for i in range(k))
        
        polynomial_votes[poly_id] = polynomial_votes.get(poly_id, 0) + 1

    majority_poly_id = max(polynomial_votes, key=polynomial_votes.get)
    majority_votes = polynomial_votes[majority_poly_id]

    if majority_votes > 1:
        return bytes([e.to_integer() for e in majority_poly_id])

    print("Cannot determine a majority polynomial for decoding.")
    raise UnrecoverableMessage


message = b'iloveyou'
expected_encoded_message = b'iloveyou\xa8\x98'
recoverable_encoded_message_1 = b'ilov3you\xa8\x98'
recoverable_encoded_message_2 = b'iloveyou\xa8#'
unrecoverbe_encoded_message = b'il0v3you\xa8#'

assert baby_rs_encode(message) == expected_encoded_message
assert baby_rs_decode(expected_encoded_message) == message
assert baby_rs_decode(recoverable_encoded_message_1) == message
assert baby_rs_decode(recoverable_encoded_message_2) == message

try:
    baby_rs_decode(unrecoverbe_encoded_message)
    assert False
except UnrecoverableMessage:
    pass