Eine Aktivität, die ich manchmal mache, wenn ich gelangweilt bin, besteht darin, ein paar Zeichen in übereinstimmenden Paaren zu schreiben. Ich zeichne dann Linien (über die Spitzen, niemals unter), um diese Charaktere zu verbinden. Zum Beispiel könnte ich schreiben und dann die Linien zeichnen als:
Oder ich schreibe
Sobald ich diese Linien gezeichnet habe, versuche ich, geschlossene Schleifen um Blöcke zu zeichnen, damit meine Schleife keine der Linien schneidet, die ich gerade gezeichnet habe. Zum Beispiel können wir im ersten die einzige Schleife um das ganze Ding zeichnen, aber im zweiten können wir eine Schleife nur um das s (oder alles andere) zeichnen.
Wenn wir ein wenig damit herumspielen, werden wir feststellen, dass einige Zeichenfolgen nur so gezeichnet werden können, dass geschlossene Schleifen alle oder keine Buchstaben enthalten (wie in unserem ersten Beispiel). Wir werden solche Zeichenfolgen als gut verknüpfte Zeichenfolgen bezeichnen.
Beachten Sie, dass einige Zeichenfolgen auf verschiedene Arten gezeichnet werden können. Zum Beispiel kann auf beide der folgenden Arten gezeichnet werden (und ein drittes nicht enthalten):
Wenn einer dieser Wege so gezeichnet werden kann, dass eine geschlossene Schleife einige der Zeichen enthält, ohne eine der Linien zu schneiden, ist die Zeichenfolge nicht richtig verknüpft. (so ist nicht gut verknüpft)
Aufgabe
Ihre Aufgabe ist es, ein Programm zu schreiben, um Zeichenfolgen zu identifizieren, die gut verknüpft sind. Ihre Eingabe besteht aus einer Zeichenfolge, bei der jedes Zeichen gerade oft vorkommt, und Ihre Ausgabe sollte einen von zwei unterschiedlichen konsistenten Werten enthalten, einen, wenn die Zeichenfolgen gut verknüpft sind, und den anderen.
Darüber hinaus muss das Programm eine gut angebundenen String Bedeutung
Jedes Zeichen erscheint in Ihrem Programm gerade oft.
Es sollte den Wahrheitswert ausgeben, wenn es selbst übergeben wird.
Ihr Programm sollte in der Lage sein, die richtige Ausgabe für eine beliebige Zeichenfolge aus druckbaren ASCII-Zeichen oder für Ihr eigenes Programm zu erstellen. Mit jedem Zeichen erscheint eine gerade Anzahl von Malen.
Antworten werden nach ihrer Länge in Bytes bewertet, wobei weniger Bytes eine bessere Bewertung darstellen.
Hinweis
Eine Zeichenfolge ist nicht gut verknüpft, wenn eine zusammenhängende, nicht leere, strikte Teilzeichenfolge vorhanden ist, sodass jedes Zeichen in dieser Teilzeichenfolge eine gerade Anzahl von Malen vorkommt.
Testfälle
abcbac -> True
abbcac -> False
bbbb -> False
abacbc -> True
abcbabcb -> True
abcbca -> False
quelle
abcbca -> False
.there
.Antworten:
Regex (ECMAScript 2018 oder .NET),
1401261181009882 Byte^(?!(^.*)(.+)(.*$)(?<!^\2|^\1(?=(|(<?(|(?!\8).)*(\8|\3$){1}){2})*$).*(.)+\3$)!?=*)
Dies ist viel langsamer als die 98-Byte-Version, da die
^\1
vom Lookahead übrig bleibt und somit danach ausgewertet wird. Unten sehen Sie einen einfachen Umschalter, der die Geschwindigkeit wieder herstellt. Aus diesem Grund können die beiden unten aufgeführten TIOs nur einen kleineren Testfall als zuvor ausführen, und der .NET-Test ist zu langsam, um seinen eigenen regulären Ausdruck zu überprüfen.Probieren Sie es online! (ECMAScript 2018)
Probieren Sie es online! (.NETZ)
Um 18 Bytes (118 → 100) zu löschen , habe ich schamlos eine wirklich nette Optimierung aus Neils Regex gestohlen , die die Notwendigkeit vermeidet, einen Lookahead in den negativen Lookbehind zu setzen (was einen uneingeschränkten Regex von 80 Bytes ergibt). Danke, Neil!
Das wurde obsolet, als es dank der Ideen von jaytea unglaubliche 16 weitere Bytes verlor (98 → 82), was zu einem uneingeschränkten Regex von 69 Bytes führte! Es ist viel langsamer, aber das ist Golf!
Beachten Sie, dass die
(|(
No-Ops für eine gute Verknüpfung des regulären Ausdrucks dazu führen, dass der Ausdruck unter .NET sehr langsam ausgewertet wird. Sie haben diesen Effekt in ECMAScript nicht, da optionale Übereinstimmungen mit der Breite Null als Nicht-Übereinstimmungen behandelt werden .ECMAScript verbietet Quantifizierer für Behauptungen. Dies erschwert das Golfen bei eingeschränkten Quellenanforderungen . Zu diesem Zeitpunkt ist es jedoch so gut, dass ich nicht glaube, dass eine Aufhebung dieser besonderen Einschränkung weitere Golfmöglichkeiten eröffnen würde.
Ohne die zusätzlichen Zeichen, die erforderlich sind, um die Einschränkungen zu umgehen (
101 bis69 Byte):^(?!(.*)(.+)(.*$)(?<!^\2|^\1(?=((((?!\8).)*(\8|\3$)){2})*$).*(.)+\3))
Es ist langsam, aber diese einfache Bearbeitung (für nur 2 zusätzliche Bytes) gewinnt die verlorene Geschwindigkeit wieder und mehr:
^(?!(.*)(.+)(.*$)(?<!^\2|(?=\1((((?!\8).)*(\8|\3$)){2})*$)^\1.*(.)+\3))
Ich schrieb es Vorgriff - Molekular (unter Verwendung von
10369 Bytes) , bevor es an variabler Länge Lookbehind Umwandlung:^(?!.*(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$))
Und um meine Regex selbst besser zu verknüpfen, habe ich eine Variante der oben genannten Regex verwendet:
(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$)\1
In der Verwendung mit
regex -xml,rs -o
gibt dies eine strenge Teilzeichenfolge der Eingabe an, die eine gerade Zahl für jedes Zeichen enthält (sofern vorhanden). Sicher, ich hätte ein Nicht-Regex-Programm schreiben können, um dies für mich zu tun, aber wo wäre der Spaß dabei?quelle
Gelee, 20 Bytes
Probieren Sie es online!
Die erste Zeile wird ignoriert. Es ist nur da, um die Bedingung zu erfüllen, dass jedes Zeichen eine gerade Anzahl von Malen erscheint.
In der nächsten Zeile
Ġ
werden die Indizes zuerst nach ihrem Wert gruppiert. Wenn wir dann die Länge jeder Unterliste in der resultierenden Liste (Ẉ
) nehmen, erhalten wir die Häufigkeit, mit der jedes Zeichen erscheint. Um zu überprüfen, ob einer dieser Werte ungerade ist , erhalten wir den letzten WertḂ
jeder Zählung und fragen, ob dortẸ
ein wahrer Wert (ungleich Null) vorhanden ist.Daher gibt diese Hilfsverknüpfung zurück, ob ein Teilstring nicht eingekreist werden kann.
Im Hauptlink nehmen wir alle Teilzeichenfolgen von input (
Ẇ
) undṖ
op vom letzten (damit wir nicht prüfen, ob die gesamte Zeichenfolge eingekreist werden kann) und führen den Hilfslink (Ç
) auf einer€
Teilzeichenfolge aus. Das Ergebnis ist dann, ob alleẠ
Teilzeichenfolgen nicht eingekreist werden können.quelle
J , 34 Bytes
Probieren Sie es online!
-8 Bytes dank FrownyFrog
Original
J , 42 Bytes
Probieren Sie es online!
Erläuterung
quelle
abc
, nur der Perl-Eintrag "scheitert" nicht daran. (Es hat jedoch andere Probleme.)1:@':.,02|~*'=1(#.,)*/@(0=2|#/.~)\.\
2:@':.,|~*'>1(#.,)*/@(1>2|#/.~)\.\
scheint auch gültigPython 3.8 (Vorabversion) , 66 Byte
Probieren Sie es online!
Die Ära der Zuweisungsausdrücke steht vor der Tür. Mit dem in Python 3.8 enthaltenen PEP 572 wird Golfen niemals so sein wie zuvor. Sie können die frühen Entwickler - Vorschau 3.8.0a1 installieren hier .
Mithilfe von Zuweisungsausdrücken können Sie
:=
einer Variablen inline zuweisen, während Sie diesen Wert auswerten. Zum Beispiel(a:=2, a+1)
gibt(2, 3)
. Dies kann natürlich verwendet werden, um Variablen zur Wiederverwendung zu speichern, aber hier gehen wir einen Schritt weiter und verwenden sie als Akkumulator in einem Verständnis.Dieser Code berechnet beispielsweise die kumulativen Summen
[1, 3, 6]
Beachten Sie, wie bei jedem Durchlauf durch das Listenverständnis die kumulative Summe
t
um erhöhtx
und der neue Wert in der vom Verständnis erstellten Liste gespeichert wird.In ähnlicher Weise wird
b:=b^{c}
der Zeichensatz aktualisiert,b
um umzuschalten, ob er Zeichen enthältc
, und es wird der neue Wert von ausgewertetb
. Der Code[b:=b^{c}for c in l]
iteriert also über die Zeichenc
inl
und akkumuliert den Zeichensatz, der ungerade oft in jedem nicht leeren Präfix angezeigt wird.Diese Liste wird auf Duplikate überprüft, indem stattdessen ein Set-Verständnis erstellt wird und überprüft wird, ob die Länge kleiner als die von ist
s
, was bedeutet, dass einige Wiederholungen reduziert wurden. Wenn dies der Fall ist, bedeutet die Wiederholung, dass in dems
zwischen diesen Zeitpunkten gesehenen Teil jedes Zeichen auf eine gerade Anzahl von Zahlen gestoßen ist, wodurch die Zeichenfolge nicht gut verknüpft ist. In Python ist es nicht zulässig, dass Mengen von Mengen nicht komprimierbar sind. Daher werden die inneren Mengen stattdessen in Zeichenfolgen konvertiert.Die Menge
b
wird als optionales Argument initialisiert und im Funktionsumfang erfolgreich geändert. Ich befürchtete, dass die Funktion dadurch nicht wiederverwendbar wird, aber sie scheint zwischen den Läufen zurückgesetzt zu werden.Für die Quellenbeschränkung werden ungepaarte Zeichen am Ende in einen Kommentar eingefügt. Schreiben
for(c)in l
eher alsfor c in l
die zusätzlichen Pars kostenlos storniert. Wir legenid
den Anfangssatz anb
, der harmlos ist, da er als jeder Satz beginnen kann, aber der leere Satz kann nicht geschrieben werden,{}
da Python ein leeres Wörterbuch erstellt. Da die Buchstabeni
undd
zu denen gehören, die gepaart werden müssen, können wir die Funktionid
dort platzieren.Beachten Sie, dass der Code negierte Boolesche Werte ausgibt, sodass er sich selbst korrekt angibt
False
.quelle
Python 2 , 74 Bytes
Probieren Sie es online!
Durchläuft die Zeichenfolge und verfolgt dabei
P
den Zeichensatz, der bisher ungerade oft gesehen wurde. In der Listed
werden alle früheren Werte von gespeichertP
, und wenn die aktuelleP
bereits angezeigt wirdd
, bedeutet dies, dass in den Zeichen, die seit dieser Zeit angezeigt wurden, jedes Zeichen eine gerade Anzahl von Malen aufgetreten ist. Wenn ja, prüfen Sie, ob wir die gesamte Eingabe durchlaufen haben: Wenn ja, akzeptieren Sie, weil die gesamte Zeichenfolge wie erwartet gepaart ist, und lehnen Sie sie ansonsten ab.Nun zur Quellenbeschränkung. Charaktere, die gepaart werden müssen, werden an verschiedenen harmlosen Stellen abgelegt, die nachfolgend unterstrichen sind:
Der
f<s
Wert wird0
beim Pairing eines ausgewertetf
, wobei der Funktionsname auchf
so genutzt wird, dass er definiert ist (zum Zeitpunkt des Funktionsaufrufs). Der0^0
Wert absorbiert ein^
Symbol.Die
0
inP={0}
ist bedauerlich: in Python{}
auswertet auf eine leere dict statt einer leeren Menge , wie wir wollen, und hier können wir in jedem Nicht-Zeichenelement setzen und es wird harmlos sein. Ich sehe jedoch nichts, was ich noch hinzufügen könnte, und habe a eingefügt0
und dupliziertbmn0
, was 2 Bytes kostet. Beachten Sie, dass anfängliche Argumente ausgewertet werden, wenn die Funktion definiert wird. Daher können hier keine Variablen eingegeben werden, die wir selbst definieren.quelle
Perl 6 , 76 Bytes
Probieren Sie es online!
Ein beliebiges Lambda, das eine None-Junction von None-Junctions zurückgibt, die auf einen Wahrheits- / Falsey-Wert verfälscht werden kann. Ich würde empfehlen, nicht das zu entfernen
?
, was das Rückgabeergebnis beeinträchtigt, da sonst die Ausgabe ziemlich groß wird .Diese Lösung ist ein wenig komplizierter als nötig, aufgrund mehrerer beteiligten Funktionen nicht verknüpft werden, zum Beispiel
..
,all
,>>
,%%
usw. Ohne die Quelle Einschränkung, diese 43 Bytes sein könnte:Probieren Sie es online!
Erläuterung:
quelle
Perl 5
-p
,94,86,78 BytesAusgang 0, wenn gut verknüpft, sonst 1.
78 Bytes
86 Bytes
94 Bytes
Wie es funktioniert
-p
mit}{
Endtrick zur Ausgabe$\
am Endem-.+(?{
..})(?!)-
, um Code über alle nicht leeren Teilzeichenfolgen auszuführen (.+
entspricht zuerst der gesamten Zeichenfolge und nach der Ausführung von Code zwischen(?{
..})
Rückverfolgungen wegen fehlgeschlagener erzwungener(?!)
$Q|=@q&grp,
Müll wegen Quellenbeschränkung$\|=
Ganzzahl bitweise oder Zuweisung, wenn es fast eine 1 gibt,$\
ist 1 (wahr), standardmäßig ist sie leer (falsch)$&eq$_
der Fall, in dem der sbustring die gesamte Zeichenfolge ist, wird bitweise^
mit "kein ungerades Zeichen Vorkommen" xored($g=$&)=~/./g
Kopieren Sie die übereinstimmende Teilzeichenfolge in$g
(da diese nach der nächsten Regex-Übereinstimmung überbewertet wird) und geben Sie das Zeichenfeld der Teilzeichenfolge zurück./^/
Müll, der zu 1 ausgewertet wirdgrep
1&(@m=$g=~/\Q$_/g),
für jedes Zeichen in der Teilzeichenfolge erhält das Array von Zeichen in$g
Übereinstimmung mit sich selbst, das Array in Skalar wird auf seine Größe ausgewertet, undgrep
das Filtern der Zeichen mit ungerader Häufigkeit1&x
entsprichtx%2==1
quelle
Netzhaut ,
150 bis96 BytesProbieren Sie es online! Link enthält Testfälle, einschließlich sich selbst. Bearbeiten: Mit Hilfe von @Deadcode die ursprüngliche Regex ein wenig runtergolfen und dann etwas weniger aufwändig zurückgepolstert, um das Quell-Layout beizubehalten. Erläuterung:
Stellen Sie sicher, dass keine Teilzeichenfolge
\3
vorhanden ist, die den folgenden Einschränkungen entspricht.Stellen Sie sicher, dass es sich bei der Teilzeichenfolge nicht um die gesamte Originalzeichenfolge handelt.
Stellen Sie sicher, dass es kein Zeichen gibt
\6
, das:Um die Einschränkung des Quelllayouts zu umgehen, habe ich
((((
mit(?:(^?(?:(
und((
mit ersetzt(|(
. Ich hatte noch eine Quellenbeschränkung))
und die Zeichen!()1<{}
übrig, also habe ich a+
in geändert{1,}
und das Unnützige eingefügt(?!,<)?
, um den Rest zu konsumieren.quelle
C # (Visual C # Interactive Compiler) ,
208206200198 BytesProbieren Sie es online!
-2 Bytes dank @KevinCruijssen!
Endlich unter 200, also könnte ich jetzt mit dem Golfen fertig sein :) Am Ende habe ich einen zweiten TIO erstellt, um die Dinge basierend auf einer vorherigen Antwort zu testen.
Probieren Sie es online!
Dinge, die diese Aufgabe schwierig machten:
==
war nicht erlaubt++
war nicht zulässigAll()
Funktion wurde nicht erlaubtKommentierter Code unten:
quelle
Python 2 , 108 Bytes
Probieren Sie es online!
-2 danke an Ørjan Johansen .
quelle
Brachylog , 16 Bytes
Probieren Sie es online!
Druck
false.
für truthy Instanzen undtrue.
für falsy Instanzen. Die TIO-Version ist zu langsam, um mit sich selbst fertig zu werden, aber sie ist klar verknüpft, da es sich um eine Zeichenfolge mit eindeutigen Zeichen handelt, die zweimal wiederholt wird.Erläuterung
quelle
05AB1E ,
2220 Bytes1
Wird ausgegeben, wenn die Zeichenfolge gut verknüpft ist und0
wenn die Zeichenfolge nicht gut verknüpft ist.Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Erläuterung:
Das Basisprogramm ist
ŒsKεsS¢ÈP}à
( 11 Byte ), das ausgibt,0
wenn es gut und1
nicht gut verknüpft ist. Das TrailingÈ
(is_even) ist ein Semi-No-Op, das die Ausgabe invertiert, also1
für gut verknüpfte Zeichenfolgen und0
für nicht gut verknüpfte Zeichenfolgen. Die anderen Teile sind No-Ops, um die Herausforderungsregeln einzuhalten.quelle