Solution for Codyssi 2025 - Patron Islands

Link to the puzzle text

Part 1

In this puzzle, we have a list of 2-D coordinates of islands. To get the distance from one island to another, we are using the Manhattan distance:

def manhattan_distance(target, origin):
    return abs(target[0] - origin[0]) + abs(target[1] - origin[1])

Starting at point (0,0), we should find both the islands closest and furthest away from us, calculate their distance and return the difference.

We wrote a function calculating the distance to every islands from a single origin point. This origin point is currently (0,0), but may be changed later on.

def calc_distances(islands, origin):
    return [manhattan_distance(target, origin) for target in islands if target != origin] 

 We only needed to ignore the distance from the start island to itself. Finally we take the max and min of the distances list and calculate the difference:

max(distances) - min(distances)

Part 2

In part 2, we start at the closest island to (0,0) instead. We should now find the distance to the closest island from this island. Whenever two islands have the same Manhattan distance, we should break the tie by using the values of the x and y coordinates.

We wrote a function for finding the closest island starting at some coordinate point. This function first calculates the distances to all other islands and chooses just the ids with the lowest distances. For breaking the tie, we first sort the islands.

Starting at point (0,0), we find the id of the closest island, calculate the distances starting from this island now and take the lowest of these new distances.

def next_island_id(islands, origin):
    distances = calc_distances(islands, origin)
    closest_islands = [i for i in range(len(islands)) if distances[i] == min(distances)]
    closest_islands.sort()
    closest_island = closest_islands[0]

    return closest_island

Part 3

In part 3, we should find a path covering all islands using the following greedy algorithm: Start at point (0,0). At every step we choose the closest, not yet visited island and move there. This is repeated until we moved to every island. We should find the length of this path.

We reuse the previous functions to implement this path finding. Just like before, we find the closest island from the current island, add the path to our total length so far and update the current position. To make sure we are never visiting an island twice, we are removing the just visited island from the list of all islands.

while len(islands) > 0:
    closest = next_island_id(islands, current)
    total_length += manhattan_distance(islands[closest], current)
    current = islands.pop(closest)

Link to my solutions