{ "cells": [ { "cell_type": "markdown", "id": "aa584fdc", "metadata": {}, "source": [ "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/MeiraDavidson/compute_module1/blob/main/notebooks/lab_05_dots_and_lines.ipynb)\n\n", "# Lab 5: Dots and Lines\n", "\n", "*From* **A First Taste of Algorithms — and the Machines That Learn** *(The Curious Family Library). A computational lab: run the cells in order. A few labs end with a deliberately broken “Break it” cell — that one is meant to fail, and seeing how is the point.*" ] }, { "cell_type": "markdown", "id": "2e954678", "metadata": {}, "source": [ "*Accompanies Chapter 5. The chapter walked graphs three ways with coins and napkins; here the same three walks run on the machine. Two small tools arrive — each because the graph demands it — and a maze of your own design gets solved by ripple, by thread, and then, with one word changed, by each pretending to be the other.*\n", "\n", "## 1. A graph in the machine\n", "\n", "The chapter's school, verbatim — a dictionary with one entry per vertex, holding its list of neighbors:" ] }, { "cell_type": "code", "execution_count": null, "id": "49fc12e1", "metadata": {}, "outputs": [], "source": [ "hallways = {\n", " \"gym\": [\"lobby\"],\n", " \"lobby\": [\"gym\", \"library\", \"cafeteria\"],\n", " \"library\": [\"lobby\", \"lab\"],\n", " \"cafeteria\": [\"lobby\", \"lab\"],\n", " \"lab\": [\"library\", \"cafeteria\"],\n", "}\n", "\n", "print(hallways[\"lobby\"])" ] }, { "cell_type": "markdown", "id": "516d661b", "metadata": {}, "source": [ "Notice the convention: every edge appears *twice* (gym lists lobby, lobby lists gym), because a hallway can be walked both ways. Check the dictionary against a drawing of the school — then deliberately desynchronize it (delete `\"gym\"` from lobby's list but keep lobby in gym's) and hold that thought for Break-it 1.\n", "\n", "## 2. The ripple\n", "\n", "BFS, with the queue kept honest in plain sight: the waiting line is a list, and a marker `head` points at who gets served next. Serving means moving the marker; joining means appending. Nothing is ever deleted — the line keeps its history, which will turn out to be a gift.\n", "\n", "One new tool, arriving with its debt: the **set**. The visited-check must be fast and duplicate-proof; a set is a bag that holds each thing at most once and answers `in` instantly. Three moves: `seen = set()`, `seen.add(x)`, `x in seen`." ] }, { "cell_type": "code", "execution_count": null, "id": "b4bee36f", "metadata": {}, "outputs": [], "source": [ "def bfs(graph, start):\n", " queue = [start]\n", " head = 0\n", " seen = {start} # a set with one thing in it\n", " dist = {start: 0} # the notebook: vertex -> hops\n", " while head < len(queue):\n", " here = queue[head]\n", " head = head + 1 # serve the front of the line\n", " for neighbor in graph[here]:\n", " if neighbor not in seen:\n", " seen.add(neighbor)\n", " dist[neighbor] = dist[here] + 1\n", " queue.append(neighbor) # join the back of the line\n", " return dist\n", "\n", "print(bfs(hallways, \"gym\"))" ] }, { "cell_type": "markdown", "id": "805a39e3", "metadata": {}, "source": [ "Run it and check every distance against your drawing. Then print `queue` itself after the run (add a print, or return it too): the line's history *is* the rings, in order — read it aloud as \"ring 0, ring 1, ring 2\" and confirm the bureaucracy did what the chapter promised.\n", "\n", "## 3. A maze is a graph wearing a costume\n", "\n", "Build a maze as a list of strings — `#` wall, `.` floor, `S` start, `E` exit:" ] }, { "cell_type": "code", "execution_count": null, "id": "021b994f", "metadata": {}, "outputs": [], "source": [ "maze = [\n", " \"#########\",\n", " \"#S..#...#\",\n", " \"#.#.#.#.#\",\n", " \"#.#...#.#\",\n", " \"#.###.#.#\",\n", " \"#.....#E#\",\n", " \"#########\",\n", "]" ] }, { "cell_type": "markdown", "id": "b7d21adb", "metadata": {}, "source": [ "Where is the graph? Every floor cell is a vertex; two floor cells side-by-side share an edge. We never build the dictionary — the maze *answers neighbor queries on demand* (look up, down, left, right; a graph is anywhere that can answer \"who are your neighbors?\").\n", "\n", "A cell's name is its (row, column) position — and here the second tool arrives with its debt. Positions must live in the `seen` set and the `dist` notebook, and Python's rule is that set members and notebook keys must be *unchangeable* things; a list, which can be appended to and edited, is not allowed. The unchangeable list is called a **tuple**: written `(5, 7)` with round brackets, indexed like a list, frozen forever at birth. Positions are tuples because positions must be lookupable." ] }, { "cell_type": "code", "execution_count": null, "id": "4c8443cc", "metadata": {}, "outputs": [], "source": [ "def maze_bfs(maze, start):\n", " queue = [start]\n", " head = 0\n", " seen = {start}\n", " dist = {start: 0}\n", " while head < len(queue):\n", " here = queue[head]\n", " head = head + 1\n", " r = here[0]\n", " c = here[1]\n", " for next_pos in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:\n", " if maze[next_pos[0]][next_pos[1]] != \"#\":\n", " if next_pos not in seen:\n", " seen.add(next_pos)\n", " dist[next_pos] = dist[here] + 1\n", " queue.append(next_pos)\n", " return dist\n", "\n", "distances = maze_bfs(maze, (1, 1)) # S is at row 1, column 1\n", "print(distances[(5, 7)]) # E is at row 5, column 7" ] }, { "cell_type": "markdown", "id": "4fa5a676", "metadata": {}, "source": [ "The ripple's answer is the shortest path length in steps. Verify it by tracing the maze with a pencil — then design your *own* maze (keep the `#` border, it is what spares the code from falling off the edge) with at least two routes from S to E of different lengths, and confirm BFS reports the shorter.\n", "\n", "## 4. The one word\n", "\n", "The chapter claimed BFS and DFS differ by which end of the line you serve. Test the claim with the smallest possible edit — serve the *back*:" ] }, { "cell_type": "code", "execution_count": null, "id": "3dfc3736", "metadata": {}, "outputs": [], "source": [ "def dfs(graph, start):\n", " line = [start]\n", " seen = {start}\n", " order = []\n", " while len(line) > 0:\n", " here = line.pop() # .pop(): remove and return the LAST item\n", " order.append(here)\n", " for neighbor in graph[here]:\n", " if neighbor not in seen:\n", " seen.add(neighbor)\n", " line.append(neighbor)\n", " return order\n", "\n", "print(dfs(hallways, \"gym\"))\n", "print(bfs(hallways, \"gym\"))" ] }, { "cell_type": "markdown", "id": "a44c725d", "metadata": {}, "source": [ "(`.pop()` is the one new move: take the last item off a list. A line served from the back is called a **stack** — the call stack of Chapter 3 is one, which is why the chapter could say DFS *is* recursion.) Compare the two visit orders on the school, then on your maze (adapt as in §3): the ripple sweeps level by level; the thread plunges. Same dots, same lines, opposite temperaments, one word.\n", "\n", "## 5. Price tags on the town\n", "\n", "The chapter's town, with weights — a dictionary of neighbor lists where each neighbor comes with a price, as a `(place, minutes)` tuple:" ] }, { "cell_type": "code", "execution_count": null, "id": "542c1863", "metadata": {}, "outputs": [], "source": [ "town = {\n", " \"Home\": [(\"Park\", 2), (\"School\", 9), ],\n", " \"Park\": [(\"Home\", 2), (\"School\", 5), (\"Library\", 9), (\"Gym\", 11)],\n", " \"School\": [(\"Park\", 5), (\"Home\", 9), (\"Library\", 1), (\"Cafe\", 7)],\n", " \"Library\": [(\"School\", 1), (\"Park\", 9), (\"Cafe\", 4)],\n", " \"Cafe\": [(\"Library\", 4), (\"School\", 7), (\"Gym\", 3)],\n", " \"Gym\": [(\"Park\", 11), (\"Cafe\", 3)],\n", "}" ] }, { "cell_type": "markdown", "id": "d815d241", "metadata": {}, "source": [ "Dijkstra's protocol, exactly as you played it with coins — tags, settle the cheapest, relax its edges:" ] }, { "cell_type": "code", "execution_count": null, "id": "622a82bd", "metadata": {}, "outputs": [], "source": [ "def dijkstra(graph, start):\n", " tags = {start: 0} # tentative prices; absent = infinity\n", " settled = set()\n", " while len(settled) < len(graph):\n", " cheapest = None # scan for the cheapest unsettled tag\n", " for place in tags:\n", " if place not in settled:\n", " if cheapest is None or tags[place] < tags[cheapest]:\n", " cheapest = place\n", " if cheapest is None:\n", " break # the rest is unreachable\n", " settled.add(cheapest)\n", " for edge in graph[cheapest]:\n", " place = edge[0]\n", " cost = tags[cheapest] + edge[1]\n", " if place not in tags or cost < tags[place]:\n", " tags[place] = cost # relax: the detour wins\n", " return tags\n", "\n", "print(dijkstra(town, \"Home\"))" ] }, { "cell_type": "markdown", "id": "52a6f187", "metadata": {}, "source": [ "(`None` is Python's word for \"nothing yet\" — the scan starts with no champion and crowns the first candidate.) Check every tag against the chapter's hand-run: Park 2, School 7, Library 8, Café 12, Gym 13 — five answers, five detours. Then rebuild `town` as **your actual neighborhood**, six or seven places with honest walking-minutes, and find something true you didn't know about your own streets.\n", "\n", "## Break it\n", "\n", "Predict first. Run second. Explain any gap third.\n", "\n", "**1.** The desynchronized graph from §1: delete `\"gym\"` from lobby's neighbor list (keep lobby in gym's). Predict `bfs(hallways, \"gym\")` and then `bfs(hallways, \"lab\")` — same reachability or different? You have built a *one-way door*. Real graphs (the web, who-follows-whom) are full of them; what single sentence of the §1 convention did you break, and which of the two BFS runs is the one that can no longer find everything?\n", "\n", "**2.** In `maze_bfs`, remove the border: change your maze's top row to open floor and run from S. Predict the failure before running — wrong answer, error, or infinite loop? — then read the error's last line and explain which innocent-looking expression walked off the world. (Two repairs exist: rebuild the wall, or teach the neighbor-check to refuse positions outside the maze. Implement the second; the first you already had.)\n", "\n", "**3.** *The road that pays you.* First, make Dijkstra's promises audible: add one line right after `settled.add(cheapest)` — `print(\"settled:\", cheapest, \"at\", tags[cheapest])` — and rerun the honest town. Compare the announcements with the final notebook: they agree perfectly, every time, on every honest map (that agreement *is* the deep-water theorem talking). Now build the chapter's Problem 3.3 graph using Break-it 1's one-way doors — `{\"Home\": [(\"B\", 2), (\"C\", 3)], \"B\": [], \"C\": [(\"B\", -2)]}` — predict the announcements, and run it. Catch the exact moment the algorithm publicly settles a lie (which vertex, announced at what price, versus the truth you can see by eye?). Then two follow-ups: (a) point to the clause of the deep-water proof that this graph kills, quoting it; (b) the *final* notebook actually shows the right number anyway — find the line of our code that quietly forgave the lie after the announcement, and explain why you still must not trust this on bigger graphs (what if the lying vertex's wrong tag had been used to relax *its* neighbors before the correction arrived?). One warning while experimenting: keep negative edges one-way here. A negative *two*-way road lets a walker pace back and forth earning money forever, and \"cheapest route\" stops meaning anything — the question itself, not just the algorithm, dies. (Restore the town when done; it has suffered enough.)\n", "\n", "**4.** *The knight's ripple* (finishing Problem 2.5). A chessboard is rows and columns 0–7; a knight at (r, c) can jump to eight positions: (r±1, c±2) and (r±2, c±1), board permitting. Adapt `maze_bfs` — same skeleton, different neighbor list, and the \"board permitting\" check is Break-it 2's repair earning rent. Compute the fewest moves from (0, 0) to (7, 7), compare with the prediction you wrote in the problem set, and then print the full `dist` notebook and find the squares that are *hardest* for a corner knight to reach. Are they where you'd have guessed?\n", "\n", "\n", "\n", "
" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }