Zufallsgenerator

8

Schreiben Sie das kürzeste Programm, das Sie können, in jeder Sprache, aus der eine kontextfreie Grammatik und die Anzahl der zu produzierenden Sätze gelesen werden stdin, und generieren Sie so viele zufällige Sätze aus der Grammatik.

Eingang

Die Eingabe erfolgt im folgenden Format:

n <START>
{"<A>":["as<A>df","0<A>","<B><C>","A<A>", ...], "<B>":["1<C>1","\<<T>>",...], ...}

nist die Anzahl der zu generierenden Sätze. <START>ist die Kennung des nicht terminalen Startsymbols.

Die Grammatik ist im {} enthalten und wie folgt formatiert:

  • Regeln haben die Form "<S>":[productions]. <S>ist die Kennung des Nichtterminals.
    • Regeln werden durch Kommas getrennt.
    • Die rechte Seite einer Regel ist eine Zeichenfolge in doppelten Anführungszeichen, deren erstes und letztes Zeichen "<" bzw. ">" sind. Das verbleibende Zeichen sollte in [A-Z](Alpha in Großbuchstaben) sein.
  • productionsist eine durch Kommas getrennte Liste von Zeichenfolgen in doppelten Anführungszeichen, die Produktionen darstellen. Alle Zeichen, einschließlich Leerzeichen, in der Regel sind Terminalsymbole, mit Ausnahme derjenigen, die in spitzen Klammern ( "<"und ">") eingeschlossen sind. Dies sind nicht-Terminalsymbole und befinden sich auf der linken Seite einer anderen Regel. Eine offene Winkelhalterung kann ausgeblendet werden, es ist jedoch nicht erforderlich, einer geschlossenen Winkelhalterung zu entkommen.
    • Produktionen enthalten keine Zeilenumbrüche oder die Zeilenumbruchsequenz.

Ausgabe

Sie sollten jeden generierten Satz stdoutmit einem nachgestellten Zeilenumbruch drucken.

Testfälle
5 Sätze ausgewogener Klammern:

5 <S>
{"<S>":["<S><S>", "(<S>)", ""]}

Beispielergebnis:

(())()
()
()()()

(())(()())((((()))()()))

4 postfix arithmetische Ausdrücke (beachten Sie, dass Leerzeichen innerhalb von Zeichenfolgen von Bedeutung sind, Leerzeichen an anderer Stelle nicht):

4 <S>
{"<S>":["<N>", "<S> <S> <O>"], "<O>":["+","-","*","/"], "<N>":["<D><N>", "<D>"],
 "<D>":["1","2","3","4","5","6","7","8","9","0"]}

Beispielergebnis:

1535235 76451 +
973812
312 734 99 3 + / *
1 1 1 1 1 + - * +
Hoa Long Tam
quelle
2
Können wir ein Beispiel für eine Eingabe / Ausgabe haben? (Ich weiß, dass die genaue Ausgabe in jedem Fall anders wäre, aber nur als Referenz).
Dogbert
Gute Herausforderung, aber ich denke, das Eingabeformat ist komplizierter als es sein könnte. Angesichts der Tatsache, dass das Eingabeformat in erster Linie auf JSON basiert, würde dies JavaScript und Sprachen mit integriertem JSON-Parsing keinen unfairen Vorteil verschaffen. Was zeigt der Backslash in \<<T>>an?
Joey Adams
1
Der Backslash entweicht der offenen Klammer. Wenn also T "1" \<<T>>erzeugt \<1>, würde das Muster erzeugen , was a <1>als endgültige Ausgabe erzeugen würde . Ja, Sprachen mit JSON-Unterstützung hätten einen kleinen Vorteil (obwohl die eckigen Klammern einen Schraubenschlüssel hineinwerfen sollten), aber dies gleicht zumindest die Wettbewerbsbedingungen für Sprachen aus, die nicht "Perl" heißen.
Hoa Long Tam
Die Regeln und Beispiele scheinen in Bezug auf die Anzahl der Leerzeichen in der Eingabe nicht ganz konsistent zu sein.
Peter Taylor
@Peter: Leerzeichen außerhalb von Zeichenfolgen sind unbedeutend. Leerzeichen innerhalb von Zeichenfolgen ist.
Hoa Long Tam

Antworten:

4

Ich wollte ein bisschen JavaScript machen. Außerdem habe ich innerlich ein wenig geweint, als ich "document.write" schrieb.

<body>
    <script type='text/javascript'>
    function foo(){
        t=document.getElementById('ta').value.split("\n");
        eval('p='+t[1]);
        t[0]=t[0].split(' ');
        while(t[0][0]--) {
            s=t[0][1]
            while(x=s.match(/<\w+>/)) {
                ps=s;
                s=s.replace(x,p[x][Math.floor(Math.random()*p[x].length)]);
            }
            document.write(s+"<br>");
        }
    }
    </script>
    <textarea id='ta' cols='80'></textarea>
    <button onclick="foo()">go</button>
</body>

Eingang:

10 <A>
{"<A>":["a<A>b","c<A>d","<B>"],"<B>":["e<C>e"],"<C>":["z","<A>","<B>"]}

Ausgabe:

ccaaceeeeezeeeeedbbdd
accccceeeezeeeedddddb
aecezedeb
eaezebe
ccccaacezedbbdddd
eeeaaaceecacezedbdeedbbbeee
acaecaeaaeacccceeeeeeeaeeezeeebeeeeeeeddddbebbebdebdb
aaceezeedbb
aacezedbb
ceeaceecacaacezedbbdbdeedbeed
Mitch
quelle
Ich denke, Sie können dies ein wenig verkürzen, indem Sie d=document;den Wert anschließend schreiben und wiederverwenden. Möglicherweise möchten Sie auch die Anzahl der Zeichen angeben.
Element118