Rating:

We had access to a service (139.59.28.4:1340) and had to solve 10 levels to get the flag. Each level consists of a 2D matrix n*m, and a list of checkpoints. We have to find a path in the matrix from (1,1) to (n,m) maximizing the sum of the matrix's visited cells. We can only move to right or bottom direction.

Another constraint is to visit every checkpoints given. At a first try I developed a recursive algorithm, but it was too slow on larges matrix.

So I developed a second solution with [dynamic programming](https://en.wikipedia.org/wiki/Dynamic_programming) paradigm. Here is my solution in Python (important function is solve_matrix) :

```python
from pwn import *

def solve_matrix(matrix, cp):
r = len(matrix)
c = len(matrix[0])

matrix_mem = [[0 for _ in range(c)] for _ in range(r)]
matrix_mem[0][0] = matrix[0][0]

# We give a high value to each checkpoint
for i in range(r):
for j in range(c):
if len(filter(lambda x: x == (i, j), cp)) > 0:
matrix_mem[i][j] += 10000

for i in range(1, r):
matrix_mem[i][0] += matrix_mem[i-1][0] + matrix[i][0]
for j in range(1, c):
matrix_mem[0][j] += matrix_mem[0][j-1] + matrix[0][j]

for i in range(1, r):
for j in range(1, c):
mij = matrix[i][j]
mi = matrix_mem[i-1][j]
mj = matrix_mem[i][j-1]
matrix_mem[i][j] += max(mi, mj) + mij

# Don't count checkpoint special value
return matrix_mem[r-1][c-1] - 10000 * len(cp)

def solve_level(p):
p.recvuntil(" ]\n")
(r, c) = p.recvuntil("\n").split(" x ")
r = int(r)
c = int(c)

matrix = [[0 for _ in range(c)] for _ in range(r)]
for i in range(r):
l = p.recvline().split(" ")
for j in range(c):
matrix[i][j] = int(l[j])

checkpoints = int(p.recvline())
cp = []
for i in range(checkpoints):
l = p.recvline().split(" ")
cp.append((int(l[0])-1, int(l[1])-1))

return solve_matrix(matrix, cp)

if __name__ == "__main__":
p = remote('139.59.28.4', 1340)
for i in range(1, 11):
log.info("Solving level %d..." % i)
s = solve_level(p)
log.info("Soluce: %d" % s)
p.sendline(str(s))
p.interactive()
```

And we got :

```
[+] Opening connection to 139.59.28.4 on port 1340: Done
[*] Solving level 1...
[*] Soluce: 2364
[*] Solving level 2...
[*] Soluce: 3153
[*] Solving level 3...
[*] Soluce: 5792
[*] Solving level 4...
[*] Soluce: 4133
[*] Solving level 5...
[*] Soluce: 6830
[*] Solving level 6...
[*] Soluce: 4577
[*] Solving level 7...
[*] Soluce: 3091
[*] Solving level 8...
[*] Soluce: 2871
[*] Solving level 9...
[*] Soluce: 2877
[*] Solving level 10...
[*] Soluce: 3884
[*] Switching to interactive mode
Congrats the flag is xiomara{recursion_is_better_than_iteration}
[*] Got EOF while reading in interactive
```

Original writeup (https://t0x0sh.org/2018/02/24/xiomara-mario-maze.html).