Dies ist ein etwas Beweis Golf -ähnlichen Cops-und-Räuber Herausforderung. Dies ist der Faden der Polizei; Der Räuberfaden ist da.
Bullen
Ihre Aufgabe ist es, ein abstraktes Umschreibungssystem zu definieren , bei dem die Erreichbarkeit eines Wortes von einem anderen schwer zu bestimmen ist. Sie bereiten folgende Dinge vor:
Eine Reihe von Symbolen, die als Alphabet bezeichnet werden. (Sie können für diese Zeichen beliebige Unicode-Zeichen verwenden. Verwenden Sie jedoch keine Leerzeichen oder Symbole, die nur schwer voneinander zu unterscheiden sind.)
Eine Quellzeichenfolge, die aus Symbolen aus Ihrem Alphabet besteht.
Eine Zielzeichenfolge, die aus Symbolen aus Ihrem Alphabet besteht.
Eine Reihe von Umschreiberegeln, die Zeichen aus Ihrem Alphabet verwenden. (Siehe unten für die Definition einer Umschreiberegel.)
Ein Beweis, der zeigt, ob Ihre Quellzeichenfolge durch sukzessive Anwendung Ihrer Umschreiberegeln in Ihre Zielzeichenfolge konvertiert werden kann. Dieser Beweis kann aus einer tatsächlichen Folge von Umschreibschritten bestehen oder aus einem mathematischen Beweis, dass eine solche Folge existieren muss, oder aus einem mathematischen Beweis, dass eine solche Folge nicht existiert.
Sie werden die ersten vier davon veröffentlichen und den Beweis geheim halten. Die Räuber versuchen, Ihre Antwort zu knacken, indem sie selbst nachweisen, dass Ihre Zielzeichenfolge von Ihrer Quellzeichenfolge aus erreichbar ist oder nicht. Wenn Ihr Beitrag nicht innerhalb von zwei Wochen geknackt wird , können Sie ihn als sicher markieren und in Ihrem Proof bearbeiten.
Die Einreichungen werden gemäß der Anzahl der Zeichen in ihren Umschreiberegeln und ihren Quell- und Zielzeichenfolgen gewertet, wie nachstehend beschrieben. Der Gewinner ist die ungerissene Einsendung mit der niedrigsten Punktzahl.
Was ist eine Umschreiberegel?
Eine Umschreiberegel besteht einfach aus zwei Zeichenfolgen in Ihrem Alphabet. (Eine dieser Zeichenfolgen kann leer sein.) Eine Anwendung einer Umschreiberegel besteht darin, eine Teilzeichenfolge zu finden, die der ersten Zeichenfolge im Paar entspricht, und diese durch die zweite zu ersetzen.
Ein Beispiel soll dies verdeutlichen:
Angenommen Alphabet ist A, Bund C; die Quellzeichenfolge ist " A"; Die Zielzeichenfolge lautet " C" und die Umschreiberegeln lauten
A:B
B:BB
B:A
AA:C
dann ist die Zielzeichenfolge auf folgende Weise erreichbar:
A
B (using rule 1)
BB (using rule 2)
AB (using rule 3)
AA (using rule 3)
C (using rule 4)
Wertung
Ihre Punktzahl wird sein
- die Länge Ihrer Quellzeichenfolge,
- plus die Länge Ihrer Zielzeichenfolge,
- zuzüglich der Länge aller Zeichenfolgen, die in Ihren Umschreiberegeln enthalten sind,
- zuzüglich eines zusätzlichen Punktes für jede Umschreiberegel.
Wenn Sie Ihre Umschreiberegeln wie oben beschrieben mit einem Doppelpunkt als Trennzeichen schreiben, entspricht dies lediglich der Gesamtlänge aller Umschreiberegeln (einschließlich des Trennzeichens) zuzüglich der Länge der Quell- und Zielzeichenfolgen. Eine niedrigere Punktzahl ist besser. Die Anzahl der unterschiedlichen Zeichen in Ihrem Alphabet wird zum Unterbrechen von Bindungen verwendet, wobei weniger besser ist.
Kopfgeld
Ich würde gerne Antworten sehen, die wirklich niedrige Punktzahlen anstreben. Ich werde 200 Wiederholungen für die erste Antwort vergeben, die bei dieser Herausforderung weniger als 100 Punkte erzielt und nicht geknackt wird.
Mx -> MxxRegel zu implementieren , sodass sie viel komplizierter als die von Hofstadter wird Original.Antworten:
326 Punkte - Gebrochen von Jimmy23013
Das Level ist Picokosmos # 13 von Aymeric du Peloux (mit einer unbedeutenden Modifikation). Ich habe versucht, eine geschmackvolle Ebene zu finden, bei der "Boxen" und "Wände" den gleichen Charakter haben. Für dieses Niveau war es möglich, den zentralen Drosselpunkt zwei statt nur einer Spalte breit zu machen.
Die Regeln / Initialen / Ziel-Saiten könnten ein bisschen mehr golfen werden, aber das ist nur zum Spaß.
Anfangszeichenfolge:
Zielzeichenfolge:
Regeln:
quelle
171 Punkte, geknackt von HyperNeutrino
Quelle:
YAAATZiel:
VW626206555675126212043640270477001760465526277571600601Regeln:
Nur etwas Offensichtliches. Die tatsächliche Reihenfolge der Umschreibeschritte passt wahrscheinlich nicht in eine SE-Antwort.
quelle
VWxwoxaus gebildet ist , jede binäre Zeichenkette von_(0) und+(1) , die zur Bewertung10*n+6(einschließlich der führenden_;n= nicht-negative ganze Zahl ist ) noch diexgegebene (626...601) aus binären welche auswertet gebildet zu10*n+3(für ein großesn).33 Punkte, geknackt von user71546
Ein einfacher Einstieg.
Quelle:
xnorZiel:
xorRegeln umschreiben:
Die letzte Regel benötigt 11 0 für die leere Zeichenfolge.
quelle
139 Punkte (sicher)
Ich wollte, dass diese Antwort geknackt wird, und user202729 hat sie im Grunde genommen in den Kommentaren gelöst, aber niemand hat eine Antwort im Räuber-Thread gepostet, also markiere ich sie als "sicher" und füge meinen Beweis darunter ein.
(Diese Dinge sind offensichtlich viel einfacher zu machen als sie zu knacken. Noch hat niemand versucht, eine wirklich niedrige Punktzahl zu erzielen, und es könnte mehr Spaß machen, wenn diese Herausforderung jemals auftaucht. )
Hier ist eine Selbstantwort. Es ist möglicherweise sehr schwer, sollte aber einfach sein, wenn Sie herausfinden, woher es kommt.
Alphabet:
ABCDEⒶⒷⒸⒹⒺⒻ⬛⚪️️🎂←→Quelle:
←A→Ziel:
←🎂→Regeln: (Leerzeichen sind nicht signifikant)
Hier ist eine ASCII-Version für den Fall, dass der Unicode nicht für alle gut angezeigt wird.
Beweis
Dies entspricht dem derzeit besten Anwärter für einen Biber mit sechs beschäftigten Bundesstaaten . Ein vielbeschäftigter Biber ist eine Turingmaschine, die nach sehr langer Zeit anhält. Aus diesem Grund
←A→kann die Quellzeichenfolge in der Tat in die Zielzeichenfolge umgewandelt werden←🎂→, jedoch erst nach mehr als7*10^36534Schritten, die für eine physische Implementierung erheblich länger als das Alter des Universums dauern würden.Das Band der Turingmaschine wird durch die Symbole
⬛(0) und⚪(1) dargestellt. Die Regelnbedeutet, dass die Enden des Bands immer mit mehr Nullen verlängert werden können. Sollte sich der Kopf der Turingmaschine jemals einem Ende des Bandes nähern, können wir nur eine dieser Regeln anwenden, die uns vorgeben lassen, dass das Band unendlich ist und mit allen Nullen gefüllt beginnen. (Die Symbole
→und←werden niemals erstellt oder zerstört, sie befinden sich also immer am Ende des Bandes.)Der Kopf der Turingmaschine ist mit den Symbolen
ABCDEⒶⒷⒸⒹⒺⒻund dargestellt🎂.Abedeutet, dass sich der Kopf im Status befindetAund das Symbol unter dem Kopf eine⬛(0) ist, wohingegen Ⓐ bedeutet, dass er sich im Status befindetAund das Symbol unter ihm eine⚪(1) ist. Dies wird für die anderen Zustände fortgesetzt, wobei der eingekreiste Buchstabe eine 1 unter dem Kopf und die nicht eingekreiste Version eine 0 darstellt. (Es gibt kein Symbol,Fda der Kopf niemals in einem ZustandFmit einer 1 darunter endet .)Der Staat
🎂ist der Stillstand. Es hat die besonderen RegelnWenn der Stopp-Zustand jemals erreicht wird, können wir diese Regeln wiederholt anwenden, um das gesamte Band "einzusaugen" (einschließlich aller zusätzlichen Nullen, die durch mehr als notwendiges Erweitern des Bandes entstanden sind), wodurch wir in dem Zustand zurückbleiben
←🎂→. Daher läuft das Problem der Erreichbarkeit darauf hinaus, ob der Staat🎂jemals erreicht wird.Die übrigen Regeln sind die Übergangsregeln für die Turingmaschine. Zum Beispiel die Regeln
kann wie folgt gelesen werden: "Befindet sich die Maschine im Zustand A und befindet sich eine Null unter dem Kopf, schreiben Sie eine 1, wechseln Sie in den Zustand B und bewegen Sie sich nach rechts." Das Verschieben nach rechts erfordert zwei Regeln, da die Bandzelle rechts u. U. ein enthält
⬛. In diesem Fall sollte die Maschine in den Status wechselnB, oder die Zelle könnte ein enthalten⚪. In diesem Fall sollte sie in den Status wechselnⒷ, da sich⚪darunter ein befindet.Ähnlich,
bedeutet "Wenn sich die Maschine im Zustand D befindet und sich eine 1 unter dem Kopf befindet, schreiben Sie eine 0, wechseln Sie in den Zustand C und bewegen Sie sich nach links."
Die verwendete Turing-Maschine wurde 2010 von Pavel Kropitz entdeckt. Obwohl sie häufig im Zusammenhang mit vielbeschäftigten Bibern erwähnt wird, ist ihre tatsächliche Übergangstabelle etwas schwierig zu finden, aber sie kann zum Beispiel hier gefunden werden . Es kann geschrieben werden als
Dies kann wie folgt gelesen werden: "Befindet sich die Maschine im Zustand A und befindet sich eine Null unter dem Kopf, schreiben Sie eine 1, wechseln Sie in den Zustand B und bewegen Sie sich nach rechts." Wenn mühsam, sollte es einfach sein, zu überprüfen, ob jeder Eintrag dieser Tabelle einem Paar von Regeln entspricht, wie oben beschrieben.
Die einzige Ausnahme ist die Regel
1RH, die auftritt, wenn sich die Maschine im Zustand F über einer 0 befindet, da es ziemlich sinnlos erschien, die Maschine eine 1 schreiben zu lassen und nach rechts zu gehen, wenn sie sofort anhalten könnte, sobald sie jemals in den Zustand F übergeht über eine 0. Also habe ich die Regel geändert, die gewesen wärein
Aus diesem Grund enthält
Fdas Alphabet kein Symbol . (Es gibt noch ein paar andere Golfplätze, die ich hätte machen können, aber ich wollte sie nicht zu sehr verschleiern.)Das war's im Grunde. Die Zielzeichenfolge ist von der Quellzeichenfolge aus erreichbar, aber nur nach einer lächerlichen Anzahl von Schritten.
Eine weitere lustige Tatsache: wenn ich verwendet hätte
←A⚪⚪→als ausgangspunkt müsste man dann nicht
7*10^36534schritte machen, um anzuhalten, sondern10^10^10^10^18705352schritte, was in der tat eine sehr große zahl ist.quelle
48 Punkte, geknackt von BB94
Alphabet:
abcQuelle:
cbaabaabcZiel:
cbacbcabcRegeln umschreiben:
quelle
287 Punkte, sicher
Quelle:
YAATZiel:
Regeln:
Ich fand, dass openssl für diesen Zweck viel einfacher zu benutzen ist als gpg.
Siehe HyperNeutrinos Sprung zur schwächeren Version. In diesem Fall ist die Anzahl von
Cs:Und die Hauptfaktoren sind:
Die erste Zahl mod 5 = 2, so dass es möglich ist, die letzte Zeichenfolge zu erhalten.
quelle
402 Punkte
Alphabet:
abcdefghijklmnopqrstuQuelle:
abcdoiZiel:
ioabcdnnnnnnnnnnnnnnnnnnRegeln umschreiben:
Mit der letzten Regel können Sie so viele
ns erstellen, wie Sie benötigen.Hässlich wie es scheint, ist es eigentlich ganz nett, so oder so ...
quelle
aoi:eogwirdeogsein solleag?1337 Punkte
Auf jeden Fall nicht wettbewerbsfähig und es hat viel zu lange gedauert, um es zu schaffen (ich hoffe, ich habe keinen Fehler gemacht).
Hinweis:
Alphabet:
ABEILRSTabcdefijlrQuelle:
SIbbbbbbbdbffacebbfadbdbeecddfaeebddcefaddbdbeeecddaaaaadfaeeebdddcefbbfadbdbdbeeecdddfaeeebdddcefaddbdbeeecddaaaadfaeeebdddcefbfadbdbdbeeecdddfaeeebdddcbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaceefacdffacebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaaceefacdffacebdcecefacEZiel:
SERegeln umschreiben:
quelle
154 Punkte
Alphabet:
P.!xABC[{mD<Quelle:
[x!P.P...P..P.P....P..P.P.....P.P....P......P.P..P...P.P...Pm(61 Zeichen)Ziel:
{CCCCC<(es gibt 5Cs, also 7 Zeichen)Regeln:
Es gibt 19 Regeln, Gesamtanzahl der Zeichen = 67.
quelle
106 Punkte - von HyperNeutrino geknackt
Alphabet:
ABCDEFGHIJQuelle:
FIABCJAGJDEHHIDZiel:
FRewrite-Regeln:
Okay, HyperNeutrino hat bewiesen, dass dies nicht lösbar ist. Hierfür gibt es jedoch eine andere Lösung.
Nehmen:
Der Wert der Quelle ist gerade. Der Wert des Ziels ist ungerade. Wenn wir jede Seite nehmen, den Wert aufsummieren und den Wert auf Mod 2 setzen, bleiben die Werte gleich. Daher kann dies nicht erreicht werden.
quelle