Is the two-color leapfrog problem in P?

My question is whether a specific decision problem is in P or not. It’s straightforwardly in NP. The decision problem is a specific case of the general $k$-color leapfrog problem.

I can already show that when $k=1$, the problem is in P. And when $k$ is unlimited, the problem is NP-complete. I have not been able to find an algorithm for the $k=2$ case, but I suspect it is in P. I am wondering if we can prove that it is in P, or (what would surprise me) that it is in fact NP-complete.

This question springs from an interesting discussion in a question I previously asked on this site.

The $k$-color leapfrog problem. Fix $k$. In a $k$-color leapfrog problem, you are given some number of transparent urns containing colored balls. Each ball is one of $k$ possible colors. You are also supplied with an agenda, which is an ordered list of colors, for example "red, red, red, blue, red, green, …". The object of the game is to draw balls out of the urns, one at a time, following the sequence of colors specified in the agenda. You can easily see the contents of all urns at all times, and can draw any ball out at will. If you could draw the appropriate color from multiple urns, you may choose which one. The only constraint is that you may not draw from the same urn twice in a row. You win the game if you complete the agenda, otherwise you lose.

The decision problem is whether, for a given arrangement of urns and a given agenda, the game is winnable.

The 1-color leapfrog problem is in P. If there is only one color of ball, you can decide it with the following algorithm: at each turn, draw the ball from the urn with the most balls in it (among urns you’re allowed to draw from). If the game is winnable at all, this algorithm will win it. (Note that even when $k=1$, a game may still be unwinnable if there’s too great a disparity in ball count. For example, the setup ["R", "RRR"] with the agenda "RRRR" is unwinnable.)

The $infty$-color leapfrog problem is NP-complete. See my previous question and the dazzling solution provided. You can perform a reduction from SAT using a game with two new urns and three new colors per clause.

What about 2-color leapfrog? This is my main question. I suspect the problem is in P, as with the 1-color case, but the 1-color algorithm doesn’t seem to generalize — or at least I’m not sure.

Bonus: What about $k$-color leapfrog? An interesting higher level question is where exactly the problem becomes hard. Is is still in P when $k=3$, or does the leapfrog game have a phase transition like 2SAT to 3SAT? Is perhaps in P for all finite $k$? I’ve been struggling to find an efficient algorithm— I suspect there might be one, just based on how the problem becomes smaller and smaller as you remove balls.

---

Edit : The naive extension does not work. Note that the "leveling" strategy — generally ensuring that the urns have approximately the same number of balls of each color by removing from the urn that has the most— perfectly solves the $k=1$ case. I expect finding an extension of this strategy will solve the $k=2$ case, but note that one naive extension does not work:

For the scenario where the urns contain [AAB, ABB] and the agenda requires AABBBA, the naive strategy of taking from the legal urn with the most of the requested color does not work. It fails to find a solution despite the fact that this instance is actually solvable. (Similarly, the strategy of taking each color from the urn that has the least amount of the other color also fails on this problem instance.)

---

Update: In the special case that the agenda has the form $A^m B^n$ $(m,ngeq 1)$, you can determine whether it’s solvable in polynomial time by playing two single-color games in series. Briefly put, a single-color game is winnable if and only if the vase with the most balls has at most one more ball than the rest of the vases put together. Equivalently, it’s winnable if and only if you can pair up each ball with a ball from another vase, with at most one left over. You can construct a winning sequence of moves given such a pairing: first draw the unpaired ball if any. Then iterate over each pair in an arbitrary order. Because the pairs come from different vases, at least one of them will be legal to draw next; draw it, then the other one. Proceed until you draw all the balls.

Because you can iterate over the pairs in an arbitrary order, you can generally always choose a drawing order such that the last ball comes from the vase of your choice. Or, reversing the drawing order*, that the first ball comes from the vase of your choice. Hence in the two-color scenario, when the agenda is $A^mB^n$, you can solve it as follows: Pick a vase $V_A$ with an $A$-colored ball and another vase $V_B$ with a $B$-colored ball (if you can’t, then there’s only one vase and it has multiple balls in it, so the game is unwinnable). If it’s possible to win the $A^m$, choose the winning strategy to draw from $V_A$ in the last step. If it’s possible to win the $B^n$ game, choose the winning strategy to draw from $V_B$ in the first step. This can all be done and checked in polynomial time, QED.

[*] Actually, reversing a path is not always possible: if the vase with the largest amount has exactly one more ball than the rest of them put together, then you must draw from the largest vase first. The proof for how to solve $A^mB^n$ in this case will have to wait.

---

Update: By exchanging the notion of urns and colors, you can get the following equivalent formulation:

Reformulated leapfrog problem: Fix $k$. You are given $k$ urns full of different-colored balls, and an agenda which tells you which urn you must draw from at each step. Your goal is to empty all of the urns subject to the constraint that each ball must be a different color from the one before it.

Perhaps rephrasing this way can be useful. Also in this reformulation, I think the complexity is exposed by supposing you have two urns, where the second urn contains at most two balls.