Lösen Sie die mathematische Problemnotation

14

Stellen Sie sich vor, ich habe unendlich viele Hausaufgabenprobleme (!) Mit jeweils einer ganzen Zahl.

Die mathematische Problemnotation ist eine Notation zur Beschreibung von Teilmengen des Problems mithilfe von Problemspezifizierern.

Ein MPN-Ausdruck kann aus mehreren Dingen bestehen:

  • Ein einzelner Wert. Dies stellt einen Satz mit der Nummer: 99 -> {99}.
  • Ein einfacher Bereich. Dies stellt den Satz alle Zahlen von Anfang bis zum Ende des Bereichs enthalten: 10~13 -> {10, 11, 12, 13}. Wenn die linke oder rechte Seite fehlt, dann wird angenommen , dass sie -Infinity oder Unendlichkeit sein beziehungsweise: ~10 -> {x|x ≤ 10}; ~ -> ℤ.
  • Ein MPN-Ausdruck, gefolgt von "Überspringen" und einem anderen MPN-Ausdruck. Dies stellt den Unterschied der beiden Sätze: 10~20 skip 12~14 -> {10, 11, 15, 16, 17, 18, 19, 20}.
  • Zwei MPN-Ausdrücke, durch Komma getrennt. Dies stellt die Vereinigung von zwei Sätzen: 1,8~9,15~17 -> {1,8,9,15,16,17}.

Der "Überspringen" -Operator bindet enger als der Komma-Operator, also 16,110~112 skip 16 -> {16,110,111,112}(16 ist nicht in der Menge enthalten {110,111,112}, daher spielt das Ausschließen von 16 keine Rolle.)

Sie können Ausdrücke auch zur Disambiguierung in Klammern setzen: 1~9 skip (2~8 skip (3~7 skip (4~6 skip 5))) -> {1,3,5,7,9}

Das ist die Grammatik:

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

Ihre Aufgabe ist es, ein Programm zu schreiben, das zwei Eingaben übernimmt:

  • Ein MPN-Ausdruck
  • Eine Zahl

und gibt in Abhängigkeit davon, ob sich dieses Problem in der Menge befindet, die durch den MPN-Ausdruck beschrieben wird, einen Wahrheitsgehalt oder einen falschen Wert aus.

Spezifikationen

  • Sie können davon ausgehen, dass die erste Eingabe ein wohlgeformter MPN-Ausdruck ist (dh, dass er der obigen Grammatik entspricht).
  • Zahlen in einem MPN-Ausdruck sind immer ganze Zahlen. Sie können negativ oder null sein, haben aber niemals einen Bruchteil.
  • Dies ist , also gewinnt die kürzeste gültige Übermittlung (gemessen in Bytes).
  • Sie können verschiedene Zeichen für ~und verwenden ,, wenn Sie möchten.

Testfälle

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
quelle
Ist es möglich, andere Zeichen zur Darstellung von Operatoren zu verwenden? Zum Beispiel # anstelle von ~
rahnema1
1
@ rahnema1 Für ~und ,, aber nicht für skip.
Esolanging Fruit
3
Warum ist ~ 10,5 ~ für 4 falsch? Denn das ist die Vereinigung von -infinity zu 10 und 5 zu Infinity, von denen die erste 4
ev3commander
@ ev3commander Bearbeitet. Ich vermassle immer meine Testfälle. Ich wette, meine Herausforderungen wären klarer, wenn ich sie nicht hinzufüge: P
Esolanging Fruit
1
@ Challenger5 Ich habe einen Testfall hinzugefügt, 6 skip 6,~den ich meiner Meinung nach richtig interpretiert habe. Die anderen 2 Antworten sind noch nicht zufriedenstellend (vorausgesetzt, ich interpretiere richtig). Wenn ich es falsch verstanden habe, korrigieren Sie es bitte und klären Sie es, aber meines Wissens sollte es mit allem übereinstimmen (es ist die Vereinigung einer Menge, die mit nichts übereinstimmt, mit einer Menge, die mit allem übereinstimmt). Dies sind die Fälle, über die ich vorhin gesprochen habe und von denen ich denke, dass sie beim Testen unserer Lösungen sehr hilfreich sein können.
Briantist

Antworten:

3

PowerShell , 189 bis 195 Byte

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

Erläuterung

Ich habe früh gemerkt, dass die Unendlichkeit dies unhaltbar macht, um Arrays zu generieren und auf Werte zu testen.

Ich habe Bereiche untersucht, aber in .Net fehlt der erforderliche Bereich (die Länge des Bereichs ist auf eine 32-Bit-Ganzzahl mit Vorzeichen beschränkt). Selbst wenn es in Ordnung wäre, den Bereich auf eine 32-Bit-Ganzzahl mit Vorzeichen zu beschränken Ich hätte nicht alle Bereiche bewältigen können.

Also habe ich angefangen, mich nur mit Anfang und Ende und schließlich mit einer Reihe von Booleschen Tests zu befassen, und angefangen, eine Reihe von Regex-Ersetzungen zu erstellen, um einen MPN in einen Booleschen Ausdruck zu verwandeln, den PowerShell versteht.

Ich habe dies im Grunde genommen in ein paar Regeln unterteilt:

  • Bereiche waren zunächst einfacher zu bearbeiten, da sie keine Ausdrücke an beiden Enden sein können, aber die Offenheit war ein Problem, das in Kürze umgesetzt werden musste. Die Prämisse ist 2~8wie gesagt n >=2 && n <=8, aber wenn eines der Enden fehlt, lassen Sie die &&und die fehlende Seite weg . Wenn beide fehlen, wollte ich sie ursprünglich nur durch ersetzen $true. Am Ende habe ich nicht wirklich nach den fehlenden Seiten gesucht, aber ich habe darauf geachtet, dass ich jede Zahl einpacke ().
  • Führen Sie dann eine direkte Ersetzung durch, bei der leere Klammern ()durch den Eingabewert ersetzt werden. Im Fall einer MPN ~8mit einem Eingabewert von 55wird also die erste Ersetzung generiert (55-ge()-and55-le(8)), und dann wird die zweite Ersetzung durchgeführt, um diesen (55-ge55-and55-le(8))Teil des Bereichs im Wesentlichen zu annullieren.
  • Als nächstes musste ich mich mit einzelnen Nummern im MPN befassen, aber darauf achten, mich nicht mit den Nummern zu verwechseln, die ich zuvor eingefügt hatte. Es sind wirklich nur Zahlen in durch Kommas ,getrennten Listen und einzelne Zahlen vor oder nach einem skip, also habe ich leider lange Lookarounds verwendet.
  • skipist im grunde das selbe wie -and -notalso ich mache einen direkten ersatz von skipzu -and!(benutze !als kurzschrift für -not).
  • Die nächste schwierige Sache war die niedrige Rangordnung für die verbleibenden Kommas. Ursprünglich habe ich sie nur durch ersetzt, -oraber nachfolgende Ausdrücke wurden nicht berücksichtigt, sodass 16,17 skip 16Code wie generiert wurde ($n-eq16)-or($n-eq17) -and! ($n-eq16). Es brauchte Klammern, aber das schien mit einem Straight Replace nicht zu funktionieren. Da alle anderen Elemente mit Ausnahme von Kommas ersetzt wurden und die niedrigste Priorität haben, habe ich die gesamte generierte Zeichenfolge auf die verbleibenden Kommas aufgeteilt, dann jedes Element in Klammern eingeschlossen und es erneut mit verknüpft -or.

Letztendlich wird der generierte Code einfach in Invoke-Expression( iex) geleitet, um ausgeführt zu werden, und dann erhalten wir das boolesche Ergebnis ( Sie können den generierten Code anstelle des Ergebnisses hier sehen ).

Das hat viel zu lange gedauert und ich bin mir sicher, dass noch ein paar Bytes übrig sind, aber ich kann es mir nicht mehr ansehen :-p

Briantist
quelle
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}

Probieren Sie es auf 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
quelle
1
Schlägt für ~ -2 für Eingabe -2 fehl. Auch beim Einfügen -? vor allen drei \ d *
Kjetil S.
@KjetilS. Bei negativen Zahlen und Nullen behoben.
Denis Ibaev
Nizza Code (vollständige Grammatikanalyse oft nicht erforderlich, Regexes sind einfacher)
Kjetil S.
1

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

(-5 Bytes dank 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,'-'))

Beeindruckend. Das war wegen all der Randfälle nicht einfach, aber ich glaube, ich habe es geschafft. Ich hoffe nur , dass es keine Sonderfälle gibt, die gegen die verwendeten regulären Ausdrücke verstoßen könnten. Ich werde mehr Golf spielen, wenn ich kann.

Testschnipsel

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
quelle
@AriaAx Es sollte jetzt funktionieren.
R. Kap
@ R.Kap könntest du 1/0für verwenden Infinity.
Okx
@ R.Kap Ich habe Wert 6mit dem Ausdruck versucht, von dem 6 skip 6,~ich glaube, dass er sein sollte, trueaber er gibt zurück false.
Briantist
@briantist Eigentlich glaube ich , dass sollte zurückkehren falseals skipbezieht alles , das es (folgt 6,~in diesem Fall), solange es nicht in Klammern eingewickelt. Deshalb halte ich es zurückgeben sollte trueauf (6 skip 6),~anstatt 6 skip 6,~mit Integer - Eingang 6.
R. Kap
@briantist Mit anderen Worten, 6 skip 6,~sollte mit nichts übereinstimmen , da es den Unterschied zwischen der Menge {6}und der Menge darstellt {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"}

Dies ähnelt der PowerShell-Antwort (oder ich glaube, ich verstehe PowerShell nicht). Die Zahl wird als Argument und der Code als Wert im Eingabestream verwendet main { push("1~9") | f(5) }.

Ich denke es funktioniert, zumindest löst es alle Testfälle. Das folgende Skript kann verwendet werden, um dies zu überprüfen.

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
}

Und die 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
fergusq
quelle