G-Bee-S - miscellaneous - n0pstopia

WriteUp: ap10

I have use this script to get the flag.

import math
from itertools import combinations

def dist(a, b):
    return math.hypot(a[0] - b[0], a[1] - b[1])

with open("flowers.txt") as f:
    flowers = [tuple(map(int, line.strip().split())) for line in f]

points = [(0, 0)] + flowers

def total_distance(path):
    return sum(dist(points[path[i]], points[path[i+1]]) for i in range(len(path)-1))

def greedy_path():
    unvisited = set(range(1, len(points)))
    path = [0]
    current = 0
    while unvisited:
        next_node = min(unvisited, key=lambda i: dist(points[current], points[i]))
        path.append(next_node)
        unvisited.remove(next_node)
        current = next_node
    path.append(0)
    return path

def two_opt(path):
    improved = True
    while improved:
        improved = False
        for i in range(1, len(path) - 2):
            for j in range(i+1, len(path) - 1):
                if j - i == 1:
                    continue
                new_path = path[:i] + path[i:j][::-1] + path[j:]
                if total_distance(new_path) < total_distance(path):
                    path = new_path
                    improved = True
        if not improved:
            break
    return path

initial_path = greedy_path()
optimized_path = two_opt(initial_path)
print("Path:", " ".join(map(str, optimized_path)))
print("Total distance:", total_distance(optimized_path))

Output:

Path: 0 45 38 26 3 14 29 34 15 2 11 8 17 49 5 25 27 42 31 21 12 4 19 41 1 39 18 16 47 50 33 40 7 28 37 43 36 44 6 9 32 10 24 35 20 13 48 22 46 23 30 0
Total distance: 1370.9177066737818

So just do that to get the flag:

$ nc 0.cloud.chals.io 13055
Enter the path Valentine should follow:
>>> 0 45 38 26 3 14 29 34 15 2 11 8 17 49 5 25 27 42 31 21 12 4 19 41 1 39 18 16 47 50 33 40 7 28 37 43 36 44 6 9 32 10 24 35 20 13 48 22 46 23 30 0
The length of your path is 1370.9177066737818.
Well done! Thanks to you, Valentine can visit all the waterlillies <3
Here is your flag: N0PS{w4t3rl1ll13s_f0r_v4l3nt1n3}