Progetto Finale di API

This project is an implementation in C of the final exam for Algorithms and Data Structures (2024–2025).
The main challenge is to design and implement data structures that guarantee the best performance in both space and time.

Performance & Grading

The project is evaluated based on execution time and memory usage of the program, as measured by the official testbench verifier (with undisclosed test cases).
Grades are assigned according to the following thresholds:

Grade	Time Limit (s)	Memory Limit (MiB)
18	30,000	194
21	25,250	152
24	20,500	110
27	12,000	68.0
30	11,000	26.0
Lode	10,000	26.0

My results

Results below are based on the official verifier’s evaluation.

• Execution time: ~7 s
• Memory usage: ~13 MiB
• Grade: 30L

Features

The system models a transportation network on a hexagonal-tiled map and efficiently computes optimal travel routes, while supporting dynamic updates to land costs and air routes.

• Hexagonal grid representation (rows × columns).
• Dynamic land costs: modify exit costs of hexagonal cells within a configurable radius.
• Air routes management: toggle directional air routes (maximum of 5 per cell).
• Optimal pathfinding: compute the minimum travel cost between two cells using both land and air routes.
• Efficient data structures: optimized for memory usage and execution time.

Commands

The program reads commands from standard input and prints responses to standard output.
Each output is terminated by a newline (\n).

• init <rows> <columns>
  Initializes the map. All exit costs set to 1, no air routes. Returns OK if successful, otherwise KO.

• change_cost <x> <y> <v> <radius>
  Updates exit costs of hexagons within the given radius of (x,y) using the provided formula.
  Returns OK if successful, otherwise KO.

• toggle_air_route <xO> <yO> <xD> <yD>
  Adds or removes a directed air route.
  Returns OK if successful, otherwise KO.

• travel_cost <xO> <yO> <xD> <yD>
  Computes the minimum travel cost from source (xO,yO) to destination (xD,yD).
  Returns the cost or -1 if unreachable/invalid.

Implementation Details

Grid & Coordinates

typedef struct {
  Cell *cells; // Flat array of all cells
  int rows;
  int columns;
} Map;

• The Map holds the entire hexagonal grid as a flat array of Cell.
• A cell can be accessed in O(1) using id = y * columns + x.
• This layout avoids the overhead of nested arrays or pointers to rows, improving memory locality and simplifying indexing.
• rows and columns store the dimensions of the grid; they are used in bounds checking and in the toID / fromID helpers.
• Neighbors (land): 6-neighborhood computed via two lookup tables X_HEX[2][6] and Y_HEX[2][6] using y & 1 to decide even/odd row offsets.

Cell & Air-Route Model

typedef struct {
  int cost;        // land exit cost in [0,100]; 0 -> cannot exit
  int n_routes;    // number of outgoing air routes from this cell
  int *routes;     // array of destination IDs (size up to MAX_ROUTES=5)
} Cell;

• Air routes are stored as destination IDs only, as the cost is the same as the cell. Memory is allocated on the first insertion and freed when n_routes returns to 0.
• Toggle logic (toggle_air_route):
  • If the route exists -> remove it.
  • Else if n_routes < MAX_ROUTES -> add it (append destination ID).
  • Else -> reject with KO.

Cost Updates (change_cost)

typedef struct {
  int id;
  int dist; // distance from the center cell
} BFSNode;

typedef struct {
  BFSNode *data; // Array of BFSNodes
  int head;
  int tail;
  int capacity;
} BFSQueue;

• Uses a ring-BFS centered at (x,y) with capacity 1 + 6 * r * (r-1) / 2 to visit cells with hex distance < r.
• Each visited cell has its exit cost adjusted using the prescribed formula, clamped to the valid range.

Shortest Path (travel_cost)

• Algorithm: Dijkstra with a binary Min-Heap over integer costs.
• Data structures:
  • dist[] (pre-allocated once, size up to MAX_DIST) stores the best-known cost for each cell.
  • A min-heap maintains the next cell with the smallest tentative distance.
• Relaxation:
  • Land neighbors (up to 6):
    For each adjacent hex cell v:
    candidate = dist[cell] + land_cost(cell)
    If candidate < dist[v], update dist[v] and adjust the heap.
  • Air routes (up to 5):
    Each air route has the same cost as the land exit of the source:
    candidate = dist[cell] + land_cost(cell)
• Early exit: the algorithm stops as soon as the destination is extracted from the heap.
• Returns -1 if the destination is unreachable.

Priority Queue (Min-Heap)

typedef struct {
  int id;
  int cost;
} HeapNode;

typedef struct {
  int size;     // current number of elements in the heap
  int capacity; // maximum number of elements in the heap
  HeapNode *array;
  int *pos; // maps node id -> position in heap for O(log n) decrease_key
} MinHeap;

• insert_heap, decrease_key, extract_min, swap_heap and min_heapify are all inlined/tight to minimize branch mispredicts and memory traffic.

Cache

typedef struct {
  int origin_id, destination_id;
  int cost;
} CacheEntry;

typedef struct {
  CacheEntry *entries;
  int size;     // current number of entries in the cache
  int capacity; // maximum number of entries in the cache
} Cache;

• Lookup: binary search (find_cache) on a sorted array by (origin_id, destination_id).
• Insert: append and re-sort the small array using QuickSort (Hoare partition) or MergeSort:
• Growth: capacity grows multiplicatively (capacity *= 3) to keep amortized O(1) appends.
• Invalidation: on toggle_air_route, change_cosst and init the cache is cleared (cache.size = 0).

Note: two versions of the cache were implemented, one using MergeSort and one using QuickSort. Both have essentially equivalent performance in time and space. The final submission uses the QuickSort version.

Time and Space

• init
  Time: field assignments O(1) + malloc of N cells O(N) + loop initialization O(N) + cache setup O(1) = O(N)
  Space: map stores N cells, each a constant-size struct O(N) + cache has fixed size O(1)) = O(N)

• change_cost
  Time: BFS exploring all cells within radius r O(min(N, r²))
  Space: visited array O(N) + BFS queue O(min(N, r²)) = O(N)
  visited array is sized to the whole map O(N), but in practice only ~r² cells are touched.
  This design was chosen for simplicity and stable performance, since the memory usage is acceptable within project limits.

• toggle_air_route
  Time: cell lookup O(1) + remove_route is O(1), scans at most MAX_ROUTES entries since MAX_ROUTES=5 + add_route just appends and, if needed, performs a one-time malloc = O(1)
  Space: O(1) per operation (for a cell, the first insertion allocates a fixed buffer of MAX_ROUTES integers. For the whole map, the worst case is O(N) if all cells reach 5 routes.)

• travel_cost
  Time: Dijkstra with a binary heap -> worst-case O((N + E) log N). We have to consider there is a bounded degree: up to 6 land + ≤5 air per cell -> E = O(N).
  Also, there is an early-exit when the destination is reached -> in practice O(k log k), k = number of nodes actually explored.
  Space: dist[N] + heap array N + heap positions N; all linear-size arrays = O(N)

• cache: find_cache
  Time: binary search on the sorted array by (origin_id, destination_id) O(log K)
  Space: O(1)

• MergeSort: add_cache
  Time: amortized O(1) for append + O(K log K) to keep the array sorted = O(K log K)
  Space: O(K) for the array + O(K) extra during mergesort = O(K)

• QuickSort: add_cache
  Time: amortized O(1) for append + QuickSort over K entries -> expected O(K log K), worst-case O(K²)
  Space: in-place QuickSort O(log K)