Imagina que tengo un número infinito de problemas de tarea (!) Cada uno con un número entero.

La notación de problemas matemáticos es una notación para describir subconjuntos del problema utilizando especificadores de problemas.

Una expresión MPN puede constar de varias cosas:

• Un solo valor. Esto representa un conjunto que contiene el número: 99 -> {99}.
• Un rango simple. Esto representa el conjunto que contiene todos los números desde el comienzo hasta el final de la gama: 10~13 -> {10, 11, 12, 13}. Si los lados izquierdo o derecho se pierden, entonces se supone que son -Infinity o infinito, respectivamente: ~10 -> {x|x ≤ 10}; ~ -> ℤ.
• Una expresión MPN, seguida de "omitir" y otra expresión MPN. Esto representa la diferencia de los dos conjuntos: 10~20 skip 12~14 -> {10, 11, 15, 16, 17, 18, 19, 20}.
• Dos expresiones MPN, separadas por una coma. Esto representa la unión de dos conjuntos: 1,8~9,15~17 -> {1,8,9,15,16,17}.

El operador "omitir" se une más fuerte que el operador de coma, por lo tanto 16,110~112 skip 16 -> {16,110,111,112}(16 no está incluido en el conjunto {110,111,112}, por lo que el 16 excluyente no importa).

También puede poner expresiones entre paréntesis para la desambiguación: 1~9 skip (2~8 skip (3~7 skip (4~6 skip 5))) -> {1,3,5,7,9}

Esta es la gramática:

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

Su tarea es escribir un programa que tome dos entradas:

• Una expresión MPN
• Un número

y genera algún valor verdadero o falso dependiendo de si ese problema está en el conjunto descrito por la expresión MPN.

Especificaciones

• Puede suponer que la primera entrada es una expresión MPN bien formada (es decir, que coincide con la gramática anterior)
• Los números en una expresión MPN son siempre enteros. Pueden ser negativos o cero, pero nunca tendrán una parte fraccional.
• Este es el código de golf , por lo que gana el envío válido más corto (medido en bytes).
• Puede usar diferentes caracteres para ~y ,, si lo desea.

Casos de prueba

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 , 189 195 bytes

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

• Pruébalo en línea! (con un solo MPN y valor)
• Pruebe todos los casos de prueba con -100..100valores
• Ver el código intermedio generado, para todos los casos de prueba (con 666 como valor)

Explicación

Al principio me di cuenta de que los infinitos hacen que esto sea insostenible para generar matrices y probar valores.

Miré los rangos, pero en .Net no tienen el rango necesario (la longitud del rango se limita a un entero con signo (32 bits), por lo que incluso si estuviera bien limitar el rango a un int con signo de 32 bits , No habría podido manejar todos los rangos.

Entonces comencé a pensar en esto en términos de comienzos y fines, y finalmente una serie de pruebas booleanas y comencé a crear un montón de regex reemplaza para convertir un MPN en una expresión booleana que PowerShell entiende.

Básicamente dividí esto en algunas reglas:

• Primero fue más fácil trabajar con los rangos porque no pueden ser expresiones en ninguno de los extremos, pero la terminación abierta fue difícil de implementar en breve. La premisa es 2~8como decir n >=2 && n <=8, pero cuando falta uno de los extremos, omita &&el lado y el lado que falta. Cuando faltan ambos, originalmente iba a reemplazarlo por $true. Lo que terminé haciendo no fue realmente probar los lados faltantes, pero me aseguré de incluir cada número ().
• y luego haga una sustitución directa que reemplace los paréntesis vacíos ()con el valor de entrada. Entonces, en el caso de un MPN como ~8con un valor de entrada de 55, se generará el primer reemplazo (55-ge()-and55-le(8)), luego aparecerá el segundo reemplazo para hacerlo (55-ge55-and55-le(8)), esencialmente anulando esa parte del rango.
• Luego tuve que tratar con números individuales en la MPN, pero tuve que tener cuidado de no meterme con los que inserté antes. Realmente son solo números en ,listas separadas por comas , y números individuales antes o después de un skip, así que usé desafortunadamente largas búsquedas.
• skipes básicamente lo mismo, -and -notasí que hago un reemplazo directo de skipto -and!(usando !como abreviatura para -not).
• La siguiente cosa difícil fue el bajo orden de precedencia para las comas restantes. Originalmente los reemplacé, -orpero no tenía en cuenta las expresiones posteriores, por 16,17 skip 16lo que generaba código como ($n-eq16)-or($n-eq17) -and! ($n-eq16). Necesitaba paréntesis, pero eso parecía inviable con un reemplazo directo. Como todas las otras cosas fueron reemplazadas, excepto las comas, y tienen la prioridad más baja, simplemente dividí toda la cadena generada en las comas restantes, luego envolví cada elemento entre paréntesis y lo volví a unir -or.

Finalmente, el código generado se canaliza a Invoke-Expression( iex) para ejecutarse y luego obtenemos el resultado booleano ( puede ver el código que se genera en lugar del resultado aquí ).

Esto tomó demasiado tiempo, y estoy seguro de que hay espacio para exprimir algunos bytes más, pero ya no puedo verlo :-p

Perl, 99 130 bytes

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}

Pruébalo en Ideone.

Sin 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 bytes

(-5 bytes gracias a 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,'-'))

Guau. Esto no fue fácil debido a todos los casos extremos, pero creo que lo hice. Solo espero que no haya casos especiales que puedan romper las expresiones regulares utilizadas. Jugaré más golf cada vez que pueda.

Fragmento de prueba

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 bytes

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"}

Esto es similar a la respuesta de PowerShell (o creo que no entiendo PowerShell). Se necesita el número como argumento y el código como un valor en el flujo de entrada, como esto: main { push("1~9") | f(5) }.

Creo que funciona, al menos resuelve todos los casos de prueba. El siguiente script se puede utilizar para verificar esto.

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
}

Y las pruebas:

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