ClockWork Guardian Writeup

Challenge Name

ClockWork Guardian

The Clockwork Sentinels defending Eldoria’s Skywatch Spire have gone rogue! You must navigate the spire, avoiding hostile sentinels and finding the safest path.

Challenge Description

In this challenge, you are tasked with finding the shortest safe path from the start position (0,0) to the exit ('E') in a grid while avoiding the sentinels (1). The grid represents the layout of the Skywatch Spire, where '0' indicates a safe path, '1' indicates a sentinel, and 'E' indicates the exit.

We are given an example, and a box to input a script for the website to run.

Solution

To solve this problem, we used a Breadth-First Search (BFS) algorithm. BFS is well-suited for finding the shortest path in an unweighted grid because it explores all possible paths level by level, ensuring that the first time it reaches the exit, it has found the shortest path.

Steps to Solve the Challenge

  1. Parse the Input: The input is a string representation of a list of lists. We used ast.literal_eval to safely evaluate the input string as a Python list.
  2. Find the Exit: We searched the grid to find the position of the exit ('E').
  3. Initialize BFS: We initialized a queue for BFS and a set to keep track of visited nodes.
  4. Explore Neighbors: We explored all possible moves (up, down, left, right) and added valid moves to the queue.
  5. Check for Exit: If the current position is the exit, we returned the distance.

Code

Here is the final code that worked:

python

from collections import deque
import ast

def parse_grid(input_text):
# Use ast.literal_eval to safely evaluate the string as a Python list
grid = ast.literal_eval(input_text)
return grid

def find_shortest_path(grid):
rows = len(grid)
cols = len(grid[0])
start = (0, 0)
end = None

# Find the position of the exit 'E'
for i in range(rows):
for j in range(cols):
if grid[i][j] == 'E':
end = (i, j)
break
if end:
break

if not end:
return -1  # Exit not found

# Directions for moving up, down, left, right
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# BFS initialization
queue = deque([(start[0], start[1], 0)])  # (row, col, distance)
visited = set()
visited.add(start)

while queue:
row, col, dist = queue.popleft()

# Check if we have reached the exit
if (row, col) == end:
return dist

# Explore neighbors
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] != 1 and (new_row, new_col) not in visited:
visited.add((new_row, new_col))
queue.append((new_row, new_col, dist + 1))

return -1  # If no path is found

# Get the input from the webapp
input_text = input()
grid = parse_grid(input_text)
print(find_shortest_path(grid))

Output

For the input:

[[0, 1, 1, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 1, 'E']]

The output is:

9
--
HTB{CL0CKW0RK_GU4RD14N_OF_SKYW4TCH_a1aca0773697487a2eb01b451842d1a4}

This indicates that the shortest path to the exit is 9 steps long, and the flag is HTB{CL0CKW0RK_GU4RD14N_OF_SKYW4TCH_a1aca0773697487a2eb01b451842d1a4}.