From 5 Seconds to 1.2 Milliseconds: Rewriting a Combinatorial Optimizer with GitHub Copilot

Croatian open-source grocery price tracker Cijene reduced its shopping cart optimization time from 5 seconds to 1.2 milliseconds by rewriting the backend with GitHub Copilot. The project, which won first place at a national hackathon, now serves thousands of Croatian families by optimizing entire shopping lists across 14 major grocery chains based on location and preferences. The developer refactored the Python API from a naive exact solver into an asynchronous architecture with bitmask validation and pre-indexed price lookups to handle concurrent production traffic.

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 : php 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.