In this post I'll explain the reasoning behind my solutions to the problems of the Tuenti Challenge 8.

List of challenges (you can check the problem statements here):

## Challenge 1 - Waffle love

There is not much to explain for this one. If $n$ and $m$ are the numbers of vertical and horizontal lines of the waffle, the number of holes will be $(n - 1) (m - 1)$.

## Challenge 2 - Hidden numbers

In this problem we deal with the representation of base-$n$ numbers, where $2$ $\le$ $n$ $\le$ $26$. The problem asks to compute the maximum and minimum number that we can represent in this base (starting with a non-zero value) and return $max - min$ as a result.

We'll receive a string as an input, with all the chars different in it. As a first step we'll compute the base just by looking at the length of the string.

For the $max$ number, how do you construct the biggest number in base-10 with the numbers $[0..9]$? $9876543210$, right?. Then, for a base-$n$ number it will be given by the expression: $$max = \sum_{i=1}^{n - 1} i n^i$$

The $min$ case is a little bit tricky. If we assume that there is no leading zero, again, for the base-10 case it would be $1023456789$. We just exchanged the $0$ and the $1$ and voilá!. For our base-$n$ case: $$min = n^{n - 1} + \sum_{i=0}^{n - 3} (n - i - 1) n^i$$

And now some code implementing the idea:

## Challenge 3 - Scales

So, music time!

Summarizing the problem: We are going to receive a set of musical notes and we have to return all the major and natural minor scales that can match these notes.

To simplify the problem we are going to keep only the following notes: $A, A\#, B, C, C\#, D, D\#, E, F, F\#, G, G\#$. Why would we need $Cb$ if it's equivalent to $F\#$?

Now, let's generate the 24 scales! The first step for this is to know the half-step between notes and the progression of both scales:

Once we have this, generating the scales is piece of cake:

Now that we have the scales we are all setup to solve our problem. Supposing that $notes$ is a set with the notes of the input (converted to our equivalent set of notes), the solution would be:

## Challenge 4 - Brave Knight

Ingredients: 2D Grid, one source, two sequential destinations, obstacles, lava, trampolines and horse chess-style jumps!

Well, we can reduce this problem to a double shortest-path problem, one between the knight and the princess, and other between the princess and the destination.

In this case, every jump has the same cost, so a breadth-first search will be fine. Starting with the Knight, we generate the possible jumps. If $(row, col)$ is the position of the knight, we have 8 possible jumps, which are the following:

$(row + 2, col + 1)$,$(row + 2, col - 1)$,$(row - 2, col + 1)$,$(row - 2, col - 1)$,$(row + 1, col + 2)$,$(row + 1, col - 2)$,$(row - 1, col + 2)$,$(row - 1, col - 2)$.

In the case of trampolines the jumps will be of length $\pm 4$ and $\pm 2$. Now, given a position we can generate all the possible new jumps:

Now we'll use this function to implement our breadth-first search algorithm:

And finally, we use our BFS algorithm to solve our problem!

## Challenge 5 - DNA Splicer

It's bioinformatics time!

We have a bunch of strings and we have to get two identical sequences by aligning some of them, so... OK, we can start with two strings that have the same prefix and then try to concatenate with some of the rest strings.

Fingers crossed... nope. Sometimes we were wrong at the beginning, or in the middle of the process. Let's read the notes again... "There are at most 18 parts". Somebody said backtracking? Let's go for it:

Eeeh... but what are the initial arguments of our backtracking function? We'll have to try with all the pairs of strings that have a common prefix:

Well, ready to go. We only need to connect to the server, retrieve the sequences and solve the cases until we get the key!

## Challenge 6 - Button Hero

Did you say job note scheduling? This is a typical dynamic programming problem. First, let's create a class to compute the start and the end time from the input data:

The idea is to sort the notes by end time in ascending order and create a table (array) of $n$ elements, where $n$ is the number of notes. Now, we compute the values for each entry of the table in the following way: For each $i \in [0..n-1]$ we compute:

\begin{equation*}table[i] = \left \{ \begin{array}{lc} note_0.score & i = 0\\ \max \left\{ \begin{array}{l} \text{Maximum by including } note_i\\ table[i - 1]\\ \end{array} \right . & 1 \leq i \le n \end{array} \right . \end{equation*}

Note that $table[i-1]$ is equivalent to "Maximum by excluding $note_i$". Now, for computing the maximum value including the $i^{th}$ note we will have to go back in the table and find the latest note compatible with $note_i$. Summarizing, we want to find a $j$ such that:

$$j \mid note_j.end < note_i.start \wedge \not\exists k : k > j \mid note_k.end < note_i.start$$

If there is not such $j$, the maximum value will be just $note_i.score$. On the other hand, if it exists the maximum value will be $note_i.score + table[j]$.

Now it's code time! Let's implement this idea:

In this case we use binary search in order to search the latest compatible note, instead of going one by one through the previous notes. This reduces the time complexity of the search ($\mathcal{O}(log\ n)$ vs $\mathcal{O}(n)$).

Also notice that when parsing the notes we can find notes that have the same start and end, so we first combine these notes into a new one with the sum of both scores.

To finish here you have also the implementation of the binary search, just in case ;).

## Challenge 7 - Unknown cartridge

When we click on the game boy cartridge image we'll download an unknown file of 32K. First thing that I tried was...

Surprise! A game boy ROM. You could load the ROM with a game boy emulator and see a lot of letters appearing in the screen, but we are not going to copy them by hand, isn't it?

The second line seems like base64...

So yep, now we have a Pikachu singing... After searching a little I found this. Really? A 1-1 mapping to the brainfuck programming language.

First I tried to run the program with an interpreter, but if you search a little about brainfuck and see the translation of the pikalang program you'll see that it contains a ']' before '[' which doesn't make sense.

Or does it? Do you remember the image of the cartridge? It was backwards... so let's try this.

And now let's try to execute this pikalang program... Bingo! P1K4L4NG_R00LZ.

## Challenge 8 - Security by doorscurity

If you do a couple of examples by hand, you'll notice that you have to find the instant of time where the first door have 0 seconds left to open, the second one 1 second left to open...

Let's take the first example: first door opens every 7 seconds and 5 remaining for the next opening, and the second door opens every 9 seconds and 6 remaining for the next opening.

If you apply the previous reasoning, you want to find an instant with restrictions: 7 seconds of cycle with 5 remaining and 9 seconds of cycle with (6-1)=5 remaining.

In this case the remaining are the same for both doors, so we have only to wait 5 seconds! Let's take the second example:

5 seconds of cycle with 3 remaining, 9 seconds of cycle with (6-1)=5 remaining, and 7 seconds of cycle with (5-2)=3 remaining. Now let me rewrite this in other way:

\begin{align*} x & \equiv 3 \mod 5 \\ x & \equiv 5 \mod 9 \\ x & \equiv 3 \mod 7 \\ \end{align*}

This is a congruence system, $x$ represents our instant of time, the remainders indicate the remaining seconds of the doors, and the modulus represent the door cycles. If we solve this congruence system we get $x = 248$, the solution to the second example.

If $p$ and $t$ are the cycle and the time that has passed from the last opening of the $i^{th}$ door, we will add to our system one of the following congruences (both are equivalent):

\begin{align*} x & \equiv - (t + i) & \mod p \\ x & \equiv p - t - i & \mod p \\ \end{align*}

For solving the congruence system we can use the Chinese remainder theorem, but... if you read about it in wikipedia you'll find "under the condition that the divisors are pairwise coprime". And guess what? Some of the inputs of the problem don't meet this condition.

But no worries, thanks to the power of Internet I could find an implementation of the Chinese remainder theorem that also works for non-pairwise coprime cases :).

In the implementation below, $a$ represents the list of remainders, and $n$ the list of the modulus.

## Challenge 9 - Scrambled Photo

Rocket science! Seeing the paper shredder and the image you can imagine that the columns of the picture has been shuffled.

After that I found a good implementation of an image unshredder here by Project Nayuki that works pretty good. I used it, scanned the QR codes on both images, and went for the next challenge!

## Challenge 10 - Dance

When I first read about returning the number of different ways modulo $10^9 + 7$, I realized that brute force was not an option for this problem.

Then I thought that maybe this is an opportunity to use a divide and conquer strategy, let me explain:

We pick a person from the group of people, let's say that we have the case 4 from the problem statement, with 8 people. If we pick the upper left person, we have 7 possibilities of joining the person with another one (we'll forget about relationships for now). At both sides of the new couple (marked in red) we'll have new groups of people, that can be transformed into new sub-instances of the problem. Both sub-instances can be combined using the rule of product to compute the total number of ways of arranging all the people.

Notice that this transformation also have to reassign indexes to the members of the new sub-groups. This will help us in further optimizations.

The solution for the problem of $n$ people would be, picking a person $p_i$:

$$\sum_{\substack{j\\j \ne i}}^{0 \leq j \le n} sub(i, j)\ sub(j, i)$$

Where $sub(i,j)$ denotes the sub-instance of the problem generated with the people from the $i^{th}$ person to the $j^{th}$ person (both excluded).

The problem has also some base cases:

if $n = 0$, then the ways of arranging people is $1$, if $n$ is odd, it's $0$, and in the case of $n = 2$ we'll return $1$ in the case of compatibility between both persons and $0$ in the case of non-compatibility between them.

$$\left \{ \begin{array}{l} n = 0: 1\\ n\ mod\ 2\ = 1: 0\\ n = 2 \left \{ \begin{array}{l} 1\ \text{if both persons are compatible}\\ 0\ \text{otherwise} \end{array} \right . \end{array} \right .$$

Now optimizations! When we're pairing the person with all the rest of people we have to check if both persons are compatible. If this is not the case, we can skip the whole call of both sub-groups, because it would be invalid.

Another technique that I used to reduce the computation time is memoization. Look at splits 1-7, 2-5, 3-6. When transformed into sub-instances they will be equivalent (assuming we also have the same compatibilities among them).

So, every time we solve an instance, we store the input and their corresponding relationships with the solution, then when we match another sub-instance that is equivalent, we can return the result without computing it again.

Here you have the implementation (I assure you it can be further optimized).

## Challenge 11 - Lasers

The only thing I was sure at the beginning is that we could put lasers in all the rows and columns that are totally empty, good! After that, I found the order in which we should process the items to decide which laser to put in order to achieve the optimal solution.

Even with this order, when with one item I had the choice of putting a horizontal or a vertical laser, I couldn't find the heuristic to choose in an optimal way, so I tried using backtracking. For the test case it was fine, but for the submit cases it was way too slow.

So, in the end I opted to use integer linear programming (ILP) for solving the problem. The formalization for this problem is the following:

Let:

$n = \text{number of columns of the grid}\\ m = \text{number of rows of the grid}$

$X = \{x_0, x_1, x_2, ..., x_{n-1}\}\\ Y = \{y_0, y_1, y_2, ..., y_{m-1}\}$

The expression to maximize is:

$$sum(X) + sum(Y)$$

Subject to:

$$\forall (i, j) \in items : x_i + y_j \leq 1$$ $$x_i \in \{0, 1\}\ \forall\ 0 \leq i < n\\ y_i \in \{0, 1\}\ \forall\ 0 \leq i < m$$

Now we can use cvxpy for implementing our problem in an easy way:

Notice that we can optimize the execution time removing variables that are not necessary (empty rows or columns).

## Challenge 12 - Victoria's Secret

First of all, IP and port: nothing on telnet, "This is not the protocol you are looking for" with curl, let's try wget:

I'm a keyboard!.

That answer plus the debian hint and the usb to ethernet connector in the image = usbip. I setup a vm with the latest debian and installed the usbip package.

After that, I binded the usb keyboard and the magic started. Something was writing on my terminal, but it introduced a stty command that hid some of the keystrokes.

I'm not going to tell you what happens if you don't follow the instructions, be my guest and try. If after binding the keyboard you switch to a text editor you'll see the hidden message, follow the instructions and all will be fine.

If you are a morse code master, you'll end seeing something like this, and if you're a vi master, you'll get the solution :). I hope you enjoyed these solutions, and see you next year!

Categories:

Updated: