Resolver notação de problemas matemáticos

14

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 é , 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
Esolanging Fruit
fonte
É possível usar outros caracteres para representar operadores exemplo .Para usando # em vez de ~?
rahnema1
1
@ rahnema1 Para ~e ,, mas não para skip.
Esolanging Fruit
3
Por que ~ 10,5 ~ é falso para 4? Porque que é a união de -infinity a 10 e 5 para o infinito, a primeira das quais inclui 4
ev3commander
@ ev3commander Editado. Eu sempre estrago meus casos de teste. Aposto que meus desafios seriam mais claros se não os adicionasse: P
Esolanging Fruit 5/17/17
1
@ Challenger5 Adicionei um caso de teste 6 skip 6,~que acredito ter interpretado corretamente. As outras 2 respostas até agora não a satisfazem (novamente, assumindo que estou interpretando corretamente). Se eu entendi errado, corrija-o e esclareça, mas, pelo meu entendimento, ele deve corresponder a qualquer coisa (é a união de um conjunto que não corresponde a nada com um conjunto que corresponde a tudo). Esses são os tipos de casos sobre os quais eu estava falando anteriormente, que acho que poderiam ajudar muito ao testar nossas soluções.
Briantist

Respostas:

3

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

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

briantist
fonte
2

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);
}
Denis Ibaev
fonte
1
Falha em ~ -2 na entrada -2. Também ao inserir -? antes de todos os três \ d *
Kjetil S.
@KjetilS. Corrigido para números negativos e zero.
Denis Ibaev 7/03
bom código (gramática soprado completa análise muitas vezes não é necessário, expressões regulares são mais fáceis)
Kjetil S.
1

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. Kap
fonte
@AriaAx Deve funcionar agora.
R.Rap Kap
@ R.Kap Você pode usar 1/0para Infinity.
Okx 06/03/19
@ R.Kap Tentei valor 6com a expressão 6 skip 6,~que acredito ser, truemas ela retorna false.
briantist
@briantist Na verdade, eu acredito que deve retornar falsecomo skipse aplica a tudo o que se segue ( 6,~neste caso), desde que ele é não acondicionada dentro de parênteses. Portanto, acredito que deve retornar trueem (6 skip 6),~vez de 6 skip 6,~com a entrada inteira 6.
R. Kap
@ briantist Em outras palavras, não 6 skip 6,~deve corresponder a nada , pois representa a diferença entre o conjunto {6}e o conjunto {6,-Infinity...Infinity}.
555 R. R. Kap
0

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
fergusq
fonte