Only the number of shuffles is linear. Shuffling an array and marking/deleting correctly-placed elements still take linear time even with a "placement oracle." It's at best O(n^2) so the algorithm still wouldn't be a good sorting algorithm.

It's like doing selection sort, except we're selecting a random set of elements (from that poisson distribution) instead of the smallest one.

I'm not sure the median is what you want. The worst case behavior is unbounded. There is no guarantee that such an algorithm ever actually terminates, and in fact (with very low probability) it may not! But that means there is no well-defined median; we can't enumerate the space.

So let's instead ask about the average, which is meaningful, as the increasingly high iteration-count datapoints are also decreasingly likely, in a way that we can compute without trying to enumerate all possible sequences of shuffles.

Consider the problem like this: at every iteration, remove the elements that are in the correct positions and continue sorting a shorter list. As long as we keep getting shuffles where nothing is in the correct position, we can go forever. Such shuffles are called derangements, and the probability of getting one is 1/e. That is, the number of derangements of n items is the nearest integer to n!/e, so the probability of a derangement would be 1/n! * [n!/e]. This number converges to 1/e incredibly quickly as n grows - unsurprisingly, the number of correct digits is on the order of the factorial of n.

We're now interested in partial derangements D_{n,k}; the number of permutations of n elements which have k fixed points. D_{n,0} is the number of derangements, as established that is [n!/e]. Suppose k isn't 0. Then we can pick k points to be correctly sorted, and multiply by the number of derangements of the others, for a total of nCk * [(n-k)!/e]. Note that [1/e] is 0, indeed, it's not possible for exactly one element to be out of place.

So what's the probability of a particular partial derangement? Well now we're asking for D_{n,k}/n!. That would be nCk/n! * [(n-k)!/e]. Let's drop the nearest integer bit and call it an approximation, then (nCk * (n-k)!)/(n! * e) = 1/(k!*e). Look familiar? That's a Poisson distribution with λ = 1!

But if we have a Poisson distribution with λ = 1, then that means that on average we expect one new sorted element per shuffle, and hence we expect to take n shuffles. I'll admit, I was not expecting that when I started working this out. I wrote a quick program to average some trials as a sanity check and it seems to hold.

Patrick's parabox?

I'm a bit confused by your comment. They say in their post that they will reevaluate when Lemmy's mod tools improve. More granular control over federation could help too. It's a temporary measure.

It's not like they're taking extreme action because they want to cause schisms. "They will defederate with everyone" only seems to apply if every other huge instance also has high numbers of trolls. Maybe not so unlikely, but mod tools on Lemmy will hopefully improve by then. Note: you sign up for beehaw's rules when you choose to interact on beehaw, not when you sign up to beehaw. The issue they are dealing with here is that they have had to disproportionately moderate users interacting on beehaw coming from those instances.

And at the end of the day, if beehaw becomes too isolated, it takes like 5 clicks to open a different instance in my browser and sign up there instead.

Lemmy specifically hasn't implemented less harsh measures yet. This is a stop-gap action to cut off a trolling problem at its source. The beehaw admins say they will reevaluate when less drastic tools are available, e.g. allow beehaw users to interact with lemmy.world but not the other way around.

I'm not sure I 100% agree, personally, but beehaw's ethos is "be(e) nice" and if trolls are trolling, it can make it very hard for some people to open up and contribute. So I see where it's coming from.

Shadow of the Colossus and Undertale.

Yeah, these are examples of the bad gameplay patterns I was referring to. One of them in particular (trying to be spoiler-light) provides you a ranged power... But you have to go to melee range to activate it. Whose idea was that?

I searched for it before posting the original comment and it appeared.

Casually, I enjoyed it a lot. It felt like better BOTW, with much more new stuff to explore than I expected. My only gripes where the delay on quick menus (botw did not have that, and it feels awful) and I generally think the sage mechanic leads to bad play patterns. But overall, it's amazing.

I've been involved in speedrunning both games. Versioning issues in TOTK are way worse. Movement tech in botw was a lot more interesting and varied, until windbombs were found anyway. The menu lag feels even worse while speedrunning. The stuff we've got for inside shrines is pretty cool, and there's some very cool out-of-bounds stuff found already. So it'll probably stay fresh for a while. I'm not sure if it'll hold me for as long as botw did though.

Search for [email protected] in Beehaw's search and it should come up. This initial search causes our instance to "federate" with that one.

However, if the instance you're searching for has been explicitly defederated with by Beehaw, you won't be able to see it here at all. We're federated with that instance already though, I thought, so it's strange that it wasn't showing up with other search terms.

As in could instances on different forks federate with each other? Sure. We already federate with mastodon instances and with kbin and other fediverse platforms. Having two versions of Lemmy is more an issue for maintenance, as well sharing new features and fixes between the forks.

To his credit, Ohanian hasn't been involved with reddit for a while. He and u/spez sold the company years ago, then spez came back.

I totally agree. Just want to point out you mean "raze." I was confused for a bit.

But that feels terrible if you want to follow them without stopping (or in the case of obstacles, are able to).

Even Ocarina of Time, in 1998, got this right. The Dampe race, which isn't technically an escort, would feel weird if Dampe was too much faster or slower than you, because it would feel unfair. But not everyone moves as fast while playing - some people like rolling, which is a different speed from walking, etc. Also, he throws fireballs at you, and players who are less good at dodging them will end up being slower. So Dampe doesn't "follow you," (in fact, he spends most of the thing in front of you), but he has a rubber band effect. If you get too far behind, he slows down. If you get too far ahead, he speeds up. This does a good job of keeping him in view, which helps give the feeling that you're going at an intended pace, whatever reasonable pace you take. If you're too slow, you will fail, but... it pretty much requires standing still or getting hit by lots of fireballs.

In contrast, the Yunobo escort in BOTW feels terrible casually and even worse to speedrun. He's faster than you walk, but much, MUCH slower than you run. And if you get too far ahead of him? He stops.

"Valid" and "disingenuous" mean very different things. How would you feel about editing that README point to be explicit that you use an unofficial undocumented YouTube API?

For the record, I don't think "InnerTube" would be considered unofficial, legally. It's authorized by YouTube, since they made and use it internally. That's the definition of "official." This is a small part of why I think the wording in the TOS makes the TOS apply to "InnerTube." What makes you think that it doesn't?

I've replied to that, I'm not satisfied. It's a bit of a wall of text though.

TL;DR: "clean room reverse engineering" has a specific definition and I don't believe it applies here. I do believe that the cited TOS applies to an internal API endpoint which is publicly accessible. Both things spell trouble.

I also take issue with the phrase "does not use official YouTube APIs" in the readme, but maybe that's pedantry between "official" and "documented."

That makes Invidious' readme (which claims no YouTube APIs at all) disingenuous at the very least.

More likely, you need a lawyer. I read that TOS, and I think it applies to any YouTube API endpoint, internal or otherwise. Best of luck, because I agree with Invidious' goals...

Side note: a browser communicating with YouTube would be communicating with youtube. Not with com.google.android.youtube.api or whatever. What I'm seeing is that Invidious tries to act like the youtube service itself, which is very different from acting like a browser.

Edit: I've spent about 5 minutes looking for EU case law about this but haven't been able to find anything except un-cited references to an exception for "producing interoperable devices." Do you have sources? In the United States, at least, "clean room reverse engineering" has a pretty specific definition that follows four steps:

1. A (team of) engineers reverse-engineers an existing product, in this case, the YouTube internal API.
2. Those engineers write a specification of the product's (outwardly-visible) behavior.
3. A lawyer reviews that specification to ensure that it does not contain anything infringing on any copyrights relevant to the product.
4. A separate (team of) engineers re-implement the product according to the specification.

I don't think what you're doing meets that definition. You achieved step 1, and possibly step 2, and then didn't attempt the others. You reverse engineered something for the purpose of using it - but you haven't actually reimplemented it, which is the "clean room" part of "clean room reverse engineering." Re-implementing it would presumably require building your own server for actually hosting videos on Invidious instances.

There's quite a history of this term in the US, going back to even before Intel vs. NEC, when it was very much in the public eye. NEC had designed a microprocessor with the same instruction set as the popular Intel 8080 [same instruction set = interoperability]. Internally, both devices use "microcode" to drive their execution. In the analogy, that microcode is the "InnerTube" API. NEC's "V20" device was quite different from the 8080, and needed its own microcode. Intel claimed that NEC violated Intel's copyright by basing NEC's microcode on the 8080's. As part of arguing this, NEC rewrote their microcode from scratch following proper cleanroom procedure, and the decision in the case partly relies on this to decide that NEC is in the clear. Had NEC simply injected the 8080 microcode into their NEC-V20 device directly, the case would probably have gone very differently. It would also be a very different case, because the NEC-V20 device would look completely different.

You didn't re-implement InnerTube. You injected InnerTube into your own service. Had you re-implemented InnerTube as part of Invidious, Invidious would look completely different.

Anyway, all that aside, even if what you're doing did meet the conditions of clean-room reverse engineering, I don't think it would fall under the (again, un-cited, so maybe we're talking about different things) interoperability exception in the EU. You're not producing a device/service that needs to be interoperable with other devices/services. You're producing a service with an explicit goal of operating differently.

To be clear, IANAL, but your reasoning seems shaky.

It's certainly possible to scrape data from interactions with a site directly, without using its API. This is even legal - there were no gymnastics in my response there. However, that decision has since been remanded, then re-affirmed, then challenged, and then LinkedIn obtained an injuction against HiQ which the two of them are still fighting over. So it could get properly overturned.

I definitely thought it seemed like it would be difficult to do this to offer a youtube frontend, but plausible enough that I didn't look into it. Thank you for this. I'm looking more closely now :)

If they are using undocumented internal APIs, do YouTube's API TOS apply to those? I checked the text of the TOS and it seems to me like it should apply; they say "The YouTube API services ... made available by YouTube including ...". That seems broad enough to me to cover internal APIs as well, if their endpoints are accessible, but IANAL.

Also, the open response to the C&D seems to throw shade at the TOS saying "The "YouTube API Services" means (i) the YouTube API services" but ignores that this is immediately followed by parenthetical examples and qualifiers. The TOS is defining the term so that it doesn't have to repeatedly add the qualifiers. Nothing weird about that. That's uh... pretty bad-faith arguing, if I'm interpreting it correctly.

Edit: assuming you refer to the same reverse engineering points that they made above... yeah.

I used gbf-dtb's fork. It seems like they've updated it to be easier to install since then as well. I used it by manually updating the URL to grab the script from in j0be's bookmarklet, but gbf-dtb appears to have re-linked to a codepen with a corrected one for easy installation now.

They've (convincingly) followed up above. I'm hoping the contributors to Invidious can clear this up. If no one replies here, I'll open an issue on Invidious' GitHub page asking that clarification be added to the readme on how their YoutubeAPI wrapper is not using an official YouTube API.