Resolver notación de problemas matemáticos

14

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 , 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
Fruta Esolanging
fuente
¿Es posible usar otros caracteres para representar operadores? Por ejemplo, usando # en lugar de ~
rahnema1
1
@ rahnema1 Para ~y ,, pero no para skip.
Esolanging Fruit
3
¿Por qué es ~ 10,5 ~ falso para 4? Porque esa es la unión de -infinito a 10 y 5 a infinito, el primero de los cuales incluye 4
ev3commander
@ ev3commander Editado. Siempre me equivoco en mis casos de prueba. Apuesto a que mis desafíos serían más claros si no los añadiera: P
Esolanging Fruit
1
@ Challenger5 He añadido un caso de prueba 6 skip 6,~que creo que he interpretado correctamente. Las otras 2 respuestas hasta ahora no lo satisfacen (nuevamente, suponiendo que estoy interpretando correctamente). Si no he entendido bien, corríjalo y aclare, pero, según tengo entendido, debería coincidir con cualquier cosa (es la unión de un conjunto que no coincide con nada con un conjunto que coincide con todo). Estos son los tipos de casos de los que hablaba anteriormente que creo que podrían ayudar mucho al probar nuestras soluciones.
briantist

Respuestas:

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

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

briantista
fuente
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}

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);
}
Denis Ibaev
fuente
1
Falla para ~ -2 para la entrada -2. También al insertar -? antes de los tres \ d *
Kjetil S.
@KjetilS. Corregido para números negativos y cero.
Denis Ibaev
código agradable (el análisis de gramática completo a menudo no es necesario, las expresiones regulares son más fáciles)
Kjetil S.
1

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. Kap
fuente
@AriaAx Debería funcionar ahora.
R. Kap
@ R.Kap Podrías usar 1/0para Infinity.
Okx
@ R.Kap Probé el valor 6con la expresión 6 skip 6,~que creo que debería ser truepero devuelve false.
briantist
@briantist En realidad, creo que debería volver falsecomo skipse aplica a todo lo que le sigue ( 6,~en este caso), siempre que se no se ajusta dentro de paréntesis. Por lo tanto, creo que debería regresar trueen (6 skip 6),~lugar de 6 skip 6,~con una entrada entera 6.
R. Kap
@briantist En otras palabras, no 6 skip 6,~debe coincidir con nada, ya que representa la diferencia entre el conjunto {6}y el conjunto {6,-Infinity...Infinity}.
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"}

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