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

جلسه‌ی 14: راه را پیدا کن Finding the Way

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

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

درس

این ماز ۸ در ۸ را ببین. اول حدس بزن: اگر از خانه‌ی شروع آب بریزیم، آب زودتر به کدام خانه‌ها می‌رسد؟ بعد دکمه‌ی «یک قدم آب» را چند بار بزن: هر بار آب یک خانه جلوتر می‌رود و هر خانه‌ی خیس یک شماره می‌گیرد. زیر صفحه صف را ببین. حالا روی یک خانه کلیک کن تا دیوار شود، «از اول» و «تا آخر» را بزن. شماره‌ها چطور عوض شدند؟ آخر «کوتاه‌ترین راه» را بزن.

مثل لیوان آبی که روی کاشی‌های کف آشپزخانه بریزد: آب اول به کاشی‌های کنار خودش می‌رسد، بعد به کنارِ کنارها، و از دیوار رد نمی‌شود. شماره‌ی هر خانه یعنی آب چند قدم طول کشید تا برسد. ماز را با یک لیست از رشته‌ها می‌نویسیم: # دیوار، . راه، S شروع و G هدف. maze[r][c] خانه‌ی سطر r و ستون c است.

maze = [
    "S..#....",
    ".#.#.##.",
    ".#...#..",
    ".####.#.",
    "......#G",
]

print(maze[0][0], maze[4][7])
print("rows:", len(maze), "columns:", len(maze[0]))

آب باید بداند نوبت کدام خانه است. برای این یک صف داریم، درست مثل صف نانوایی: هر کس اول آمده، اول نان می‌گیرد. خانه‌ی تازه را آخر صف می‌گذاریم (append) و خانه‌ی اول صف را برمی‌داریم (pop(0)). جای هر خانه را هم با یک جفت (r, c) می‌نویسیم؛ این جفت می‌تواند کلید دیکشنری باشد.

queue = ["Ali", "Sara"]
queue.append("Reza")
first = queue.pop(0)
print("served:", first)
print("waiting:", queue)
dist = {(0, 0): 0}
print(dist[(0, 0)])

حالا همه با هم: شماره‌ی شروع 0 است. تا وقتی صف خالی نشده، خانه‌ی اول صف را بردار؛ به هر همسایه‌ی بازش که هنوز شماره ندارد، شماره‌ی خودش به‌علاوه‌ی یک را بده و آن را ته صف بگذار. همین چند خط اسم ترسناکی دارد: جست‌وجوی سطح‌به‌سطح (BFS). ولی تو فقط آب ریختی!

maze = [
    "S..#....",
    ".#.#.##.",
    ".#...#..",
    ".####.#.",
    "......#G",
]

def neighbours(r, c):
    result = []
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < len(maze) and 0 <= nc < len(maze[0]) and maze[nr][nc] != "#":
            result.append((nr, nc))
    return result

dist = {(0, 0): 0}
queue = [(0, 0)]
while queue:
    cell = queue.pop(0)
    for nxt in neighbours(cell[0], cell[1]):
        if nxt not in dist:
            dist[nxt] = dist[cell] + 1
            queue.append(nxt)

print("G is", dist[(4, 7)], "steps away")

کوتاه‌ترین راه را برعکس پیدا می‌کنیم، مثل رد خرده‌نان در قصه‌ها: از G شروع کن، به همسایه‌ای برو که شماره‌اش یکی کم‌تر است، و همین را تکرار کن تا به 0 برسی. چون آب همیشه از کوتاه‌ترین راه آمده، این راه هم کوتاه‌ترین است.

بازی بدون کامپیوتر: کف کلاس را کاشی‌کاشی کنید؛ چند صندلی دیوار است. یک نفر روی شروع کاغذ «۰» می‌گیرد. معلم می‌گوید «یک قدم!»: هر کس کاغذ دارد، به هم‌کلاسی‌های کاشی‌های کناری کاغذ عدد بعدی می‌دهد. آخر از هدف، عددها را برعکس دنبال کنید.

⚠️ به نقشه کورکورانه اعتماد نکن. «کوتاه‌ترین راه» یعنی کوتاه‌ترین روی نقشه‌ای که به کامپیوتر دادی. اگر نقشه کهنه باشد (کوچه بسته شده، پل خراب است)، مسیریاب گوشی هم با اطمینان تو را به بن‌بست می‌برد. یک چیز دیگر: برنامه‌های مسیریاب می‌دانند تو کجایی؛ موقعیت خانه‌ات را با هر برنامه‌ای شریک نشو.

در پروژه: آب همه‌ی راه‌ها را یکی‌یکی امتحان کرد تا بهترین را پیدا کند. جلسه‌ی بعد کامپیوتر دوز همین کار را با حرکت‌های بازی می‌کند: همه‌ی آینده‌ها را امتحان می‌کند، و در جلسه‌ی ۱۶ همین فکر، دوز شکست‌ناپذیرت را می‌سازد.

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

چالش‌ها

  1. Read the Maze (آسان)
  2. Number the Water (آسان)
  3. Open Neighbours (متوسط)
  4. Pour the Water (متوسط)
  5. Walk Back the Path (سخت)
  6. The Robot Follows the Water (سخت)

بیشتر بخوان

← جلسه‌ی 13: شخصیت باهوش یعنی چه؟ جلسه‌ی 15: یک حرکت جلوتر فکر کن →