Hackvent 2024: Day 7
[HV24.07] Merry Mazemas
A clumsy elf lost all the gifts in a magical maze right before Christmas Eve. Now, with time of the essence, Santa must navigate this maze, collecting every gift in the most optimal way - the shortest path possible - to save Christmas. Can you guide him to gather all the gifts and reach the exit before it's too late?
Navigate the maze and get the flag.
Flag format: HV24{}
This challenge was written by keep3r. He k33ps on giving.Solution
We are given an IP address belonging to a server (e.g. 203.0.113.0) and a port (8000).
First, we connect to this IP and port using netcat (nc):
nc 203.0.113.0 5000Upon connecting, we are presented with the following text:
Ho Ho Ho! It's Merry Mazemas!
Guide Santa through the maze to collect all the gifts in the most efficient way possible before exiting.
s = Santa
x = Gift
e = Exit
###########
#s # #
### ### # #
# # # # #
# ### ### #
# # # #
#x# # # # #
# # # # #
# # #####x#
#e# #
###########
Move (w/a/s/d):As it turns out, we need to play and solve this little maze game. Our goal is to start at the Santa position (s), collect all the gifts (x) and then proceed to the exit at (e). We can make one move at a time by sending the server a w / a / s / d depending on if we want to go up / left / down / right.
Through trial and error, I notice a few things:
- Each attempt generates a different set of puzzles.
- Upon solving the puzzle, a new puzzle is provided to us. In total there are 3 puzzles to solve before we are given the flag.
- The minimum number of moves must be made. If you use too many moves the connection will be dropped with an error message:
Oops, it seems you've taken quite the merry meander through the maze! Next time, let's try to find a more direct path to make sure all the gifts are collected before dawn. - If you do not collect all the gifts, you get the error:
Bravo for reaching the exit, but oh my, Santa's sleigh is missing some gifts! It looks like we need to give it another go to make sure we gather all the presents this time.
With all of this in mind, we write a Python script to solve this challenge for us.
# Hackvent 2024 - Day 7
# Mo Beigi
#
# Solve maze puzzles using travelling salesman.
import socket
from collections import deque
import time
server_host = '203.0.113.0'
server_port = 8000
# Models
class Maze:
WALL = '#'
SANTA = 's'
GIFT = 'x'
EXIT = 'e'
def __init__(self, maze):
"""
Initialize a new maze object.
:param maze: 2D list representing the maze layout
:param santa: Tuple (x, y) representing Santa's position
:param gift: List of gift positions [(x, y), ...] (default is an empty list)
:param exit_pos: Tuple (x, y) representing the exit position
"""
self.maze = maze
self.santa_pos = None
self.gifts_pos = []
self.exit_pos = None
self._find_positions()
def _find_positions(self):
"""Find positions of Santa, gifts, and exit."""
for y, row in enumerate(self.maze):
for x, char in enumerate(row):
if char == Maze.SANTA:
self.santa_pos = (x, y)
elif char == Maze.GIFT:
self.gifts_pos.append((x, y))
elif char == Maze.EXIT:
self.exit_pos = (x, y)
def display(self):
"""Display the maze in a user-friendly format."""
for row in self.maze:
print("".join(row))
def parse_maze(received_data):
lines = received_data.splitlines()
# Reverse the lines to start collecting from the bottom
# In case multiple 'mazes' exist in buffer
reversed_lines = lines[::-1]
valid_lines = []
collecting = False
for line in reversed_lines:
if line.startswith(Maze.WALL):
collecting = True
valid_lines.append(line)
elif collecting:
break
# Reverse the collected lines to restore their original order
valid_lines = valid_lines[::-1]
return Maze(valid_lines)
# Socker & data transfer
def connect_to_server(host, port, timeout=2):
server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server.settimeout(timeout)
try:
server.connect((host, port))
print(f"Connected to {host}:{port}")
return server
except socket.timeout:
print(f"Connection attempt timed out after {timeout} seconds.")
exit(1)
except Exception as e:
print(f"Error connecting to {host}:{port}: {e}")
exit(1)
def receive_data(s):
data = s.recv(65535)
if not data:
print("No data received. The server might have closed the connection.")
exit(1)
else:
data_str = data.decode('utf-8', 'ignore').strip()
return data_str
# Path finding
def get_move(dx, dy):
"""Get the move corresponding to the direction (dx, dy)."""
if dx == 1:
return 'd' # Right
elif dx == -1:
return 'a' # Left
elif dy == 1:
return 's' # Down
elif dy == -1:
return 'w' # Up
def bfs(maze, start, goal):
"""Breadth-First Search to find the shortest path from start to goal."""
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # Right, Down, Left, Up
queue = deque([(start, [])]) # Queue of (position, path)
visited = set()
visited.add(start)
while queue:
(x, y), path = queue.popleft()
# If we reach the goal, return the path
if (x, y) == goal:
return path
# Explore neighbors
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and \
(nx, ny) not in visited and maze[ny][nx] != Maze.WALL:
visited.add((nx, ny))
queue.append(((nx, ny), path + [get_move(dx, dy)]))
return [] # No path found
def find_all_distances(maze, start_pos, gift_positions, exit_pos):
"""Calculate the shortest distance between all important points (start, gifts, exit)."""
important_positions = [start_pos] + gift_positions + [exit_pos]
distances = {}
# Calculate BFS distance from each important position
for point1 in important_positions:
distances[point1] = {}
for point2 in important_positions:
if point1 != point2:
path = bfs(maze, point1, point2)
distances[point1][point2] = len(path) # Store path length
return distances
def solve_tsp(distances, start_pos, gift_positions, exit_pos):
"""Solve the TSP-like problem to collect all gifts and then reach the exit."""
all_points = [start_pos] + gift_positions
n = len(all_points)
dp = {}
# Use dynamic programming with bitmasking to solve TSP
def tsp(mask, pos):
"""Recursive TSP with memoization."""
if mask == (1 << n) - 1: # All points visited
return distances[all_points[pos]][exit_pos], [exit_pos] # Go to the exit from the last gift
if (mask, pos) in dp:
return dp[(mask, pos)]
# Try visiting all unvisited points
best_dist = float('inf')
best_path = []
for next_pos in range(n):
if (mask & (1 << next_pos)) == 0: # If the next point is unvisited
new_mask = mask | (1 << next_pos)
dist, path = tsp(new_mask, next_pos)
dist += distances[all_points[pos]][all_points[next_pos]]
if dist < best_dist:
best_dist = dist
best_path = [all_points[pos]] + path
dp[(mask, pos)] = best_dist, best_path
return best_dist, best_path
# Start TSP from the start position with no gifts visited
return tsp(1, 0)[1] # Return the path (not the total distance)
def find_path(maze):
"""Find the most efficient path to collect all gifts and then reach the exit."""
# Find all positions (Santa, Gifts, Exit)
current_pos = maze.santa_pos
gift_positions = maze.gifts_pos
exit_pos = maze.exit_pos
# Find all distances between points
distances = find_all_distances(maze.maze, current_pos, gift_positions, exit_pos)
# Solve the TSP to find the optimal path
moves = []
optimal_moves = solve_tsp(distances, current_pos, gift_positions, exit_pos)
# Now that the optimal path is found, we reconstruct the path from the solution
# Assuming the solution gives us the correct sequence, we need to compute the exact moves
for gift_pos in optimal_moves:
path_to_gift = bfs(maze.maze, current_pos, gift_pos)
moves.extend(path_to_gift)
current_pos = gift_pos
# Finally, go to the exit
path_to_exit = bfs(maze.maze, current_pos, exit_pos)
moves.extend(path_to_exit)
return moves
def main():
server = connect_to_server(server_host, server_port)
maze = None
# Communicate back and forth
while True:
received_data = receive_data(server)
if received_data:
print(f"Received from server: {received_data}")
else:
break
# Process new maze
if any(phrase in received_data for phrase in [
'Guide Santa through the maze',
'Please lend a helping hand',
'Could you kindly assist him again']):
print("Processing new maze...")
maze = parse_maze(received_data)
# Find best path
path = find_path(maze)
if not path:
print("Failed to find optimal path for maze.")
exit(1)
print(f"Optimal traversal path is: {path}")
# Make all moves
print(f"Sending all moves to server...")
for move in path:
server.sendall(f"{move}\n".encode('utf-8'))
print("\n")
# Delay between Maze prevents output race conditions
time.sleep(2)
# Close the socket
server.close()
if __name__ == '__main__':
main()
Our script allows us to connect to the server, retrieve the maze data, parse the maze into our model class, then apply our pathfinding algorithm to it to find the optimal moves needed to solve each puzzle. The algorithm utilizes a breadth-first search (BFS) to calculate the shortest path between key points: Santa, the gifts, and the exit. Using this, we solve a Travelling Salesman Problem (TSP)-like challenge by applying dynamic programming with bitmasking to determine the most efficient sequence of moves. The resulting optimal path ensures that all gifts are collected before heading to the exit with the fewest total moves.
It is important to note that the pathfinding code above was generated with AI. This script also does not solve the challenge on every single attempt, but it appears to have a relatively high success rate.
Running our code gives us the following server responses, which contain the flag for today's challenge:
Ho Ho Ho! It's Merry Mazemas!
Guide Santa through the maze to collect all the gifts in the most efficient way possible before exiting.
s = Santa
x = Gift
e = Exit
###########
#s # #
### ### # #
# # # # #
# ### ### #
# # # #
#x# # # # #
# # # # #
# # #####x#
#e# #
###########
Move (w/a/s/d):
Congratulations! You've masterfully guided Santa through the maze, collecting every gift with the perfect path!
Received from server: Oh no, it seems the exit has led Santa into yet another maze! Please lend a helping hand to guide him through once more.
#########################
#s # # #
##### # # ### ######### #
# # # # # #
# ### # ############### #
# # # x #
# ####### ############# #
# # x # # #
####### # ##### ### # ###
# # # # # # #
# ### ########### # ### #
# # # #e #
### ############### ### #
# x # #
# ########### ######### #
# # # # #
# ### ######### # # #####
# # # # # # # #
# # # # # # ######### # #
# # # # # # # #
# # ##### ######### # # #
# # # x # # # #
##### # ##### ### ##### #
# # #
#########################
Move (w/a/s/d):
Congratulations! You've masterfully guided Santa through the maze, collecting every gift with the perfect path!
Oh dear, the exit has whisked Santa away to another maze! Could you kindly assist him again?
###################################################
#s# # # # # # x #
# # ### ####### # # # # ### ####### # # # ##### ###
# # # # # # # # # # # # # #
# ### ### # # ### # ############# ######### # ### #
# # # # # # # # # # # # # #
### # ##### # # ########### # # ### # # # ### # # #
# # # # # #e # # # # # # # #
# ##### ##### # ### # ########### # ##### # ### # #
# # # # # # # # # # # # # #
# ### ### # # ### ####### # # ### ### # ####### # #
# # # # # # # # # # # # # # # # # #
# # ##### # # # # # ### ### ### ### ### # # # ### #
# # # # # # # # # # # # #
# # # # ##### ########### ############# # ##### # #
# # # # # # # # # # # # #
# # ####### ### # ##### # # ######### # # # # ### #
# # # # # # # # # # # # # # # #
# ##### ### # # ### # ### ##### # ### ####### # # #
# # # # # # # # # # #x# #
##### # # ### ####### # ##### # ############### # #
# # # # # # # # # # # #
# ##### # # ####### # # # ### ##### # # ### # # ###
# # # # # #x# # # # # x# # # #
##### # # ##### ### # ### ######### # ####### # # #
# # # # # # # # # # # # # #
# # ####### # ##### ### ### ######### ##### ##### #
# # # # # # # # # # #
# ### ####### ### ### ####### # # # ##### # # ### #
# # # # # # # # # # # # # # # #
### ### # # # # # ### ##### # # # ### # ##### # # #
# # # # # # #x # # # # # # # #
# # #x##### ### ### ### ##### # ########### ##### #
# # # # # # # # # # # x # #
# ##### ##### ### # ##### ####### ### ##### # # # #
# # # # # # # # # # #
# ######### ##### ##### ####### ### ### # # # #####
# # # # # # # # # # # # # #
# ##### # ### # ### # ### # ##### ####### # # ### #
# # # # # # # # # # #
########### ########### ############### ### # # # #
# # # # # # # # # # # #
# ####### ### # # # ### # # # # # ##### ##### # ###
# # # # # # # # # # # #
# # ####### ####### ##### ########### ### ####### #
# # # # # # # # # # # #
# ##### ##### # # ### ##### # # ### ########### # #
# # # # # # # # # # # # # # #
### # ##### # ##### ### ######### # # # # # ### # #
# x # # # # # #
###################################################
Move (w/a/s/d):
Congratulations! You've masterfully guided Santa through the maze, collecting every gift with the perfect path!
Well done for guiding Santa through all the levels! Here's your gift:
HV24{santa-is-a-travelling-salesman}
Flag:
HV24{santa-is-a-travelling-salesman}