Starting from start, the rings of a graph are: ring 0 is [start]; ring 1 holds every node one step away; ring k + 1 holds the nodes that are one step from a node of ring k and do not appear in any earlier ring. The graph is given as a function: neighbours(node) returns a list of the nodes one step from node (it may contain duplicates, or node itself).
Write a generator rings(start, neighbours) that yields the rings one at a time, each as a sorted list. When a ring would be empty, the generator stops. The graph may be endless, so the generator must not look further than it has been asked to: the neighbours of ring k's nodes may only be asked for when ring k + 1 is requested.
Helpers available with Run: first(gen, n), grid_steps (an endless square grid of (x, y) points), knight_on(n) (knight moves on an n-by-n board) and asks_needed(rings, start, neighbours, k), which counts the calls to neighbours while the first k rings are taken.
Examples
Input: first(rings(1, lambda x: [x + 1, 2 * x]), 4)
Output: [[1], [2], [3, 4], [5, 6, 8]]
Input: first(rings("a", lambda s: {"a": ["b", "c"], "b": ["a"], "c": ["c", "d"]}.get(s, [])), 10)
Output: [["a"], ["b", "c"], ["d"]]
Input: asks_needed(rings, 1, lambda x: [x + 1, 2 * x], 4)
Output: 4
Explanation: rings 1, 2 and 3 need the neighbours of 1, of 2, and of 3 and 4.
Constraints
- Nodes are hashable and comparable with each other (numbers, strings or tuples).
- The tests take at most a few thousand nodes in total.
Goals
- Write a generator that yields whole layers of a search, one per request
- Take the graph as a function, so it can be endless
- Do only the work the caller has asked for so far