Full of Stars - HackTheBox Challenge Writeup

Challenge Information

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?

The challenge ships a Jupyter notebook with two NumPy arrays: core.npy (256 labeled “seed” points — one per byte value 0–255) and data.npy (131,527 unlabeled 3-D points). Every unlabeled point secretly belongs to one of the 256 classes; recovering the full labeling and reading the labels off as raw bytes reconstructs the flag image.

Solution

The description frames this as “clustering 256 classes from one sample each,” which is a trap — classic distance-based clustering (nearest-centroid, GMM/EM) tops out at 22/25 correct header bytes because the underlying structure isn’t blobs, it’s geometry.

1. Discover the data lies on exact planes, not clusters

Running local PCA over each point’s 30 nearest neighbors showed the third eigenvalue collapsing to ~1e-8 — i.e., every local neighborhood is flat. That’s the signal that this isn’t a density-clustering problem at all; it’s a plane-fitting problem in disguise.

2. RANSAC a plane per class, then dedupe

For each of the 256 core (labeled) points, RANSAC-fit a plane through its 120 nearest neighbors (400 trials, inlier tolerance 1e-6). Many classes turned out to share the same plane, so the 256 raw planes were deduplicated using a sign-invariant embedding of the plane parameters, collapsing to 155 distinct planes (101 holding two classes each, 54 holding one).

3. Assign every point to its plane

With 155 canonical planes, every one of the 131,527 unlabeled points assigns unambiguously — min |n·x − o| came out to ~1e-13 for the correct plane, with a massive fit-quality gap to any wrong plane.

4. Recognize the two-spirals shape per plane

Projecting a single plane’s points into 2-D and whitening the covariance revealed the classic two-spirals toy dataset: two interleaved spiral arms, 180° apart, squashed through a random affine embedding into 3-D. Each plane holding two classes = one spiral per class, and separating the two arms is the actual final puzzle.

5. Separate the interleaved spiral arms with an MST cut

Naive radius/angle heuristics failed on the interleaved arms (nearest-core assignment misclassified arm membership; doubled-angle radial-shell tracking merged both cores onto the same arm on 26/155 planes). The robust fix:

• Build the dense minimum spanning tree (MST) of the whitened in-plane points.
• Walk the MST path between the plane’s two known core seeds.
• Cut the single longest edge on that path.

This splits the MST into exactly two components — one per spiral arm — with every point correctly assigned and nothing left stranded.

6. Reassemble and decode

Concatenating all point labels (in original array order) into bytes produced a clean JPEG: a 512×512 progressive RGB night seascape with the flag rendered across it.

Key Steps

Local PCA to detect flatness (the key insight):

import numpy as np
from sklearn.neighbors import NearestNeighbors

X = np.vstack((np.load('core.npy'), np.load('data.npy')))
nn = NearestNeighbors(n_neighbors=31).fit(X)
_, I = nn.kneighbors(X)

P = X[I]                                   # (N, 31, 3) local neighborhoods
Q = P - P.mean(1, keepdims=True)
C = np.einsum('nkd,nke->nde', Q, Q) / 31   # local covariance per point
w, v = np.linalg.eigh(C)
# w[:,0] (smallest eigenvalue) collapses to ~1e-8 -> points lie on exact planes

RANSAC plane fit per core class:

import numpy as np

def ransac_plane(pts, trials=400, tol=1e-6):
    best_inliers, best_n, best_o = 0, None, None
    for _ in range(trials):
        i, j, k = np.random.choice(len(pts), 3, replace=False)
        p0, p1, p2 = pts[i], pts[j], pts[k]
        n = np.cross(p1 - p0, p2 - p0)
        norm = np.linalg.norm(n)
        if norm < 1e-12:
            continue
        n /= norm
        o = n @ p0
        resid = np.abs(pts @ n - o)
        inliers = (resid < tol).sum()
        if inliers > best_inliers:
            best_inliers, best_n, best_o = inliers, n, o
    return best_n, best_o

Dedupe planes with a sign-invariant embedding:

import numpy as np

# canonicalize sign so n and -n / o and -o map to the same plane
s = np.sign(N[np.arange(len(N)), np.argmax(np.abs(N), axis=1)])
N = N * s[:, None]
O = O * s

# embed as [outer(n,n) upper-triangle, o*n] -> unique rows = unique planes
V = np.hstack((
    np.einsum('ni,nj->nij', N, N)[:, [0, 0, 0, 1, 1, 2], [0, 1, 2, 1, 2, 2]],
    (O[:, None] * N)
))
_, plane_ids = np.unique(np.round(V, 6), axis=0, return_inverse=True)
# 256 raw planes -> 155 distinct planes

Assign every point to its plane by residual:

d = np.abs(X @ N.T - O)     # (n_points, n_planes)
plane_of_point = d.argmin(1)

Whiten a plane’s 2-D projection to reveal the two-spirals shape:

U = X[mask] @ basis            # project plane points into its own 2D basis
C = np.cov(U.T)
w, v = np.linalg.eigh(C)
W = U @ (v / np.sqrt(w))       # whitening transform
# plotting W now shows two clean interleaved spiral arms

Split the two spiral arms via MST longest-edge cut:

from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.spatial.distance import pdist, squareform
import numpy as np

D = squareform(pdist(W))
mst = minimum_spanning_tree(D).toarray()
mst = np.maximum(mst, mst.T)                 # symmetrize

# find path between the two known core-seed nodes in the MST
path = mst_path(mst, core_idx_a, core_idx_b)  # BFS/DFS along tree edges
edge_weights = [mst[path[i], path[i+1]] for i in range(len(path) - 1)]
cut_at = np.argmax(edge_weights)              # longest edge on the path

# removing that edge splits the tree into the two spiral arms

Reassemble bytes into the flag image:

labels = np.zeros(len(X) - 256, dtype=np.uint8)
# ... populate labels[i] = class id for each data point via plane + arm assignment ...

flag_bytes = labels.tobytes()
with open('flag.jpg', 'wb') as f:
    f.write(flag_bytes)

Tools Used

• Python 3 / NumPy — array manipulation, plane math, byte reassembly
• scikit-learn (NearestNeighbors) — k-NN queries for local PCA and RANSAC neighborhoods
• SciPy (scipy.sparse.csgraph.minimum_spanning_tree, scipy.spatial.distance.pdist) — MST construction for spiral-arm separation
• Matplotlib — visual sanity checks of plane projections and whitened spiral shapes (proj.png, p0.png, planes6.png, f4.png)
• Pillow (PIL) — validating and cropping the recovered JPEG (flag.jpg, flagzoom.png)

Key Learnings

• When “clustering” a very high class-count, low-sample dataset stalls, check local geometry before tuning the clustering algorithm. A local-PCA eigenvalue check (30-NN covariance) immediately revealed the points lay on exact planes rather than fuzzy blobs — reframing the entire problem from statistical clustering to deterministic plane-fitting.
• RANSAC + a canonical/sign-invariant embedding is a clean way to detect and merge duplicate fitted primitives (here, 256 raw planes collapsing to 155 unique ones via a sign-normalized [nnᵀ, o·n] feature vector).
• Distance/centroid-based methods (nearest-core, GMM/EM) silently plateau on interleaved structures like two-spirals — they can’t be fixed by more iterations because the loss function itself is wrong for the geometry. Recognizing the classic two-spirals shape after whitening was the pivot point.
• Radius and angle heuristics are fragile for spiral separation (only worked on a handful of concentric-circle planes; doubled-angle tracking mis-merged cores on 26/155 planes) — but an MST longest-edge cut between two known seed points is a robust, parameter-light way to split two interleaved 1-D manifolds, because the only edge “bridging” two spiral arms in a near-uniform-density MST is disproportionately long.
• Keep two known reference points (the core seeds) per component whenever a manifold-separation problem allows it — anchoring the MST path to the two labeled cores turned an ambiguous split into a well-defined one.