Rex To Lynx

Developers from Team Rex¹ built a wildly popular bill-splitting app, making it easy for people around the world to settle debts with friends and family. Whether splitting dinner costs, rent, or a round of drinks, users loved the simplicity of entering calculations directly into the app.

For example, if a friend covered 12 drinks at 5 euros each for a group of 4 people, you could simply type:

(5 * 12) / 4

The app would then calculate that you wish to transfer 15.

But as the app’s popularity soared, so did the number of complaints. Users were reporting suspicious transactions, where they had sent more money than intended. With trust in the app plummeting and negative reviews piling up, the project was handed over to Team Lynx² for a full security audit. It didn't take them long to find the source of the scam.

Let's take a look at one particular scam report, where the user had received the following message:

Please send me 11 + (5 - 15) for drinks last night.

Apparently the total should have been exactly 1 But the actual calculation done on the server was:

11 + (15 - 5) = 21

You see, the text contained carefully crafted invisible Unicode BiDi markers, like so:

Please send me 11 + [U+2067](15 - 5)[U+2069] for drinks last night

The user had unwittingly copied the above expression into the app's input field, which was a custom rich text editor component created by Team Rex. The component includes support for right-to-left languages, such as عربي (Arabic) and עִברִית (Hebrew). However, the calculations on the server ignored all bidirectional markup. Taking a fresh perspective, team Lynx argued that bidirectional text should be taken into account in these calculations. This would not be a true WYSIWYG rich text editor otherwise!

You must now go through all the money transfer logs, and calculate the result of each line with and without applying the BiDi algorithm. The difference between the calculations gives an indication of how much money has been extracted in scams.

Here are some examples:

⁧(1 * ((⁦(66 / 2)⁩ - 15) - 4)) * (1 + (1 + 1))⁩
⁧(8 / (⁦(1 * 3)⁩ + 1)) * 130⁩
47 * ((3 + 1) * (⁧(40 * (24 - 8))⁩ / (⁧(72 / 6)⁩ - ⁧(⁦(2 * 1)⁩ + 2)⁩)))
90 * ⁧(((810 / (⁦(3 + 5)⁩ + 1)) + ((169 - 79) / 2)) - ⁦(93 - 28)⁩)⁩
92 * (⁧(92 / ((54 / 3) / (5 + 4)))⁩ - ⁧(2 * (64 / 8))⁩)
73 + (3 * (1 * ⁧(((3 + (6 - 2)) * 6) + ⁦((52 * 6) / ⁧(13 - (7 - 2))⁩)⁩)⁩))

Note, your browser will likely render the above text with BiDi transformation applied! Be sure to download the raw test-input. If you open that in an editor that highlights BiDi markers, you should see something like this:

[U+2067](1 * (([U+2066](66 / 2)[U+2069] - 15) - 4)) * (1 + (1 + 1))[U+2069]
[U+2067](8 / ([U+2066](1 * 3)[U+2069] + 1)) * 130[U+2069]
47 * ((3 + 1) * ([U+2067](40 * (24 - 8))[U+2069] / ([U+2067](72 / 6)[U+2069] - [U+2067]([U+2066](2 * 1)[U+2069] + 2)[U+2069])))
90 * [U+2067](((810 / ([U+2066](3 + 5)[U+2069] + 1)) + ((169 - 79) / 2)) - [U+2066](93 - 28)[U+2069])[U+2069]
92 * ([U+2067](92 / ((54 / 3) / (5 + 4)))[U+2069] - [U+2067](2 * (64 / 8))[U+2069])
73 + (3 * (1 * [U+2067](((3 + (6 - 2)) * 6) + [U+2066]((52 * 6) / [U+2067](13 - (7 - 2))[U+2069])[U+2069])[U+2069]))

Stripping the markers away, the test input looks like this:

(1 * (((66 / 2) - 15) - 4)) * (1 + (1 + 1))
(8 / ((1 * 3) + 1)) * 130
47 * ((3 + 1) * ((40 * (24 - 8)) / ((72 / 6) - ((2 * 1) + 2))))
90 * (((810 / ((3 + 5) + 1)) + ((169 - 79) / 2)) - (93 - 28))
92 * ((92 / ((54 / 3) / (5 + 4))) - (2 * (64 / 8)))
73 + (3 * (1 * (((3 + (6 - 2)) * 6) + ((52 * 6) / (13 - (7 - 2))))))

This was what Rex' calculations were based on.

The BiDirectional algorithm

How does the BiDi algorithm work? The official specification is not an easy read. Below is my attempt to describe this algorithm in simple terms. (Note that you don't need the full algorithm for this puzzle, certain shortcuts are possible).

1. First determine the embedding level for each character.
   1. Start by setting your embedding level at 0, and assume you start with left-to-right text.
   2. Process your input character by character.
   3. If you encounter an RLI marker (U+2067) within left-to-right text, you increase the embedding level. You now enter right-to-left text, and the embedding level is now an odd number.
   4. If you encounter an LRI marker (U+2066) within right-to-left text, you increase the embedding level again. You are back to left-to-right text, and the embedding level must now be an even number.
   5. Whenever you encounter a PDI marker (U+2069), the embedding level drops back one level.
   6. Numbers will always end up from left to right. So 42 is always 42 and never 24, no matter what the surrounding BiDi markers say. To account for this, you must increase the embedding level for digits up to the nearest even number.
2. Now identify the stretch with the highest embedding level, and reverse it, making it a level lower. Work your way from high to low. Stretches with a length of 1 are of course trivial and can be ignored.
3. Parentheses are mirrored when you reverse a bit of text. For example (1 - 2) would be written from right-to-left as )2 - 1( but then the parentheses are mirrored to form (2 - 1)

Here is a worked example (representing RLI, LRI and PDI markers with ⏴, ⏵ and ⏶ respectively):

Input line short : 73 + (3 * (1 * ⏴(((3 + (6 - 2)) * 6) + ⏵((52 * 6) / ⏴(13 - (7 - 2))⏶)⏶)⏶))
Embedding levels : 00000000000000001112111121112111112111112222222222222344333343334332211000
Flips            :                                                       --
                                                                        --------------
                                                           -----------------------------
                                   -------------------------------------------------------
After 1st flip   : 73 + (3 * (1 * ⏴(((3 + (6 - 2)) * 6) + ⏵((52 * 6) / ⏴(31 - (7 - 2))⏶)⏶)⏶))
After 2nd flip   : 73 + (3 * (1 * ⏴(((3 + (6 - 2)) * 6) + ⏵((52 * 6) / ⏴((2 - 7) - 13)⏶)⏶)⏶))
After 3rd flip   : 73 + (3 * (1 * ⏴(((3 + (6 - 2)) * 6) + ⏵(⏶(31 - (7 - 2))⏴ / (6 * 25))⏶)⏶))
After 4th flip   : 73 + (3 * (1 * ⏴(⏶((52 * 6) / ⏴((2 - 7) - 13)⏶)⏵ + (6 * ((2 - 6) + 3)))⏶))
Result           : 73 + (3 * (1 * (((52 * 6) / ((2 - 7) - 13)) + (6 * ((2 - 6) + 3)))))

Going back to the test-input, it should transform into this:

((1 + 1) + 1) * ((4 - (15 - (66 / 2))) * 1)
130 * ((1 + (1 * 3)) / 8)
47 * ((3 + 1) * (((8 - 24) * 40) / ((6 / 72) - (2 + (2 * 1)))))
90 * ((93 - 28) - ((2 / (79 - 169)) + ((1 + (3 + 5)) / 810)))
92 * ((((4 + 5) / (3 / 54)) / 92) - ((8 / 64) * 2))
73 + (3 * (1 * (((52 * 6) / ((2 - 7) - 13)) + (6 * ((2 - 6) + 3)))))

Now, take each line and calculate what it appears to be according to Lynx, and how much was actually transferred by Rex. Take the absolute differences, and sum them all up.

• Line 1 according to Lynx: 66, but according to Rex: 42. The absolute difference is: 24.
• Line 2 according to Lynx: 65, but according to Rex: 260. The absolute difference is: 195.
• Line 3 according to Lynx: 30720, but according to Rex: 15040. The absolute difference is: 15680.
• Line 4 according to Lynx: 5851, but according to Rex: 6300. The absolute difference is: 449.
• Line 5 according to Lynx: 139, but according to Rex: 2760. The absolute difference is: 2621.
• Line 6 according to Lynx: 3, but according to Rex: 316. The absolute difference is: 313.

For this test-input, the scams add up to 19282

What is the sum total of differences between appearance and reality in your puzzle input? Your answer is guaranteed to be a positive integral number.

Reading & reference materials

• Wikipedia on Bidirectional text
• Unicode BiDi markers can potentially cause security issues. Most IDEs have implemented mitigations since this was first discovered. Nevertheless it's good to be aware.
• You can even spoof file extensions using BiDi markers
• And there are more ways to create an invisible backdoor with Unicode.

To play, please log in with one of these options:
GitHub Login | Google Login