Esme Povirk @madewokherd@computerfairi.es

@viridian Is this approach still going to work when I start randomizing land unlock requirements (which means I have to calculate reachability)?

The naive algorithm is not as slow as I expected, in this case. I suspect that in other cases we'll have a problem.

So, I still have no good solution. I guess we go naive for now.

Turns out I do not understand this as well as I thought. PlaceOrbsInLands in this example (even though that's not quite how I actually wrote it) has a probability of failure that's proportional to the ideal failure probability, for one step, but it's lower than that ideal. For it to be the same, we'd have to stop everything immediately after encountering any failure. But, if it is the same, we end up with an equivalent of trying every permutation.

And now I have to rewrite my placement algorithm because I realized while writing this that I took some shortcuts that may not be valid.

This is actually easy. The probability of stopping based on this specific orb that we placed should be 1/N * (probability of a valid combination based on having placed that orb). Well, the probability of PlaceOrbsInLands failing is equal to the second term in that multiplication, so we can treat this the same as an invalid pairing. It doesn't really matter that there might be some valid ones.

OK, so what if an orb placement succeeds? We still have to place the rest of them. For that, we call PlaceOrbsInLands for our remaining set of lands and orbs. If it succeeds, great. We add the one pair placed in this step, and return the list.

If it fails, we need to decide whether to stop at this step. We want to do that in such a way that the overall probability of returning failure is proportional to the number of valid permutations given our input state.

If we move on to trying a second orb after a failure, and that one also fails, we should return failure a total of 2/N of the time. But we already did the 1/N check, so at this stage we should return failure 1/(N-1) of the time, to increase the total probability to where we need it.