Programming Puzzle: Exam-Cheating Codes

This continuous-assessment exercise consists of a small applied project with algorithmic and programming components.

Will you be able to beat your classmates, or even your professor?

As for the Panda Feeding Problem, this assignment requires more thinking than coding, and the focus is as much on the process of finding solutions as on the actual outcome. It is also an open research problem for which the ultimate best solution is as of yet unknown!

Exam Cheating Codes

Final exams are fast approaching. While you are perfectly well prepared and are eagerly awaiting examination day, your significant other is much less relaxed about an upcoming exam. Actually, desperate is more the appropriate term. You decide to help.

The most frightening test, COMP666 👿, is a multiple-choice exam with 20 questions, and each question requires a single Yes/No answer. You are confident that you can perfectly answer any possible question on behalf of your better half, but of course, the main challenge is how to communicate the answers to your loved one after you left the exam. (To your great relief, the instructor chose not to randomize questions or shuffle answers…)

Clearly, you are not able to enter the exam hall once you have left, but you arrange with your significant other the following code: Honking once (on your moped parked in the side street next to the building) will mean Yes, quickly honking twice means No. Unfortunately, as you figured out from painful experimentation, you have only time to send 10 Yes/No signals before campus police politely removes you (and your irritating source of noise) from university premises.

What is the best mark you can guarantee for your sweetheart to achieve, irrespective of the actual sequence of correct answers?

Formalization

Clearly, the correct answers to the 20 Yes/No questions of the exam can be given as an array of 20 bits $B[0..20)$, where $B[i]=1$ (for $i=0,\ldots,19$) means that the correct answer to the $i$th question is Yes, whereas $B[i] = 0$ means the answer is No.

Likewise, your honking “message” can be encoded as an array of 10 bits $H[0..10)$.

The task now consists in finding an encoding function $e:\lbrace 0,1\rbrace^{20} \to \lbrace0,1\rbrace^{10}$ and a decoding function $d:\lbrace0,1\rbrace^{10} \to \lbrace0,1\rbrace^{20}$ for you respectively your significant other to memorize. Your goal is to get the best guaranteed mark for your sweetie, i.e., to find $d$ and $e$ so that $\max_{B\in\lbrace0,1\rbrace^{20}} d_H(d(e(B)),B)$ is as small as possible. Here, $d_H$ denotes the Hamming distance, and the maximum is taken over all possible bit arrays $B$ of length 20.

In code, this looks as follows (for full code see Code template):

worst_mark = 20
for exam in exams: # iterate over all possible exams
    code = compute_and_send_code(exam) # <- your code!
    answers = enter_solution_based_on_code(code) # <- your code!
    mark = 0
    for i in range(20):
        if answers[i] == exam[i]:
            mark += 1
    if mark < worst_mark:
        worst_mark = mark
print(worst_mark)

Inputs

Your protocol has to work for any possible set of correct answers $B$, and it will be tested on all of them.

Design as good a protocol as you can find!

Code template

We prepared a Python 3 implementation of the exam sitting that you will use to evaluate your protocol:

• Python sources

Obey the comments! Once you have downloaded the code, replace the marked sections in examCheatingCode.py with

1. code for your encoding function and
2. code for your decoding function.

To run the simulation, extract the zip archive to a folder and run python3 sitExam.py there. The output is the worst mark (minimal number of correctly answered questions) that your loved one could achieve with the help of your protocol.

Deliverables

This is an individual project; each student has to submit their own solution.

The submission is on Canvas. It consists of the following parts and you have to submit all of them by uploading 3 files for the submission (plus the optional file 4 if you choose to include it). Note: Canvas does not automatically check whether you included all needed files, so this is up to you!

• File 1: Solution
  A textfile MWSUSERNAME-results.txt with the guaranteed mark you achieved, i.e., containing a single number.
  The guaranteed mark is output by our code and should be copied to a plain textfile. (Unlike for the panda problem, this file is not generated automatically by the code.) The name of the file should be your MWS username; just the user id, no @liverpool.ac.uk.
  Marks will be given for solutions achieving a higher guaranteed mark. A secondary criterion here is simplicity of the solution: If you cannot seem to improve the guaranteed mark, extra marks can be awarded for the simplest solution that achieves that solution quality.
  Upload a single TXT file with your result.
• File 2: Code
  Submit all examCheatingCode.py file as well as any other code you may have created/used.
  Upload a single ZIP file with your code.

• File 3: Report
  (a) Describe any systematic approaches you used (if applicable) and (b) explain any additional code you used. Structure your writing with sections.
  (Not more than 1 page.)
  Submit 1 PDF file for this part. Only typed solutions will be marked.

• [OPTIONAL] File 4: Impossibility results
  Challenge task: Try to prove impossibility results for the achievable mark, i.e., worst marks that are provably impossible to attain with any thinkable honking code (not just yours). You will have to employ formal arguments to be able to do this.
  Submit 1 PDF file for this part (if you want).

Marking

The mark is given for the quality of the achieved mark. The baseline are solutions that your tutors have found; You could get more than 100% if you manage to beat their solution!

However, marks for solutions are withheld or reduced if the report does not adequately support them, i.e., if it fails to explain how they were found, e.g., by describing the process to obtain them including relevant intermediate steps or used algorithms.

Collaboration & GenAI Policy

This programming puzzle is an individual project, and you have to submit you own solution. As for all assessments, the University of Liverpool Policy on Academic Integrity applies; please refer to the Canvas page for details.

The use of generative AI for producing solutions to this assessment is not encouraged since it is intended to be worked on to build intuitions on the algorithmic problems. Using tools to generate code (such as GitHub Copilot) is allowed for routine code, but strongly discouraged for generating algorithmic solutions. If you are using generative AI in any form, it has to be documented as precisely as possible. For example, for ChatGPT, you are required to include your chat as an appendix.