Solve Math Problem Notation

Question

Imagine I have an infinite number of homework problems (!) each given an integer number.

Math Problem Notation is a notation for describing subsets of the problem using problem specifiers.

An MPN expression can consist of several things:

• A single value. This represents a set containing the number: 99 -> {99}.
• A simple range. This represents the set containing all the numbers from the beginning to the end of the range: 10~13 -> {10, 11, 12, 13}. If the left or right sides are missing, then they are assumed to be -Infinity or Infinity respectively: ~10 -> {x|x ≤ 10}; ~ -> ℤ.
• An MPN expression, followed by "skip" and another MPN expression. This represents the difference of the two sets: 10~20 skip 12~14 -> {10, 11, 15, 16, 17, 18, 19, 20}.
• Two MPN expressions, separated by a comma. This represents the union of two sets: 1,8~9,15~17 -> {1,8,9,15,16,17}.

The "skip" operator binds tighter than the comma operator, so 16,110~112 skip 16 -> {16,110,111,112} (16 is not included in the set {110,111,112}, so the excluding 16 does not matter.)

You can also put expressions in parentheses for disambiguation: 1~9 skip (2~8 skip (3~7 skip (4~6 skip 5))) -> {1,3,5,7,9}

This is the grammar:

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

---

Your task is to write a program that takes two inputs:

• An MPN expression
• A number

and outputs some truthy or falsey value depending on whether that problem is in the set described by the MPN expression.

Specifications

• You can assume that the first input is a well-formed MPN expression (i.e. that it matches the above grammar)
• Numbers in an MPN expression are always integers. They can be negative or zero, but will never have a fractional part.
• This is code-golf, so the shortest valid submission (measured in bytes) wins.
• You can use different characters for ~ and ,, if you want.

Test Cases

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

Answer 1

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

• Try it online! (with a single MPN and value)
• Try all test cases with -100..100 as values
• View the intermediate code generated, for all test cases (with 666 as the value)

Explanation

I realized early on that the infinities make this untenable for generating arrays and testing for values.

I looked into ranges but in .Net they don't have the range needed (the length of the range is limited to a signed (32 bit) integer, so even if it were ok to limit the range to a signed 32-bit int, I wouldn't have been able to handle all ranges.

So I started to just think about this in terms of starts and ends, and ultimately a series of boolean tests and started creating a bunch of regex replaces to turn an MPN into a boolean expression that PowerShell understands.

I basically broke this down into a few rules:

• Ranges were easier to work with first because they can't be expressions on either end, but the open-endedness was a pain to implement shortly. The premise is 2~8 is like saying n >=2 && n <=8, but when one of the ends is missing, leave out the && and the missing side. When both are missing, I was going to originally just replace it with $true. What I ended up doing was not really testing for the missing sides at all, but I made sure to wrap each number in ().
• and then do a straight substitution that replaces empty parentheses () with the input value. So, in the case of an MPN like ~8 with an input value of 55, the first replace will generate (55-ge()-and55-le(8)), then the second replace comes along to make it (55-ge55-and55-le(8)), essentially nullifying that part of the range.
• Next I had to deal with individual numbers in the MPN, but had to take care not to mess with the ones I inserted from before. It's really just numbers in comma , separated lists, and individual numbers before or after a skip, so I used unfortunatley long lookarounds.
• skip is basically the same as -and -not so I do a straight replace of skip to -and! (using ! as shorthand for -not).
• The next tricky thing was the low order of precendence for the remaining commas. I originally just replaced them with -or but it didn't account for subsequent expressions so 16,17 skip 16 was generating code like ($n-eq16)-or($n-eq17) -and! ($n-eq16). It needed parentheses, but that seemed unworkable with a straight replace. Since all the other things were replaced except commas, and they have the lowest precedence, I just split the entire generated string on the remaining commas, then wrapped each element in parentheses, and rejoined it with -or.

Ultimately the generated code is just piped into Invoke-Expression (iex) to be executed and then we get the boolean result (you can see the code that gets generated instead of the result here).

This took way too long, and I'm sure there's some room to squeeze out a few more bytes, but I can't look at it anymore :-p

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

Try it on 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);
}

Answer 3

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

(-5 bytes thanks to 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,'-'))

Wow. This was not easy because of all the edge cases, but I think I did it. I just hope there are no special cases that could break the regular expressions used. I will golf this more whenever I can.

Test Snippet

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>

Answer 4

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

This is similar to the PowerShell answer (or I think so, I don't understand PowerShell). It takes the number as an argument and the code as a value in the input stream, like this: main { push("1~9") | f(5) }.

I think it works, at least it solves all test cases. The script below can be used to verify this.

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
}

And the 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