Comment puis-je noter des défis avec des tailles de problème variables?

21

Il y a un soutien assez fort sur la méta pour que les questions de rédaction de défis soient sur le sujet principal, à condition que ces questions soient spécifiques et répondent. Cependant, nous n'avons pas encore de telles questions, alors j'ai pensé que je testerais les eaux. Cette question entre probablement dans un bon territoire subjectif, un mauvais territoire subjectif , mais je pense que c'est probablement ce que les questions de rédaction de défis devront être. Pour vous assurer qu'ils génèrent toujours un contenu de haute qualité, veuillez ne pas simplement publier des idées spéculatives sauvages dans les réponses. Expliquez pourquoi ils évitent les problèmes mentionnés ci-dessous ou, dans l'idéal, signalez les défis existants qui ont utilisé avec succès la technique suggérée dans le passé.

Pour certains défis d'optimisation, un paramètre libre dans la définition du défi est la taille du problème à optimiser. Par «défi d'optimisation», je ne veux pas dire des choses comme notre genre de , où les réponses doivent généralement être exactes / optimales, et le défi est noté soit sur une taille de problème fixe, soit sur la plus grande taille de problème qui peut être gérée dans un laps de temps fixe. Je veux dire spécifiquement les défis où des solutions sous-optimales au problème sous-jacent sont autorisées et même probables, et l'objectif est de faire le mieux possible.

Par souci de clarté, considérez les défis des castors occupés , bien qu'en principe cela s'applique également à d'autres types de défis sans solutions optimales connues (j'utilise juste des castors occupés ici car ils aggravent les problèmes mentionnés ci-dessous). Dis, je voulais me lancer un défi pour trouver le castor Brainfuck le plus occupé. Le paramètre libre dans les problèmes de castor occupés est la taille du code. Je ne peux pas relever le défi sans faire référence à la taille du code d'une manière ou d'une autre. D'une certaine manière, chaque valeur du paramètre de taille du problème représente Nun défi distinct (de plus en plus difficile). Ma principale question est de savoir comment faire fonctionner un tel défi sans rencontrer de problèmes d'équilibrage.

La solution évidente est de corriger N: "Trouvez un programme Brainfuck de terminaison avec des Noctets de code source qui imprime autant de caractères que possible / s'exécute pour autant de ticks que possible." Cela a d'énormes problèmes d'équilibrage: si je choisis la taille trop petite, quelqu'un pourrait rapidement trouver lecastor le plus occupé et le défi est terminé. Si je choisis une taille trop grande, la solution optimale imprimera une quantité astronomique de caractères avant de terminer, ce qui signifie qu'il sera probablement trivial de trouver de tels programmes et le défi devient une corvée / exercice de patience - cela laisse également le territoire où les castors occupés peuvent être trouvés par programme, et à la place, les gens devraient commencer à prouver formellement leurs résultats, ce que beaucoup de gens pourraient ne pas considérer comme très amusant. Bien sûr, ce problème est plus prononcé dans les défis de castor occupés que les autres types, en raison de la croissance des solutions optimales, mais il s'applique néanmoins à d'autres défis.

L'option suivante consisterait à laisser Nsans contraintes et à en faire partie du score via une fonction. Même pour les défis «normaux», il est incroyablement difficile de trouver le juste équilibre entre les scores combinés, mais dans le cas des castors occupés, c'est en fait fondamentalement impossible, car les solutions optimales se développent plus rapidement avec Nn'importe quelle fonction calculable. Cela signifie que je peux toujours battre la meilleure réponse existante en allant à une taille suffisamment grande Noù je peux facilement trouver un programme qui fonctionne si longtemps que je peux obtenir un meilleur score sans trop d'effort.

J'ai également envisagé de fixer un fixe Net de permettre aux gens de soumettre également des castors pour plus gros Nqui seront utilisés comme briseurs de cravate successifs. Cela a un problème similaire, en ce sens que quelqu'un peut simplement "trouver un castor occupé tout aussi bon" pour un N, créant ainsi une égalité, puis soumettant à peu près n'importe quoi pour le prochain Noù trouver un score élevé est plus facile (même si trouver le le score optimal devient plus difficile). Dans ces cas, comment traiteriez-vous avec plusieurs personnes utilisant la même solution? Interdire, ce serait aussi bizarre au cas où il serait optimal.

On pourrait peut-être trouver un terrain d'entente, en faisant une supposition éclairée à un niveau raisonnable Net en demandant ensuite des castors occupés pour toutes les tailles dans (disons) 5 octets N, de sorte qu'il y ait une certaine latitude dans les deux directions (et ensuite vous combinez les ~ 10 scores en une seule par une technique ou une autre). Cela ne semble pas tout à fait satisfaisant non plus, car ma supposition initiale Npourrait encore être largement hors de portée, ce qui crée des défis intéressants.

TL; DR: dans les cas où le défi consiste à (résoudre de manière sous-optimale et) optimiser un problème dont la taille est variable, comment puis-je intégrer la taille dans le défi? Idéalement, je voudrais que les gens puissent travailler avec une valeur Nproche de l'extrémité supérieure de la gamme de tailles maniables. Mais juste au cas où il s'avérerait que des solutions optimales sont possibles pour cela N, ce serait bien si des solutions pour un peu plus grandes Ncommençaient à peser, de sorte que le défi pourrait continuer avec une taille de problème plus intéressante.

Martin Ender
la source
6
J'aime cela comme modèle pour les questions de rédaction de défis car ce n'est pas spécifique au PPCG. Ce n'est pas "Comment devrions-nous faire cela?" mais "Quelle est la bonne façon de procéder?". Je pourrais imaginer que de tels défis soient exécutés sur un site de programmation amateur ou lors d'un concours en personne.
xnor
Mettez le tldr au sommet!
Majora320
1
@ Majora320 ... mais changez ensuite d en w :-)
Luis Mendo

Réponses:

3

Trouvez le prochain N

Le défi indiquerait Nque les soumissions devraient commencer à.

Ensuite, les gens soumettraient des réponses au courant N. Si une soumission donnée s'avère optimale, elle Nest augmentée de 1 et le processus se répète.

Il existe plusieurs façons de noter cela:

  1. Marquez la meilleure soumission au niveau actuel N
  2. Donnez un point à la meilleure soumission au courant N, plus un point pour chaque solution optimale
  3. Identique à # 2, mais donne également un point à la personne qui a prouvé qu'une soumission donnée était optimale.
Nathan Merrill
la source
1

Donner des points pour les solutions dans un N borné

Permet Nd'être dans des limites fixes. La borne inférieure devrait exclure les réponses manifestement triviales, et que la borne supérieure ne devrait pas être trop éloignée de la borne inférieure.

Ensuite, donnez 1 point pour chaque personne qui a la meilleure solution pour chacune Ndans les limites. Si plus élevé Nsignifie que la solution est plus difficile, donnez-leur N points. (ou une formule basée sur N).

Cette méthode est similaire à la façon dont les AZsPC le font, mais aucun point partiel n'est donné.

Nathan Merrill
la source