Imagine que eu tenho um número infinito de problemas nos trabalhos de casa (!), Cada um com um número inteiro.

A notação de problemas matemáticos é uma notação para descrever subconjuntos do problema usando especificadores de problemas.

Uma expressão MPN pode consistir em várias coisas:

• Um único valor. Isto representa um conjunto contendo o número: 99 -> {99}.
• Uma gama simples. Este representa o conjunto contendo todos os números desde o início até ao fim do intervalo: 10~13 -> {10, 11, 12, 13}. Se os lados esquerdo ou direito está faltando, então eles estão a ser assumida -Infinity ou Infinito respectivamente: ~10 -> {x|x ≤ 10}; ~ -> ℤ.
• Uma expressão MPN, seguida por "ignorar" e outra expressão MPN. Isso representa a diferença entre os dois conjuntos: 10~20 skip 12~14 -> {10, 11, 15, 16, 17, 18, 19, 20}.
• Duas expressões MPN, separadas por vírgula. Isto representa a união de dois conjuntos: 1,8~9,15~17 -> {1,8,9,15,16,17}.

O operador "ignorar" se liga mais firmemente que o operador de vírgula, portanto 16,110~112 skip 16 -> {16,110,111,112}(16 não está incluído no conjunto {110,111,112}, portanto os 16 excluídos não importam).

Você também pode colocar expressões entre parênteses para desambiguação: 1~9 skip (2~8 skip (3~7 skip (4~6 skip 5))) -> {1,3,5,7,9}

Esta é a gramática:

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

Sua tarefa é escrever um programa que aceite duas entradas:

• Uma expressão MPN
• Um número

e gera algum valor de verdade ou falsey, dependendo se esse problema está no conjunto descrito pela expressão MPN.

Especificações

• Você pode assumir que a primeira entrada é uma expressão MPN bem formada (ou seja, que corresponde à gramática acima)
• Os números em uma expressão MPN são sempre números inteiros. Eles podem ser negativos ou zero, mas nunca terão uma parte fracionária.
• Isso é código-golfe , então o menor envio válido (medido em bytes) vence.
• Você pode usar caracteres diferentes para ~e ,, se desejar.

Casos de teste

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

• Experimente online! (com um único MPN e valor)
• Tente todos os casos de teste com -100..100como valores
• Visualize o código intermediário gerado, para todos os casos de teste (com 666 como o valor)

Explicação

Percebi desde o início que os infinitos tornam isso insustentável para gerar matrizes e testar valores.

Eu olhei para os intervalos, mas no .Net eles não têm o intervalo necessário (o comprimento do intervalo é limitado a um número inteiro assinado (32 bits), portanto, mesmo se estiver tudo bem em limitar o intervalo a um int assinado de 32 bits , Eu não teria sido capaz de lidar com todos os intervalos.

Então comecei a pensar sobre isso em termos de início e fim e, finalmente, uma série de testes booleanos e comecei a criar um monte de substituições de regex para transformar uma MPN em uma expressão booleana que o PowerShell entende.

Basicamente, dividi isso em algumas regras:

• As faixas eram mais fáceis de trabalhar primeiro, porque elas não podem ser expressões de ambos os lados, mas a abertura era uma dor para implementar em breve. A premissa é 2~8como dizer n >=2 && n <=8, mas quando um dos extremos estiver faltando, deixe de lado o &&lado que falta. Quando ambos estão faltando, eu iria substituí-lo originalmente por $true. O que acabei fazendo não foi realmente testar os lados ausentes, mas fiz questão de agrupar cada número ().
• e faça uma substituição direta que substitua parênteses vazios ()pelo valor de entrada. Portanto, no caso de um MPN ~8com um valor de entrada igual 55, a primeira substituição será gerada (55-ge()-and55-le(8))e a segunda substituição será criada , (55-ge55-and55-le(8))anulando essencialmente essa parte do intervalo.
• Em seguida, tive que lidar com números individuais no MPN, mas tive que tomar cuidado para não mexer com os números que inseri antes. Na verdade, são apenas números em ,listas separadas por vírgula e números individuais antes ou depois de uma skip, então usei infelizes informações longas.
• skipé basicamente o mesmo que -and -noteu faço uma substituição direta de skippara -and!(usando !como abreviação de -not).
• A próxima coisa complicada foi a baixa ordem de precedência para as vírgulas restantes. Originalmente, eu os substituí por, -ormas não 16,17 skip 16contava com as expressões subseqüentes, assim como estava gerando código ($n-eq16)-or($n-eq17) -and! ($n-eq16). Precisava de parênteses, mas isso parecia impraticável com uma substituição direta. Como todas as outras coisas foram substituídas, exceto vírgulas, e elas têm a menor precedência, eu apenas divido toda a cadeia gerada nas vírgulas restantes, depois coloquei cada elemento entre parênteses e juntei-o novamente -or.

Por fim, o código gerado é apenas canalizado para Invoke-Expression( iex) para ser executado e, em seguida, obtemos o resultado booleano ( você pode ver o código que é gerado em vez do resultado aqui ).

Isso levou muito tempo, e tenho certeza de que há espaço para extrair mais alguns bytes, mas não consigo mais olhar para isso :-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}

Experimente em Ideone.

Ungolfed:

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 graças 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,'-'))

Uau. Isso não foi fácil por causa de todos os casos extremos, mas acho que consegui. Só espero que não haja casos especiais que possam quebrar as expressões regulares usadas. Vou jogar mais isso sempre que puder.

Snippet de teste

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

Isso é semelhante à resposta do PowerShell (ou acho que não entendo o PowerShell). Ele pega o número como argumento e o código como valor no fluxo de entrada, assim:main { push("1~9") | f(5) } .

Eu acho que funciona, pelo menos resolve todos os casos de teste. O script abaixo pode ser usado para verificar isso.

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
}

E os testes:

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