بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 14: مسیرها و پیشنهادها Paths and Suggestions

گراف جان می‌دهد برای دو سؤال که در جدول سخت‌اند: «از من تا او چند قدم راه است؟» و «چه کسی یا چه چیزی را پیشنهاد کنم؟». با graph.path کوتاه‌ترین زنجیره‌ی دوستی را می‌گیری، درجه‌ی جدایی را می‌شماری، «کسانی که شاید بشناسی» را با شمردن دوست‌های مشترک رتبه‌بندی می‌کنی و بازی‌ای پیشنهاد می‌دهی که دوست‌هایت بازی می‌کنند.

در این جلسه یاد می‌گیری

درس

🔐 قانون طلایی این دوره: داده‌ی آدم‌ها امانت است. پشت هر ردیف جدول یک آدم واقعی است: اسمش، کلاسش، کتاب‌هایی که خوانده. داده‌ی کسی را بدون اجازه جمع نکن، به کسی نده و برای مسخره کردن یا سرک کشیدن به کار نبر. همه‌ی داده‌های این دوره ساختگی‌اند و هر بار که برنامه را اجرا می‌کنی از اول ساخته می‌شوند، پس هر چه می‌خواهی امتحان کن: چیزی خراب نمی‌شود.

🔁 یادت هست؟ در جلسه‌ی ۱۳ «دوستِ دوست»ها را با دو حلقه پیدا کردیم: روی دوست‌هایم، و داخلش روی دوست‌های آن‌ها. خودم و دوست‌های مستقیمم را کنار گذاشتیم و جواب‌ها را در یک set جمع کردیم تا تکراری نشوند. امروز همین دو حلقه را می‌شماریم.

from db import graph

me = "Omid"
mine = graph.friends(me)
fof = set()
for f in mine:
    for ff in graph.friends(f):
        if ff != me and ff not in mine:
            fof.add(ff)
print(sorted(fof))

مسیر (path): graph.path("Sara", "Omid") کوتاه‌ترین زنجیره‌ی دوستی از سارا تا امید را به شکل لیست می‌دهد: هر نفر دوستِ نفر بعدی است. اگر دو زنجیره‌ی هم‌اندازه باشد، آن که به ترتیب الفبا جلوتر است انتخاب می‌شود، پس جواب همیشه یکی است. اگر اصلاً راهی نباشد (یا آن اسم در گراف نباشد) جواب None است، یعنی «هیچ». " -> ".join(path) زنجیره را قشنگ چاپ می‌کند.

from db import graph

path = graph.path("Sara", "Omid")
print(path)
print(" -> ".join(path))
print(graph.path("Sara", "Parisa"))

درجه‌ی جدایی یعنی چند قدم دوستی بین دو نفر است. دوست مستقیم ۱ قدم است، دوستِ دوست ۲ قدم. تعداد قدم‌ها یکی کمتر از تعداد آدم‌های مسیر است: len(path) - 1. می‌گویند هر دو نفر روی زمین با حدود شش قدم به هم وصل‌اند! اول بپرس if path is None: و بعد طول بگیر، چون len(None) خطا می‌دهد.

from db import graph

path = graph.path("Leila", "Ali")
if path is None:
    print("no path")
else:
    print(" -> ".join(path))
    print("steps:", len(path) - 1)

«کسانی که شاید بشناسی» در شبکه‌های اجتماعی این‌طوری کار می‌کند: هر چه با کسی دوست مشترک بیشتری داشته باشی، احتمال این‌که او را بشناسی بیشتر است. همان دو حلقه‌ی دوستِ دوست را می‌زنیم، ولی به جای set یک دیکشنری داریم که برای هر نفر می‌شمارد از چند راه پیدا شد: count[ff] = count.get(ff, 0) + 1. هر راه یعنی یک دوست مشترک.

from db import graph

graph.add_friend("Ali", "Kian")
me = "Sara"
mine = graph.friends(me)
count = {}
for f in mine:
    for ff in graph.friends(f):
        if ff != me and ff not in mine:
            count[ff] = count.get(ff, 0) + 1
for p in sorted(count):
    print(p, count[p])

حالا رتبه‌بندی: بیشترین دوست مشترک اول، و اگر مساوی بودند به ترتیب الفبا. sorted(count, key=lambda p: (-count[p], p)) همین کار را می‌کند. key به sorted می‌گوید برای هر اسم p چه چیزی را مقایسه کند: اول -count[p] (منفی، تا عدد بزرگ‌تر جلو بیاید) و اگر مساوی بود، خود اسم. ranked[:3] فقط سه‌تای اول لیست را می‌دهد (اگر کمتر باشد، همان‌قدر).

count = {"Yasmin": 2, "Reza": 1, "Kian": 2, "Omid": 1}
ranked = sorted(count, key=lambda p: (-count[p], p))
print(ranked)
print(ranked[:3])

همین فکر برای پیشنهاد بازی هم کار می‌کند: روی دوست‌هایم و بازی‌های هر کدام حلقه می‌زنم، بازی‌هایی را که خودم بازی می‌کنم کنار می‌گذارم، و می‌شمارم هر بازی را چند دوست بازی می‌کنند. پربازی‌ترین (با شکستن تساوی به ترتیب الفبا) پیشنهاد من است. فروشگاه‌ها و سایت‌های فیلم هم کم‌وبیش همین کار را می‌کنند.

from db import graph

me = "Reza"
count = {}
for f in graph.friends(me):
    for g in graph.plays(f):
        if g not in graph.plays(me):
            count[g] = count.get(g, 0) + 1
print(count)

اشتباه رایج: len(path) تعداد آدم‌های مسیر است، نه تعداد قدم‌ها. مسیر سارا تا علی ['Sara', 'Ali'] است: دو نفر، ولی یک قدم. پس قدم‌ها len(path) - 1 است. اشتباه دوم: رتبه‌بندی فقط با تعداد (sorted(count, key=count.get, reverse=True)) وقتی دو نفر مساوی‌اند، ترتیب را به این می‌سپارد که کدام زودتر شمرده شد، نه به الفبا؛ پس جواب ممکن است با چیزی که خواسته شده فرق کند.

from db import graph

path = graph.path("Sara", "Ali")
print(len(path), "people,", len(path) - 1, "step")

مثال‌های این جلسه

چالش‌ها

  1. Nima's Friends of Friends (آسان)
  2. From Sara to Reza (آسان)
  3. How Many Steps? (متوسط)
  4. Common Friends (متوسط)
  5. People You May Know (سخت)
  6. Suggest a Game (سخت)

بیشتر بخوان

← جلسه‌ی 13: گراف: کی کی را می‌شناسد؟ جلسه‌ی 15: کدام پایگاه داده برای کدام کار؟ →