HackTheBox: Full of Stars Challenge

Category: AI-ML | HARD

https://app.hackthebox.com/challenges/756 https://labs.hackthebox.com/achievement/challenge/1948178/756

Description

While density scanning the galaxy we've found something extraordinary! It seems that the stars in our local group are communicating a message: The stars, spread over 256 clusters, were seen to blink in a specific order. However, in our charts we have only one star per cluster to uniquely identify the cluster, which leaves us with >99% stars uncategorized. Could you assist our researchers by identifying what stars belong to which cluster and deciphering the message left for us by mysterious extraterrestrial intelligence?

Our goal is to classify thousands of unknown stars into 256 clusters based on spatial coordinates, then reconstruct an extraterrestrial message hidden in the cluster patterns.

Each star is represented by 3D spatial coordinates (X, Y, Z). The key insight: cluster labels correspond to byte values that can be reconstructed into a file.

Proof-of-Concept:

#!/usr/bin/python3
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import numpy as np
from scipy.spatial import KDTree
import warnings
warnings.filterwarnings("ignore")

print("Loading celestial data...")
data = np.loadtxt("data.npy.gz")
core_data = np.loadtxt("known_samples.npy.gz")
all_data = np.vstack((core_data, data))

print("Normalizing coordinates...")
x_min, x_max = np.min(all_data[:, 0]), np.max(all_data[:, 0])
y_min, y_max = np.min(all_data[:, 1]), np.max(all_data[:, 1])
z_min, z_max = np.min(all_data[:, 2]), np.max(all_data[:, 2])

all_data[:, 0] = (all_data[:, 0] - x_min) / (x_max - x_min)
all_data[:, 1] = (all_data[:, 1] - y_min) / (y_max - y_min)
all_data[:, 2] = (all_data[:, 2] - z_min) / (z_max - z_min)

class_count = len(core_data)
out_labels = np.full((all_data.shape[0],), -1)
kdtree = KDTree(all_data)

def expand_cluster(start_indices, cluster_label, out_labels, kdtree, max_distance):
    current_indices = np.array(start_indices)
    while True:
        nearby_indices = kdtree.query_ball_point(all_data[current_indices], max_distance, p=1, eps=0, workers=-1)
        nearby_indices = set(np.hstack(nearby_indices))
        unprocessed_indices = [idx for idx in nearby_indices if out_labels[idx] == -1]
        
        if not unprocessed_indices:
            break
            
        for idx in unprocessed_indices:
            out_labels[idx] = cluster_label
            
        current_indices = np.array(unprocessed_indices)

print("Running clustering algorithm...")
out_labels = np.full((all_data.shape[0],), -1)

for iteration in range(10):
    print(f"Iteration {iteration + 1}/10")
    for idx in range(class_count):
        out_labels[idx] = idx
        matching_indices = np.where(out_labels == idx)[0]
        expand_cluster(matching_indices, idx, out_labels, kdtree, 0.002 * iteration)

assert(np.all(np.logical_and(0 <= out_labels, out_labels < 256)))
print("Clustering completed")

print("Generating analysis plots...")
fig = plt.figure(figsize=(16, 12))

ax1 = fig.add_subplot(231, projection='3d')
colors = plt.cm.viridis(np.linspace(0, 1, 256))
for cluster_id in range(256):
    cluster_mask = (out_labels == cluster_id)
    if np.any(cluster_mask):
        cluster_points = all_data[cluster_mask]
        ax1.scatter(cluster_points[:, 0], cluster_points[:, 1], cluster_points[:, 2], 
                   s=1, alpha=0.7, color=colors[cluster_id])
ax1.set_title('3D Cluster Distribution')
ax1.set_xlabel('X')
ax1.set_ylabel('Y')
ax1.set_zlabel('Z')

ax2 = fig.add_subplot(232)
cluster_sizes = [np.sum(out_labels == i) for i in range(256)]
ax2.bar(range(256), cluster_sizes, color='steelblue', alpha=0.8)
ax2.set_title('Cluster Size Distribution')
ax2.set_xlabel('Cluster ID')
ax2.set_ylabel('Number of Stars')
ax2.grid(True, alpha=0.3)

ax3 = fig.add_subplot(233)
compactness = []
for i in range(256):
    cluster_points = all_data[out_labels == i]
    if len(cluster_points) > 1:
        centroid = np.mean(cluster_points, axis=0)
        avg_distance = np.mean(np.linalg.norm(cluster_points - centroid, axis=1))
        compactness.append(avg_distance)
    else:
        compactness.append(0)
ax3.scatter(range(256), compactness, alpha=0.6, color='crimson')
ax3.set_title('Cluster Compactness')
ax3.set_xlabel('Cluster ID')
ax3.set_ylabel('Avg Distance to Centroid')
ax3.grid(True, alpha=0.3)

ax4 = fig.add_subplot(234)
scatter = ax4.scatter(all_data[:, 0], all_data[:, 1], c=out_labels, 
                     cmap='viridis', s=0.5, alpha=0.6)
ax4.set_title('XY Plane Projection')
ax4.set_xlabel('X Coordinate')
ax4.set_ylabel('Y Coordinate')

ax5 = fig.add_subplot(235)
ax5.scatter(cluster_sizes, compactness, alpha=0.6, color='purple')
ax5.set_title('Size vs Compactness')
ax5.set_xlabel('Cluster Size')
ax5.set_ylabel('Compactness')
ax5.grid(True, alpha=0.3)

ax6 = fig.add_subplot(236)
sorted_sizes = np.sort(cluster_sizes)[::-1]
cumulative = np.cumsum(sorted_sizes) / np.sum(sorted_sizes)
ax6.plot(range(256), cumulative, linewidth=2, color='green')
ax6.set_title('Cumulative Size Distribution')
ax6.set_xlabel('Cluster Rank')
ax6.set_ylabel('Cumulative Proportion')
ax6.grid(True, alpha=0.3)
ax6.axhline(y=0.5, color='red', linestyle='--', alpha=0.5, label='50%')
ax6.axhline(y=0.8, color='orange', linestyle='--', alpha=0.5, label='80%')
ax6.legend()

plt.tight_layout()
plt.savefig('cosmic_analysis.png', dpi=300, bbox_inches='tight')
print("Analysis plot saved as 'cosmic_analysis.png'")

file_data = bytearray(out_labels[class_count:].shape[0])
for ix, val in enumerate(out_labels[class_count:]):
    file_data[ix] = val

with open("flag.jpg", "wb") as outfile:
    outfile.write(bytes(file_data))

print("Message decoded as 'flag.jpg'")

cluster_sizes = [np.sum(out_labels == i) for i in range(256)]
print(f"\nResults:")
print(f"Total stars: {len(out_labels):,}")
print(f"Clusters: 256")
print(f"Avg cluster size: {np.mean(cluster_sizes):.1f} ± {np.std(cluster_sizes):.1f}")
print(f"Size range: {min(cluster_sizes):,} - {max(cluster_sizes):,}")
print(f"Median size: {np.median(cluster_sizes):.1f}")

The final output flag.jpg contains the decrypted message from the extraterrestrial intelligence. The successful clustering demonstrates how spatial data analysis can reveal hidden patterns and reconstruct meaningful information from raw coordinates.

Key Learnings:

1. Spatial Data Analysis: Techniques for processing and clustering 3D coordinate data

2. Algorithm Selection: Choosing appropriate clustering methods for specific data characteristics

3. File Reconstruction: Understanding how byte sequences can represent structured data

4. Python Data Science: Practical experience with NumPy, SciPy, and Matplotlib