14
\$\begingroup\$

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 , 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
\$\endgroup\$
  • \$\begingroup\$ Is it possible to use other characters to represent operators?.For example using # instead of ~ \$\endgroup\$ – rahnema1 Mar 5 '17 at 21:25
  • 1
    \$\begingroup\$ @rahnema1 For ~ and ,, but not for skip. \$\endgroup\$ – Esolanging Fruit Mar 5 '17 at 22:17
  • 3
    \$\begingroup\$ Why is ~10,5~ false for 4? Because that is the union of -infinity to 10 and 5 to infinity, the first of which includes 4 \$\endgroup\$ – ev3commander Mar 5 '17 at 22:48
  • \$\begingroup\$ @ev3commander Edited. I always mess up on my test cases. I bet my challenges would be clearer if I didn't add them :P \$\endgroup\$ – Esolanging Fruit Mar 5 '17 at 23:14
  • 1
    \$\begingroup\$ @Challenger5 I've added a test case 6 skip 6,~ which I believe I've interpreted correctly. The other 2 answers so far don't satisfy it (again, assuming I'm interpreting correctly). If I've misunderstood please correct it and clarify, but from my understanding, it should match anything (it's the union of a set that matches nothing with a set that matches everything). These are the kinds of cases I was talking about earlier that I think could help out a lot when testing our solutions. \$\endgroup\$ – briantist Mar 6 '17 at 15:24
3
\$\begingroup\$

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

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

\$\endgroup\$
2
\$\begingroup\$

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);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Fails for ~-2 for input -2. Also when inserting -? before all three \d* \$\endgroup\$ – Kjetil S. Mar 7 '17 at 2:13
  • \$\begingroup\$ @KjetilS. Fixed for negative numbers and zero. \$\endgroup\$ – Denis Ibaev Mar 7 '17 at 7:21
  • \$\begingroup\$ nice code (full blown grammar parsing often not needed, regexes are easier) \$\endgroup\$ – Kjetil S. Mar 8 '17 at 23:23
1
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ @AriaAx It should work now. \$\endgroup\$ – R. Kap Mar 6 '17 at 10:00
  • \$\begingroup\$ @R.Kap You could use 1/0 for Infinity. \$\endgroup\$ – Okx Mar 6 '17 at 10:04
  • \$\begingroup\$ @R.Kap I tried value 6 with the expression 6 skip 6,~ which I believe should be true but it returns false. \$\endgroup\$ – briantist Mar 6 '17 at 14:44
  • \$\begingroup\$ @briantist Actually, I believe that should return false as skip applies to everything that follows it (6,~ in this case) as long as it is not wrapped inside parenthesis. Therefore, I believe it should return true on (6 skip 6),~ rather than 6 skip 6,~ with integer input 6. \$\endgroup\$ – R. Kap Mar 6 '17 at 16:52
  • \$\begingroup\$ @briantist In other words, 6 skip 6,~ should match nothing as it represents the difference between the set {6} and the set {6,-Infinity...Infinity}. \$\endgroup\$ – R. Kap Mar 6 '17 at 16:59
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.