1"""Chapter 44 (case study: ride-hailing with surge pricing, Uber / Rapido) deep-dive code.
21. Location updates: write volume, and keeping only the latest position in a cell index.
32. Matching: nearest by ETA (not straight-line distance), offers with timeouts, no double assignment.
43. Surge pricing: demand/supply per cell, smoothed and capped.
54. Trip state machine with idempotent transitions and fare.
6Run: python3 ch44_ride_hailing.py"""
7import math
8import random
9from collections import defaultdict
10
11
12# ---- 1. location index -------------------------------------------------------------
13
14CELL_DEG = 0.01 # ~1.1 km cells (a stand-in for geohash/H3)
15
16
17def cell(lat, lng):
18 return (int(lat // CELL_DEG), int(lng // CELL_DEG))
19
20
21class DriverIndex:
22 def __init__(self, stale_s=30):
23 self.pos, self.cells, self.seen = {}, defaultdict(set), {}
24 self.available = {}
25 self.stale_s = stale_s
26
27 def update(self, driver, lat, lng, now, available=True):
28 old = self.pos.get(driver)
29 if old and cell(*old) != cell(lat, lng):
30 self.cells[cell(*old)].discard(driver)
31 self.pos[driver] = (lat, lng)
32 self.cells[cell(lat, lng)].add(driver)
33 self.seen[driver] = now
34 self.available[driver] = available
35
36 def nearby(self, lat, lng, now, rings=1):
37 cx, cy = cell(lat, lng)
38 out = []
39 for dx in range(-rings, rings + 1):
40 for dy in range(-rings, rings + 1):
41 for d in self.cells.get((cx + dx, cy + dy), ()):
42 if self.available.get(d) and now - self.seen[d] <= self.stale_s:
43 out.append(d)
44 return out
45
46
47def km(a, b):
48 return math.hypot((a[0] - b[0]) * 111.2, (a[1] - b[1]) * 111.2 * math.cos(math.radians(a[0])))
49
50
51# ---- 2. matching -------------------------------------------------------------------
52
53def eta_minutes(driver_pos, pickup, road_factor):
54 """Road distance is longer than straight-line; average city speed 20 km/h (assumed)."""
55 return km(driver_pos, pickup) * road_factor / 20 * 60
56
57
58class Dispatcher:
59 def __init__(self):
60 self.assigned = {} # driver -> trip
61
62 def try_assign(self, driver, trip):
63 """Conditional: only if the driver isn't already on a trip (one row update in real life)."""
64 if driver in self.assigned:
65 return False
66 self.assigned[driver] = trip
67 return True
68
69
70def dispatch(candidates, accept, dispatcher, trip, max_offers=3):
71 """Offer to the best candidates one at a time; each offer times out if not accepted."""
72 for d in candidates[:max_offers]:
73 if accept(d) and dispatcher.try_assign(d, trip):
74 return d
75 return None
76
77
78# ---- 3. surge ----------------------------------------------------------------------
79
80def surge(requests, drivers, prev=1.0, cap=2.5, smooth=0.5):
81 ratio = requests / max(drivers, 1)
82 target = 1.0 if ratio <= 1 else min(cap, 1 + 0.5 * (ratio - 1))
83 m = prev + smooth * (target - prev) # don't jump around every minute
84 return round(max(1.0, min(cap, m)), 2)
85
86
87# ---- 4. trip state machine ---------------------------------------------------------
88
89NEXT = {"requested": {"matched", "cancelled"}, "matched": {"arriving", "cancelled"},
90 "arriving": {"in_trip", "cancelled"}, "in_trip": {"completed"},
91 "completed": set(), "cancelled": set()}
92
93
94class Trip:
95 def __init__(self, tid):
96 self.id, self.state, self.applied = tid, "requested", set()
97
98 def event(self, event_id, new_state):
99 if event_id in self.applied: # retried from a flaky phone
100 return "duplicate"
101 if new_state not in NEXT[self.state]:
102 return "rejected"
103 self.applied.add(event_id)
104 self.state = new_state
105 return "ok"
106
107
108def fare(km_, minutes, multiplier, base=40, per_km=12, per_min=1.5, minimum=80):
109 return round(max(minimum, (base + per_km * km_ + per_min * minutes) * multiplier))
110
111
112# ---- checks ------------------------------------------------------------------------
113
114def run_checks():
115 # Step 2 arithmetic: 1M drivers online, update every 4 s
116 assert 1_000_000 / 4 == 250_000
117
118 # 1. index: 2,000 drivers around a city centre
119 rnd = random.Random(44)
120 centre = (12.9716, 77.5946)
121 idx = DriverIndex()
122 for i in range(2_000):
123 idx.update(f"d{i}", centre[0] + rnd.uniform(-0.1, 0.1), centre[1] + rnd.uniform(-0.1, 0.1), now=0)
124 idx.update("d0", centre[0] + 0.0001, centre[1], now=0) # moves next to the rider
125 idx.update("stale", centre[0], centre[1], now=-100) # app died 100 s ago
126 near = idx.nearby(*centre, now=0)
127 assert "d0" in near and "stale" not in near and len(near) < 2_000
128
129 # 2. ETA, not distance: across the river is closer as the crow flies but 3x by road
130 pickup = centre
131 across = (centre[0] + 0.006, centre[1]) # ~0.7 km straight line
132 same_side = (centre[0], centre[1] + 0.011) # ~1.2 km
133 assert km(across, pickup) < km(same_side, pickup)
134 assert eta_minutes(across, pickup, road_factor=3.0) > eta_minutes(same_side, pickup, road_factor=1.3)
135
136 # two riders' requests both pick driver d0 at the same moment
137 disp = Dispatcher()
138 assert dispatch(["d0", "d7"], lambda d: True, disp, "t1") == "d0"
139 assert dispatch(["d0", "d7"], lambda d: True, disp, "t2") == "d7" # d0 taken: next best
140 assert dispatch(["d9", "d10"], lambda d: False, disp, "t3") is None # nobody accepts: retry wider
141
142 # 3. surge: 300 requests, 100 drivers in a cell after a concert
143 m1 = surge(300, 100)
144 m2 = surge(300, 100, prev=m1)
145 m3 = surge(1_000, 50, prev=m2)
146 assert (m1, m2) == (1.5, 1.75) and m3 <= 2.5
147 assert surge(80, 100, prev=1.75) == 1.38 # eases off gradually
148
149 # 4. trip states, with a duplicate event from a flaky phone
150 t = Trip("t1")
151 assert t.event("e1", "matched") == "ok"
152 assert t.event("e1", "matched") == "duplicate"
153 assert t.event("e2", "in_trip") == "rejected" # can't skip "arriving"
154 assert [t.event("e3", "arriving"), t.event("e4", "in_trip"), t.event("e5", "completed")] == ["ok"] * 3
155 assert fare(8, 25, 1.0) == 174 and fare(8, 25, 1.5) == 260 and fare(1, 3, 1.0) == 80
156
157 return {"nearby": len(near), "surge": (m1, m2, m3), "fare": (174, 260)}
158
159
160if __name__ == "__main__":
161 print("All checks pass.", run_checks())