---title: "Writeup: M0leCon Teaser CTF 2021 - Left or Right?"author:  - TorioCremadate: 2021-05-16categories:  - writeupstags:  - writeups  - jeopardy  - misc  - ctf  - m0lecon---
## Information
*   *category* : misc*   *points* : 219
## Description
> nc challs.m0lecon.it 5886
## Writeup
After connecting to the challenge and solving the proof of work we receive the following message:
[Screenshot](https://i.imgur.com/QOootWQ.png)
We have to write an algorithm that can find which sequence of the given strings will result inthe leftmost point reached during the path is as near as possible to 0.
We decided, to use a greedy algorithm, since calculating all possible permutations of the stringswould require too much time and we have a limit of 1 second for each test.
To make sure that our sequence will result in the optimal solution we want to move right as much aspossible before moving to the left, so that when we do move left the strings that result in a leftmovement will be countered by the fact that we have already moved right, thus minimizing the overhallleft movement of the whole sequence.
To do so we read each sequence from the output and create a list based on two values: one is the leftmostposition reached during that string, we will call this value `cost`, and the other is the positionreached at the end of the string, we will call this value `pos`.
With these values we can sort the strings and reach an optimal solution. Like we said before we first wantto move right as much as possible, then move left. To do so we sort the strings in increasing order based ontheir `cost` value if their `pos` value is positive, meaning that at the end of those strings we willend up to the right of the starting position and we will move left as little as possible; however if somestrings have a negative `pos` value we will sort those based on the differce between their `cost` and `pos`value, meaning that the ones with a greater differce will be put first. This is because in case of a negative`pos` value our ending position will be left of the starting position, if we used the same sorting criteria aswith the positive `pos` value strings we would end up increasing the effective `cost` value of the following strings,thus obtaining a solution that isn't optimal.
## Exploit
```py#!/usr/bin/env python3from pwn import *from hashlib import sha256
# proof-of-workdef solvepow(p, n):    s = p.recvline()    starting = s.split(b'with ')[1][:10].decode()    s1 = s.split(b'in ')[-1][:n]    i = 0    print("Solving PoW...")    while True:        if sha256((starting+str(i)).encode('ascii')).hexdigest()[-n:] == s1.decode():            print("Solved!")            p.sendline(starting + str(i))            break        i += 1
def solve(l):    v = []    for s in l:        cost = 0        pos = 0        # create list of (cost, pos)        # cost = left-most point reached during string        # pos = position reached at the end of the string        for c in s:            if c == 'L':                pos -= 1            elif c == 'R':                pos += 1            else:                assert False            cost = max(cost, -pos)        v.append((cost, pos))
    # sort list based on cost if pos > 0 else based on abs(cost - pos)    v.sort(key=lambda t: (t[1] < 0, t[0] if t[1] >= 0 else -t[0]-t[1]))    print(v)
    # calculate left-most point during string sequece    max_cost = 0    pos = 0    for cost, delta in v:        max_cost = max(max_cost, cost - pos)        pos += delta    return max_cost
r = remote('challs.m0lecon.it', 5886)solvepow(r, n = 5)
r.readuntil('one second for each test.\n')r.sendline()for _ in range(200):    n = int(r.readline()) # read number of strings    # create list of strings    l = []    for i in range(n):        l.append(r.readline().decode().strip())
    # calculate and send result    ans = solve(l)    print(ans)    r.sendline(str(ans))    print(r.readline())r.interactive()```