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}`

Original writeup (https://wrecktheline.com/writeups/m0lecon-2021/#left_or_right_writeup).