Dynamic Paths — HackTheBox

Description

"On your way to the vault, you decide to follow the underground tunnels, a vast and complicated network of paths used by early humans before the great war. From your previous hack, you already have a map of the tunnels, along with information like distances between sections of the tunnels. While you were studying it to figure your path, a wild super mutant behemoth came behind you and started attacking. Without a second thought, you run into the tunnel, but the behemoth came running inside as well. Can you use your extensive knowledge of the underground tunnels to reach your destination fast and outrun the behemoth?"

Connection: nc 154.57.164.65 30945

Analysis

Protocol Reconnaissance

Connecting to the server revealed the following protocol:

1. 100 rounds (grids) to solve sequentially
2. Each round provides dimensions i x j (2 <= i,j <= 100) and a flat list of numbers representing the grid
3. Goal: find the minimum path sum from top-left to bottom-right, moving only right or down
4. Server provides an example: 4x3 grid with answer 17 (path: 2 -> 5 -> 2 -> 1 -> 3 -> 4)

Key Insight

The challenge name "Dynamic Paths" directly hints at Dynamic Programming. This is a classic minimum path sum problem (equivalent to LeetCode #64):

• Given an m x n grid of non-negative integers
• Find a path from top-left to bottom-right
• Can only move right or down at each step
• Minimize the total sum of values along the path

Algorithm

Classic 2D DP with recurrence:

dp[0][0] = grid[0][0]
dp[i][0] = dp[i-1][0] + grid[i][0]       (first column — can only come from above)
dp[0][j] = dp[0][j-1] + grid[0][j]       (first row — can only come from left)
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])   (general case)

Answer: dp[rows-1][cols-1]

Time complexity: O(rows x cols) per round — easily handles 100x100 grids.

Solution

Solve Script

from pwn import *


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] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[rows - 1][cols - 1]


r = remote("154.57.164.65", 30945)

# Read the intro text
intro = r.recvuntil(b"Test 1/100")
print(intro.decode())

for t in range(100):
    if t > 0:
        r.recvuntil(f"Test {t + 1}/100".encode())

    # Read dimensions line
    r.recvuntil(b"\n")
    dims_line = r.recvline().decode().strip()
    print(f"\n--- Test {t + 1}/100 ---")
    print(f"Dims: {dims_line}")

    parts = dims_line.split()
    rows = int(parts[0])
    cols = int(parts[1])

    # Read the numbers line
    nums_line = r.recvline().decode().strip()
    nums = list(map(int, nums_line.split()))
    print(f"Numbers: {nums[:20]}{'...' if len(nums) > 20 else ''}")

    # Build grid
    grid = []
    for i in range(rows):
        row = nums[i * cols : (i + 1) * cols]
        grid.append(row)

    answer = min_path_sum(grid)
    print(f"Answer: {answer}")

    r.recvuntil(b"> ")
    r.sendline(str(answer).encode())

# Get the flag
print("\n=== GETTING FLAG ===")
remaining = r.recvall(timeout=10)
print(remaining.decode())

Execution

All 100 tests passed on the first run. Grid sizes ranged from 2x2 up to ~100x100. The DP algorithm handled all sizes efficiently with no timeouts.

Lessons Learned

1. Challenge name is a hint — "Dynamic Paths" directly points to Dynamic Programming
2. Classic DP problem — minimum path sum in a grid is LeetCode #64, a well-known textbook problem
3. Only right/down moves simplify the recurrence — each cell depends only on the cell above and to the left
4. Socket automation with pwntools is essential for multi-round challenges — 100 rounds cannot be solved manually
5. Parsing protocol matters — correctly parsing dimensions and flat number lists into a 2D grid is the main implementation challenge