Lassen Sie uns einige Zeichenfolgen dem 2D-Raum im fraktalen Stil zuordnen. Ihre Aufgabe ist es, eine Hilbert-Kurve zu berechnen und eine Zeichenfolge entlang zu legen.
Aufgabe
Die Aufgabe besteht darin, die einzeilige Eingabezeichenfolge entlang einer Hilbert-Kurve zu legen, die groß genug ist, um sie aufzunehmen, aber nicht größer. Versuchen Sie, die Anzahl der Bytes so gering wie möglich zu halten. Das ist doch Code-Golf !
Bedingungen
- Mit Leerzeichen aufzufüllende Lücken, am Zeilenende ist jedoch kein Auffüllen erforderlich.
- Der Anfang der Linie sollte in der oberen linken Ecke und das Ende in der unteren linken Ecke sein.
- Sie können ein Programm oder eine Funktion erstellen.
- Es könnten einige neue Testfälle auftauchen, also codieren Sie nichts!
Boni
Hinweis: Boni stapeln sich wie folgt: -50% & -20% on 100B
= -20% on 50B
oder -50% on 80B
= 40B
.
- -50% Handelt es sich bei der Eingabe um eine mehrzeilige Zeichenfolge, kehren Sie den Vorgang um, um die ursprüngliche Eingabe zu erstellen. Testfälle für den Bonus: Verwenden Sie einfach die vorhandenen (inklusive der Bonus-Testfälle!)
- -20% Wenn Sie alle unnötigen Leerzeichen aus der Ausgabe entfernen (z. B. am Ende einer Zeile).
- -5% Wenn Sie den globalen Namespace nicht verschmutzen (Sie wissen, was ich meine!)
Testfälle
abcdefghijklmn
adef
bchg
nij
mlk
The quick brown fox jumps over the lazy dog.
Thn f ju
ewooxpm
qckr rs
ui btevo
hlaz
e y
do
.g
Und für den Whitespace-Stripping-Bonus:
No hitespac her
Noher
hesc
itpa
Bestenliste
/* Configuration */
var QUESTION_ID = 66958; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 43394; // 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 "https://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 "https://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,]*[^\s,]),.*?(\d+(?:[.]\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,
});
});
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;
if (/<a/.test(lang)) lang = jQuery(lang).text();
languages[lang] = languages[lang] || {lang: a.language, 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 > b.lang) return 1;
if (a.lang < b.lang) 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="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>
<div id="language-list">
<h2>Winners 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>
<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>
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 Leaderboard-Snippet angezeigt wird:
# [><>](http://esolangs.org/wiki/Fish), 121 bytes
No..hitespac..her.
Wo die Punkte Leerzeichen sind, wäre ein besserer Testfall für den Bonus. (Und zur Zeit fehlt dem Testfall das Trailing.
)Antworten:
CJam,
119117113112109 * 0,5 * 0,8 = 43,6 BytesVielen Dank an Dennis für das Speichern von 1 Byte.
Hier ist ein Anfang ...
Testen Sie die Forward-Transformation . Testen Sie die inverse Transformation.
Ich bin sicher, es gibt einen kürzeren Weg, um die Kurve zu erzeugen ...
Erläuterung
Zuerst definiere ich eine Funktion zum Trimmen eines Elements vom Ende eines Arrays, weil ich das an mehreren Stellen brauche. Es erwartet das Array und das Element (innerhalb eines separaten Arrays) oben auf dem Stapel.
Jetzt bestimmt der Großteil des Codes die Größe der erforderlichen Hilbert-Kurve und erstellt sie als 2D-Array, in dem die Elemente Indizes entlang der Kurve sind. Ich konstruiere dies basierend auf der folgenden Beobachtung:
Betrachten Sie die 2x2-Hilbert-Kurve:
Die 4x4 Hilbert Kurve ist:
Wenn wir den Minimalwert von jedem Quadranten subtrahieren (und sie aus Gründen der visuellen Klarheit ein wenig trennen), erhalten wir:
Dieses Muster gilt für jede Größe. Dies bedeutet, dass wir die nächste Ebene aus der aktuellen Ebene konstruieren können, indem wir als die vier Quadranten verwenden: a) die Transponierung der aktuellen Ebene, b) die aktuelle Ebene selbst, c) die Transponierung entlang der Antidiagonale, d) erneut das aktuelle Niveau selbst. Und dann versetzen wir sie jeweils um das 0, 1, 3, 2-fache der Größe des aktuellen Pegels.
Schließlich verwenden wir diese Hilbert-Indexkurve, um die entsprechende Transformation auf die Eingabe anzuwenden:
quelle
Python 3,
467434423457451426386374342291304 * 80% * 95% = 231,04 ByteDas funktioniert so, dass ich die Hilbert-Kurve mit einem Lindenmayer-System erstelle und den Anweisungen für Links, Rechts und Vorwärts entlang einer Reihe von Zeichenfolgen folge. Es gibt jedoch wahrscheinlich viele Möglichkeiten, wie man besser Golf spielen könnte. vor allem in den Bedingungen und bei der Zusammenstellung der Saiten. (Ich habe versucht,
[" "*p for i in range(p)]
aber Strings unterstützen die Elementzuweisung nicht (anscheinend). Wenn ich das zum Laufen bringen könnte, könnte ich auch den Join loswerden.)Edit: Golfed einige der Bedingungen mit Dank an Dennis . Und ich spielte die Saiten ab. Und eine No-Byte-Änderung, weil die Ergebnisse im Vergleich zu den obigen Beispielen transponiert herauskamen.
Bearbeiten: Der Bonus zum Entfernen von Leerzeichen wurde implementiert.
Bearbeiten: Ein Fehler in meinem Code zum Entfernen von Leerzeichen für sechs weitere Bytes wurde behoben
Edit: Da diese Antwort den globalen Namensraum nicht verschmutzt, bekomme ich hier laut wizzwizz4 den 5% Bonus .
Bearbeiten: Ändert, wie
g
inkrementiert und dekrementiert wird. Jetzt miteval()
undstr.translate
.Bearbeiten: Diese Antwort ist jetzt ein Programm anstelle einer Funktion.
Bearbeiten: Einige Fehler aus dem vorherigen Golf wurden behoben.
Ungolfed:
quelle
Ruby,
358356344322319 * 80% * 95% = 242,44 BytesDies ist mein Python-Code, der in Ruby umgesetzt wurde. Ich sollte mehr Antworten in Ruby schreiben. Es ist eine anständige Sprache zum Golfspielen.
Edit: Ich habe vergessen, dass Funktionen in dieser Frage nicht benannt werden müssen.
Edit: Da diese Antwort den globalen Namensraum nicht verschmutzt, bekomme ich hier laut wizzwizz4 den 5% Bonus .
Ungolfed:
quelle
JavaScript (ES6), 227 - 20%: 181,6 Byte
Der Versuch, den 5% Bonus zu bekommen
241 * 0,8 * 0,95: 183,16 größer
Weniger golfen
Prüfung
quelle
var
s hinzuzufügen , um den 5% -Bonus zu erhalten?var s,x,y,u,v,t,p,q,n,h
Nein, es ist nicht wert @ wizzwizz4var
vor der ersten Verwendung eines jeden setzen ... Oh, das ist noch schlimmer.