Die meisten Sprachen verfügen über eine integrierte Funktion, mit der eine Zeichenfolge nach allen Vorkommen einer bestimmten Teilzeichenfolge durchsucht und durch eine andere ersetzt werden kann. Ich kenne keine Sprache, die diesen Begriff auf (nicht unbedingt zusammenhängende) Teilfolgen verallgemeinert. Das ist also Ihre Aufgabe bei dieser Herausforderung.
Die Eingabe besteht aus drei Zeichenfolgen A
, B
und C
, wo B
und C
sind garantiert gleich lang. Wenn dies B
als Folge erscheint A
, sollte es durch ersetzt werden C
. Hier ist ein einfaches Beispiel:
A: abcdefghijklmnopqrstuvwxyz
B: ghost
C: 12345
Es würde so verarbeitet werden:
abcdefghijklmnopqrstuvwxyz
|| | ||
abcdef12ijklmn3pqr45uvwxyz
Wenn es mehrere Möglichkeiten gibt, B
eine Unterfolge zu finden , sollten Sie die ganz linke gierig ersetzen:
A: abcdeedcba
B: ada
C: BOB
Result: BbcOeedcbB
and NOT: BbcdeeOcbB
Das gleiche gilt, wenn B
an mehreren getrennten Orten gefunden werden könnte:
A: abcdeedcbaabcde
B: ed
C: 12
Result: abcd1e2cbaabcde
and NOT: abcd112cbaabc2e (or similar)
Wenn in B
nicht angezeigt wird A
, sollten Sie A
unverändert ausgeben .
Regeln
Wie oben erwähnt, nehmen drei Saiten A
, B
und C
als Eingabe und ersetzen Sie die am weitesten links Auftreten B
als Teilfolge in A
mit C
, wenn es irgendwelche gibt.
Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.
Sie können die drei Zeichenfolgen in beliebiger Reihenfolge verwenden, die Sie in Ihrer Antwort angeben sollten. Sie können das annehmen B
und C
haben die gleiche Länge. Alle Zeichenfolgen enthalten nur alphanumerische Zeichen.
Es gelten die Standardregeln für Code-Golf .
Testfälle
Jeder Testfall ist vier Zeilen: A
, B
, C
durch das Ergebnis gefolgt.
abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz
abcdeedcba
ada
BOB
BbcOeedcbB
abcdeedcbaabcde
ed
12
abcd1e2cbaabcde
121
121
aBc
aBc
abcde
acb
123
abcde
ABC
ABCD
1234
ABC
012345678901234567890123456789
42
TT
0123T5678901T34567890123456789
edcbaedcbaedcbaedcba
abcde
12345
edcbaedcbaedcbaedcba
edcbaedcbaedcbaedcbaedcba
abcde
12345
edcb1edc2aed3bae4cba5dcba
daccdedca
ace
cra
dcrcdadca
aacbcbabcccaabcbabcaabbbbca
abaaaccbac
1223334444
aacbcbabcccaabcbabcaabbbbca
aacbcbabcccaabcbabcaabbbbcac
abaaaccbac
1223334444
1ac2cb2bccc33b3bab4aa4bbbc44
Bestenliste
Das Stapel-Snippet am Ende dieses Beitrags generiert Ranglisten aus den Antworten a) als Liste der kürzesten Lösungen pro Sprache und b) als Gesamtrangliste.
Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:
## Language Name, N bytes
Wo N
ist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:
## Perl, 43 + 2 (-p flag) = 45 bytes
Sie können den Namen der Sprache auch als Link festlegen, der dann im Snippet angezeigt wird:
## [><>](http://esolangs.org/wiki/Fish), 121 bytes
/* Configuration */
var QUESTION_ID = 77719; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 8478; // This should be the user ID of the challenge author.
/* App */
var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;
function answersUrl(index) {
return "http://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}
function commentUrl(index, answers) {
return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}
function getAnswers() {
jQuery.ajax({
url: answersUrl(answer_page++),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
answers.push.apply(answers, data.items);
answers_hash = [];
answer_ids = [];
data.items.forEach(function(a) {
a.comments = [];
var id = +a.share_link.match(/\d+/);
answer_ids.push(id);
answers_hash[id] = a;
});
if (!data.has_more) more_answers = false;
comment_page = 1;
getComments();
}
});
}
function getComments() {
jQuery.ajax({
url: commentUrl(comment_page++, answer_ids),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
answers_hash[c.post_id].comments.push(c);
});
if (data.has_more) getComments();
else if (more_answers) getAnswers();
else process();
}
});
}
getAnswers();
var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;
var OVERRIDE_REG = /^Override\s*header:\s*/i;
function getAuthorName(a) {
return a.owner.display_name;
}
function process() {
var valid = [];
answers.forEach(function(a) {
var body = a.body;
a.comments.forEach(function(c) {
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});
var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
link: a.share_link,
});
else console.log(body);
});
valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});
var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;
var answer = jQuery("#answer-template").html();
answer = answer.replace("{{PLACE}}", lastPlace + ".")
.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)
.replace("{{LINK}}", a.link);
answer = jQuery(answer);
jQuery("#answers").append(answer);
var lang = a.language;
lang = jQuery('<a>'+lang+'</a>').text();
languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
});
var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);
langs.sort(function (a, b) {
if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
return 0;
});
for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
.replace("{{LINK}}", lang.link);
language = jQuery(language);
jQuery("#languages").append(language);
}
}
body { text-align: left !important}
#answer-list {
padding: 10px;
width: 290px;
float: left;
}
#language-list {
padding: 10px;
width: 290px;
float: left;
}
table thead {
font-weight: bold;
}
table td {
padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
<h2>Shortest Solution by Language</h2>
<table class="language-list">
<thead>
<tr><td>Language</td><td>User</td><td>Score</td></tr>
</thead>
<tbody id="languages">
</tbody>
</table>
</div>
<div id="answer-list">
<h2>Leaderboard</h2>
<table class="answer-list">
<thead>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
</thead>
<tbody id="answers">
</tbody>
</table>
</div>
<table style="display: none">
<tbody id="answer-template">
<tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
<tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
[[1], [2], [3]]
.Antworten:
Jelly ,
232221 BytesProbieren Sie es online! Beachten Sie, dass den letzten beiden Testfällen der Speicherplatz ausgeht.
Nachprüfung
Wie es funktioniert
quelle
Python 2, 88 Bytes
Eine Funktion, die die drei Zeichenfolgen aufnimmt und das Ergebnis an STDOUT ausgibt. Die Funktion übergibt die Zeichenfolge einfach einmal, nimmt das entsprechende Zeichen und aktualisiert es,
b,c
während wir fortfahren.Zum Testen (nach dem Ersetzen
print
durchreturn
):quelle
Java 7, 141
Ich glaube, ich kann noch mehr damit anfangen, aber ich muss erst einmal davonlaufen. Es ist nur eine einfache Iteration / Ersetzung, die einen Index in A und B führt.
Leerzeichen für Ihr Vergnügen:
quelle
Whitespaced
Ja, das ist total lesbarj<k?a:d
Lua, 121 Bytes
Die einfache Lösung
gsub
ermöglicht es uns, jedes Zeichen genau einmal zu durchlaufen und durch eine neue Instanz der Zeichenfolge zu ersetzen.Es nimmt Eingaben über 3 Befehlszeilenargumente entgegen und gibt eine Zeichenfolge an STDOUT aus.
Ungolfed
quelle
Python 3, 127 Bytes.
16 Bytes dank Katenkyo gespart.
Der Mensch arbeitete immer noch ein bisschen daran, aber es war so schlimm, als ich es mir vorgestellt hatte.
Erklärung: Awww ja, Rekursion.
Testfälle:
quelle
all(x in a for x in b)
überprüfe auch, ob die Elemente in b und a in derselben Reihenfolge erscheinen, oder nur, wenn sie hier sind.return a.replace(b[0],c[0],1)[:l(b[0])+1]+f(a[l(b[0])+1:],b[1:],c[1:])if b and all(x in a for x in b)else a
ein paar Bytes sparen?Python 3.5, 87 Bytes
repl.it um alle Testfälle zu verifizieren .
Wie es funktioniert
'(.*?)'.join(p)
Erstellt ein Suchmuster, das der zu ersetzenden Teilsequenz und allen Elementen zwischen den Elementen entspricht.Da die Quantifizierer faul sind, entspricht jeder
(.*?)
so wenig Zeichen wie möglich.Für das Muster
ghost
ist der konstruierte reguläre Ausdruckg(.*?)h(.*?)o(.*?)s(.*?)t
.'\g<%d>'.join(r)%(*range(1,len(r)),)
Erstellt die Ersatzzeichenfolge unter Verwendung der Zeichenfolgenformatierung.Jedes
\g<n>
bezieht sich auf die n- te erfasste Gruppe, genau wie\n
es der Fall wäre.Für den Ersatz
12345
ist der konstruierte String1\g<1>2\g<2>3\g<3>4\g<4>5
.re.sub(...,...,s,1)
Führt höchstens eine Ersetzung in der Zeichenfolge durchs
.quelle
Pyth, 27
Test Suite
In der Testsuite werden die letzten beiden Fälle ausgelassen, da der Arbeitsspeicher knapp wird. Der hier verwendete Algorithmus besteht darin, alle Indizes jedes Zeichens in der zweiten Zeichenfolge in der ersten Zeichenfolge zu finden, dann alle möglichen Reihenfolgen dieser Indizes zu finden und nur die zu verwenden, die in sortierter Reihenfolge vorliegen. Verwenden Sie dann die erste davon in sortierter Reihenfolge als Liste der Indizes in der ersten Zeichenfolge, um die Werte aus der dritten Zeichenfolge zu aktualisieren.
Ich denke, es sollte etwas kürzer sein als
.nM*F
...quelle
MATL , 33 Bytes
Probieren Sie es online!
Erläuterung
quelle
JavaScript (ES6), 84 Byte
Erklärung / Test
Code-Snippet anzeigen
quelle
JavaScript (ES6),
8476 BytesWeil ich mir sicher war, dass dies ein Job für RegExp war.
Edit: 8 Bytes gespeichert dank @ MartinBüttner ♦.
Ein Port von @ KevinLaus Ruby-Antwort nahm 82 Bytes in Anspruch:
Ich habe auch versucht, eine rekursive RegExp-Lösung, aber das dauerte 90 Bytes:
quelle
Julia,
89-70BytesVerwendet einen Index
i
, um die Muster- / Ersetzungszeichenfolgen zu durchlaufen. -19 Bytes dank @Dennis!quelle
C 98 Bytes
/ * Erweiterter Code * /
Die Argumente sind: i nput string, o utput Puffer, s earch string, r eplacement.
Nachdem wir uns an den Beginn der Eingabe und Ausgabe erinnert haben, gehen wir die Eingabe durch und ersetzen und erweitern die Substitution, wann immer wir eine treffen. Wenn wir am Ende keine Substitutionen mehr haben, geben Sie den Ausgabepuffer zurück, ansonsten die nicht geänderte Eingabe.
/ * Tests * /
quelle
R, 76 Bytes
verwendet
sub
erstes Spiel zu ersetzenUngolfed
quelle
C ++, 204 Bytes
Golf gespielt
Ungolfed
quelle
std
genug verwenden, um dies zu rechtfertigenusing namespace std;
. Unter Verwendungstd::cin
,std::cout
undstd::string
wird 5 Bytes speichern , da diejenigen , scheinen die einzigen Verwendungen von diesem Namensraum zu sein.b
in gierig ersetzena
, aber die späteren Buchstaben müssen auch nach den früheren Buchstaben stehen. (Sehen Sie sich Testfall 3 an und vergleichen Sie ihn mit Ihrer Ausgabe. Ich denke, Sie werden feststellen, dass Ihr Code ausgegeben wird,abc21ed...
wenn die erwartete Ausgabe vorliegtabcd1e2...
!)Retina , 63 Bytes
Eingang wird genommen , um
B
,C
,A
, getrennt durch Zeilenvorschübe.Probieren Sie es online aus.
quelle
Haskell, 87 Bytes
Ich bemerkte das Fehlen einer Haskell-Antwort und beschloss, das zu beheben. Dies definiert eine ternäre Funktion
!
mit dem Argument order pattern-replacement-string. Probieren Sie es hier aus.Erläuterung
Die Hilfsfunktion verwendet
#
eine Listex
von Zeichenpaaren (Muster und Ersetzung) und eine Zeichenfolgey
. Wenn die "Muster" -Zeichenx
eine Untersequenz von bildeny
, wird die leere Liste zurückgegeben undy
jedes Musterzeichen durch das Gegenstück ersetzt. Andernfalls wird das Paar zurückgegeben(x,y)
. Die Funktion!
zippt die Muster- und Ersetzungszeichenfolgen in die dritte Zeichenfolge undx
gilt#
für diesex
und gibt die zweite Komponente des Ergebnisses zurück.Wenn das Muster eine Teilfolge der Zeichenfolge ist, wird der Code in der O (n) -Zeit ausgeführt, wobei ein rekursiver Durchlauf durch die Zeichenfolge erfolgt und die Ersetzung dabei gierig konstruiert wird. Wenn das Muster jedoch keine Untersequenz ist, läuft es im schlimmsten Fall in O (2 n ) -Zeit. Dies liegt daran, dass die Funktion sich an jeder Stelle, an der das Muster und die Zeichenfolge übereinstimmen, selbst aufruft, um zu überprüfen, ob das Muster tatsächlich eine Teilsequenz ist.
quelle
JavaScript (ES6),
100 bis95 ByteDies ist eine gültige JavaScript-Lambda-Funktion. Ausgänge als Funktion
return
. Nimmt drei Argumente auf (a,b,c
). Fügen Sief=
am Anfang und rufen Sie wief(arg1,arg2,arg3)
.quelle
f=
sei denn, Ihre Funktion ist rekursiv, sie sieht jedoch anders aus.a
schlägt dies fehl, wenn das Muster nicht enthalten ist. Ich bin mir auch nicht sicher, ob es akzeptabel ist, eine Reihe von Zeichenfolgen zurückzugeben.C (gcc),
67626159 BytesProbieren Sie es online!
quelle
Oktave, 97 Bytes
Iterieren Sie über die zu ersetzende Teilsequenz. finde das erste Vorkommen des ersten Zeichens, finde das nächste Zeichen in der verbleibenden Zeichenkette, wiederhole. Das einzig interessante daran ist:
Da ideone immer noch keine Funktionen mit anderen Namen als '' akzeptiert, lasse ich hier nur einen Probelauf. Eingaben werden der Kürze halber nur für die ersten Testfälle angezeigt.
key
ist die erwartete Ausgabe,ans
ist die Funktionsausgabe.quelle
D(t=...)
) verwirren mich immer wieder :-)Python 3, 123 Bytes
Ein anderer Ansatz, den ich teilen wollte, der einige Bytes kürzer ist. Es gibt keine Regeln gegen Standardbibliothek / Regex, oder?
PS. Dies ist mein erster Golf. Informieren Sie mich über mögliche Probleme / Verbesserungen.
quelle
Pyth, 22 Bytes
Überprüfen Sie alle Testfälle im Pyth-Compiler .
Hintergrund
Wir erstellen einen regulären Ausdruck aus dem Muster, indem wir ein anfügen
$
und(.*?)
zwischen alle Zeichen setzen. Dieser reguläre Ausdruck entspricht der zu ersetzenden Teilsequenz und allen Elementen zwischen den Elementen und allen Elementen bis zum Ende der Zeichenfolge.Da die Quantifizierer faul sind, entspricht jeder
(.*?)
so wenig Zeichen wie möglich.Für den Mustergeist ist der konstruierte reguläre Ausdruck
g(.*?)h(.*?)o(.*?)s(.*?)t(.*?)$
.Wenn das Muster mit der Eingabe übereinstimmt, gibt das Builtin
r<str><regex>3
ein Array zurück, das das Prematch (alles vor der Subsequenz), alle erfassten Gruppen (alles zwischen und nach der Subsequenz) und das Postmatch (die leere Zeichenfolge) enthält.Wenn das Muster nicht übereinstimmt, gibt das Builtin ein Singleton-Array zurück, das die ursprüngliche Eingabe enthält.
Wie es funktioniert
quelle
Jelly , 23 Bytes
Dies ist zwei Bytes länger als meine andere Gelee-Antwort , endet aber sofort. Probieren Sie es online!
Nachprüfung
Wie es funktioniert
quelle
CJam, 29 Bytes
Probieren Sie es online! oder überprüfen Sie alle Testfälle .
quelle
Java 7, 102 Bytes
Ausführlicher Versuch hier
quelle
Julia,
939086 BytesSeparat testen zu müssen, ob das Match erfolgreich war, zerstört das Ergebnis. Eine Substitution würde ein Casting erfordern
Base.SubstitutionString
, was sich wahrscheinlich nicht lohnt ...Testlauf
quelle
Julia,
625958 BytesI / O besteht aus Zeichenfeldern.
Nachprüfung
quelle
PHP,
130109 BytesIch würde es immer noch gerne kürzer haben; könnte 3 Bytes (
""<
) einsparen, wennB
garantiert nicht enthalten wäre0
.Übernimmt Argumente von der Kommandozeile. Laufen Sie mit
-r
.Ersetzt die Zeichen, wenn sie gefunden werden.
druckt Kopie, wenn alle Zeichen ersetzt wurden; Original sonst.
quelle
Ruby,
70645958 BytesAnonyme Funktion. Gehen Sie durch die Zeichenfolge
a
eine neue Zeichenfolge zu bauen mit Buchstaben in Übereinstimmung zum nächsten Zeichen ersetzt inb
undc
dann , wenn alle Zeichen inb
am Ende erschöpft, kehren das neu errichteten Zeichenfolge, sonst gibt die ursprüngliche Zeichenfolge.@histocrat half beim Speichern von 6 Bytes über
gsub
.1 Byte dank @Cyoce gespeichert.
Probieren Sie es online!
quelle
-1+i+=1
mit~-i+=1
Perl, 80 + 1 = 81 Bytes
Laufen Sie mit der
-p
FlaggeProbieren Sie es online!
Der Code generiert prozedural einen Befehl zum Suchen und Ersetzen von Regex, den er dann im letzten Codebit ausführt.
Die Zeichenfolge
ghost
im ersten Beispiel wird in eine Zeichenfolge umgewandeltg(.*?)h(.*?)o(.*?)s(.*?)t(.*?)
, dhg
gefolgt von 0 oder mehr Zeichen, gefolgt vonh
0 oder mehr Zeichen, gefolgt von usw. Der*?
Quantifizierer bedeutet, dass die Suche nicht gierig und "verschlingen" sein sollte msgstr "so wenig Zeichen wie möglich, anstatt so viel wie möglich abzugleichen.Die Zeichenfolge wird
12345
dann in umgewandelt1 .$1.2 .$2.3 .$3.4 .$4.5 .$5
, die ausgewertet wird, nachdem der reguläre Ausdruck ausgeführt wurde. Jedes von$1,$2,$3,$4,$5
ist tatsächlich ein Rückverweis auf eine Erfassungsgruppe (in Klammern) aus der ersten Zeichenfolge.quelle
perl -pe 'eval"s/".<>=~s/.\K/(.*?)/gr."/".<>=~s/.\K/"\${".++$i."}"/gre."/"'
. Kam alleine mit, aber es ist ziemlich nah an deiner, also werde ich es nicht posten, das wären zwei sehr nahe beieinander liegende Antworten, aber zögern Sie nicht, Ihre zu bearbeiten!perl -E 'chomp(($f,$t,$s)=(<>));$f=join"(.*?)",split"",$f;@r=split"",$t;@t=shift@r;push@t,"\${",++$x,"}"for(@r);$t=join"",@t;say$s=~s/$f/$t/r;'
Clojure, 113 Bytes
Eine grundlegende
reduce
, nicht allzu glücklich über all die langefirst
,rest
undconj
Funktionsaufrufe. Ich hoffe auf einen besseren Ansatz.quelle