Turning the alleys round

Barrows run one way down every alley in the market. The office will turn an alley round if it has to, and wants to sign as few orders as it can.

The problem

The market has stalls stalls numbered 0 to stalls - 1, joined by alleys. An alley [start, end] may be pushed from start to end only. One signed order turns an alley round for good.

A barrow leaves the gate for one stall. Report the fewest orders that give it a route, -1 if no run of alleys joins the two.

Input. stalls — an integer. alleys — a list of [start, end]. gate, target — two stall numbers.

Output. The fewest orders, or -1.

Example.

stalls = 4, alleys = [[0, 1], [1, 2], [3, 2]], gate = 0, target = 3   ->  1

The barrow runs 0 to 1 to 2 with the flow. The last alley faces the wrong way, so one order turns it and the barrow gets to stall 3.

A second example, where the shorter route is the dearer one:

stalls = 5, alleys = [[0, 1], [2, 1], [0, 3], [3, 4], [4, 2]], gate = 0
target = 2   ->  0

Two alleys reach stall 2 by way of stall 1, but the second faces the wrong way. Three by way of stalls 3 and 4 all face the right way and cost nothing.

Constraints.

• 1 <= stalls <= 10^5 and 0 <= len(alleys) <= 2 × 10^5
• 0 <= start < stalls, 0 <= end < stalls, and an alley may be listed twice
• 0 <= gate < stalls, 0 <= target < stalls

Hints

Approach

Brute force

Try the subsets of alleys to turn. Even the cut-down version — turn one alley, re-run a reachability check, repeat — costs 2 × 10⁵ × 3 × 10⁵ = 6 × 10¹⁰ steps and only finds an answer of 1.

The insight

Read each alley as two moves — free with the flow, one order against it — and a deque keeps the frontier sorted, a 0 at the front and a 1 at the back.

The queue then holds at most two order counts, the smaller in front — the property a breadth-first queue has when every step costs 1. Stalls still leave it in non-decreasing order, with no heap and no log factor.

Algorithm

1. For each alley [start, end], record a move start -> end at cost 0 and end -> start at cost 1.
2. Set every count to infinity, the gate to 0, and put the gate in a deque.
3. Pop from the front. For each move out, if the popped count plus the cost beats the neighbour's, write it and push the neighbour — at the front for a cost of 0, at the back for 1.
4. Return the target's count, or -1 if it is infinite.

Complexity

Time O(stalls + alleys) — each alley makes two moves and a count falls at most twice: 6 × 10⁵ steps, not 6 × 10¹⁰. Space O(stalls + alleys) — the moves and the deque.

Solution

"""Turning the alleys round — a deque, because an alley costs 0 with the flow and 1 against it."""

from collections import deque


def solve(stalls, alleys, gate, target):
    moves = [[] for _ in range(stalls)]
    for start, end in alleys:
        moves[start].append((end, 0))   # with the flow: no order needed
        moves[end].append((start, 1))   # against it: one order to turn the alley round

    INF = float('inf')
    orders = [INF] * stalls
    orders[gate] = 0
    queue = deque([gate])
    while queue:
        # Invariant: the queue holds at most two order counts, the smaller at the front,
        # so a stall still leaves it in non-decreasing order without a heap.
        stall = queue.popleft()
        for nxt, cost in moves[stall]:
            if orders[stall] + cost < orders[nxt]:
                orders[nxt] = orders[stall] + cost
                if cost == 0:
                    queue.appendleft(nxt)
                else:
                    queue.append(nxt)

    return -1 if orders[target] == INF else orders[target]

TESTS = [
    ((4, [[0, 1], [1, 2], [3, 2]], 0, 3), 1),
    ((5, [[0, 1], [2, 1], [0, 3], [3, 4], [4, 2]], 0, 2), 0),  # three free alleys beat two
    ((3, [[0, 1]], 0, 2), -1),                                 # no alley touches stall 2
    ((3, [[0, 1], [1, 2]], 0, 0), 0),                          # already at the gate
    ((3, [[1, 0], [2, 1]], 0, 2), 2),                          # every alley faces the wrong way
    ((4, [[0, 1], [1, 2], [2, 3], [0, 3]], 0, 3), 0),
    ((2, [[1, 0], [1, 0]], 0, 1), 1),                          # the same alley written twice
    ((3, [[1, 0], [0, 2], [2, 1]], 0, 1), 0),                  # the free route is found second
]

Pitfalls

• Pushing every move at the back. The deque degrades to a queue mixing the two batches, so routes come out ranked by alley count, not orders.
• Marking a stall settled when it is queued. With alleys [[1, 0], [0, 2], [2, 1]] and the gate at 0, stall 1 is queued at one order before the free route through stall 2 is found: a queue-time mark prices it 1 instead of 0.
• Recording only the against-the-flow move. Turning an alley the barrow can already use is wasteful: the first example then costs 3.

Variants

• Word from the fire towers — the same frontier, sorted by a heap because the weights are arbitrary.
• Shortest paths — the question about the weights that picks between queue, deque and heap.