# programming/back-from-brazil

### Writeup by Aryan

This is the source code we are provided with.

```python
import random, time

def solve(eggs):
    redactedscript = """
    â–ˆ â–ˆ â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ
    â–ˆâ–ˆ â–ˆ â–ˆâ–ˆ

    â–ˆâ–ˆâ–ˆ â–ˆ â–ˆâ–ˆ â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ
        â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ â–ˆ â–ˆâ–ˆ

    â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ â–ˆ â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ

    â–ˆâ–ˆâ–ˆ â–ˆ â–ˆâ–ˆ â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ
        â–ˆâ–ˆâ–ˆ â–ˆ â–ˆâ–ˆ â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ
            â–ˆâ–ˆ â–ˆ â–ˆâ–ˆ â–ˆ â–ˆâ–ˆâ–ˆ â–ˆ â–ˆâ–ˆ â–ˆâ–ˆ
                â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ

            â–ˆâ–ˆ â–ˆ â–ˆâ–ˆ â–ˆâ–ˆ
                â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ â–ˆ â–ˆâ–ˆâ–ˆâ–ˆ â–ˆ â–ˆâ–ˆâ–ˆâ–ˆâ–ˆ
            â–ˆâ–ˆ â–ˆ â–ˆâ–ˆ â–ˆâ–ˆ
                â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ â–ˆ â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ â–ˆ â–ˆâ–ˆâ–ˆ

            â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ â–ˆâ–ˆ â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ

    â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ
    """

    return sum([ord(c) for c in redactedscript])

n = 1000

start = time.time()

for _ in range(10):
    eggs = []
    for i in range(n):
        row = []
        for j in range(n):
            row.append(random.randint(0, 696969))
            print(row[j], end=' ')
        eggs.append(row)
        print()

    solution = solve(eggs)
    print("optimal: " + str(solution) + " ðŸ¥š")
    inputPath = input()
    inputAns = eggs[0][0]
    x = 0
    y = 0

    for direction in inputPath:
        match direction:
            case 'd':
                x += 1
            case 'r':
                y += 1
            case _:
                print("ðŸ¤”")
                exit()

        if x == n or y == n:
            print("out of bounds")
            exit()

        inputAns += eggs[x][y]


    if inputAns < solution:
        print(inputAns)
        print("you didn't find enough ðŸ¥š")
        exit()
    elif len(inputPath) < 2 * n - 2:
        print("noooooooooooooooo, I'm still in Brazil")
        exit()

    if int(time.time()) - start > 60:
        print("you ran out of time")
        exit()

print("tnxs for finding all my ðŸ¥š")
f = open("/flag.txt", "r")
print(f.read())
```

We have a 1000 x 1000 grid of random numbers, and we have to find the path that has max sum (based on the numbers in the cells of our path). We can only move right or down.

It is a standard dynamic programming problem, and many implementations exist online. Here's [one](https://www.geeksforgeeks.org/maximum-sum-path-in-a-matrix-from-top-left-to-bottom-right/) in case you want to understand the approach in more detail. Attached below is my solve script.

```python
import socket

def connect_and_retrieve(sock):
    def recv_until_optimal(sock):
        data = b""
        while True:
            chunk = sock.recv(4096)
            if not chunk:
                break
            data += chunk
            if b"optimal:" in chunk:
                break
        return data.decode('utf-8')

    data = recv_until_optimal(sock)
    lines = data.strip().split('\n')
    optimal = ""
    eggs = []
    for line in lines:
        if "optimal:" in line:
            optimal = int(line.split(": ")[1].split(" ")[0])
            break
        row = [int(x) for x in line.split()]
        eggs.append(row)

    return eggs, optimal

def solve(eggs):
    n = len(eggs)
    dp = [[0 for _ in range(n)] for _ in range(n)]
    path = [['' for _ in range(n)] for _ in range(n)]

    dp[0][0] = eggs[0][0]

    for i in range(1, n):
        dp[i][0] = dp[i-1][0] + eggs[i][0]
        path[i][0] = path[i-1][0] + 'r'

    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + eggs[0][j]
        path[0][j] = path[0][j-1] + 'd'

    for i in range(1, n):
        for j in range(1, n):
            if dp[i-1][j] > dp[i][j-1]:
                dp[i][j] = dp[i-1][j] + eggs[i][j]
                path[i][j] = path[i-1][j] + 'r'
            else:
                dp[i][j] = dp[i][j-1] + eggs[i][j]
                path[i][j] = path[i][j-1] + 'd'

    return dp[n-1][n-1], path[n-1][n-1]

def main():
    server_ip = "24.199.110.35"
    server_port = 43298

    with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
        s.connect((server_ip, server_port))

        for _ in range(10):
            print(f"Iteration #{_}")
            eggs, optimal = connect_and_retrieve(s)
            print("got the input")

            optimal_calculated, path = solve(eggs)
            print("solve script executed")

            assert optimal == optimal_calculated, "optimal dp doesnt match"
            assert len(path) == 1998, "wrong path length"

            s.sendall((path + "\n").encode('utf-8'))

        flag = s.recv(4096).decode('utf-8')
        print("Flag:", flag)

if __name__ == "__main__":
    main()
```

Flag: `n00bz{1_g0t_b4ck_h0m3!!!}`


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://centinels.gitbook.io/home/writeups/n00bzctf/programming-back-from-brazil.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.