[Link to original writeup](https://wrecktheline.com/writeups/m0lecon-2021/#left_or_right_writeup/)
# Left or right? (19 solves, 217 points)by y011d4
```Just follow your instinct. Are you going left or right?
nc challs.m0lecon.it 5886
Authors: Drago_1729, matpro, mr96```
This challenge is algorithmic task.
```Hello hacker! This challenge will test your programming skills.I will give you some strings made up only by L and R. You start at a point O, L means moving to the left by 1 unit, R means moving to the right by 1 unit.Your objective is to concatenate ALL these strings such that the leftmost point that you reach during your path is as near as possible to O.Let's call this point P. What is the distance between O and P?
The first line of the input contains a number N.The following N lines contain a string made up only of the characters L and R.Your answer should be a non-negative integer.In every testcase 0<N<=150 and the sum of the lengths of the given strings is at most 100000.You must answer to 200 testcases to get the flag! Time limit is one second for each test.```
Examples are:
```4LRLRLLRRRLLRLLRRRRLRLRLRRLRLLRLLLRRLRRLRLLLLLLLLLLRLRRLLLLRRLLLRRRLLLLRLRLLR```
First of all, we need to hold not all "LR" but:- the leftmost place from the current position (call it `lr_diff_max`)- the final place from the current position (call it `last_pos`)
for each string, where the left side is positive.For example above:
```lr_diff_max: 2, 3, 12, 3last_pos: -2, 1, 10, 1```
Note that `lr_diff_max >= last_pos`.
In the following, we consider the case `last_pos <= 0` and the other case separately.
#### `last_pos` <= 0In this case, the last position will be on the right or the same. This is higher priority than the other case.
For each choice, we should pick the case of `lr_diff_max` <= `ans` (`ans` means the current answer for each task) because it won't affect the answer. If there are no such cases, choose the smallest `lr_diff_max` case in order to minimize the `ans`
#### `last_pos` > 0After the all `last_pos` <= 0 cases are chosen, we go to this case.Considering the fact that the final position (call it `all_last_pos`) after all are selected doesn't change, we should pick the case of maximum `lr_diff_max - last_pos` in each choice, because naively the final `ans` equals to the final `lr_diff_max - last_pos + all_last_pos`.
The all script is as follow:
```pythonimport refrom hashlib import sha256from itertools import product
import numpy as npfrom pwn import *
_r = remote("challs.m0lecon.it", 5886)ret = _r.recvline().strip().decode()prefix, suffix = re.findall(    r"Give me a string starting with (.+) such that its sha256sum ends in (.+).", ret)[0]
for i_list in product(list(range(32, 128)), repeat=4):    c_list = list(map(chr, i_list))    tmp = prefix + "".join(c_list)    tmp_hash = sha256(tmp.encode()).hexdigest()    if tmp_hash[-len(suffix):] == suffix:        print("found!")        _r.sendline(tmp)        break
_r.sendlineafter("Time limit is one second for each test.\n", "")
for epoch in range(200):    print(epoch)    N = int(_r.recvline().strip())    steps_list = []    for _ in range(N):        steps_list.append(_r.recvline().strip().decode())    lr_diff_max_list_0 = []    lr_diff_max_list_1 = []    last_pos_list_0 = []    last_pos_list_1 = []    for steps in steps_list:        lr_diff_max = 0        tmp = 0        for step in steps:            if step == "L":                tmp += 1            else:                tmp -= 1            if tmp > lr_diff_max:                lr_diff_max = tmp        if tmp <= 0:            lr_diff_max_list_0.append(lr_diff_max)            last_pos_list_0.append(tmp)        else:            lr_diff_max_list_1.append(lr_diff_max)            last_pos_list_1.append(tmp)
    lr_diff_max_list_0 = np.array(lr_diff_max_list_0)    lr_diff_max_list_1 = np.array(lr_diff_max_list_1)    last_pos_list_0 = np.array(last_pos_list_0)    last_pos_list_1 = np.array(last_pos_list_1)
    ans = 0    # case0: last_pos <= 0    n_0 = len(lr_diff_max_list_0)    used = [False] * n_0    current_pos = 0
    for _ in range(n_0):        found = None        for i in range(n_0):            if not used[i] and lr_diff_max_list_0[i] <= current_pos:                found = i                break        if found is None:            pos_min = 10 ** 10            for i in range(n_0):                if not used[i] and lr_diff_max_list_0[i] <= pos_min:                    pos_min = lr_diff_max_list_0[i]                    found = i        assert found is not None        used[found] = True        ans = max(ans, current_pos + lr_diff_max_list_0[found])        current_pos += last_pos_list_0[found]
    # case1: last_pos > 0    argidx = np.argsort(lr_diff_max_list_1 - last_pos_list_1)[::-1]    for idx in argidx:        ans = max(ans, current_pos + lr_diff_max_list_1[idx])        current_pos += last_pos_list_1[idx]    _r.sendline(str(ans))    if "Yay" not in _r.recvline().strip().decode():        breakprint(_r.recvall())```
`ptm{45_r16h7_45_p0551bl3}` 