Pebellslearn by building
0%
RoadmapMatrixCatalogSandboxSign in
Graphs  ›  Capstone Project

Capstone — Recommendations

30 minTurning graph walks into suggestions
You're building a piece ofTunebox — recommendations
This piece — recommend_for(): Suggests tracks from what nearby listeners play.
Scenario Ana's Discover page fills with tracks her network plays — weighted so a close friend's favourite counts for more than a stranger's three follows away.
Your task
Build recommend_for(follows, plays, listener, max_hops). `follows` is the follow graph (an adjacency dict; a name with no key follows nobody) and `plays` maps listeners to the tracks they play. Walk the follows breadth-first from `listener`; every listener d hops away (1 ≤ d ≤ max_hops) adds max_hops − d + 1 to each track they play, skipping tracks `listener` already plays. Return [track, score] pairs, highest score first, ties alphabetically. Example: with follows {"ana": ["ben", "cal"], "ben": ["dia"], "cal": ["dia"], "dia": ["ana"]} and plays {"ana": ["Glow"], "ben": ["Drift", "Glow"], "cal": ["Drift"], "dia": ["Aura"]}, recommend_for(follows, plays, "ana", 2) → [["Drift", 4], ["Aura", 1]].

Capstone — Recommendations

Ana's Discover page should fill with tracks her network plays — and a track her close friends love should outrank one that a stranger three follows away happens to have on repeat. That's the whole section in one feature: a graph of follows, a traversal that finds who's nearby and how near, and a ranking built from what they play. You've written every piece already. Now wire them into Tunebox's recommender.

What you're building

recommend_for(follows, plays, listener, max_hops)
  • follows — the follow graph, an adjacency dict. A name with no key follows nobody.
  • plays — each listener's tracks, e.g. {"ben": ["Drift", "Glow"]}. No repeats within one list; a listener with no key plays nothing.
  • listener — who the recommendations are for.
  • max_hops — how far out to look.

The rules, in order:

  1. Walk the follows breadth-first from listener, out to max_hops hops.
  2. Every listener found at distance d (1 ≤ d ≤ max_hops) has a weight of max_hops - d + 1 — direct follows count most.
  3. Each of those listeners adds their weight to every track they play — except tracks listener already plays.
  4. Return [track, score] pairs, highest score first, ties alphabetically.

Here's the example, worked by hand, with max_hops = 2:

Listener Hops from ana Weight Plays Adds
ben 1 2 Drift, Glow Drift +2 (Glow skipped — ana plays it)
cal 1 2 Drift Drift +2
dia 2 1 Aura Aura +1

So recommend_for(follows, plays, "ana", 2) → [["Drift", 4], ["Aura", 1]].

Step 1 — find the neighbourhood

This is BFS from the BFS lesson, with one addition: don't expand anyone who is already max_hops out. The hops dict records distance and doubles as the visited set, so follow loops can't send you round forever.

python

One thing to notice before you use that dict:

What does this print?
from collections import deque
follows = {"ana": ["ben", "cal"], "ben": ["dia"], "cal": ["dia"], "dia": ["ana"]}
hops = {"dia": 0}
queue = deque(["dia"])
while queue:
    name = queue.popleft()
    if hops[name] >= 2:
        continue
    for nxt in follows.get(name, []):
        if nxt not in hops:
            hops[nxt] = hops[name] + 1
            queue.append(nxt)
print(sorted(hops))

Step 2 — closer listeners count more

A direct follow is a deliberate choice; a friend-of-a-friend is a weaker signal. The weight max_hops - d + 1 turns distance into influence: with max_hops = 3, direct follows weigh 3, the next ring 2, the outermost 1. Step through it:

step through it
1hops = {"ana": 0, "ben": 1, "cal": 1, "dia": 2}
2max_hops = 2
3weights = {}
4for name, distance in hops.items():
5 if distance > 0:
6 weights[name] = max_hops - distance + 1
7print(weights)

❓ Cross-question — "Why not just count how many nearby listeners play each track?" Then a hundred strangers two hops away drown out your three closest friends. Weighting by distance is the simplest way to say who recommends something matters, not just how many.

Step 3 — tally the votes

Add each listener's weight to each of their tracks. A track the listener already plays isn't a discovery, however popular it is nearby. This tally forgets that:

broken — fix it

This should score only tracks new to ana — Drift 4 and Aura 1 — but Glow sneaks in with 2. Fix the tally.

A set of the listener's tracks makes that check O(1) per track, however long their history.

Step 4 — rank

Highest score first, ties alphabetically — one sort with a two-part key. Negating the score sorts it high-to-low while the name still sorts A-to-Z:

What does this print?
scores = {"Zen": 2, "Echo": 3, "Bloom": 2}
ranked = sorted(scores.items(), key=lambda item: (-item[1], item[0]))
print([track for track, _ in ranked])

Turn each (track, score) tuple into a [track, score] list on the way out — tuples aren't equal to lists, and the grader compares lists.

What it costs

Stage Cost
Neighbourhood BFS O(V + E) of the part of the graph within max_hops
Weights and tally O(total tracks played by that neighbourhood)
Own-track check O(1) per track, with a set
Ranking O(K log K) for K candidate tracks

Idioms & real-world patterns

Counter for tallies — but not for tie-breaking

collections.Counter adds weighted votes neatly. Its most_common() breaks ties by first insertion, though, which depends on traversal order — so sort explicitly when the order has to be deterministic:

python

Choosing a decay

Linear decay is easy to reason about. Real systems often halve the weight per hop so far-away listeners fade faster:

python

This family of techniques — recommend what similar or connected people like — is collaborative filtering. The graph version you're building is its most direct form.

⚡ Advanced — taste distance instead of hops

Hops treat every follow as equally close. If links carried a taste gap — small when two listeners' histories overlap a lot — the neighbourhood becomes "everyone within a total gap of r", which is a shortest-path question, not a hop count. The recommender's shape doesn't change: find the neighbourhood, weight by closeness, tally, rank. Only step 1 swaps BFS for Dijkstra.

⚡ Advanced — why real recommenders cap the radius

With each listener following about b others, the neighbourhood grows like b^d. At b = 200, three hops is already 8 million listeners — for one Discover page. Production systems keep max_hops tiny, sample the neighbourhood, or precompute scores offline. And a brand-new listener who follows nobody gets nothing from this approach at all — the cold-start problem — so real apps fall back to charts.

🎯 Your turn

Write recommend_for(follows, plays, listener, max_hops):

  1. BFS the follows from listener, out to max_hops hops.
  2. Every listener d hops away (1 ≤ d ≤ max_hops) adds max_hops - d + 1 to each track they play, skipping tracks listener already plays.
  3. Return [track, score] pairs, highest score first, ties alphabetically.

With follows = {"ana": ["ben", "cal"], "ben": ["dia"], "cal": ["dia"], "dia": ["ana"]} and plays = {"ana": ["Glow"], "ben": ["Drift", "Glow"], "cal": ["Drift"], "dia": ["Aura"]}:

  • recommend_for(follows, plays, "ana", 2) → [["Drift", 4], ["Aura", 1]]
  • recommend_for(follows, plays, "ana", 1) → [["Drift", 2]] — with one hop, every direct follow weighs 1

Hint — reuse your BFS from the BFS lesson, tally into a dict, and sort with the key (-score, track).

Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. All green = Tunebox's recommendations are live — and the Graphs section is complete. 🎉

Practice — level up

0/5 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upWho's nearby

Stage one of the recommender. Write hop_map(follows, listener, max_hops) returning a dict of every listener within 1 to max_hops follow hops of listener, mapped to their hop count — never listener themselves. A name with no key in follows follows nobody. Example: {"ana": ["ben", "cal"], "ben": ["dia"], "cal": ["dia"], "dia": ["ana"]}, "ana", 2 → {"ben": 1, "cal": 1, "dia": 2}.

bfsvisited-setdict
DrillCount the votes

Write track_votes(plays, listeners) — plays maps listeners to the tracks they play (no repeats per listener) — returning a dict counting how many of the given listeners play each track. A listener missing from plays plays nothing. Example: {"ben": ["Drift", "Glow"], "cal": ["Drift"]}, ["ben", "cal"] → {"Drift": 2, "Glow": 1}.

frequency-countdict.get
BuildWho to follow

'Who to follow' suggests listeners that the people you follow also follow. Write who_to_follow(follows, listener) returning every listener followed by someone listener follows — excluding listener and anyone they already follow — ranked by how many of the people listener follows follow them (most first, ties alphabetically). A name with no key follows nobody. Example: {"ana": ["ben", "cal"], "ben": ["dia", "eli"], "cal": ["dia"]}, "ana" → ["dia", "eli"].

graphsorted-keydict.get
BossClosest fan

When ana opens a track, Tunebox shows 'played by someone you follow'. Write closest_fan(follows, plays, listener, track) returning [name, hops] for the listener nearest to listener in the follow graph who plays track — never listener themselves. If several fans are equally near, pick the alphabetically first. Return [] if no reachable listener plays it. A name with no key in follows or plays follows or plays nothing.

bfsvisited-setsorted
CapstoneRecommendations by taste distance

Upgrade the recommender with taste distance. links is an undirected weighted edge list — [a, b, gap], where a smaller positive gap means more similar taste — and a listener's distance is the cheapest total gap from listener. Write affinity_recs(links, plays, listener, radius): every other listener at distance d ≤ radius adds radius - d + 1 to each track they play; skip tracks listener already plays; return [track, score] pairs, highest score first, ties alphabetically. A listener missing from plays plays nothing.

dijkstraweighted-graphsorted-key
recommend_for.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
recommend_for(follows, plays, listener, max_hops) → listRecommended [track, score] pairs from nearby listeners, best first.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.