Wyobraź sobie, że mam nieskończoną liczbę problemów domowych (!), Z których każdy ma liczbę całkowitą.

Matematyka Notacja problemu to notacja opisująca podzbiory problemu za pomocą specyfikatorów problemu.

Wyrażenie MPN może składać się z kilku rzeczy:

• Jedna wartość. Stanowi zbiór zawierający numer: 99 -> {99}.
• Prosty zakres. Stanowi zbiór zawierający wszystkie numery od początku do końca zakresu: 10~13 -> {10, 11, 12, 13}. Jeżeli lewa lub prawa strona brakuje, to są one traktowane jako -Infinity lub Nieskończoność odpowiednio: ~10 -> {x|x ≤ 10}; ~ -> ℤ.
• Wyrażenie MPN, po którym następuje „pomiń” i inne wyrażenie MPN. Stanowi różnicę dwóch zestawach: 10~20 skip 12~14 -> {10, 11, 15, 16, 17, 18, 19, 20}.
• Dwa wyrażenia MPN, oddzielone przecinkiem. Stanowi to związek dwóch zestawach: 1,8~9,15~17 -> {1,8,9,15,16,17}.

Operator „pomiń” wiąże się mocniej niż operator przecinka, więc 16,110~112 skip 16 -> {16,110,111,112}(16 nie jest zawarte w zestawie {110,111,112}, więc wykluczenie 16 nie ma znaczenia).

Możesz także umieścić wyrażenia w nawiasach, aby uzyskać jednoznaczność: 1~9 skip (2~8 skip (3~7 skip (4~6 skip 5))) -> {1,3,5,7,9}

Oto gramatyka:

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

Twoim zadaniem jest napisanie programu, który przyjmuje dwa dane wejściowe:

• Wyrażenie MPN
• Numer

i generuje pewną wartość prawdy lub falseya w zależności od tego, czy problem występuje w zestawie opisanym przez wyrażenie MPN.

Dane techniczne

• Możesz założyć, że pierwsze wejście jest poprawnie sformułowanym wyrażeniem MPN (tzn. Że pasuje do powyższej gramatyki)
• Liczby w wyrażeniu MPN są zawsze liczbami całkowitymi. Mogą być ujemne lub zerowe, ale nigdy nie będą miały części ułamkowej.
• To jest golf golfowy , więc wygrywa najkrótsze prawidłowe zgłoszenie (mierzone w bajtach).
• Możesz użyć różnych znaków dla ~i ,, jeśli chcesz.

Przypadki testowe

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 bajtów

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

• Wypróbuj online! (z jednym numerem MPN i wartością)
• Wypróbuj wszystkie przypadki testowe z -100..100 wartościami as
• Wyświetl wygenerowany kod pośredni dla wszystkich przypadków testowych (z wartością 666)

Wyjaśnienie

Wcześnie zdałem sobie sprawę, że nieskończoności sprawiają, że jest to niemożliwe do generowania tablic i testowania wartości.

Patrzyłem na zakresy, ale w .Net nie mają wymaganego zakresu ( długość zakresu jest ograniczona do liczby całkowitej ze znakiem (32-bitowym), więc nawet jeśli można ograniczyć zakres do 32-bitowej liczby całkowitej ze znakiem , Nie byłbym w stanie obsłużyć wszystkich zakresów.

Zacząłem więc myśleć o tym w kategoriach początków i końców, a ostatecznie serię testów boolowskich i zacząłem tworzyć kilka wyrażeń regularnych, aby przekształcić MPN w wyrażenie boolowskie, które rozumie PowerShell.

Zasadniczo podzieliłem to na kilka zasad:

• Przedziały były łatwiejsze do pracy na początku, ponieważ nie mogą być wyrażeniami na żadnym końcu, ale otwartość była trudna do wdrożenia w najbliższym czasie. Przesłanka jest 2~8jak powiedzenie n >=2 && n <=8, ale gdy brakuje jednego z końców, pomiń &&stronę brakującą. Kiedy brakuje obu, pierwotnie zamierzałem po prostu go zastąpić $true. Skończyło się na tym, że tak naprawdę wcale nie testowałem brakujących stron, ale upewniłem się, że zapakowałem każdą liczbę ().
• a następnie wykonaj proste podstawienie, które zastępuje puste nawiasy ()wartością wejściową. Tak więc, w przypadku numeru MPN, na przykład ~8o wartości wejściowej 55, pierwsza zamiana wygeneruje (55-ge()-and55-le(8)), a następnie pojawi się druga zamiana, aby ją zrobić (55-ge55-and55-le(8)), zasadniczo unieważniając tę ​​część zakresu.
• Następnie miałem do czynienia z indywidualnymi numerami w MPN, ale musiałem uważać, aby nie zadzierać z tymi, które wstawiłem wcześniej. To tak naprawdę tylko liczby na ,listach oddzielonych przecinkami oraz pojedyncze liczby przed lub po skip, więc użyłem niefortunnych długich spojrzeń.
• skipjest w zasadzie taki sam, jak -and -notja, więc dokonuję prostej zamiany skipna -and!(używając !jako skrót -not).
• Kolejną trudną rzeczą było niskie uporządkowanie pozostałych przecinków. Pierwotnie po prostu je zastąpiłem, -orale nie uwzględniało to kolejnych wyrażeń, więc 16,17 skip 16generowałem podobny kod ($n-eq16)-or($n-eq17) -and! ($n-eq16). Potrzebował nawiasów, ale wydawało się to niewykonalne przy prostym zastąpieniu. Ponieważ wszystkie inne rzeczy zostały zastąpione oprócz przecinków i mają one najniższy priorytet, po prostu podzieliłem cały wygenerowany ciąg na pozostałe przecinki, następnie zawinąłem każdy element w nawiasy i ponownie dołączyłem -or.

Ostatecznie wygenerowany kod jest po prostu przesyłany do Invoke-Expression( iex) w celu wykonania, a następnie otrzymujemy wynik boolowski (tutaj możesz zobaczyć kod, który zostanie wygenerowany zamiast wyniku ).

Trwało to zbyt długo i jestem pewien, że jest miejsce na wyciśnięcie jeszcze kilku bajtów, ale nie mogę już na to patrzeć :-p

Perl, 99 130 bajtów

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}

Wypróbuj na Ideone.

Nie golfowany:

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 bajtów

(-5 bajtów dzięki 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,'-'))

Łał. Nie było to łatwe z powodu wszystkich skrajnych przypadków, ale myślę, że to zrobiłem. Mam tylko nadzieję, że nie ma specjalnych przypadków, które mogłyby złamać użyte wyrażenia regularne. Będę grał w golfa więcej, kiedy tylko będę mógł.

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>

Röda + bc, 183 bajtów

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

Jest to podobne do odpowiedzi programu PowerShell (lub tak myślę, nie rozumiem PowerShell). Zajmuje liczbę jako argument i kod jako wartość w strumieniu wejściowym, na przykład: main { push("1~9") | f(5) }.

Myślę, że to działa, przynajmniej rozwiązuje wszystkie przypadki testowe. Poniższy skrypt może być użyty do weryfikacji tego.

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
}

A testy:

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