# [m0lecon 2021] Left or Right

My first idea was to use itertools and calculate te minimum leftmost point for every possible combination but this solution was obvioslly to slow so i ended up with another idea. My final solution can be divided in three main steps:

1. Cleaning
2. Sorting
3. Calculate the distance

### Cleaning

I noticed that in every string i recive, for example RLRLRRRLL, his leftmost point is 0 because we never go left more than the starting point, when we go RL, we remain in the same place so we can replace recursively alle the RL from each string with an empty string ( RLRLRRRLL in the end becomes just R and LRLL will be LL). Our final string will have every time the format `'L'*n + 'R'*m `

``````  for string in inputArray:
n=string.replace('RL','')
x=string
while x!=n:
x=n
n=n.replace('RL','')
if n!='':
newArray.append(n)
``````

### Sorting

After cleaning my array i just sort it by the percentage of L in each string , this is were the “magic” happens

``````newArray.sort(key = lambda x: (x.count('L')/len(x))*100000 )
``````

higher the percentage of L in the string, higher will be the index of the string into the new array, in this way we have at the beginning elements that are just R, then we have R and L (higher the index of the array, lower the percentage of R in each string) and in the end we have the strings with just L `['LLLLLLLLRRRRR', 'LR', 'RRRRRRRRRRRR', 'LLLLLL']` sorted will become `['RRRRRRRRRRRR', 'LR', 'LLLLLLLLRRRRR', 'LLLLLL']` the result of the sort is the *combination of strings with lower leftmost value because we are going as right as possible to avoid the L strings.

### Calculate the distance

Once we have the sorted array in the correct order the last thing we have to do is to make a string from it and calculate the leftmost point from 0, our start point. Each R i increments by 1, each L i decrements by 1, our final solution will be 0 or a negative number so we will send the absolute value of our distance.

``````    position=0
distance=0
for c in ''.join(newArray):
position= position+1 if c=='R' else position-1
distance=distance if position>distance else position

p.sendline(str(abs(distance)))
``````

# Final script

``````from hashlib import *
from pwn import *
import time

p=remote("challs.m0lecon.it",5886)
res=p.recv()
ar=str(res).replace('.\\n\'','').split(' ')

#solving the Proof of Work
h=''
d=''
while(d=='' or h[-5::]!=ar):
d=ar+str(random.randrange(1, 0xffffffffffffffffffffffff))
h=hashlib.sha256(d.encode()).hexdigest()
print(d,h)
time.sleep(1)
p.sendline(d)
time.sleep(1)
log.info(p.recvuntil('each test.\n'))
p.sendline()

for i in range (200):

#Number of inputs
numeroDiInp=int(p.recvline().decode('utf-8'))

#Get the MOFO strings
inputArray=[]
for t in range(numeroDiInp):
inputArray.append(p.recvline().decode('utf-8').strip())

#Cleaning
newArray=[]
for string in inputArray:
n=string.replace('RL','')
x=string
while x!=n:
x=n
n=n.replace('RL','')
if n!='':
newArray.append(n)

#Sorting
newArray.sort(key = lambda x: (x.count('L')/len(x))*100000 )

#Calculate the distance
position=0
distance=0
for c in ''.join(newArray):
position= position+1 if c=='R' else position-1
distance=distance if position>distance else position

#Send the solution
p.sendline(str(abs(distance)))
print(i,') ',distance,p.recvline().decode('utf-8'))

print('flag:',p.recvline().decode('utf-8'))
``````