**Background and Symbols:**

Merlin was a hand-held electronic gaming-device from 1978. It played multiple games with the kids back then, including "Magic Square"

We will refer to each location (aka button) within Merlin's Magic Square using this numbering system (which is the same as the instructions from the original game):

1 2 3

4 5 6

7 8 9

(This is also shown in the banner image)

asterisk * = lit

tilde ~ = unlit (not lit)**Situation:**

You and your friend Lizzo are given a starting "Merlin's Magic Square", which consists of:

3 rows of 3 characters (characters are separated by a space), such as....

~ * ~ ~ ~ ~ ~ * ~

And y'all want to solve it by changing it into The Solved State, which is:

* * * * ~ * * * *

**Your Task:**

Lizzo presses some buttons, such as 884 (meaning: first she presses 8, then 8, then 4).

You only need to press one more button to solve it; what button is that?**The Rules of Merlin's Magic Square:**

• When you press a corner button (1, 3, 7 or 9), it reverses the 4 buttons in the 2x2 corner square it's in

• When you press a side button (2, 4, 6 or 8), it reverses the 3 buttons in that border row

• When you press the middle button (5), it reverses the 5 buttons in the middle "**+**" shape

• ("Reverse" means that if it's lit, it becomes unlit; if it's unlit, it becomes lit.)

• The Solved State is when all buttons are lit except for the middle one (5) ; this is shown above in blue

**Lines 1 to 3:**The starting Merlin's Magic Square, in 3 rows

**Line 4:**The numbers of the buttons that Lizzo presses

## Solution

Merlin's Magic Square is basically the same as Lights Out with the difference that not all lights have to be turned off, but the winning configuration is all lights on except the one in the middle. Since the 9x9 matrix we would need to invert has full rank for our 3x3 problem here, the Linear Algebra solution would be fairly straightforward to apply.

However, for this problem we don't have to find a general solution but only the last move. Instead of arrays for the bit vectors we use integers this time, so that the button presses change the cells with the bit set to one. When translating the button-press rules to bit vectors we get:

```
const WINNING_BOARD = 0b111101111;
const buttons = [
0b110110000,
0b111000000,
0b011011000,
0b100100100,
0b010111010,
0b001001001,
0b000110110,
0b000000111,
0b000011011
];
```

Since the input format uses symbols instead of digits, we need to translate them to a format we can understand:

```
let board = parseInt((readline() + readline() + readline())
.replace(/./g, x => ({
' ': '',
'*': '1',
'~': '0'
}[x])), 2);
```

We now get a list of button presses that were made by Lizzo already. To apply them, we use our bit masks and XOR them to the initial board configuration:

```
[...readline()].forEach(i => {
board^= buttons[~-i];
});
```

Having all set up now, the only remaining part is searching for the button that is missing. To do so we pretend to press a button and check if the resulting configuration is our winning board configuration:

```
for (let i in buttons) {
if ((board ^ buttons[i]) == WINNING_BOARD) {
console.log(-~i);
break;
}
}
```

Side note: since the keys are string, we make use of JavaScripts implicit casting from string to number when having a prefix operation like ~ or -. Using the two's-complement allows to increase or decrease a number by one by saying ~-x or -~x which is then used here instead of x+1 or x-1.