Tags: programming algebra

Rating: 0

**Description**

> Are you a real math wiz?
>
> nc misc.chal.csaw.io 9002

**No files provided**

**Solution**

After conecting we are presented with some simple math problems:

____ __ _ _ ___ ___
/ ___|__ _ _ __ _ _ ___ _ _ / _(_)_ __ __| | __ __ |__ \__ \
| | / _ | '_ \ | | | |/ _ \| | | | | |_| | '_ \ / _ | \ \/ / / / / /
| |__| (_| | | | | | |_| | (_) | |_| | | _| | | | | (_| | > < |_| |_|
\____\__,_|_| |_| \__, |\___/ \__,_| |_| |_|_| |_|\__,_| /_/\_\ (_) (_)
|___/
**********************************************************************************
18 - X = 121
What does X equal?: -103
YAAAAAY keep going
14 * X = 64
What does X equal?: 64/14
HEYYYY THAT IS NOT VALID INPUT REMEMBER WE ONLY ACCEPT DECIMALS!

At some point the problems become a bit lengthier:

...
YAAAAAY keep going
((((1 - 5) + (X - 15)) * ((18 + 2) + (11 + 3))) - (((4 + 8) * (3 * 3)) * ((2 * 5) * (13 - 9)))) - ((((8 - 14) - (11 - 6)) - ((14 + 12) + (13 * 15))) - (((9 - 1) - (3 * 9)) * ((5 * 4) * (19 + 4)))) = -13338

And at some point later still, the intermediate results cross the overflow limits for both 32-bit and 64-bit integers. So Python with its native bigints seemed like a natural choice for the solver.

Performance was not particularly important for this challenge, since it seemed the server would wait 20 seconds before timing out on any given problem. Additionally, the equation always had one occurrence of X, always had a single integer on the right-hand side, and the operations on the left-hand side were grouped into parentheses properly and only included +, -, and *.

So my approach was to have a couple of simple regular expressions to match a bracketed operation with specific integers and replace that (in the equation string) with the result, then repeat as long as needed. Also, some of the problems had non-integer solutions. The default precision of Python seemed good enough, but I was worried about inaccuracy build-up if I used floats, so instead I kept the result as a fraction of two integers until the very end when it was submitted to the server.

([Full Python script here](https://github.com/Aurel300/empirectf/blob/master/writeups/2018-09-14-CSAW-CTF-Quals/scripts/algebra.py))

flag{y0u_s0_60od_aT_tH3_qU1cK_M4tH5}