Chapter 6 Python Practical Work

6.1 Lights Out

6.1.1 Introduction and Instructions

The goal of this practical work is to create the game (Exercises 6.1 to 6.3), then to determine in which dimensions the game always has a solution (Exercise 6.5), and finally to create a solver (Exercises 6.4 to 6.7).

Throughout this practical work, matrices of size \(n\) will have indices \(i, j\) ranging from \(0\) to \(n-1\) to be compatible with Python notation.

The practical work will be submitted in the form of a JupyterLab notebook (https://jupyter.org) on the Moodle platform of the IUT (https://cours.iut-orsay.fr/). It is possible to use the online version, but the input() command poses problems. It is therefore recommended to use Jupyter locally. To do this, you can launch it with the following command in a terminal on Linux:

jupyter lab

If this does not work, you can try jupyter notebook. On Windows, jupyter lab can be found following this path:

C:\winpython\jupyterlab

It is also possible to write Jupyter notebooks with some IDEs like Visual Studio Code or PyCharm: (https://www.jetbrains.com/help/pycharm/jupyter-notebook-support.html).

Once launched, a browser will open. You can choose a new Python notebook. You will then have an IDE-like interface with example files and the option to create a new file with a Python kernel.

You can then create cells with text in Markdown format or Python code. This will allow you to format your practical work and run code. A brief Markdown cheat sheet is provided at the end of this document. It is advisable to create separate cells for defining functions and running examples. The order in which cells are executed is important.

This is a mathematics practical work and not just coding. It is essential to take out a scratch pad and a pen to think before starting to write code! Good coding practices still apply (commenting code, choosing descriptive variable names, defining intermediate functions, etc.).

You will need some libraries to manipulate matrices. The main one is numpy. You can import it with the following command.

import numpy as np

The “as np” option means that you can call this library using the shortcut np.

With numpy, a matrix is an object of the array class. It is essentially a list of lists, representing the rows of the matrix. For example, the matrix \(\begin{bmatrix}1&2&3\\4&5&6\end{bmatrix}\) is defined with the following command:

np.array([[1, 2, 3], [4, 5, 6]])

The advantage of using this class is that you can utilize predefined methods. For instance, the matrix product (np.dot(A,B) returns the matrix product of \(A\) and \(B\)) or the method .shape() which returns the pair \((n,m)\) corresponding to the dimensions of the matrix.

The official numpy documentation can be found here: (https://numpy.org).

6.1.2 Exercises

Exercise 6.1 The goal of this exercise is to create two functions: one that associates the column vector in the canonical basis to a matrix in \(\mathrm{M}_{m,n}(\mathbf{K})\) and another that performs the inverse operation.

  1. Let \(A \in \mathrm{M}_{m,n}(\mathbf{K})\) and \(V\) be the associated column vector. What is the dimension of \(V\)? What is the relationship between \(V_k\) and \(A_{i,j}\)?
  2. Write a function Vecteur_Colonne(\(A\)**) that takes a matrix as input and returns the associated column vector of the correct size.
  3. Write the function Matrice(\(V\)**) that takes a column vector of size \(n^2\) as input and returns the corresponding \(n \times n\) matrix.

Exercise 6.2 (Creating Cross Matrices) Create a function Croix(\(i,j,n\)**) that creates the matrix \(C_{i,j}\) of size \(n^2\) with ones only at \((i,j)\) and its vertical and horizontal neighbors. All other positions will have zeros.

Exercise 6.3 (3x3 Game) In this exercise, you are asked to create a function Lights_Out() with no input variables that starts the game with the following instructions:

  1. Welcome message in the game,
  2. Generate a random configuration using the random.randint() command from Numpy,
  3. Display the initial configuration,
  4. Prompt the player for the cell where they want to play,
  5. Retrieve the row and column numbers using the input() command,
  6. Update the configuration and display it,
  7. Continue until the player has turned off all the lights, at which point display a congratulatory message and exit the game.

Exercise 6.4 (Transition Matrix) Create a function Matrice_Passage(\(n\)**) that takes the dimension \(n\) as input and returns the matrix whose vectors are the \(C_{i,j}\) expressed in the canonical basis of \(\mathrm{M}_n(\mathbf{F}_2)\). Use the \(C_{i,j}\) in the same order as the \(E_{i,j}\) vectors of the canonical basis.

Exercise 6.5 Determine for which dimensions the game always has a solution.

  1. Write a loop that computes the determinant of Matrice_Passage(\(n\)) for \(n = 2\) to 11. Note that this determinant is a number in \(\mathbf{F}_2\), i.e., 0 or 1. Since Python performs calculations with floating-point numbers, it may be useful to use the commands round(), int(), and add %2** to get the remainder in the Euclidean division by 2.
  2. Provide the list of dimensions less than 11 for which the game has a unique solution for any initial configuration.

Exercise 6.6 (Inverse of the Transition Matrix in Dimension 3) Using Python, calculate the inverse of the transition matrix in dimension 3. You can either perform the calculations in \(\mathbf{R}\) with the linalg.inv() command from Numpy, convert to integers, and then reduce modulo 2, or use the Sympy package, change the matrix type with Matrix(), and compute the inverse in \(\mathrm{M}(\mathbf{F}_2)\) using the .inv_mod(2) method.

Exercise 6.7 (Solver in Dimension 3) Write a function Solution(\(A\)**) that takes an initial configuration in the form of a \(3 \times 3\) matrix \(A\) as input and returns a solution matrix \(S\) (containing 1s for cells where you need to press and 0s elsewhere).

Test it with an online version of the game.

Exercise 6.8 (Bonus) Create a graphical interface for the game using the Pygame library. You can start with dimension 3 and then allow the player to choose the dimension, add a button to display the solution (in which case, the solution will be drawn randomly and the initial configuration will be its image by the transition matrix)…

6.1.3 Markdown Cheat Sheet

A level 1 title (equivalent to the HTML tag “h1”):

# Title

A level 2 title (equivalent to the HTML tag “h2”):

## Subtitle

A level 3 title (equivalent to the HTML tag “h3”):

### Sub-subtitle

Bold text:

**bold text**

Italic text:

*italic text*

A mathematical formula:

Pythagoras' theorem is $a^2+b^2=c^2$.

An ordered list:

1. First item
2. Second item
3. Third item

An unordered list:

* First item
* Second item
* Third item