Grade: 30 L (30/30 cum laude) – Data Structures & Algorithms, A.Y. 2023-2024
This repository contains the C implementation of a discrete-time simulator for an industrial bakery’s order-fulfilment workflow. The project was developed for the final examination of the “Algoritmi e Strutture Dati” course and received the maximum mark cum laude.
An industrial bakery wants to digitise the flow of recipes, ingredient stocks, customer orders, warehouse replenishments and courier pick-ups. The simulator processes a stream of textual commands (one per simulation tick) read from stdin and prints acknowledgements or logistics events to stdout.
Key rules (see specifica_completa_progetto.pdf for the full formal specification):
| Entity | Summary |
|---|---|
| Ingredients | Identified by name (ASCII letters, digits & \_). Stored in lots, each with a quantity (g) and a best-before timestamp. Always consumed from the lot with the earliest expiry. |
| Recipes | Mapping recipe → (ingredient, grams). Duplicates are ignored. |
| Orders | An order requests n copies of a recipe. If all ingredients are available, production is instantaneous; otherwise the order is enqueued. Queued orders are reconsidered after every replenishment. |
| Courier | Arrives every P ticks with a van that can carry C grams. Ready orders are loaded FIFO until capacity runs out, then physically sorted by descending weight (ties → FIFO). |
- First line: two positive integers
P C– courier periodP(ticks) and capacityC(grams). - Subsequent lines: one command per tick.
aggiungi_ricetta <recipe_name> <ing₁> <qty₁> … <ingₖ> <qtyₖ>
rimuovi_ricetta <recipe_name>
rifornimento <ing₁> <qty₁> <expiry₁> … <ingₖ> <qtyₖ> <expiryₖ>
ordine <recipe_name> <count>
All integers fit in 32 bits.
See test_cases_pubblici/ for concrete examples.
| Token | Meaning (high level) |
|---|---|
aggiunta / ignorato |
Recipe added / duplicate ignored |
rimossa / non presente |
Recipe removed / not found |
rifornito |
Warehouse successfully replenished |
accettato / rifiutato |
Order queued/produced or rejected |
ordini in sospeso |
A removal attempted while orders pending |
camioncino vuoto |
Courier arrived but nothing was ready |
t peso recipe count |
Courier shipment line: tick t, order weight, recipe, quantity |
The project is pure C (gnu11) with no external dependencies.
# 1. Compile
gcc progetto.c -o bakery_simulator -Wall -Werror -std=gnu11 -O2 -lm
# or simply
make # uses the provided CFLAGS/LDFLAGS./bakery_simulator < test_cases_pubblici/example.txtRedirect stdout if you wish to compare with the expected output:
./bakery_simulator < test_cases_pubblici/example.txt > my.out \
&& diff -u my.out test_cases_pubblici/example.output.txt| Component | Technique |
|---|---|
| Warehouse lots | Red-Black tree per ingredient → O(log N) expiry retrieval |
| Recipe catalog | Hash table with separate chaining |
| Pending / ready orders | Doubly-linked FIFO queues |
| Courier loading | On-the-fly weight computation & stable sort by weight (O(M log M)) |
All structures are implemented from scratch without STL/GLib, fulfilling course constraints.
├── progetto.c # 2000+ LOC core simulator
├── Makefile # Compiler flags helper
├── specifica_completa_progetto.pdf
├── test_cases_pubblici/ # 12 public I/O test pairs
└── LICENSE # MIT
This project prioritizes strict adherence to the exam specification, algorithmic correctness, and asymptotic guarantees over code elegance.
The codebase reflects typical constraints of a timed academic setting: manual memory management, limited refactoring, and direct implementations of required data structures.
Released under the MIT License. See LICENSE for details.