Pebellslearn by building
0%
RoadmapMatrixCatalogSandboxSign in
Recursion, Searching & Sorting  ›  Capstone Project

Capstone — Smart Shuffle

35 minFlatten, sort and search together to build a shuffle that never repeats an artist back to back
You're building a piece ofTunebox — search & charts
This piece — smart_shuffle(): Orders a library so the same artist never plays twice in a row.
Scenario A listener's road-trip folder is half Kai. Plain shuffle keeps playing Kai back to back; Smart Shuffle flattens the folder and spreads each artist out — and when that's impossible, it only doubles up at the very end.
Your task
Build smart_shuffle(playlist). A playlist is a list of tracks {"title", "artist"} and nested sub-playlists, to any depth. Return every title in play order: flatten the playlist; each artist's tracks play in title order A→Z; at each step play the next track of the artist with the most tracks left, skipping the artist who just played, with ties going to the artist name that comes first A→Z. If the only artist left is the one who just played, their remaining tracks play back to back. Example: smart_shuffle([{"title": "Dawn", "artist": "Kai"}, [{"title": "Aria", "artist": "Kai"}, {"title": "Blue", "artist": "Mo"}]]) → ["Aria", "Blue", "Dawn"].

Capstone — Smart Shuffle

Hit shuffle on a playlist that's half one artist and you will hear three of their songs in a row. Tunebox's Smart Shuffle promises something better: the same artist never plays twice in a row whenever that's possible — and when it isn't, it says exactly what happens. Building it takes everything in this section: recursion to flatten nested playlists, sorting to put tracks and artists in order, and binary search to keep the "who plays next" queue sorted.

What you're building

smart_shuffle(playlist)  ->  list of titles, in play order

A playlist is a list of tracks — {"title": ..., "artist": ...} — and nested sub-playlists, to any depth. The rules, in order:

  1. Flatten every track out of the nested playlists.
  2. Each artist's own tracks play in title order A→Z.
  3. At each step, play the next track of the artist with the most tracks left, skipping the artist who just played. Ties go to the artist whose name comes first A→Z.
  4. Fallback: if the only artist with tracks left is the one who just played, their remaining tracks play back to back.

The same input always produces the same order — no randomness, so it can be tested and trusted.

Step 1 — flatten (recursion)

The nested-playlist walk from the first lesson, with track dicts as the leaves:

python

Step 2 — group, then sort

Group titles by artist and sort each group. Then order the artists themselves: a tuple (-tracks_left, artist) sorts most-tracks-first, ties A→Z — the trick from Top picks.

python
What does this print?
counts = {"Mo": 2, "Kai": 3, "Lu": 2}
queue = sorted((-n, artist) for artist, n in counts.items())
print([artist for _, artist in queue])

When is it even possible?

Between any two tracks by Kai, at least one other track has to play. So Kai's k tracks need k − 1 separators from everyone else. With n tracks in total, that works exactly when the biggest artist has at most (n + 1) // 2 of them.

What does this print?
def possible(counts):
    n = sum(counts)
    return max(counts) <= (n + 1) // 2

print(possible([3, 1, 1]), possible([3, 1]))

Step 3 — the pick, with a sorted queue

Why "most tracks left" first? The biggest artist is the one in danger of running out of separators, so spend their tracks early while there are others to put between them. Always choosing that way is guaranteed to avoid back-to-back whenever it's possible.

Keep the queue sorted so the best artist is at the front. If the front artist just played, take the second. After playing, that artist has one track fewer — so take their entry out and put it back where it now belongs. bisect.insort finds that spot with a binary search.

step through it
1from bisect import insort
2queue = [(-2, "Kai"), (-1, "Mo")]
3order, last = [], None
4while queue:
5 pick = 1 if queue[0][1] == last and len(queue) > 1 else 0
6 left, artist = queue.pop(pick)
7 order.append(artist)
8 last = artist
9 if left + 1 < 0:
10 insort(queue, (left + 1, artist))
11print(order)

left is negative, so left + 1 is one track fewer, and left + 1 < 0 means "still has tracks". Here is the same loop with one slip in the skip check:

broken — fix it

This should print Kai, Mo, Kai. It prints Kai twice in a row — the "skip whoever just played" check never fires.

Step 4 — the fallback

When only the artist who just played is left, len(queue) > 1 is false, so pick stays 0 and they play again. That gives the fewest back-to-backs possible: biggest − everyone_else − 1.

python
step cost (n tracks, a artists)
flatten O(n · depth) with extend
group, sort each artist's titles O(n log n)
build the sorted queue O(a log a)
each pick + insort O(log a) to search, O(a) to shift the list
whole shuffle O(n log n + n · a)

Idioms & real-world patterns

Why not Counter.most_common()?

It orders by count — but ties come out in the order artists were first seen, not A→Z. Deterministic output means stating the tie rule and encoding it, which the (-count, artist) tuple does.

python

⚡ Advanced — a heap does the queue's job

insort shifts the list on every insert: O(a). A heap (next section) pops the best item and pushes one back in O(log a). The trick is to hold back the artist who just played for one turn:

python

🎯 Your turn

Write smart_shuffle(playlist): flatten the nested playlist, sort each artist's titles A→Z, then repeatedly play the next track of the artist with the most tracks left — skipping whoever just played, ties A→Z by artist — falling back to back-to-back only when no one else is left.

  • smart_shuffle([{"title": "Dawn", "artist": "Kai"}, [{"title": "Aria", "artist": "Kai"}, {"title": "Blue", "artist": "Mo"}]]) → ["Aria", "Blue", "Dawn"]
  • smart_shuffle([{"title": "Aria", "artist": "Kai"}, {"title": "Blue", "artist": "Kai"}]) → ["Aria", "Blue"] (the fallback)

Hint — reuse flatten, build by_artist, keep (-left, artist) tuples in a sorted list, and insort each artist back after they play.

Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. All green = Section 3 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-upCan it be spread?

artists lists the artist of every track in a queue. Write can_spread(artists) returning True if the tracks can be ordered so the same artist never plays twice in a row, False otherwise. An empty queue is True.

frequency-countmaxconditionals
DrillGroup and sort

Each track is {"title", "artist"}. Write titles_by_artist(tracks) returning a dict mapping every artist to a list of their titles sorted A→Z.

groupingsorting
BuildEven slots first

Write interleave_spread(artists) using a different construction: count each artist's tracks; list the artists by count high→low, ties A→Z; write out each artist's plays in that order (all of the first artist's, then the next…); then place those plays into positions 0, 2, 4, … and after that 1, 3, 5, …. Return the resulting list of artists. If no order without back-to-back exists, return [] (an empty queue also gives []).

sortingfrequency-countindex
BossHow many smart orders?

artists lists the artist of every track. Write count_shuffles(artists) returning how many different sequences of artists have no artist twice in a row. Tracks by the same artist count as identical here, so ["Kai", "Kai", "Mo"] has exactly one: Kai, Mo, Kai. An empty list has one sequence (the empty one).

recursiontree-recursionfrequency-count
CapstoneMaximum artist spacing

Smart Shuffle Pro spreads artists as far apart as it can. For an ordering, the spacing is the smallest distance (difference in positions) between two tracks by the same artist. Write max_spacing(artists) returning the largest spacing any ordering can achieve. If no artist has more than one track, return len(artists). max_spacing(["Kai", "Kai", "Mo", "Mo", "Lu"]) → 3 (Kai, Mo, Lu, Kai, Mo).

binary-searchfrequency-countsearching
smart_shuffle.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
smart_shuffle(playlist) → listEvery title in a play order where no artist plays twice in a row, unless nobody else is left.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.