Python Tuple State Keys for DSA

Why This Matters

Many algorithm states are compound values: (row, col), (node, mask), (distance, counter, node), or (i, remaining). Python tuples make those states hashable, sortable, and easy to pass around.

The point is not to use tuples everywhere. The point is to know when a fixed immutable record is the right state key.

Core Idea

A tuple is an immutable ordered record. It can be used as a dictionary or set key when all of its elements are hashable.

Pattern	Tuple shape	Typical use
Coordinate	`(row, col)`	grids, visited sets
Memoization	`(i, remaining)`	dynamic programming cache
Graph state	`(node, mask)`	shortest path with extra state
Heap tie-breaker	`(priority, counter, item)`	stable priority queue entries
Sort key	`(primary, secondary)`	explicit multi-field ordering

Non-Example or Failure Mode

([1, 2], 3) cannot be a dictionary key because the list inside the tuple is mutable and unhashable. Tuple hashability depends on the elements, not only the outer container.

Worked Example

In a shortest-path search with extra state, the node alone is not enough. If the state also depends on a collected-key mask, use both:

state = (node, mask)
seen.add(state)

This prevents incorrectly merging visits that reached the same node with different resources.

Common Mistakes

Mistake	Correction
Using a list as a dict key.	Use a tuple if the state is fixed.
Assuming every tuple is hashable.	All contained values must also be hashable.
Forgetting tuple ordering in heaps.	If priorities tie, Python compares the next tuple fields.
Putting unorderable objects after priority.	Add a numeric counter before the payload.
Merging graph states too aggressively.	Include every state variable needed by future transitions.

Diagnostic Questions

Question type	Question	Answer signal
Definition	Why can tuples often be dict keys?	They are immutable and hashable when their elements are hashable.
Example / non-example	Can `([1], 2)` be a key?	No. The nested list is unhashable.
Computation	How are tuples ordered?	Lexicographically by field from left to right.
Transfer	Why use `(priority, counter, item)` in a heap?	The counter breaks ties before Python compares the payload.

Runnable Drill

Python tuple state key drill

Checks tuple keys, memoization state, coordinate states, tuple ordering, and heap tie-breakers.

Output will appear here.

Exercises

Beginner:

Store visited grid coordinates as (row, col) tuples.
Sort intervals by (start, end).
Explain why lists cannot be dictionary keys.

Intermediate:

Memoize a recursive function using (index, remaining) as the state key.
Build a heap entry with (priority, counter, payload) and explain the counter.

Challenge:

Solve a graph search where the state is (node, mask), not just node.

Diagram Recommendation

Type: state-key decomposition.

Caption: "A state key such as (node, mask) separates location from resources collected so far."

Purpose: Prevent learners from collapsing distinct states into one visited marker.

Next Topics

References

Python documentation. Tuples and sequence types: https://docs.python.org/3/library/stdtypes.html#tuples
Python documentation. Data structures tutorial: https://docs.python.org/3/tutorial/datastructures.html
Python documentation. heapq priority queue notes: https://docs.python.org/3/library/heapq.html#priority-queue-implementation-notes