Façons de spécifier la génération aléatoire dans les défis

Remarque : Conformément au consensus sur Meta , les questions de rédaction de défis sont sur le sujet ici.

À la lumière de cette «chose à éviter lors de l'écriture de défis» , j'ai commencé à penser à des défis impliquant la génération aléatoire de certains types d'objets.

Il arrive parfois que je souhaite publier un défi de code-golf qui implique la génération aléatoire d'un foo, où

1. il est très facile de vérifier si une chose donnée est un fou, et
2. il est un peu plus difficile de générer rapidement un foo aléatoire de "bonne qualité".

Par exemple, un foo peut être une matrice binaire où il n'y a pas de segments de 4 bits égaux dans n'importe quelle direction. Il est facile de vérifier si une matrice binaire donnée est un foo, mais générer un foo aléatoire avec une distribution bien répartie semble nécessiter un algorithme de retour arrière ou quelque chose de similaire.

Quoi qu'il en soit, je vais maintenant devoir spécifier objectivement ce qui est considéré comme un foo aléatoire, et j'aimerais que ce soit "imprévisible" dans le sens intuitif du fait que lorsque j'exécute le programme plusieurs fois, les résultats sont toujours différents. L'approche la plus restrictive consiste à exiger que la sortie soit uniformément aléatoire: tous les foos valides ont la même probabilité d'être générés. C'est généralement trop restrictif, car je ne sais pas comment le faire sauf pour générer tous les foos valides, supprimer les doublons et en choisir un, ce qui est ennuyeux et lent.

Ma prochaine idée est d'exiger que tous les foos valides aient une probabilité positive d'être générés. Cependant, cela signifie que l'approche suivante est valide: générer une chose aléatoire semblable à foo (dans notre exemple, une matrice binaire aléatoire), si c'est un foo, puis la retourner, sinon retourner un foo codé en dur (par exemple, la matrice d'identité ). C'est aussi un peu ennuyeux, car il s'agit simplement d'un identificateur de foos collés à un générateur de matrice aléatoire.

Pourrait-il y avoir une belle définition générale pour un foo imprévisiblement aléatoire?

TL; DR

Existe-t-il un bon moyen de spécifier un objet généré de manière aléatoire "imprévisible" qui ne corrige pas la distribution mais décourage le codage en dur?

Rendez mille foos différents

Cela rend impossible le retour des valeurs codées en dur et un golf à moitié décent. Cependant, un générateur foo légitime a une petite chance de produire des foos en double à moins qu'il ne les vérifie réellement. Pour supprimer la charge de la vérification, un taux d'échec testé empiriquement, par exemple 10%, pourrait être spécifié comme acceptable.

Soyez conscient du paradoxe d'anniversaire , que la probabilité de doublons peut être plus élevée que vous ne le pensez. S'il n'y a qu'un million de foos possibles, un millier de foos aléatoires aura une probabilité d'environ 0,6 qu'il y ait un doublon quelque part, et cela suppose que la génération de foo soit complètement uniforme. Si cela pouvait être un problème, exigez disons 900 foos uniques pour 1000 générés, ce qui est beaucoup plus généreux pour un véritable générateur de foo mais toujours peu pratique pour le codage en dur.

Cela vous permet également de générer à plusieurs reprises des choses semblables à des foo et de vérifier les fooness jusqu'à ce que vous obteniez des foos. Je pense que c'est une solution valable moi-même, mais si vous ne l'aimez pas:

Fais le rapidement

Les chances qu'une chose semblable à foo complètement aléatoire soit foo sont probablement assez faibles, donc la spécification d'une limite de temps est susceptible de forcer une véritable tentative de génération de foo.

Pour s'adapter aux différences de vitesse entre les différentes langues, vous souhaiterez peut-être avoir des délais différents selon la langue comme Hackerrank: https://www.hackerrank.com/environment . Cependant, si vous spécifiez des foos suffisamment grands, la probabilité que des choses semblables à des foo aléatoires soient foo peut être vraiment faible, donc une règle "avant la mort par la chaleur de l'Univers" pourrait être suffisante.

Je ne prétends pas avoir la solution ultime au problème (ou que cette liste est exhaustive), mais je veux décrire quelques approches possibles qui me viennent à l'esprit et pourquoi elles fonctionneraient ou non. Je n'aborderai pas non plus les problèmes tangentiels tels que l'utilisation de l'horodatage actuel comme source de caractère aléatoire est suffisamment "imprévisible" et comment appliquer certaines propriétés de la distribution de probabilité - je me concentrerai simplement sur l'évitement des solutions qui utilisent le codage en dur.

Pas une solution: interdire explicitement le codage en dur

C'est une mauvaise idée. C'est une exigence non observable (ce qui signifie que vous ne pouvez pas déterminer si elle est satisfaite simplement en exécutant le programme), ce qui est fortement déconseillé sur PPCG et peut être carrément impossible si vous exécutez le programme sur une autre plate-forme, où les soumissions sont vérifiées dans un manière automatisée. Le problème avec une telle exigence est que vous devez commencer par trouver une définition objective du "codage en dur". En général, si vous essayez cela, vous ne ferez qu'empirer les choses.

Rendre le codage en dur impossible

Si vous ne pouvez pas l'interdire complètement, mais que vous ne voulez pas que les gens l'utilisent, vous pouvez essayer de concevoir le défi de telle sorte que le codage en dur ne soit tout simplement pas une approche compétitive. Cela est possible si les objets qui doivent être générés sont suffisamment grands et incompressibles pour que la mise d'un exemple dans le code nécessite beaucoup plus d'octets que l'écriture d'un algorithme qui génère des solutions valides de manière aléatoire. Dans votre exemple spécifique, ce n'est pas le cas bien sûr, car les matrices d'identité sont valides et sont généralement faciles à générer, mais pour d'autres problèmes, cela pourrait ne pas être le cas. Si les objets cibles sont suffisamment irréguliers, exigez simplement qu'ils soient de grande taille, ce qui n'affectera probablement pas le nombre d'octets d'un algorithme réel mais fera exploser la partie codée en dur.

Paramétrer la sortie

Souvent, ces problèmes viennent avec un ou plusieurs paramètres naturels, comme la taille de la matrice dans votre exemple. Si c'est le cas, faire de ce paramètre une entrée peut être suffisant pour rendre le codage en dur impossible ou du moins impossible. Dans certains cas, il peut être facile de coder en dur une solution spécifique pour une valeur de paramètre donnée qui a été trouvée manuellement ou via une recherche approfondie, mais il n'y a peut-être pas de formulaire fermé simple pour une instance de ces solutions en général, donc ce n'est pas possible de générer facilement une valeur par défaut pour les entrées arbitraires. Encore une fois, ce n'est pas le cas pour l'exemple que vous mentionnez, car la matrice d'identité fonctionne à n'importe quelle taille, mais une solution optimale pour ce problème connexeest généralement très irrégulier, il n'est donc pas possible d'avoir une valeur par défaut sans rechercher activement de toute façon des valeurs valides. Vous pouvez combiner cela avec un délai pour éviter une recherche par force brute d'une valeur par défaut.

Mettre une certaine restriction sur la distribution de probabilité

Si vous êtes prêt à renoncer à une distribution de probabilité totalement illimitée, vous pouvez lui imposer certaines contraintes, qui donnent encore beaucoup de liberté aux répondeurs dans le choix de leur distribution, mais qui rendent le codage en dur difficile ou impossible:

• La contrainte la plus simple qui vient à l'esprit est d'exiger que la différence entre la probabilité minimale et maximale pour toute sortie possible soit inférieure à un certain seuil. Une approche codée en dur aura probablement des probabilités presque nulles pour presque toutes les sorties et une probabilité proche de 1 pour la valeur par défaut. Si vous exigez que la différence maximale soit inférieure à 0,1, disons, il devrait y avoir 10 valeurs par défaut (choisies au hasard) pour faire de l'approche une option. De même, vous pouvez également exiger une probabilité minimale pour chaque sortie possible, par exemple 1 / (2 * N *), où N est le nombre de sorties possibles.
• Alternativement, vous pouvez exiger qu'il n'y ait pas (de vraisemblance) d'écarts dans la distribution, de sorte qu'il n'y ait pas d'intervalle de taille δ (choisi par vous) tel qu'il existe des probabilités plus élevées et plus faibles. Cela signifie qu'il ne peut y avoir de valeurs aberrantes en termes de probabilité, qui sont probablement générées par une approche de codage en dur.

Le principal problème avec ces approches est qu'elles sont beaucoup plus difficiles à raisonner, il est difficile de prouver l'exactitude des réponses, et la vérification expérimentale de l'exactitude peut être impossible pour les grands espaces de sortie. Pourtant, ils fournissent une exigence principalement observable pour le programme qui peut rendre impossible le codage en dur.

Ces approches peuvent également nécessiter une limite de temps, car une façon d'augmenter la probabilité des valeurs non par défaut serait d'essayer de trouver un foo aléatoire plusieurs fois avant de retomber à la valeur par défaut.