Esme Povirk @madewokherd@computerfairi.es

So, for the induction step, we try to place 1 orb.

We have to first account for permutations that fail at that step: we should have an M/N probability of failing outright, where M is the number of invalid orbs for the first land, and N is the total remaining.

So, we can try the orbs in a random order. If the first one fails, we know M is at least one, and so we should randomly return failure 1/N of the time.

The base case (N=1) is simple. If that 1 orb is valid for that 1 land, return a single pair of that land and that orb. If not, return failure.

What I'm trying to do is build this by induction. If I solve the problem for N, I can solve it for N+1. I need a problem statement where that works and is somewhat efficient.

So here it is:
PlaceOrbsInLands(list of lands remaining, list of orbs remaining)

This either returns a list of pairs of lands and orbs, or "failure". Each valid permutation has equal probability, and probability of failure is proportional to the number of invalid permutations.

There's one critical difference though: this allows me to interrupt the process early. If I find an invalid orb placement, I can stop right there and start over. I don't have to calculate the rest of the permutation.

That helps, slightly, but I still expect a lot of retries.

Let's say N is sufficiently small that that algorithm works. Can I make it work for N+1? Yes, here's how:

I need to decide what orb to place in my first land. In order to eliminate bias, I must weigh the probability of each orb by the number of valid permutations with that orb in the given land. I can't calculate that value, but I can just try a random permutation. If it doesn't work, I reroll the first orb. Easy.

Except that's equivalent to the bad naive algorithm.

@viridian Oh, also, olrPNever is not allowed.

@viridian Here's the function that decides it: https://github.com/zenorogue/hyperrogue/blob/master/orbgen.cpp#L216

Orbs that are useless, forbidden, dangerous, or burn are not allowed.

Except, if I check the permutations in a random order, I don't have to test all of them. I can just choose permutations until I find one that works. That's my naive algorithm from earlier that rerolls way too often and takes too long. But we can build off of that.

The algorithm I settled on is.. maybe more understandable if you start from the end.

Let's say I have N orbs left to place in N lands. Naively, I could check all N permutations, store the valid ones, choose one at random, and I'm done. Of course, there are N! permutations, and I start out with N = 60, so this would take an impossible amount of computation and memory.

And this algorithm can still hit dead ends, if an orb or land has no valid pairings left.

One could adjust that by checking pairs during the process and rerolling any invalid pairs. However, this would introduce bias. Early on, each pairing is equally likely, but these pairings eliminate different numbers of possibilities later. If I place a more "restricted" orb that can go in only a few lands, that eliminates relatively few possibilities for it, compared to other orbs that could go anywhere.

The naive algorithm would be to shuffle the orbs completely at random. If this results in an invalid configuration, try again until it works. That would be unbiased, but in this case, certain lands and orbs accept only a few pairings, so there'd be a lot of retries.

So for the randomizer, I wanted to add a mode ("full") that assigns orbs to lands as close to 1:1 as possible. Some pairings of orbs/lands are not allowed, and there are a lot of special cases in this logic. I wanted to place them such that they are unbiased, i.e. every possible placement has equal probability. That is surprisingly difficult.

The master branch on my fork of HyperRogue now has the beginnings of a randomizer, and a thorn weapon, both selectable in the menus and (in theory if I didn't screw up) not affecting game logic when turned off: https://github.com/madewokherd/hyperrogue

For the moment it requires building the game yourself if you want to try it. Hoping to fix that soon-ish.

1. Photos are already a demanding task, and I would've been additionally "encumbered" by carrying a pizza during the process.

Of course, explaining any of that in the moment would've itself been a demanding task, so I just awkwardly said no, and that was accepted. Had people been less reasonable and willing to accommodate, it could've escalated into a conflict in which I come off as stubborn/inflexible.

So, what were the resource costs? I think it was:

1. Unexpected mode shifting. I had been focused on a task (eating) and would've had to shift my focus to something else.
2. Unanticipated logistics. While the plan seemed reasonable enough on the surface, based on prior experiences I thought there was a significant probability that further minor problems would have to be navigated in this process.
3. ...

I know that I had very quickly calculated the resource expenditure of getting up to be in the photo and decided it was not worth it. A lot of non-verbal thought was packed into a few moments, and it's surprisingly difficult to "unpack" that into words.

OK. A thing happened on Friday that I'm trying to work out how to properly explain. I was at Can Can Wonderland with a group. I was hungry and apparently no one else was, so I got a pizza (which was bigger than expected). I was interrupted because they were taking a group photo, and I said "that is awkward timing". Was told i could probably hold my food during the photo, but I decided not to, despite this being a completely reasonable plan.

Me: Yesterday was a light day.
Me journaling the events of yesterday: So much stuff happened.

she (in a binary way) / any (in an I want people to be absolute goblins about it way)