import itertools

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:

# Encoding:
def baby_rs_encode(message: bytes) -> bytes:
    assert len(message) == k

    # Converting message bytes to field elements
    message_value = [F.from_integer(byte) for byte in message]
    
    # Creating Lagrange interpolation polynomial
    points = [(alpha**i, message_value[i]) for i in range(k)]
    l = R.lagrange_polynomial(points)

    # Evaluating the polynomial at points α^0 to α^(n-1)
    encoded_value = [l(alpha**i).to_integer() for i in range(n)]
    return bytes(encoded_value)

# Defining an exception for unrecoverable messages during decoding
class UnrecoverableMessage(Exception):
    pass

# Decoding:
def baby_rs_decode(encoded_value: bytes) -> bytes:
    assert len(encoded_value) == n

    # Converting encoded message bytes to field elements
    encoded_value = [F.from_integer(byte) for byte in encoded_value]
    #print(encoded_value)

    # Polynomials  voting system
    polynomials = {}
    #Starting with i = 0 and iterating over all the possible polynomials and increasing i by one everytime
    for indices in itertools.combinations(range(n), k):
        #prints i:
        points = [(alpha**i, encoded_value[i]) for i in indices]
        try:
            # Creating a Lagrange interpolation polynomial based on the selected points
            l = R.lagrange_polynomial(points)
            # Calculating a hash of the coefficients of the polynomial
            polynomial_hash = hash(str(l.coefficients()))
         
      
            # If the hash of the polynomial coefficients is already in the dictionary
            if polynomial_hash in polynomials:
                #increasing the votes number by one
                polynomials[polynomial_hash]['votes'] += 1
            else:
                # If it's a new hash, create a new entry in the dictionary
                polynomials[polynomial_hash] = {'polynomial': l, 'votes': 1}
        except:
            # If an exception occurs during polynomial creation, continue with the next iteration
            continue

    # Select the polynomial with the majority of votes
    max_vote = max(polynomials.values(), key=lambda x: x['votes'])['votes']
    # Getting the winner polynomial based on the maximum of vote.
    winner_polynomials = [p['polynomial'] for p in polynomials.values() if p['votes'] == max_vote]    
    
    # If there is no winning polynomial 
    if len(winner_polynomials) != 1:
        raise UnrecoverableMessage

    # Decoding the message
    l_winner = winner_polynomials[0]
    # Decoding the message using the selected polynomial and Convert the resulting field elements to integers
    decoded_value = [l_winner(alpha**i).to_integer() for i in range(k)]

    return bytes(decoded_value)



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#'
unrecoverable_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(unrecoverable_encoded_message)
    assert False
except UnrecoverableMessage:
    print("This message can not be recovered!")