This is a submission for the GitHub Finish-Up-A-Thon Challenge
Cijene ("Prices") is Croatia's premier open-source grocery price tracker and shopping cart optimizer, designed to help families fight double-digit inflation. It began as a hackathon prototype that won first place at a national software development competition in Croatia, built under high-pressure, 24-hour constraints. Since then, it has evolved into a production-ready application that serves thousands of Croatian families, allowing them to track, compare, and optimize their grocery expenses.
The core innovation of Cijene is its Košarica (Smart Shopping Cart Optimizer). Instead of simply comparing prices item-by-item, Cijene optimizes a user's entire shopping list across all major Croatian grocery chains (including Konzum, Lidl, Spar, Kaufland, Plodine, Tommy, Studenac, Eurospin, Metro, Žabac, Vrutak, Ribola, and NTL) based on their geographical location, search radius, and shopping preferences.
Users can choose between three optimization modes:
By refactoring the backend API and redesigning the core cart optimizer from the ground up, we turned a struggling prototype into a highly scalable, enterprise-grade system capable of handling concurrent production traffic.
Below you will find the links, interactive video walkthrough, and screenshots demonstrating Cijene's live optimization engine, user interface, and real-time savings calculations.
In the original competition prototype, the Python API service struggled under even minor loads. The shopping cart calculation function was a massive performance bottleneck. The old algorithm utilized a naive exact solver: to optimize a cart of NN N items across SS S nearby stores, it generated and evaluated every single combination of stores up to size KK K (where K≤5K \le 5 K≤5 ).
In a dense urban area like Zagreb, with 28+ stores within a 15 km radius and a store limit of 5, the number of combinations exploded to:
For every single combination, the prototype:
product_prices.get(store_id)
) to check availability and find the minimum price.signature = tuple((product_id, assignment[product_id]) for product_id in sorted(assignment))
to eliminate duplicate solutions.This approach resulted in massive memory allocation overhead, excessive garbage collection cycles, and CPU starvation. A simple 10-item cart in a dense area took 2 to 5 seconds to execute. Under concurrent user traffic, this synchronous blocking behavior quickly led to request timeouts and server crashes.
To transition the prototype to a production-grade system, we refactored the backend into a highly optimized, asynchronous architecture. The optimization pipeline was completely rewritten to incorporate advanced algorithms and data structures:
The optimizer now begins with a pre-analysis pass that scans the cart items and identifies "mandatory stores"—stores that are the only option within the user's radius for at least one item. If the number of mandatory stores exceeds the user-configured store limit ( M>KM > K M>K ), the algorithm immediately exits. Otherwise, those MM M stores are fixed, and we only generate combinations of size K−MK - M K−M from the remaining non-mandatory stores.
For instance, if M=2M = 2 M=2 and K=5K = 5 K=5 , we only need to choose 3 additional stores from the remaining 26 non-mandatory options:
Rather than verifying cart feasibility in a nested loop using dictionary lookups, we mapped each product in the cart to a specific bit index in an integer (e.g., product
ii i
corresponds to 1 << i
).
if subset_mask != target_mask: continue
. If a subset is infeasible, the check fails in a single CPU cycle, completely skipping expensive price calculations.We replaced nested string-hashed dictionary lookups in the hot loop with contiguous memory structures. Store prices are now pre-indexed into a flat tuple of floats where the position corresponds to the product's index in the cart. Finding the best price for product ii i in a store subset is now a direct array lookup:
price = store_prices_indexed[store_id][i]
This is an
O(1)O(1) O(1)
operation that bypasses Python's dictionary hashing overhead entirely. Furthermore, store distances are pre-cached in a flat dictionary (store_distances
) to prevent redundant distance recalculations.
In _prune_dominated_stores
, stores are sorted by distance first. For any two stores
AA A
and
BB B
, if store
BB B
is further away than store
AA A
and does not offer a better price for any product,
BB B
is pruned as "dominated." Because the stores are sorted by distance, the algorithm breaks out of the loop early the moment distance_b > distance_a
, saving thousands of redundant iterations.
When the number of stores after pruning still exceeds the enumeration limit (enum_store_limit = 12
), exact enumeration is bypassed in favor of a heuristic solver (_heuristic_optimize
). The heuristic:
_improve_candidate_by_swaps
), iteratively swapping active stores with high-ranking pool stores to minimize the multi-objective score (cost, distance, store count).
This heuristic solver guarantees a near-optimal recommendation in less than To protect the backend from duplicate queries, we implemented CartOptimizeCache
using Redis and an in-memory TTL fallback. To ensure high cache hit rates for geographic queries, we implemented location bucketing. Instead of caching on raw GPS coordinates, we round latitude and longitude to a configurable grid (~200 meters):
def _bucket_coordinate(latitude: float, longitude: float) -> tuple[float, float]:
lat_step = bucket_size_m / 111_320.0
lon_scale = max(0.01, cos(radians(latitude)))
lon_step = bucket_size_m / (111_320.0 * lon_scale)
return (round(round(latitude / lat_step) * lat_step, 6), round(round(longitude / lon_step) * lon_step, 6))
If multiple users in the same neighborhood search for the same cart items, they hit the cache even if their exact coordinates differ by a few meters.
To align recommendations with actual user behavior, we added a feedback endpoint (POST /v1/cart/optimize/feedback
) and run tracking database tables. If the user acceptance rate for a particular optimization mode falls below a threshold (e.g., 25% over a 30-day window), the system dynamically adjusts the weights (cost, distance, store count) in ±0.05\pm 0.05 ±0.05 increments, automatically fine-tuning the algorithm to user preferences over time.
GitHub Copilot acted as an expert pair programmer throughout the refactoring process. It didn't just write boilerplate code; it helped redesign our core data structures and mathematical models.
Here is how Copilot accelerated our development and achieved the 1000x speedup:
While explaining the bottleneck of the subset feasibility check to Copilot, it suggested mapping the cart items to a bitmask and utilizing bitwise operations for set cover evaluation. It generated the code to transform our complex product lists into bitwise integers:
product_to_bit = {item.product_id: (1 << idx) for idx, item in enumerate(cart_items)}
target_mask = (1 << num_products) - 1
This suggestion eliminated the slow set-union logic and replaced it with ultra-fast bitwise math, reducing the feasibility checking time to near-zero.
When writing the heuristic solver for large store sets, Copilot co-authored the 2-opt local search swap loop (_improve_candidate_by_swaps
). It perfectly implemented the logic to remove a store from the active subset, find the best replacement candidate from the ranked pool, evaluate if the swap improved the multi-objective utility score, and apply the swap. This ensured that even when falling back to the heuristic solver, our recommendation quality remained exceptionally high.
To verify the performance improvements, Copilot helped write cart_optimizer_benchmark.py
. The tool generates mock shopping carts, simulates store coordinates, assigns randomized prices, and benchmarks the latency and quality gap between the exact and heuristic solver across different optimization modes.
Running this benchmark confirmed:
Copilot analyzed our database interaction layer (psql.py
) and identified a sub-optimal SQL join. It suggested refactoring the product price query to target the primary key index prices.store_id
directly instead of referencing the outer joined stores.id
. This simple suggestion cut database query latency in half, allowing the API to fetch price matrices for large carts in under 15 ms.
With GitHub Copilot, we successfully converted a slow hackathon prototype into a highly optimized, production-ready backend. Cijene now runs on a lean, asynchronous stack that provides real-time grocery savings recommendations to thousands of users, proving that with the right tools, even complex combinatorial problems can be optimized to run in milliseconds.