Imaginez que j'ai un nombre infini de problèmes de devoirs (!) Chacun étant donné un nombre entier.

La notation mathématique des problèmes est une notation permettant de décrire des sous-ensembles du problème à l'aide de spécificateurs de problème.

Une expression MPN peut comprendre plusieurs éléments:

• Une seule valeur. Cela représente un ensemble contenant le numéro: 99 -> {99}.
• Une gamme simple. Cela représente l'ensemble contenant tous les numéros du début à la fin de la plage: 10~13 -> {10, 11, 12, 13}. Si les côtés gauche ou à droite sont absents, ils sont supposés être -Infinity ou Infinity respectivement ~10 -> {x|x ≤ 10}; ~ -> ℤ.
• Une expression MPN, suivie de "skip" et d'une autre expression MPN. Cela représente la différence des deux ensembles: 10~20 skip 12~14 -> {10, 11, 15, 16, 17, 18, 19, 20}.
• Deux expressions MPN, séparées par une virgule. Cela représente l'union de deux ensembles: 1,8~9,15~17 -> {1,8,9,15,16,17}.

L'opérateur "sauter" se lie plus étroitement que l'opérateur virgule, donc 16,110~112 skip 16 -> {16,110,111,112}(16 n'est pas inclus dans l'ensemble {110,111,112}, donc l'exclusion 16 n'a pas d'importance.)

Vous pouvez également mettre des expressions entre parenthèses pour la désambiguïsation: 1~9 skip (2~8 skip (3~7 skip (4~6 skip 5))) -> {1,3,5,7,9}

Voici la grammaire:

<expr>  ::= "(" <expr> ")"
         || <number>
         || [<number>] "~" [<number>]
         || <expr> "skip" <expr>
         || <expr> "," <expr>

Votre tâche consiste à écrire un programme qui prend deux entrées:

• Une expression MPN
• Un numéro

et génère une valeur true ou falsey selon que ce problème se trouve dans l'ensemble décrit par l'expression MPN.

Caractéristiques

• Vous pouvez supposer que la première entrée est une expression MPN bien formée (c'est-à-dire qu'elle correspond à la grammaire ci-dessus)
• Les nombres dans une expression MPN sont toujours des entiers. Ils peuvent être négatifs ou nuls, mais n'auront jamais de partie fractionnaire.
• Il s'agit de code-golf , donc la soumission valide la plus courte (mesurée en octets) gagne.
• Vous pouvez utiliser différents caractères pour ~et ,, si vous le souhaitez.

Cas de test

10~20             14 -> True
10~20             20 -> True
10~20 skip 14~18  17 -> False
~ skip 6          8  -> True
16,17 skip 16     16 -> True
(16,17) skip 16   16 -> False
~10,5~            8  -> True
~10,5~            4  -> True
6 skip 6,~        6  -> True

PowerShell , 189195 octets

param($m,$q)('$m',"'(\d*)~(\d*)','($q-ge(`$1)-and$q-le(`$2))'","'\(\)',$q","'((?<=,|skip )\d+|\d+(?=,| skip))','($q-eq`$1)'","'skip','-and!'"-join'-replace'|iex|% Sp* ','|%{"($_)"})-join'-or'|iex

• Essayez-le en ligne! (avec un seul MPN et une seule valeur)
• Essayez tous les cas de test avec des -100..100valeurs as
• Afficher le code intermédiaire généré, pour tous les cas de test (avec 666 comme valeur)

Explication

J'ai réalisé très tôt que les infinis rendent cela intenable pour générer des tableaux et tester des valeurs.

J'ai regardé dans les gammes mais en .Net ils n'ont pas la gamme nécessaire (la longueur de la plage est limitée à un entier signé (32 bits), donc même s'il était correct de limiter la plage à un entier 32 bits signé , Je n'aurais pas pu gérer toutes les gammes.

J'ai donc commencé à penser à cela en termes de débuts et de fin, et finalement une série de tests booléens et j'ai commencé à créer un tas de remplacements d'expression régulière pour transformer un MPN en une expression booléenne que PowerShell comprend.

J'ai essentiellement décomposé cela en quelques règles:

• Les plages ont été plus faciles à utiliser en premier car elles ne peuvent pas être des expressions à l'une ou l'autre extrémité, mais le caractère ouvert a été difficile à mettre en œuvre sous peu. La prémisse est 2~8comme dire n >=2 && n <=8, mais quand une des extrémités est manquante, omettez le côté &&et le côté manquant. Quand les deux sont manquants, j'allais à l'origine le remplacer par $true. Ce que j'ai fini par faire, ce n'était pas du tout de tester les côtés manquants, mais je me suis assuré d'envelopper chaque numéro ().
• puis effectuez une substitution directe qui remplace les parenthèses vides ()par la valeur d'entrée. Donc, dans le cas d'un MPN comme ~8avec une valeur d'entrée de 55, le premier remplacement va générer (55-ge()-and55-le(8)), puis le deuxième remplacement vient le faire(55-ge55-and55-le(8)) , annulant essentiellement cette partie de la plage.
• Ensuite, je devais traiter des numéros individuels dans le MPN, mais je devais faire attention à ne pas jouer avec ceux que j'avais insérés auparavant. C'est vraiment juste des nombres dans ,des listes séparées par des virgules , et des nombres individuels avant ou après un skip, donc j'ai utilisé des longues recherches malheureusement.
• skipest fondamentalement le même que -and -notje fais donc un remplacement direct de skipto -and!(en utilisant !comme raccourci pour -not).
• La prochaine chose délicate était le faible ordre de priorité pour les virgules restantes. Je les ai simplement remplacés à l'origine, -ormais cela ne tenait pas compte des expressions suivantes, donc 16,17 skip 16générait du code comme ($n-eq16)-or($n-eq17) -and! ($n-eq16). Il fallait des parenthèses, mais cela semblait irréalisable avec un remplacement direct. Étant donné que toutes les autres choses ont été remplacées, sauf les virgules, et qu'elles ont la priorité la plus faible, je viens de diviser la chaîne générée en entier sur les virgules restantes, puis de placer chaque élément entre parenthèses et de le rejoindre -or.

En fin de compte, le code généré est simplement canalisé dans Invoke-Expression( iex) pour être exécuté, puis nous obtenons le résultat booléen ( vous pouvez voir le code qui est généré à la place du résultat ici ).

Cela a pris beaucoup trop de temps, et je suis sûr qu'il y a de la place pour extraire quelques octets de plus, mais je ne peux plus le regarder :-p

Perl, 99 130 octets

sub f{($_,$n)=@_;s/(-?\d+)?~(-?\d+)?|(-?\d+)/!(defined$3?$n!=$3:length$1&&$1>$n||length$2&&$n>$2)+0/ge;s/skip/&&!/g;s/,/||/g;eval}

Essayez-le sur Ideone.

Non golfé:

sub f {
    my ($e, $n) = @_;

    $e =~ s/(-?\d+)?~(-?\d+)?|(-?\d+)/ (defined($3) ? $n == $3 : (!length($1) || $n >= $1) && (!length($2) || $n <= $2)) + 0 /ge;
    $e =~ s/skip/ && ! /g;
    $e =~ s/,/ || /g;

    return eval($e);
}

JavaScript (ES6), 221 292 287 309 274 277 278 octets

(-5 octets grâce à Okx)

(j,v,m=1/0,Z=/(skip)([^,]+)/g)=>eval(j[M='replace'](/(-?\d*)~(-?\d*)/g,(e,a,b)=>(a[M]('-','#')||-m)+'<='+(T=v[M]('-','#'))+'&&'+T+'<='+(b[M]('-','#')||m))[M](Z,i=o=>o.match(Z)?i(o[M](Z,'&&!($2)')):o)[M](/,/g,'||')[M](/(^|[^=&#\d])(\d+)([^<\d]|$)/g,'$1$2=='+v+'$3')[M](/#/g,'-'))

Sensationnel. Ce n'était pas facile à cause de tous les cas marginaux, mais je pense que je l'ai fait. Je viens espère qu'il n'y a pas des cas particuliers qui pourraient briser les expressions régulières utilisées. Je jouerai au golf plus chaque fois que je le pourrai.

Extrait de test

D=(j,v,m=1/0,Z=/(skip)([^,]+)/g)=>eval(j[M='replace'](/(-?\d*)~(-?\d*)/g,(e,a,b)=>(a[M]('-','#')||-m)+'<='+(T=v[M]('-','#'))+'&&'+T+'<='+(b[M]('-','#')||m))[M](Z,i=o=>o.match(Z)?i(o[M](Z,'&&!($2)')):o)[M](/,/g,'||')[M](/(^|[^=&#\d])(\d+)([^<\d]|$)/g,'$1$2=='+v+'$3')[M](/#/g,'-'))

MPN Expression:<input type="text" value="1~9 skip (2~8 skip (3~7 skip (4~6 skip 5)))" id="MPN"></input>
<br>
Integer:<input type="number" id="INT" value=6></input>
<input type="button" value="Submit" onclick="T=r=>document.getElementById(r).value;console.log(D(T('MPN'),T('INT')))"></input>

Röda + bc, 183 octets

f x{{["x=",x,"\n"];replace" ","",",","||","skip\\(","&&!","skip([0-9~]+)","&&!($1)","(?<!~|\\d)(\\d+)(?!~|\\d)","x==$1","(\\d*)~(\\d*)","x>=($1)&&x<=($2)","\\(\\)",x;["\n"]}|exec"bc"}

Ceci est similaire à la réponse PowerShell (ou je pense que oui, je ne comprends pas PowerShell). Il prend le nombre comme argument et le code comme valeur dans le flux d'entrée, comme ceci:main { push("1~9") | f(5) } .

Je pense que cela fonctionne, au moins il résout tous les cas de test. Le script ci-dessous peut être utilisé pour vérifier cela.

main {
    readLines("/tmp/tests.txt") | split(sep=";") | for code, num, ans do
        push(code, " -> ")
        print(code) | replace" ","",",","||","skip\\(","&&!","skip([0-9~]+)","&&!($1)","(?<!~|\\d)(\\d+)(?!~|\\d)","x==$1","(\\d*)~(\\d*)","x>=($1)&&x<=($2)","\\(\\)",num
        a := push(code) | f(num) | head()
        result := push("OK") if [ (a = "0" and ans = "False") or (a = "1" and ans = "True") ] else push("FAIL")
        print code, " ; ", num, " -> ", a, " ", ans, " (", result, ")\n"
    done
}

Et les tests:

10~20;14;True
10~20;20;True
10~20 skip 14~18;17;False
~ skip 6;8;True
16,17 skip 16;16;True
(16,17) skip 16;16;False
~10,5~;8;True
~10,5~;4;True
6 skip 6,~;6;True