023 — Bus Routes¶

Source¶

Original source: "অদ্ভুত statement-কে graph-এ model করা"-র classic প্রয়োগ
Platform: LeetCode — https://leetcode.com/problems/bus-routes/
Topic: graphs
Difficulty: Hard
Pattern: BFS on transformed graph (node = route, edge = shared stop)
Basic idea inherited from: modeling habit (এই repo-র "nodes কী, edges কী" অভ্যাস)

1. Problem in simple words¶

তোমাকে কতগুলো bus route দেওয়া আছে; routes[i] মানে i-নম্বর bus পরপর ওই stop-গুলোতে থামে (আর route-টা চক্রাকারে চলতে থাকে)। তুমি source stop-এ দাঁড়িয়ে আছ আর target stop-এ যেতে চাও। তুমি যেকোনো bus-এ চড়তে আর নামতে পারো। সবচেয়ে কম কয়টা bus নিলে target-এ পৌঁছানো যায়, সেটা বের করো; না পারলে -1। (একই stop হলে 0।)

routes = [[1, 2, 7], [3, 6, 7]]
source = 1, target = 6

bus 0 (stop 1,2,7)-এ চড়ে stop 7-এ নামি, সেখানে bus 1 (3,6,7) ধরি, stop 6-এ নামি।
2 টা bus -> উত্তর: 2

2. Which basic idea does this inherit from?¶

এটা দাঁড়িয়ে এই repo-র সবচেয়ে কেন্দ্রীয় অভ্যাসের উপর: "আমার node কী, edge কী" (README-র modeling বাক্য)। ভুল modeling করলে problem-টা জট পাকিয়ে যায়; সঠিক modeling করলে সেটা সাধারণ BFS-এ মিলিয়ে যায়। এখানে চালাকি — node হিসেবে stop নয়, route নাও। একই stop share করা দুটো route-এর মধ্যে edge, আর "কয়টা bus" = এই route-graph-এ BFS-এর layer-সংখ্যা। unweighted, তাই ../shortest-path.md-এর প্রথম row: plain BFS, deque।

3. What is the hidden math or logic?¶

লুকানো logic হলো graph-এর সঠিক রূপান্তর। যদি stop-কে node ধরো, তবে একই route-এর সব stop পরস্পরের সাথে যুক্ত — তাতে edge-সংখ্যা বিস্ফোরিত হয় (একটা route-এ m stop হলে m^2 edge)। কিন্তু "কয়টা bus" আসলে route-পরিবর্তনের সংখ্যা। তাই node = route ধরলে, একটা bus নেওয়া = একটা route-node visit করা, আর BFS-এর layer ঠিক bus-সংখ্যা গোনে। মূল গণিত: একই stop দুটো route-কে এক ধাপে যুক্ত করে (এক bus থেকে আরেক bus-এ transfer)।

4. Which data structure is needed?¶

তিনটা: (১) একটা dict (defaultdict) — stop -> কোন কোন route সেই stop ছোঁয়, এটাই route-graph-এর adjacency-র ভিত্তি; (২) একটা deque — BFS-এর FIFO queue; (৩) দুটো set — visited routes আর visited stops, যাতে কিছু দুবার process না হয়।

5. Why this data structure fits¶

stop -> routes dict fit করে কারণ "এই stop-এ দাঁড়িয়ে কোন কোন bus ধরা যায়" প্রশ্নটা বারবার লাগে, আর dict সেটা O(1)-তে দেয়। Deque fit করে কারণ unweighted graph-এ সবচেয়ে কম bus = BFS, আর BFS-এর প্রাণ FIFO queue। visited set দুটো fit করে কারণ একই route দুবার চড়লে layer বাড়ে শুধু, লাভ নেই; আর একই stop দুবার ঘাঁটলে অপ্রয়োজনীয় কাজ — set দিয়ে দুটোই থামাই।

6. Real-life analogy¶

ভাবো শহরের bus-map। তুমি stop-গুলো নিয়ে মাথা ঘামাচ্ছ না; তোমার আসল প্রশ্ন — "কয়টা bus বদলাতে হবে।" তাই তুমি প্রতিটা bus line-কে একটা বিন্দু ভাবো, আর দুটো line-এর মধ্যে যোগ আছে যদি তাদের কোনো common stop থাকে (যেখানে তুমি transfer করতে পারো)। source stop থেকে যত line ধরা যায় সব ধরো (layer 1), তাদের transfer-stop থেকে যত নতুন line ধরা যায় (layer 2) — যে layer-এ target-ছোঁয়া line পাবে, সেটাই কম bus-সংখ্যা।

7. Visual explanation¶

routes = [[1,2,7],[3,6,7]], source 1, target 6। প্রথমে stop->routes:

stop_to_routes:  1->[0]  2->[0]  7->[0,1]  3->[1]  6->[1]

BFS (node = route):
source 1 থেকে ধরা যায় route 0  -> queue: (route0, buses=1)

pop route0 (buses=1): stops 1,2,7
   stop 7 -> route 1 নতুন -> push (route1, buses=2)
pop route1 (buses=2): stops 3,6,7
   stop 6 == target  -> return 2

8. Example input and output¶

Input : routes = [[1,2,7],[3,6,7]], source=1, target=6
Output: 2

Input : routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source=15, target=12
Output: -1

Edge case (source == target): routes=[[1,2,7],[3,6,7]], source=1, target=1 -> 0
Edge case (এক bus-ই যথেষ্ট): routes=[[1,7]], source=1, target=7 -> 1

9. Brute force thinking¶

প্রথম সরল চিন্তা: stop-কে node ধরে graph বানাও — একই route-এর প্রতি জোড়া stop-এর মধ্যে edge। তারপর সেই stop-graph-এ BFS, কিন্তু "কয়টা bus" গুনতে গেলে কোন edge কোন route-এর সেটাও track করতে হবে, যা জটিল আর ভারী।

1) প্রতিটা route-এর সব stop জোড়ায় জোড়ায় edge যোগ করো
2) source stop থেকে BFS
3) bus-পরিবর্তন গুনতে route বদলের হিসাব রাখো (ঝামেলার)

10. Why brute force is slow¶

stop-কে node ধরলে একটা m-stop route m^2 edge তৈরি করে; বড় route থাকলে edge-সংখ্যা ভয়ংকর বেড়ে যায়, memory আর সময় দুটোই ফুলে ওঠে। তার উপর "কয়টা bus" গোনা stop-graph-এ অস্বাভাবিক — কারণ একই route-এর ভেতর হাঁটা কোনো bus-পরিবর্তন নয়, কিন্তু stop-edge সেটা আলাদা করে না। মূল অপচয়: ভুল জিনিসকে (stop) node বানানো, যেখানে আসল প্রশ্ন route-পরিবর্তন নিয়ে।

11. Key observation¶

মূল observation: গোনার একক bus, তাই node হওয়া উচিত route — stop নয়। দুটো route এক ধাপে পৌঁছানো যায় যদি তাদের একটা common stop থাকে। তখন BFS-এর layer-সংখ্যা সরাসরি bus-সংখ্যা গোনে, আর "একই route-এ হাঁটা ফ্রি" ব্যাপারটা আপনাআপনি সামলে যায় (পুরো route এক node)।

12. Optimized intuition¶

আগে stop -> routes map বানাও। BFS শুরু করো source stop-এ ধরা যায় এমন সব route দিয়ে (buses=1)। queue থেকে route বের করো, তার প্রতিটা stop দেখো; কোনো stop target হলে এই buses-ই উত্তর; নাহলে সেই stop থেকে ধরা যায় এমন unvisited route গুলো queue-তে দাও (buses+1)। route আর stop দুটোই visited mark করো, যাতে চক্র না হয়। BFS layer-by-layer ছড়ায়, তাই প্রথম যে layer-এ target মেলে সেটাই সবচেয়ে কম bus।

13. Thinking tweak¶

মোচড়: "stop = node" — এই স্বাভাবিক ধারণাটা ছেড়ে দাও; প্রশ্ন যেহেতু "কয়টা bus", তাই "route = node, common stop = edge" ভাবো। যা গোনা হচ্ছে, সেটাই হওয়া উচিত graph-এর layer — এই এক বদল Hard problem-টাকে সাধারণ BFS বানিয়ে দেয়।

14. Step-by-step dry run¶

routes=[[1,7]], source=1, target=7 (উত্তর 1):

stop_to_routes: 1->[0], 7->[0]।
source != target। source 1-এ ধরা যায় route 0 → queue [(0, 1)], visited_routes={0}, visited_stops={1}।
pop (0, 1)। route 0-এর stops [1, 7]: stop 1 target নয় (আর visited); stop 7 == target → return 1।

আরেকটা: source=1, target=6, routes=[[1,2,7],[3,6,7]]:

queue [(0,1)]। pop route0 (buses 1): stop 7 → route1 push (1,2)। pop route1 (buses 2): stop 6 == target → return 2।

15. Python solution¶

from collections import defaultdict, deque

def num_buses_to_destination(routes, source, target):
    # graph-এর node bus নয়, ROUTE; দুটো route share করলে stop-এ edge
    if source == target:
        return 0
    # stop -> কোন কোন route সেই stop ছোঁয়
    stop_to_routes = defaultdict(list)
    for i, route in enumerate(routes):
        for stop in route:
            stop_to_routes[stop].append(i)
    # BFS: state = একটা route (পুরো route এক ধাপে চড়া যায়)
    queue = deque()
    visited_routes = set()
    visited_stops = {source}
    for r in stop_to_routes[source]:          # source থেকে যত route ধরা যায়
        queue.append((r, 1))                    # (route, এ পর্যন্ত নেওয়া bus সংখ্যা)
        visited_routes.add(r)
    while queue:
        route, buses = queue.popleft()
        for stop in routes[route]:
            if stop == target:
                return buses
            if stop not in visited_stops:
                visited_stops.add(stop)
                for nxt in stop_to_routes[stop]:
                    if nxt not in visited_routes:
                        visited_routes.add(nxt)
                        queue.append((nxt, buses + 1))
    return -1

# ---- tests ----
assert num_buses_to_destination([[1, 2, 7], [3, 6, 7]], 1, 6) == 2
assert num_buses_to_destination([[7, 12], [4, 5, 15], [6], [15, 19], [9, 12, 13]], 15, 12) == -1
assert num_buses_to_destination([[1, 2, 7], [3, 6, 7]], 1, 1) == 0
assert num_buses_to_destination([[1, 7]], 1, 7) == 1
assert num_buses_to_destination([[2], [2, 8]], 8, 2) == 1
print("সব test pass!")

16. Line-by-line code explanation¶

if source == target: return 0 — একই জায়গায় থাকলে কোনো bus লাগে না।
stop_to_routes[stop].append(i) — প্রতিটা stop কোন কোন route ছোঁয়, এই map-ই transfer-graph-এর ভিত্তি।
for r in stop_to_routes[source] — BFS-এর শুরু: source-এ দাঁড়িয়ে যত bus ধরা যায়, সব layer-1।
queue.append((r, 1)) — (route, এ পর্যন্ত নেওয়া bus); source-এর route গুলো 1 bus।
for stop in routes[route] — current bus-এর সব stop ঘোরো (পুরো route এক ধাপে যাওয়া যায়)।
if stop == target: return buses — কোনো stop target হলেই এই bus-সংখ্যা সবচেয়ে কম (BFS গ্যারান্টি)।
if stop not in visited_stops ও ভেতরের loop — নতুন stop থেকে যত unvisited route ধরা যায়, সব queue-তে buses+1 সহ।

17. Output walkthrough¶

num_buses_to_destination([[1,2,7],[3,6,7]], 1, 6): source ≠ target। stop_to_routes দেয় 7->[0,1] ইত্যাদি। source 1-এ route 0 ধরা যায় → queue [(0,1)]। route 0 process: stop 7 হয়ে route 1 push (1,2)। route 1 process: stop 6 == target → return 2। দ্বিতীয় test-এ source 15 আর target 12-এর route গুলো কোনো common stop দিয়ে যুক্ত হয় না (BFS শেষ হয়) → return -1। বাকি assert pass, শেষে print: সব test pass!।

18. Time complexity¶

O(সব route-এর মোট stop-সংখ্যা + transfer) — stop_to_routes বানাতে সব stop একবার; BFS-এ প্রতিটা route একবার process আর তার stop গুলো একবার দেখা হয়। প্রতিটা stop থেকে route-list একবারই খোলা হয় (stop visited হয়ে যায়), তাই কাজ মোট stop-সংখ্যার সমানুপাতিক।

19. Space complexity¶

O(সব route-এর মোট stop-সংখ্যা) — stop_to_routes map-এ প্রতিটা (route, stop) জোড়ার entry; সাথে visited দুটো set আর queue, যা route/stop-সংখ্যায় সীমিত।

20. Common mistakes¶

stop-কে node ধরা — m^2 edge-এ memory/সময় বিস্ফোরণ; route-কে node ধরো।
source == target early check বাদ দেওয়া — তখন 0-এর জায়গায় ভুলভাবে 1 আসে।
visited routes track না করে শুধু visited stops রাখা (বা উল্টো) — একটাই যথেষ্ট নয়; route আবার চড়া আর stop আবার ঘাঁটা — দুটোই থামাতে হয়।
BFS-এর বদলে DFS — কম-bus-সংখ্যার গ্যারান্টি নষ্ট।
route push-এর সময় visited mark না করে pop-এর সময় করা — একই route বহুবার queue-তে ঢুকে কাজ ফুলে ওঠে।

21. Which basic problem this inherits from¶

ভিত্তি: এই repo-র modeling habit ("node কী, edge কী") আর তার উপর সাধারণ BFS (../shortest-path.md-এর unweighted row)। আটকে গেলে আগে নিজেকে জিজ্ঞেস করো "যা গুনছি (bus) সেটা কি graph-এর layer হচ্ছে?" — উত্তর না হলে node-এর সংজ্ঞা বদলাও। তারপর বাকিটা চেনা grid-BFS-এর মতোই।

22. Similar harder problems¶

Word Ladder (implicit graph BFS, transform করে node বানানো) — https://leetcode.com/problems/word-ladder/ (এই tracker-এর #21)
Jump Game IV (index = node, একই value/পাশ = edge) — https://leetcode.com/problems/jump-game-iv/
Shortest Path to Get All Keys (state = position + key-set, BFS) — https://leetcode.com/problems/shortest-path-to-get-all-keys/

23. Pattern learned¶

BFS on a transformed graph: statement-এ যা গোনা হচ্ছে (এখানে bus) সেটাকে graph-এর layer বানাও — node-এর সংজ্ঞা বদলে (stop নয়, route) সমস্যাটা সাধারণ unweighted BFS-এ নামিয়ে আনো।

24. Final summary¶

ভবিষ্যতের আমাকে: "Bus Routes = route-কে node ধরো (stop নয়), common stop = edge; stop->routes map বানিয়ে BFS, layer = bus-সংখ্যা।" 'কয়টা X বদলাতে হবে' ধরনের প্রশ্নে X-কেই node বানিয়ে transformed-graph BFS মনে পড়বে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।