README.md

Santa's Elf Morphing Machine

Solution provided by: Gianluca Lofrumento, Alessio Di Santo e Marco Pinna

Problem

Problem in problem.pdf file and a useful information in the challenge description

Solution

Find A_i matrix

First of all we have to find A_i's eigenvalues. Given the generic 2x2 matrix

we know that its characteristic polynomial is

So just with the trace and determinant of A we can find its eigenvalues.

Then from the process of diagonalization of a matrix we know that

If we set , we obtain the similarity transformation:

where:

• M is the modal matrix, that is a matrix containing the eigenvectors of A in its columns
• D is the diagonal matrix of A's eigenvalues, also called 'spectral matrix'

We have everything (clearly we have to invert the modal matrix) so we can easily find the matrix A.

Use the matrix A_i

We know

that means

where x_i and y_i are the coordinates in input while x_o and y_o are the coordinates in output.

Moreover from the text we know that

and that the initial coordinate are (1,3).

We have implemented all this in a python script, after editing a little bit the 'trans.txt' file, as there were some irregularities in the blank spaces that were messing up the .find() function in the script (yes, we could have used a regex, but in this case it was way faster to even out the 'trans.txt' file).

The round() function at lines 54-55 in the script is needed because of the following reason: every f_i transformation applies a linear mapping from to . This, however, does not imply that every A_i matrix only has natural components. In fact, the matrices belong to .
Since we're dealing with floats, that have a limited precision, approximation errors are always behind the corner. Furthermore, since the output of the i-th iteration is the input of the (i+1)th iteration, we also have to deal with error propagation and amplification. The round() function takes care of all these issues. You can try and remove it from the script, to have a nice example of what those issues can lead to if they're not properly taken care of.

We computed all the points, plotted them on a scatter plot and got the flag