Dynamic path

---

Description

Write Up: offpath
Format du flag: HTB{flag}

Enoncé

Le challenge consiste à se connecter à un serveur via un socket. Le serveur envoie des grilles de nombres entiers, et pour chaque grille, il faut calculer la somme minimale des chemins de la case en haut à gauche (0,0) à la case en bas à droite (n-1, m-1). La solution de chaque grille doit être envoyée au serveur pour passer au test suivant. Le processus se répète jusqu'à ce que 100 tests soient complétés.

The challenge is to connect to a server via a socket. The server sends grids of integers, and for each grid, it is necessary to calculate the minimum sum of the paths from the top left box (0,0) to the bottom right box (n-1, m-1) . The solution of each grid must be sent to the server to move on to the next test. The process repeats until 100 tests are completed.

---

Solution détaillée

Le serveur envoie une série de grilles sous la forme de chaînes de caractères. Chaque grille commence par une ligne indiquant ses dimensions, suivie des valeurs des cases. Pour chaque grille, il faut déterminer la somme minimale des chemins pour aller du coin supérieur gauche au coin inférieur droit, en ne pouvant se déplacer que vers la droite ou vers le bas.

Pour résoudre ce problème, nous devons :

1. Parser les Données :
   • Extraire les dimensions de la grille et les valeurs des cases à partir de la chaîne de caractères reçue du serveur.
2. Calculer la Somme Minimale des Chemins :
   • Utiliser une approche de programmation dynamique pour calculer la somme minimale des chemins dans la grille.
3. Envoyer les Résultats au Serveur :
   • Envoyer le résultat calculé pour chaque grille au serveur et attendre les prochaines données jusqu'à ce que tous les tests soient complétés.

Voici le code que nous avons utilisé :

import socket
import re

def parse_grid(data):
    lines = data.strip().split('\n')
    dimensions = lines[0].split()
    rows = int(dimensions[0])
    cols = int(dimensions[1])
    grid_data = list(map(int, lines[1].split()))
    grid = [grid_data[i * cols:(i + 1) * cols] for i in range(rows)]
    return grid



def min_path_sum(grid):
    rows = len(grid)
    cols = len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    for i in range(1, rows):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, cols):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    return dp[rows-1][cols-1]



def solve_challenge():
    host = '94.237.49.212'
    port = 38959

    with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
        s.connect((host, port))
        buffer = ""
        tests_completed = 0

        while True:
            data = s.recv(4096).decode('utf-8')
            if not data:
                break
            buffer += data

            while True:
                match = re.search(r'Test \d+/100\n(\d+ \d+)\n((?:\d+ +)+\d+)', buffer)
                if not match:
                    break

                grid_dimensions = match.group(1)
                grid_numbers = match.group(2)
                grid_data = f"{grid_dimensions}\n{grid_numbers}"

                try:
                    grid = parse_grid(grid_data)
                    result = min_path_sum(grid)

                    s.sendall(str(result).encode('utf-8') + b'\n')
                    print(f"Sent result: {result}")
                    tests_completed += 1

                    buffer = buffer[match.end():]
                except IndexError:
                # If there is an error in parsing the grid, we might have incomplete data, so continue reading
                print("Incomplete data, waiting for more.")
                break

            # Check if we have completed all tests and the buffer is empty
            if tests_completed == 100:
                final_data = s.recv(4096).decode('utf-8')
                print("Final server message: ", final_data)
                break



if __name__ == '__main__':
    solve_challenge()