Okay, so my initial read on this is it's simply doing a bubble sort, you can move one item at a time and bubble it up or down to change the priorities. If that's the case, our worst case complexity is the same as bubble sort, which would be n-1 moves, or (p*h)-1 where p = num players and h = num hatches.
However, there are a couple different interpretations here that still fulfill the criteria of the problem, and it has to do with how strict we want the ordering. There's two variables we can tweak that give us slightly different scenarios:
Strict player orders: Do we care that player A always comes before player B?
Strict hatch order: Do we care what order the hatches release as long as they are synced for all players?
For example, this arrangement fulfills the original reqs if we don't need strict ordering for either:
B2 A2
B3 A3
B1 A1
I'm assuming here that we probably want non-strict player order (player order doesn't really have meaning since player order is random on level start) but strict hatch ordering (we want the level to spawn from top-down). Given that, we have a bit more control over the bubble sort. The worst case is still an inverted list, like so:
B2, A2, B1, A1
However, since we don't care about player order, we don't actually need to reorder B2 and A2, so instead of a worst case of 3 our worst case is only 2, to move B1 and A1 to the front (or B2 and A2 to the back, if you'd prefer
)
Best as I can tell, the worst case complexity for this scenario is equal to p(h-1). No matter the original sort order, we can always ignore one group of hatches and use their player order for the other hatches as we move them around.
Now, in the very non-strict case where we don't care about player order OR hatch order, our worst case changes yet again. Now an inverted case isn't strictly worst because we don't care about the hatch order, we just need to group the same hatches with the same player order, so I think worst case becomes hatches grouped by player (A1, A2, A3, B1, B2, B3). To me, this seems like the most complex to try and find the formula for. because it's weird to think of scenarios, but I think that it ends up being (p-1)(h-1).
That also makes me assume if you wanted to keep player strict but hatch non-strict, it would be (p-1)h, but I honestly haven't checked that at all and am just assuming based on the other formulas I came up with.
Hopefully my interpretation is correct here? I think that no matter how you slice it it should be reducible to a list so I assume it should be a valid line of reasoning.
You could make this even more complicated if you consider that it's easier to change the priority in the text file directly, which allows you to move adjacent hatches up/down at the same time with copy/paste. My gut says worst case would still be arranged in a way where you're moving single items at once, but I haven't thought much about it.
