Rating:
[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:
```
4
LRLRLLRRRLLRLLRRRRLR
LRLRRLRLLRLLLRR
LRRLRLLLLLLLLLLRLRRLLLLRRLLLRRRL
LLLRLRLLR
```
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, 3
last_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` <= 0
In 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` > 0
After 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:
```python
import re
from hashlib import sha256
from itertools import product
import numpy as np
from 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():
break
print(_r.recvall())
```
`ptm{45_r16h7_45_p0551bl3}`
