Agent Work: QR Code

Claude Sonnet 4.6 · COMP 140: Computational Thinking

Module 5: QR Codes

The goal of this assignment is to use the computational thinking process to help create a real world product. We will follow the process of: 1. Reading and understanding the problem description. 2. Determining the inputs and outputs. 3. Decomposing the problem into subproblems, as appropriate. 4. Designing a computational recipe (algorithm) to solve the subproblems/problem. 5. Implementing your solution.

Be sure to read the entire assignment before beginning.

Testing Your Solution

Use the grade tool to test your implementation:

bin/grade ./workspaces/<your_workspace>

Or if working in a workspace, simply use the grade tool provided by the agent harness.

---

1. The Problem

In this assignment, you will generate error-correction information for QR codes. You will need to implement a method to generate a Reed-Solomon error-correction code for a block of text.

We have broken down the problem into manageable pieces. You should carefully focus on each subproblem, as they will combine nicely to solve the overall problem. This is one good example of where the computational thinking process we have been teaching throughout the course really starts to shine!

2. A Solution Strategy

First, make sure you understand the problem we are trying to solve. Once you do, we need to develop a solution strategy. We are going to use polynomial arithmetic to solve this problem.

Reed-Solomon encoding consists of a number of error correction bytes, derived from the data that's being encoded. These error correction bytes come from dividing a polynomial representing your data, by a polynomial known to both the encoder and decoder (the "generator" polynomial).

To make sure that each of the coefficients of this remainder fit in a byte, each of the coefficients of these polynomials are numbers in $\mathbb{Z}_{256}$; this means that we'll need to be careful to use $\mathbb{Z}_{256}$ arithmetic instead of normal arithmetic in our recipe.

The message polynomial, which is our numerator, will be constructed as follows:

$message = \sum\limits_{i = 0}^{n-1} m_ix^{k+n-i-1}$ where $M = m_0m_1\cdots m_{n-2}m_{n-1}$ are the $n$ bytes in our message, and $k$ is the number of error correction bytes required.

The generator polynomial, which is our denominator, will constructed as follows:

$generator = \prod\limits_{i = 0}^{k-1} (x - 2^i)$ where $k$ is the number of error correction bytes required.

Note that both $message$ and $generator$ have coefficients in $\mathbb{Z}_{256}$. In particular, we must compute $2^{i}$ in $\mathbb{Z}_{256}$ to make sure this holds.

Once we have these polynomials, we will use polynomial long division to compute $remainder$ from dividing the $message$ by the $generator$ ($\frac{message}{generator}$). From here, we can pull the coefficients out of $remainder$ to get our Reed-Solomon error correction data.

Reed-Solomon Example

Here's a brief example of Reed-Solomon encoding:

For a message of bytes [32, 91, 11, 120, 209, 114, 220, 77] with k=2 error correction bytes:

1. Create message polynomial: $32x^9 + 91x^8 + 11x^7 + 120x^6 + 209x^5 + 114x^4 + 220x^3 + 77x^2$ 2. Create generator polynomial: $(x - 1)(x - 2) = x^2 - 3x + 2$ (in $\mathbb{Z}_{256}$, note $-3 = 253$) 3. Divide and get remainder: The remainder coefficients are the error correction bytes

3. Breaking Down the Problem: Manipulating Individual Terms

The first sub-problem you will need to solve is to represent polynomials and polynomial math over $\mathbb{Z}_{256}$ in Python. We have designed a Polynomial API for this purpose, which is the API you will be implementing with your Polynomial class on this assignment.

We have provided a partial implementation of Polynomial for you to start with in the template (solution.py in your workspace). We have chosen to represent polynomials internally as a dictionary of terms. A simplified polynomial only has one coefficient for each term, $ax^n$, with coefficient $a$ and power $n$. So, the terms dictionary maps powers ($n$) to coefficients ($a$). For example, the polynomial $x^5 + 4x^2 + 5$ would be represented by the dictionary {5: 1, 2: 4, 0: 5}.

Further, we have provided you with implementations of several general "utility" methods (get_coefficient, get_degree, get_terms, the constructor method __init__, the string method __str__, and equality/inequality methods __eq__, __ne__).

You will need to implement several methods that operate on a single Polynomial object and a single term: add_term, subtract_term, and multiply_by_term. Implementing these methods will help you to later implement methods that operate on two Polynomial objects.

There are several things that you should keep in mind when implementing the following three methods:

First, you should make sure to satisfy the Polynomial API (see the template docstrings), which specifies the exact inputs and outputs for each method.
Second, remember that all of the coefficient arithmetic should use the provided z256 module (from lib). As an example of how to use this module, you can look at the implementation of the provided divide_terms function. We chose not to include this function within the Polynomial class, because rather than operating on a single Polynomial and a single term, it operates on two single terms.
Last, recall that immutability has many benefits; thus, when implementing these methods, you should not mutate the Polynomial on which the method is called; rather, each of the following three methods should return a new Polynomial object reflecting the results of the operation.

A. Add Term

Write a method on the Polynomial class, add_term(self, coefficient, power), which adds a single input term $b_mx^m$ to self, a polynomial of the form $p = a_nx^n + \ldots + a_1x + a_0$. Your method should produce the polynomial $r = p + b_mx^m$, where the coefficients are added in $\mathbb{Z}_{256}$.

B. Subtract Term

Write a method on the Polynomial class, subtract_term(self, coefficient, power), which subtracts a single input term $b_mx^m$ from self, a polynomial of the form $p = a_nx^n + \ldots + a_1x + a_0$. This should produce the polynomial $r = p - b_mx^m$, where the coefficients are subtracted in $\mathbb{Z}_{256}$. *Before writing this method, think carefully about the properties of $\mathbb{Z}_{256}$ math! You should not be duplicating code that you have already written.*

C. Multiply by Term

i. Recipe

Clearly describe a recipe for multiplying a polynomial $p = a_nx^n + \ldots + a_1x + a_0$ by a single term $b_mx^m$. Your recipe should produce the polynomial $r = p \times b_mx^m$, where the coefficients have been multiplied in $\mathbb{Z}_{256}$.

ii. Code

Write a method on the Polynomial class, multiply_by_term(self, coefficient, power), which implements your recipe.

4. Breaking Down the Problem: Manipulating Polynomials

Now that we have some basic polynomial methods, including methods that deal with single terms, let's build upon the recipes and functions we've already created to manipulate whole polynomials at a time.

*Everything in this section will benefit from using the methods and recipes that have already been implemented for polynomials! If you don't find you are using what you've already developed, you should step back and rethink what you are doing.* If you choose to reuse any of the methods or functions introduced in part 3 (and you should!), you may simply refer to them by name rather than writing separate recipes for them. This applies to the provided ones (e.g. get_coefficient or divide_terms), as well as any that you implemented -- including those for which you were not required to write a recipe. As usual, however, if you choose to create any additional helper functions outside of the previously defined methods of the polynomial class, you must write separate recipes for these helper functions. Further, each recipe in this section builds upon the previous one; thus, you can also refer to these by name in subsequent parts.

You should follow these guidelines when implementing the following three methods:

Make sure to satisfy the Polynomial API we have given you, which specifies the exact inputs and outputs for each method.
Perform all of the coefficient arithmetic in $\mathbb{Z}_{256}$.
Do not mutate the Polynomial on which the method is called; instead, return a new Polynomial object reflecting the results of the operation.

A. Polynomial Addition

i. Recipe

Clearly describe a recipe for adding two polynomials $p = a_nx^n + \ldots + a_1x + a_0$ and $q = b_mx^m + \ldots + b_1x + b_0$ together. Your recipe should produce the polynomial $r = p + q$, where the coefficients are added in $\mathbb{Z}_{256}$. You should make use of the fact that you have already created a method for adding a single term to a polynomial.

ii. Code

Write a method on the Polynomial class, add_polynomial(self, other_polynomial), which implements your recipe.

B. Polynomial Subtraction

Write a method on the Polynomial class, subtract_polynomial(self, other_polynomial), which subtracts an input polynomial other_polynomial, of the form $q = b_mx^m + \ldots + b_1x + b_0$, from self, a polynomial of the form $p = a_nx^n + \ldots + a_1x + a_0$. Your method should return the polynomial $r = p - q$.

This should look *very* similar to polynomial addition. You therefore do not need to write an additional recipe.

C. Polynomial Multiplication

i. Recipe

Clearly describe a recipe for multiplying two polynomials $p = a_nx^n + \ldots + a_1x + a_0$ and $q = b_mx^m + \ldots + b_1x + b_0$ together. Your recipe should produce the polynomial $r = p \times q$, where the coefficients have been multiplied in $\mathbb{Z}_{256}$. You should make use of the fact that you have already written recipes to multiply a polynomial by a single term and to add two polynomials.

ii. Code

Write a method on the Polynomial class, multiply_by_polynomial(self, other_polynomial), which implements your recipe.

D. Polynomial Remainders

i. Recipe

Clearly describe a recipe for finding the remainder when dividing two polynomials $p = a_nx^n + \ldots + a_1x + a_0$ and $q = b_mx^m + \ldots + b_1x + b_0$, where $p$ is the numerator and $q$ is the denominator. Your recipe should produce the remainder polynomial, where the coefficients have been computed in $\mathbb{Z}_{256}$. You should make use of the fact that you were provided with methods for dividing terms, getting a polynomial's degree, and getting a polynomial's coefficient; further, you should make use of the fact that you have already written a recipe for multiplying two polynomials.

ii. Code

Write a method on the Polynomial class, remainder(self, denominator), which implements your recipe.

5. Solving the Problem

At this point, you have a representation of polynomials with coefficients in $\mathbb{Z}_{256}$, and ways to manipulate them. You should test your code to confirm that everything from Parts 3 and 4 succeeds before continuing.

To finish our Reed-Solomon encoding, we're going to need to create the polynomials and divide them, as explained in section 2.

As your work on these problems, you should refer to the hand-calculated example from section 2 for guidance. Note that you need to manipulate polynomials for this function: make sure you're using the `Polynomial` class you created above, and not solving the same problems all over again!

A. Creating the Message Polynomial

Write a function create_message_polynomial(message, num_correction_bytes) which implements the mathematical specification given in section 2 to create the message polynomial. This function should take $M$ and $k$, described above, as input. The message, $M$, is represented as a list of numbers (each between 0 and 255 inclusive). The number of error correction bytes to be generated, $k$, is an integer. The function should produce as output an instance of your Polynomial class representing the message polynomial described in section 2.

Note that the mathematical formula given in section 2 effectively *is* the recipe for this function!

B. Creating the Generator Polynomial

Write a function create_generator_polynomial(num_correction_bytes) which implements the mathematical specification given in section 2 to create the generator polynomial. This function should take $k$, described above, as input. Again, the number of error correction bytes to be generated, $k$, is an integer. The function should produce as output an instance of your Polynomial class representing the generator polynomial described in section 2.

Again, note that the mathematical formula given in section 2 is the recipe for this function!

Make sure that you remember to do all of your coefficient arithmetic in $\mathbb{Z}_{256}$, making use of the z256 module from lib.

C. Reed-Solomon Encoding

Write a function reed_solomon_correction(message_data, num_correction_bytes) that returns the remainder polynomial for the Reed-Solomon encoding for the input data message_data when we need num_correction_bytes error correction bytes. Given what you've already done, you should find that this function is fairly simple. If you are writing anything complex, step back and think about what you have already written in parts 4 and 5!

6. Discussion (Written Response)

1. If you are given a message that you want to encode and a value of $k$, which indicates how many error correction bytes you need, is it possible to guarantee that you will not have any coefficients that are equal to zero in the remainder from dividing the message polynomial by the generator polynomial? If there were coefficients that are equal to zero in the encoded data, would it be a problem? Why or why not? 2. We have discussed the importance of modularity and writing your recipes/code in such a way that you can reuse them. If you needed a Polynomial class to represent polynomials with regular, real-number coefficients (as opposed to coefficients that are elements of $\mathbb{Z}_{256}$), how could you minimally change the code you have already written in order to reuse it for this purpose?

Answer these questions by expressing your ideas in a few sentences of English. You do not need to prove anything mathematically or show any Python.

Write your response in writeup.md.

--- *COMP 140: Computational Thinking, Rice University*

solution.py8.1 KB

python

"""
QR Code Generator
"""

import comp140_module5 as qrcode
import comp140_module5_z256 as z256

def divide_terms(coefficient1, power1, coefficient2, power2):
    """
    Computes the quotient of two terms.

    The degree of the first term, power1, must be greater than or
    equal to the degree of the second term, power2.

    Inputs:
        - coefficient1: a Z_256 number representing the coefficient of the first polynomial term
        - power1: an integer representing the power of the first term.
        - coefficient2: a Z_256 number representing the coefficient of the second polynomial term
        - power2: an integer representing the power of the second term.

    Returns: an instance of a Polynomial that is the resulting
    term.
    """
    # From recipe: (a*x^b) / (c*x^d) = (a/c) * x^(b-d)
    new_coeff = z256.div(coefficient1, coefficient2)
    new_pow = power1 - power2

    # Represent our answer as a Polynomial
    divided = Polynomial()
    divided = divided.add_term(new_coeff, new_pow)
    return divided

class Polynomial:
    """
    A class used to abstract methods on a polynomial in the finite
    field Z_256 (including numbers from 0 through 255).

    Since 256 is not prime, but is rather of the form p^n = 2^8, this
    representation uses special arithmetic via the z256 module so as to
    preserve multiplicative inverses (division) inside this field.
    """

    def __init__(self, terms=None):
        """
        Creates a new Polynomial object.  If a dictionary of terms is provided,
        they will be the terms of the polynomial,
        otherwise the polynomial will be the 0 polynomial.

        inputs:
            - terms: a dictionary of terms mapping powers to coefficients or None
              (None indicates that all coefficients are 0)
        """
        if terms != None:
            self._terms = dict(terms)
        else:
            self._terms = {}

    def __str__(self):
        """
        Returns: a string representation of the polynomial, containing the
        class name and all of the terms.
        """
        # Create a string of the form "ax^n + bx^n-1 + ... + c" by
        # creating a string representation of each term, and inserting
        # " + " in between each
        term_strings = []

        # Add the highest powers first
        powers = list(self._terms.keys())
        powers.sort(reverse=True)
        for power in powers:
            coefficient = self._terms[power]
            # Don't print out terms with a zero coefficient
            if coefficient != 0:
                # Don't print "x^0"; that just means it's a constant
                if power == 0:
                    term_strings.append("%d" % coefficient)
                else:
                    term_strings.append("%d*x^%d" % (coefficient, power))

        terms_str = " + ".join(term_strings)
        if terms_str == "":
            terms_str = "0"
        return "Polynomial: %s" % terms_str

    def __eq__(self, other_polynomial):
        """
        Check if another polynomial is equvalent

        inputs:
            - other_polynomial: a Polynomial object

        Returns a boolean: True if other_polynomial contains
        the same terms as self, False otherwise.
        """
        # Make sure that other_polynomial is a Polynomial
        if not isinstance(other_polynomial, Polynomial):
            return False

        # Get the terms of the other_polynomial
        terms = other_polynomial.get_terms()

        # Check that all terms in other_polynomial appear in self
        for power, coefficient in terms.items():
            if coefficient != 0:
                if power not in self._terms:
                    return False
                if self._terms[power] != coefficient:
                    return False

        # Check that all terms in self appear in other_polynomial
        for power, coefficient in self._terms.items():
            if coefficient != 0:
                if power not in terms:
                    return False
                if terms[power] != coefficient:
                    return False

        return True

    def __ne__(self, other_polynomial):
        """
        Check if another polynomial is NOT equivalent

        inputs:
            - other_polynomial: a Polynomial object

        Return a boolean: False if other_polynomial contains the same terms
        as self, True otherwise.
        """
        return not self.__eq__(other_polynomial)

    def get_terms(self):
        """
        Returns: a dictionary of terms, mapping powers to coefficients.
        This dictionary is a completely new object and is not a reference
        to any internal structures.
        """
        terms = dict(self._terms)
        return terms

    def get_degree(self):
        """
        Returns: the maximum power over all terms in this polynomial.
        """
        # Since we don't clean zero-coefficient powers out of our dictionary,
        # we need a trickier get_degree function, to take into account that
        # some coefficients could be zero.
        highest_power = 0
        for power in self._terms:
            if (power > highest_power) and (self._terms[power] != 0):
                highest_power = power

        return highest_power


    def get_coefficient(self, power):
        """
        Determines the coefficient of x^(power) in this polynomial.
        If there is no coefficient of x^(power), this method
        returns 0.

        inputs:
            - power: an integer representing a polynomial power

        Returns: a Z_256 number that is the coefficient or 0 if there
                 is no term of the given power
        """
        if power in self._terms:
            return self._terms[power]
        else:
            return 0

    def add_term(self, coefficient, power):
        """
        Add one term to this polynomial.

        inputs:
            - coefficient: a Z_256 number representing the coefficient of the term
            - power: an integer representing the power of the term

        Returns: a new Polynomial that is the sum of adding this polynomial
        to (coefficient) * x^(power) using Z_256 arithmetic to add
        coefficients, if necessary.
        """
        # Replace with your code for part 3.A
        return Polynomial()

    def subtract_term(self, coefficient, power):
        """
        Subtract one term from this polynomial.

        inputs:
            - coefficient: a Z_256 number representing the coefficient of the term
            - power: an integer representing the power of the term

        Returns: a new Polynomial that is the difference of this polynomial
        and (coefficient) * x^(power) using Z_256 arithmetic to subtract
        coefficients, if necessary.
        """
        # Replace with your code for part 3.B
        return Polynomial()

    def multiply_by_term(self, coefficient, power):
        """
        Multiply this polynomial by one term.

        inputs:
            - coefficient: a Z_256 number representing the coefficient of the term
            - power: an integer representing the power of the term

        Returns: a new Polynomial that is the product of multiplying
        this polynomial by (coefficient) * x^(power).
        """
        # Replace with your code for part 3.C
        return Polynomial()

    def add_polynomial(self, other_polynomial):
        """
        Compute the sum of the current polynomial other_polynomial.

        inputs:
            - other_polynomial: a Polynomial object

        Returns: a new Polynomial that is the sum of both polynomials.
        """
        # Replace with your code for part 4.A
        return Polynomial()

    def subtract_polynomial(self, other_polynomial):
        """
        Compute the difference of the current polynomial and other_polynomial.

        inputs:
            - other_polynomial: a Polynomial object

        Returns: a new Polynomial that is the difference of both polynomials.
        """
        # Replace with your code for part 4.B
        return Polynomial()

    def multiply_by_polynomial(self, other_polynomial):
        """
        Compute the product of the current polynomial and other_polynomial.

        inputs:
  
... (truncated 3543 chars)

solution.py8.1 KB

python

"""
QR Code Generator
"""

import comp140_module5 as qrcode
import comp140_module5_z256 as z256

def divide_terms(coefficient1, power1, coefficient2, power2):
    """
    Computes the quotient of two terms.

    The degree of the first term, power1, must be greater than or
    equal to the degree of the second term, power2.

    Inputs:
        - coefficient1: a Z_256 number representing the coefficient of the first polynomial term
        - power1: an integer representing the power of the first term.
        - coefficient2: a Z_256 number representing the coefficient of the second polynomial term
        - power2: an integer representing the power of the second term.

    Returns: an instance of a Polynomial that is the resulting
    term.
    """
    # From recipe: (a*x^b) / (c*x^d) = (a/c) * x^(b-d)
    new_coeff = z256.div(coefficient1, coefficient2)
    new_pow = power1 - power2

    # Represent our answer as a Polynomial
    divided = Polynomial()
    divided = divided.add_term(new_coeff, new_pow)
    return divided

class Polynomial:
    """
    A class used to abstract methods on a polynomial in the finite
    field Z_256 (including numbers from 0 through 255).

    Since 256 is not prime, but is rather of the form p^n = 2^8, this
    representation uses special arithmetic via the z256 module so as to
    preserve multiplicative inverses (division) inside this field.
    """

    def __init__(self, terms=None):
        """
        Creates a new Polynomial object.  If a dictionary of terms is provided,
        they will be the terms of the polynomial,
        otherwise the polynomial will be the 0 polynomial.

        inputs:
            - terms: a dictionary of terms mapping powers to coefficients or None
              (None indicates that all coefficients are 0)
        """
        if terms != None:
            self._terms = dict(terms)
        else:
            self._terms = {}

    def __str__(self):
        """
        Returns: a string representation of the polynomial, containing the
        class name and all of the terms.
        """
        # Create a string of the form "ax^n + bx^n-1 + ... + c" by
        # creating a string representation of each term, and inserting
        # " + " in between each
        term_strings = []

        # Add the highest powers first
        powers = list(self._terms.keys())
        powers.sort(reverse=True)
        for power in powers:
            coefficient = self._terms[power]
            # Don't print out terms with a zero coefficient
            if coefficient != 0:
                # Don't print "x^0"; that just means it's a constant
                if power == 0:
                    term_strings.append("%d" % coefficient)
                else:
                    term_strings.append("%d*x^%d" % (coefficient, power))

        terms_str = " + ".join(term_strings)
        if terms_str == "":
            terms_str = "0"
        return "Polynomial: %s" % terms_str

    def __eq__(self, other_polynomial):
        """
        Check if another polynomial is equvalent

        inputs:
            - other_polynomial: a Polynomial object

        Returns a boolean: True if other_polynomial contains
        the same terms as self, False otherwise.
        """
        # Make sure that other_polynomial is a Polynomial
        if not isinstance(other_polynomial, Polynomial):
            return False

        # Get the terms of the other_polynomial
        terms = other_polynomial.get_terms()

        # Check that all terms in other_polynomial appear in self
        for power, coefficient in terms.items():
            if coefficient != 0:
                if power not in self._terms:
                    return False
                if self._terms[power] != coefficient:
                    return False

        # Check that all terms in self appear in other_polynomial
        for power, coefficient in self._terms.items():
            if coefficient != 0:
                if power not in terms:
                    return False
                if terms[power] != coefficient:
                    return False

        return True

    def __ne__(self, other_polynomial):
        """
        Check if another polynomial is NOT equivalent

        inputs:
            - other_polynomial: a Polynomial object

        Return a boolean: False if other_polynomial contains the same terms
        as self, True otherwise.
        """
        return not self.__eq__(other_polynomial)

    def get_terms(self):
        """
        Returns: a dictionary of terms, mapping powers to coefficients.
        This dictionary is a completely new object and is not a reference
        to any internal structures.
        """
        terms = dict(self._terms)
        return terms

    def get_degree(self):
        """
        Returns: the maximum power over all terms in this polynomial.
        """
        # Since we don't clean zero-coefficient powers out of our dictionary,
        # we need a trickier get_degree function, to take into account that
        # some coefficients could be zero.
        highest_power = 0
        for power in self._terms:
            if (power > highest_power) and (self._terms[power] != 0):
                highest_power = power

        return highest_power


    def get_coefficient(self, power):
        """
        Determines the coefficient of x^(power) in this polynomial.
        If there is no coefficient of x^(power), this method
        returns 0.

        inputs:
            - power: an integer representing a polynomial power

        Returns: a Z_256 number that is the coefficient or 0 if there
                 is no term of the given power
        """
        if power in self._terms:
            return self._terms[power]
        else:
            return 0

    def add_term(self, coefficient, power):
        """
        Add one term to this polynomial.

        inputs:
            - coefficient: a Z_256 number representing the coefficient of the term
            - power: an integer representing the power of the term

        Returns: a new Polynomial that is the sum of adding this polynomial
        to (coefficient) * x^(power) using Z_256 arithmetic to add
        coefficients, if necessary.
        """
        # Replace with your code for part 3.A
        return Polynomial()

    def subtract_term(self, coefficient, power):
        """
        Subtract one term from this polynomial.

        inputs:
            - coefficient: a Z_256 number representing the coefficient of the term
            - power: an integer representing the power of the term

        Returns: a new Polynomial that is the difference of this polynomial
        and (coefficient) * x^(power) using Z_256 arithmetic to subtract
        coefficients, if necessary.
        """
        # Replace with your code for part 3.B
        return Polynomial()

    def multiply_by_term(self, coefficient, power):
        """
        Multiply this polynomial by one term.

        inputs:
            - coefficient: a Z_256 number representing the coefficient of the term
            - power: an integer representing the power of the term

        Returns: a new Polynomial that is the product of multiplying
        this polynomial by (coefficient) * x^(power).
        """
        # Replace with your code for part 3.C
        return Polynomial()

    def add_polynomial(self, other_polynomial):
        """
        Compute the sum of the current polynomial other_polynomial.

        inputs:
            - other_polynomial: a Polynomial object

        Returns: a new Polynomial that is the sum of both polynomials.
        """
        # Replace with your code for part 4.A
        return Polynomial()

    def subtract_polynomial(self, other_polynomial):
        """
        Compute the difference of the current polynomial and other_polynomial.

        inputs:
            - other_polynomial: a Polynomial object

        Returns: a new Polynomial that is the difference of both polynomials.
        """
        # Replace with your code for part 4.B
        return Polynomial()

    def multiply_by_polynomial(self, other_polynomial):
        """
        Compute the product of the current polynomial and other_polynomial.

        inputs:
  
... (truncated 3543 chars)

solution.py12.9 KB

python

"""
QR Code Generator
"""

import comp140_module5 as qrcode
import comp140_module5_z256 as z256

def divide_terms(coefficient1, power1, coefficient2, power2):
    """
    Computes the quotient of two terms.

    The degree of the first term, power1, must be greater than or
    equal to the degree of the second term, power2.

    Inputs:
        - coefficient1: a Z_256 number representing the coefficient of the first polynomial term
        - power1: an integer representing the power of the first term.
        - coefficient2: a Z_256 number representing the coefficient of the second polynomial term
        - power2: an integer representing the power of the second term.

    Returns: an instance of a Polynomial that is the resulting
    term.
    """
    # From recipe: (a*x^b) / (c*x^d) = (a/c) * x^(b-d)
    new_coeff = z256.div(coefficient1, coefficient2)
    new_pow = power1 - power2

    # Represent our answer as a Polynomial
    divided = Polynomial()
    divided = divided.add_term(new_coeff, new_pow)
    return divided

class Polynomial:
    """
    A class used to abstract methods on a polynomial in the finite
    field Z_256 (including numbers from 0 through 255).

    Since 256 is not prime, but is rather of the form p^n = 2^8, this
    representation uses special arithmetic via the z256 module so as to
    preserve multiplicative inverses (division) inside this field.
    """

    def __init__(self, terms=None):
        """
        Creates a new Polynomial object.  If a dictionary of terms is provided,
        they will be the terms of the polynomial,
        otherwise the polynomial will be the 0 polynomial.

        inputs:
            - terms: a dictionary of terms mapping powers to coefficients or None
              (None indicates that all coefficients are 0)
        """
        if terms != None:
            self._terms = dict(terms)
        else:
            self._terms = {}

    def __str__(self):
        """
        Returns: a string representation of the polynomial, containing the
        class name and all of the terms.
        """
        # Create a string of the form "ax^n + bx^n-1 + ... + c" by
        # creating a string representation of each term, and inserting
        # " + " in between each
        term_strings = []

        # Add the highest powers first
        powers = list(self._terms.keys())
        powers.sort(reverse=True)
        for power in powers:
            coefficient = self._terms[power]
            # Don't print out terms with a zero coefficient
            if coefficient != 0:
                # Don't print "x^0"; that just means it's a constant
                if power == 0:
                    term_strings.append("%d" % coefficient)
                else:
                    term_strings.append("%d*x^%d" % (coefficient, power))

        terms_str = " + ".join(term_strings)
        if terms_str == "":
            terms_str = "0"
        return "Polynomial: %s" % terms_str

    def __eq__(self, other_polynomial):
        """
        Check if another polynomial is equvalent

        inputs:
            - other_polynomial: a Polynomial object

        Returns a boolean: True if other_polynomial contains
        the same terms as self, False otherwise.
        """
        # Make sure that other_polynomial is a Polynomial
        if not isinstance(other_polynomial, Polynomial):
            return False

        # Get the terms of the other_polynomial
        terms = other_polynomial.get_terms()

        # Check that all terms in other_polynomial appear in self
        for power, coefficient in terms.items():
            if coefficient != 0:
                if power not in self._terms:
                    return False
                if self._terms[power] != coefficient:
                    return False

        # Check that all terms in self appear in other_polynomial
        for power, coefficient in self._terms.items():
            if coefficient != 0:
                if power not in terms:
                    return False
                if terms[power] != coefficient:
                    return False

        return True

    def __ne__(self, other_polynomial):
        """
        Check if another polynomial is NOT equivalent

        inputs:
            - other_polynomial: a Polynomial object

        Return a boolean: False if other_polynomial contains the same terms
        as self, True otherwise.
        """
        return not self.__eq__(other_polynomial)

    def get_terms(self):
        """
        Returns: a dictionary of terms, mapping powers to coefficients.
        This dictionary is a completely new object and is not a reference
        to any internal structures.
        """
        terms = dict(self._terms)
        return terms

    def get_degree(self):
        """
        Returns: the maximum power over all terms in this polynomial.
        """
        # Since we don't clean zero-coefficient powers out of our dictionary,
        # we need a trickier get_degree function, to take into account that
        # some coefficients could be zero.
        highest_power = 0
        for power in self._terms:
            if (power > highest_power) and (self._terms[power] != 0):
                highest_power = power

        return highest_power


    def get_coefficient(self, power):
        """
        Determines the coefficient of x^(power) in this polynomial.
        If there is no coefficient of x^(power), this method
        returns 0.

        inputs:
            - power: an integer representing a polynomial power

        Returns: a Z_256 number that is the coefficient or 0 if there
                 is no term of the given power
        """
        if power in self._terms:
            return self._terms[power]
        else:
            return 0

    def add_term(self, coefficient, power):
        """
        Add one term to this polynomial.

        inputs:
            - coefficient: a Z_256 number representing the coefficient of the term
            - power: an integer representing the power of the term

        Returns: a new Polynomial that is the sum of adding this polynomial
        to (coefficient) * x^(power) using Z_256 arithmetic to add
        coefficients, if necessary.
        """
        new_terms = dict(self._terms)
        if power in new_terms:
            new_terms[power] = z256.add(new_terms[power], coefficient)
        else:
            new_terms[power] = coefficient
        return Polynomial(new_terms)

    def subtract_term(self, coefficient, power):
        """
        Subtract one term from this polynomial.

        inputs:
            - coefficient: a Z_256 number representing the coefficient of the term
            - power: an integer representing the power of the term

        Returns: a new Polynomial that is the difference of this polynomial
        and (coefficient) * x^(power) using Z_256 arithmetic to subtract
        coefficients, if necessary.
        """
        # In Z256, subtraction is equivalent to addition (XOR)
        return self.add_term(z256.sub(0, coefficient), power)

    def multiply_by_term(self, coefficient, power):
        """
        Multiply this polynomial by one term.

        inputs:
            - coefficient: a Z_256 number representing the coefficient of the term
            - power: an integer representing the power of the term

        Returns: a new Polynomial that is the product of multiplying
        this polynomial by (coefficient) * x^(power).
        """
        result = Polynomial()
        for p, c in self._terms.items():
            new_coeff = z256.mul(c, coefficient)
            result = result.add_term(new_coeff, p + power)
        return result

    def add_polynomial(self, other_polynomial):
        """
        Compute the sum of the current polynomial other_polynomial.

        inputs:
            - other_polynomial: a Polynomial object

        Returns: a new Polynomial that is the sum of both polynomials.
        """
        result = Polynomial(self._terms)
        for power, coefficient in other_polynomial.get_terms().items():
            result = result.add_term(coefficient, power)
        return result

    def subtract_polynomial(self, other_polynomial):
        """
        Compute the difference of the current polynomial and other_polynomial.

        inputs:
            - other_polynomial: a Polynomial object

        Returns: a new Polynomial that is the difference of both polynomials.
        """
        result = Polynomial(self._terms)
        for power, coefficient in other_polynomial.get_terms().items():
            result = result.subtract_term(coefficient, power)
        return result

    def multiply_by_polynomial(self, other_polynomial):
        """
        Compute the product of the current polynomial and other_polynomial.

        inputs:
            - other_polynomial: a Polynomial object

        Returns: a new Polynomial that is the product of both polynomials.
        """
        result = Polynomial()
        for power, coefficient in other_polynomial.get_terms().items():
            partial = self.multiply_by_term(coefficient, power)
            result = result.add_polynomial(partial)
        return result

    def remainder(self, denominator):
        """
        Compute a new Polynomial that is the remainder after dividing this
        polynomial by denominator.

        Note: does *not* return the quotient; only the remainder!

        inputs:
            - denominator: a Polynomial object

        Returns: a new polynomial that is the remainder
        """
        numerator = Polynomial(self._terms)
        denom_degree = denominator.get_degree()
        denom_leading_coeff = denominator.get_coefficient(denom_degree)

        while numerator.get_degree() >= denom_degree:
            num_degree = numerator.get_degree()
            num_leading_coeff = numerator.get_coefficient(num_degree)
            # If leading coefficient is zero, the degree lied — break to avoid loop
            if num_leading_coeff == 0:
                break
            quot_coeff = z256.div(num_leading_coeff, denom_leading_coeff)
            quot_power = num_degree - denom_degree
            to_subtract = denominator.multiply_by_term(quot_coeff, quot_power)
            numerator = numerator.subtract_polynomial(to_subtract)

        return numerator


def create_message_polynomial(message, num_correction_bytes):
    """
    Creates the appropriate Polynomial to represent the
    given message. Relies on the number of error correction
    bytes (k). The message polynomial is of the form
    message[i]*x^(n+k-i-1) for each number/byte in the message.

    Inputs:
        - message: a list of integers (each between 0-255) representing data
        - num_correction_bytes: an integer representing the number of
          error correction bytes to use

    Returns: a Polynomial with the appropriate terms to represent the
    message with the specified level of error correction.
    """
    result = Polynomial()
    n = len(message)
    k = num_correction_bytes
    for i, m_i in enumerate(message):
        power = k + n - i - 1
        result = result.add_term(m_i, power)
    return result

def create_generator_polynomial(num_correction_bytes):
    """
    Generates a static generator Polynomial for error
    correction, which is the product of (x-2^i) for all i in the
    set {0, 1, ..., num_correction_bytes - 1}.

    Inputs:
        - num_correction_bytes: desired number of error correction bytes.
                                In the formula, this is represented as k.

    Returns: generator Polynomial for generating Reed-Solomon encoding data.
    """
    result = Polynomial({0: 1})
    for i in range(num_correction_bytes):
        # Factor: (x - 2^i); constant term is z256.sub(0, 2^i) = 2^i in Z256
        factor_const = z256.power(2, i)
        factor = Polynomial({1: 1, 0: factor_const})
        result = result.multiply_by_polynomial(factor)
    return result

def reed_solomon_correction(encoded_data, num_correction_bytes):
    """
    Corrects the encoded data using Reed-Solomon error correction

    Inputs:
        - encoded_data: a list of integers (each between 0-255)
                        representing an encoded QR message.
        - num_correction_bytes: desired number of error correction bytes.

    Returns: a polynomial that represents the Reed-Solomon error
    correction code for the input data.
    """
    message_poly = create_message_polynomial(encoded_data, num_correction_bytes)
    generator_poly = create_generator_polynomial(num_correction_bytes)
    return message_poly.remainder(generator_poly)


# Uncomment the following line when you are ready to generate an
# actual QR code.  To do so, you must enter a short message in the
# "info" text box and hit return (be sure to hit return!).  You then
# must push the "Generate!" button.  This will generate a QR code for
# you to view - try scanning it with your phone!  If you would like to
# save your QR codes, you can use the "Image in a New Window" button
# to create a .png file that you can save by right clicking in your
# browser window.

# qrcode.start(reed_solomon_correction)

Grading: Module 5 - QR Codes (Written Questions)

Question 1: Zero Coefficients in Reed-Solomon Remainder (5 points)

Score: 5/5

The student's response is excellent and addresses both parts of the question clearly and correctly.

Part 1 — Can we guarantee no zero coefficients? The student correctly states: *"No, it is not possible to guarantee that there will be no zero coefficients in the remainder."* They provide sound reasoning that the remainder depends on the specific message data and the generator polynomial, so zeros may naturally arise depending on the input. This matches the reference solution.

Part 2 — Is it a problem? The student correctly states: *"Zero coefficients in the remainder are not a problem at all."* They provide strong justification:

A zero byte is a valid byte value (0x00) — this aligns with the rubric's point that zero is a valid element of Z₂₅₆
The decoder uses it just like any other byte — shows understanding that the mathematical relationship is preserved
The decoder knows how many error correction bytes to expect — demonstrates understanding that position information is maintained

This is a concise, well-reasoned, and complete answer that earns full marks.

---

Question 2: Reusing the Polynomial Class for Real Numbers (5 points)

Score: 5/5

The student's response demonstrates clear understanding of modularity and correctly identifies the minimal changes needed.

Key points hit:

✅ Identifies the z256 module calls as what needs to change: *"replace the calls to z256.add, z256.sub, z256.mul, and z256.div with the corresponding standard Python arithmetic operators"* — this is precisely the core insight the rubric requires.
✅ Recognizes that polynomial logic stays the same: *"All of the polynomial structure — the dictionary representation, the methods for adding/subtracting/multiplying terms and polynomials, and the polynomial long division algorithm — would remain exactly the same."*
✅ Connects to modularity: *"the arithmetic operations are isolated to a small number of places, so changing the underlying number system requires minimal code changes."*

The rubric notes that for full credit, a student could propose either (a) abstracting/parameterizing the arithmetic or (b) simply replacing z256 calls with standard operations. The student takes approach (b) and explains it clearly. While they don't propose a more sophisticated abstraction layer (e.g., dependency injection or a base class), the rubric explicitly accepts this approach at full credit level, as the student clearly identifies the arithmetic operations as the key difference, demonstrates that the polynomial logic is reusable, and ties the answer back to the principle of modularity.

---

Summary

Question	Score	Max Points
Question 1: Zero Coefficients	5	5
Question 2: Reusing Polynomial Class	5	5
Total	10	10

Overall Comments: This is an outstanding submission. Both answers are correct, concise, and well-articulated. The student demonstrates strong understanding of Reed-Solomon encoding properties (Q1) and software design principles around modularity and code reuse (Q2). The writing is clear and directly addresses each part of the questions without unnecessary filler.

Total: 10/10

.mcp.json

diff --git a/.mcp.json b/.mcp.json
deleted file mode 100644
index be32f7c..0000000
--- a/.mcp.json
+++ /dev/null
@@ -1,11 +0,0 @@
-{
-  "mcpServers": {
-    "bscs-bench": {
-      "command": "/Users/bebe/Code/bscs-bench/bin/bscs-mcp",
-      "args": [
-        "--workspace",
-        "./writeup.md b/writeup.md
index 61afd48..ee240f5 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,5 +2,10 @@
 
 ## Student Responses
 
-<!-- Fill in your writeup responses below -->
+### Question 1
 
+No, it is not possible to guarantee that there will be no zero coefficients in the remainder. The remainder is determined by the specific data bytes in the message polynomial and the generator polynomial, so depending on the input, some remainder coefficients may be zero. Zero coefficients in the remainder are not a problem at all — a zero error-correction byte is a perfectly valid byte value (0x00), and the decoder simply uses it as part of the error correction process just like any other byte. The decoder knows how many error correction bytes to expect based on the QR code specification, so zero values are handled correctly.
+
+### Question 2
+
+To reuse the `Polynomial` class for real-number coefficients, you would only need to replace the calls to `z256.add`, `z256.sub`, `z256.mul`, and `z256.div` with the corresponding standard Python arithmetic operators (`+`, `-`, `*`, `/`). All of the polynomial structure — the dictionary representation, the methods for adding/subtracting/multiplying terms and polynomials, and the polynomial long division algorithm — would remain exactly the same. This demonstrates the value of modularity: the arithmetic operations are isolated to a small number of places, so changing the underlying number system requires minimal code changes.

Agent Work: QR Code

Module 5: QR Codes

Testing Your Solution

1. The Problem

2. A Solution Strategy

Reed-Solomon Example

3. Breaking Down the Problem: Manipulating Individual Terms

A. Add Term

B. Subtract Term

C. Multiply by Term

i. Recipe

ii. Code

4. Breaking Down the Problem: Manipulating Polynomials

A. Polynomial Addition

i. Recipe

ii. Code

B. Polynomial Subtraction

C. Polynomial Multiplication

i. Recipe

ii. Code

D. Polynomial Remainders

i. Recipe

ii. Code

5. Solving the Problem

A. Creating the Message Polynomial

B. Creating the Generator Polynomial

C. Reed-Solomon Encoding

6. Discussion (Written Response)

qr_code Writeup

Student Responses

Question 1

Question 2

Grading: Module 5 - QR Codes (Written Questions)

Question 1: Zero Coefficients in Reed-Solomon Remainder (5 points)

Question 2: Reusing the Polynomial Class for Real Numbers (5 points)

Summary

Sub-Model Usage