Ways of specifying random generation in challenges

Question

Note: As per consensus on Meta, challenge-writing questions are on topic here.

In light of this "thing to avoid when writing challenges", I started to think about challenges involving random generation of certain kinds of objects.

It sometimes happens that I want to post a code-golf challenge that involves randomly generating a foo, where

1. it's very easy to check whether a given thing is a foo, and
2. it's a little harder to quickly generate a "good-quality" random foo.

As an example, a foo might be a binary matrix where there are no segments of 4 equal bits in any direction. It's easy to check whether a given binary matrix is a foo, but generating a random foo with a nicely spread distribution seems to require a backtracking algorithm or something similar.

Anyway, now I'll need to objectively specify what qualifies as a random foo, and I'd like it to be "unpredictable" in the intuitive sense that when I run the program several times, the results always look different. The most restrictive approach is to require that the output is uniformly random: all valid foos have the same probability of being generated. This is usually too restrictive, because I have no idea how to do it save for generating all valid foos, removing duplicates and choosing one, which is boring and slow.

My next idea is to require that all valid foos have a positive probability of being generated. However, this means that the following approach is valid: generate a random foo-like thing (in our example, a random binary matrix), if it's a foo then return it, otherwise return a hard-coded foo (say, the identity matrix). This is also somewhat boring, since it's basically just a recognizer of foos tacked to a random matrix generator.

Could there be a nice general definition for an unpredictably random foo?

TL;DR

Is there a good way for specifying an "unpredictable" randomly generated object that doesn't fix the distribution but discourages hard-coding?

Answer 1

Return a thousand different foos

This makes it impossible to return hardcoded values and have a half decent golf. However, a legit foo generator does have a small chance of outputting duplicate foos unless it is actually checking them. To remove the burden of checking, an empirically tested failure rate, say 10%, could be specified as acceptable.

Be aware of the birthday paradox, that the probability of duplicates may be higher than you think. If there are only a million possible foos, a thousand random foos will have a probability of about 0.6 that there is a duplicate in there somewhere, and that's assuming that foo generation is completely uniform. If this could be an issue, require say 900 unique foos for every 1000 generated, which is far more generous for a genuine foo generator but still impractical for hardcoding.

This also allows you to repeatedly generate foo-like things and check fooness until you get foos. I think this is a valid solution myself, but if you don't like it:

Do it quickly

The chances of a completely random foo-like thing being foo are probably quite low, so specifying a time limit is likely to force a genuine attempt at foo generation.

To accomodate the speed differences between different languages, you may want to have different time limits depending on the language like Hackerrank: https://www.hackerrank.com/environment . However if you specify large enough foos the probability of random foo-like things being foo might be really low, so a "before the heat death of the Universe" rule might be sufficient.

Answer 2

I don't claim to have the ultimate solution to the problem (or that this list is exhaustive), but I want to outline some possible approaches that come to mind and why they would or wouldn't work. I also won't address tangential issues like whether using the current timestamp as a source of randomness is sufficiently "unpredictable" and how to enforce certain properties of the probability distribution — I'll just focus on avoiding solutions that use hardcoding.

Not a solution: disallow hard-coding explicitly

This is a bad idea. It's a non-observable requirement (which means you can't determine whether it's satisfied just by running the program), which is strongly discouraged on PPCG and may be outright impossible if running the program on any other platform, where submissions are verified in an automated manner. The problem with a requirement like this is that you'd have to start by finding an objective definition for "hard-coding". In general, if you try this, you're only going to make things worse.

Make hard-coding infeasible

If you can't disallow it completely, but you don't want people to use it, then you can try to design the challenge such that hard-coding is simply not a competitive approach. This is possible if the objects that should be generated are sufficiently large and incompressible that putting one example into the code would require a lot more bytes than writing an algorithm that generates valid solutions randomly. In your specific example, that's not the case of course, because identity matrices are valid and are generally easy to generate, but for other problems, that might not be the case. If the target objects are sufficiently irregular, just require them to be of a large size, which probably won't affect the byte count of an actual algorithm but will blow up the hard-coded part.

Parameterise the output

Often, these problems come with one or more natural parameter, like the size of the matrix in your example. If so, making that parameter an input can be sufficient to make hard-coding impossible or at least impractical. In some cases, it might be easy to hard-code one specific solution for a given parameter value that has been found manually or via extensive search, but maybe there is no simple closed form for an instance of these solution in general, so it's not possible to generate a default value for arbitrary inputs easily. Again, this is not the case for the example you mention, because the identity matrix works at any size, but an optimal solution for this related problem is usually highly irregular, so it's not possible to have default value without actively searching for valid values anyway. You can combine this with a time-limit to avoid a brute force search for a default value.

Put some restriction on the probability distribution

If you're willing to give up a completely unrestricted probability distribution, you can put some constraints on it, that still give answerers a lot of freedom in choosing their distribution but which make hard-coding a difficult or impossible:

• The simplest constraint that comes to mind is to require the difference between minimum and maximum probability for any possible output to be below a certain threshold. A hard-coded approach will likely have almost-zero probabilities for almost all outputs and a probability close to 1 for the default value. If you require the maximum difference to be below 0.1 say, there would need to be 10 (randomly chosen) default values to make the approach an option. Similarly you could also just require a minimum probability for each possible output, e.g. 1/(2*N*), where N is the number of possible outputs.
• Alternatively, you can require that there are no (likelihood) gaps in the distribution, so that there is no interval of size δ (chosen by you) such that both higher and lower probabilities exist. That means there can't be any outliers in terms of likelihood, which are likely generated by a hard-coding approach.

The main issue with these approaches is that they're a lot harder to reason about, proving correctness of answers is difficult, and experimentally verifying the correctness can be impossible for large output spaces. Still, they provide a principally observable requirement for the program which can make hardcoding impossible.

These approaches may also need a time limit, because one way to increase the probability of the non-default values would be to attempt finding a random foo multiple times before falling back to the default value.