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
- 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. - Find the Exit: We searched the grid to find the position of the exit ('E').
- Initialize BFS: We initialized a queue for BFS and a set to keep track of visited nodes.
- Explore Neighbors: We explored all possible moves (up, down, left, right) and added valid moves to the queue.
- 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}
.