Intro
Es gibt 3 Nägel in der Wand. Sie haben ein Stück Schnur, das mit beiden Enden am Bilderrahmen befestigt ist. Um das Bild aufzuhängen, haben Sie die Schnur mit den Nägeln verwickelt. Aber bevor Sie das Bild loslassen: Können Sie vorhersagen, ob das Bild fallen wird, indem Sie sich nur ansehen, wie die Schnur um die Nägel gewickelt ist?
Im ersten Beispiel wird das Bild nicht fallen. Im zweiten Beispiel wird das Bild fallen.
Herausforderung
N
Bestimmen Sie anhand des Pfades der Schnur um die Nägel, ob das Bild fallen wird oder nicht. Geben Sie einen wahrheitsgemäßen Wert zurück, wenn das Bild sinken soll, und einen falschen Wert, wenn nicht.
Einzelheiten
- Sie können davon ausgehen, dass die Nägel und das Bild in einem regelmäßigen
N+1
Rechteck angeordnet sind , wobei sich das Bild unten befindet. - Sie können davon ausgehen, dass sich keine Knoten im Seil befinden, dh das Seil kann kontinuierlich von einem der beiden Enden abgewickelt werden.
- Jeder Nagel wird im Uhrzeigersinn mit einem Buchstaben des Alphabets aufgezählt. Sie können davon ausgehen, dass es maximal 26 Nägel (AZ) gibt.
- Ein Umwickeln eines Nagels im Uhrzeigersinn wird mit dem Kleinbuchstaben bezeichnet, ein Umwickeln im Gegenuhrzeigersinn mit dem Großbuchstaben.
Das erste Beispiel von oben wird codiert als BcA
, das zweite Beispiel wird codiert als CAbBac
.
Für den geneigten Leser: Dieses Problem ist gleichbedeutend mit der Feststellung, ob ein Element der freien Gruppe - das durch den Satz von Nägeln erzeugt wird - die Identität ist oder nicht. Dies bedeutet , es ist ausreichend , um wiederholt abbrechen Strings wie aA
oder , Aa
bis Sie einen festen Punkt erreicht. Wenn der Fixpunkt eine leere Zeichenfolge ist, ist dies das neutrale Element, andernfalls nicht.
Beispiele
Picture will fall:
Aa
CAbBac
aBbA
DAacAaCdCaAcBCBbcaAb
ARrQqRrUuVHhvTtYyDdYyEKRrkeUWwua
AKkQqEeVvBESWwseYQqyXBbxVvPpWwTtKkVHLlWwNBbAanYYyyhWwEJZUuNnzjYyBLQqQqlEGgebeEPLlTtZzpUuevZzSsbXSGgsUuLlHhUQquPpHUuFfhTZzIitGgFAaBRrBbbYXxOoDZTDdtzVvXxUudHhOVvoUuXKkxyBEeLlbFfKkHhfVAaQqHAaJjODdoVvhSsZzMZzmPpXNBbnxBbUuSSsUuDRrdNnUusJDIiUuIidCEGgeMmcLlDPOopdTEeQqCAETtNnYyeGUuPEFfSsWwHheAaBbpgCcOHUuhAaCcoEFBbfeaFHhfcCFFffNncGFfgtjMVUuKAakvKkXxLlTMmtmOFfoUuXSsYZzLXxlyxUuRPZzTtprSsWwRrPLlpGgMmKRrDHhdRCcUurYNnKCckykXJjxWwUSsJjKkLlKkuBbBbOoWwWwIiUuPDdBbCcWHBbCFfcDdYBbLlyVvSsWGgEewCchDdYywAaJjEepPpPpQXxZzFfLGXxglNnZzYDdyqCcKWXxwXxQqXTtxkFfBSSAasTFftZzsXGgxSsLlLlbZzAaCCccXVvYyxTIiOoBbFftCVQqDdBbGgAavQqKkDPpKTCctRrkdcvAaQWOowLOolqVMmvZAaHCBbcPphIiRKkrLlzFMOomDIiXJjIixMmdNnMHhmfNTtIiKkSDdTtsVvHhnAaNSVvTUutNnXxsGIiXxPpPHhUupgNnAaAAOoaaIiHJjhVvLlnYyXxQqSsTtKJjkBbNnVvEYCcFfMHGghBbmNnEeJTtjJjWYywyeNWwDIiZYyzOodnMQqmVvCcQqxVvGNnEeNBbngVvUGgYyBbDdVvIiAAaauPpQKDdEekNnVLlvHhGSDIidPZzpsPCcpgQqKkQqNOonLlIiLlJjqPAaPXxTtppYyCPpHhCIicARBbracXxWwXEVUuUuGgZHhzBSsbvGgFfeVvxLlNKknWwBLlIibWOowNnRSsrSEeKAakOosLZzZRrHhzTtTFfUuNnOKkotXxTtla
Picture will not fall:
A
BcA
ABCD
aBaA
bAaBcbBCBcAaCdCaAcaCAD
ARrQqRrUatuVHhvTYyDdYyEKRrkeUAua
AEEeQqNneHhLlAIiGgaECXxcJjZzeJFfVWwDdKkvYWwyTJjtCXxANIinaXWwxcTWwtUuWwMmTBbVWIiFLlWwZzfwPLlEepvWZzwKkEYEeWXxwySXTtEexRIiNBbnWAaTtQqNnBMSsWwOombwWwPVPpGPpgYyvDdpBbrQqHhUusKRrDAVvadLlWwOZzokGJCXSSssXxxJPpGIigZzjJjLlOoNRrnPpcMZzmjgJjNDEeQqWKkNTtnSswIidCcnYBGgbyJSsjPpIiMmMmMmSNnWVvwZzIQqLXHhxTPptlisOoeTtTtYMmVvPpyKNnMFfmkXxSVvsCGJjXxgXYJPpjWwQIiXxqyDdxFfDdAaRNnJjrctHBbZzhEQqMmeCcRBbrGgAaAaJNnRrYyWwSDdVvsJOojQGgWWwIBbiwRrqJjjWwOoFPMmDdRrQOoqNnRrDPJjpMmdPpGFfVvWUuwgpWCcNnPpwfUXCcZzJjUSsuXxxUuuRGgHhrSQqJjOosMMTtmHhmKkXxDdLlWwjSUuAaMmKYyksZzVvPZzVEeVvvHhZZOozBbzMmZCczYyGgISsiQqpXxMmXxEMmeRrAGgaGgMOGgomZFfDdzSSssBGPpgbTtBbOoRWWwGgLJjlEeGgLDdRrUulNnZzJjJjUKkuXxFfwATtaZzLVvlWwSsMmrBAaELleGBLFflbgHhbIFfiBbPpTWZzwKkKLASsaTJYyjtBbBbWwIiZCcWwzIiZLlUTtuBbYyBbIizTJjtLTtDOOoBbodBbllSsUGgLlAKkauYykUuUNnPpuDFfAaLNVvnVvlHhdMmBAaBbIiVRrGWOoPpwgWXwKkvJjOoTtYCUucVGgYyLlVvFfvRrMmySsDdbtICZzcNnINSOosDQAaXoxRGgKkrqdZznDdXxZzMGgmiJjNnACcMQqmaNnWZzUOuwTVvAJjSsaRrGgSsTtOMmRroVvRrtAVGgvMmaINniDGCcOogRrWwMVvYFfyTtmTtVvOoOIiodRrGgAxaSsGgiJja
quelle
Antworten:
Netzhaut , 21 Bytes
Probieren Sie es online!
Wie bei der Lösung von flawr werden dabei nur wiederholt benachbarte Paare aus Groß- und Kleinbuchstaben gelöscht und anschließend geprüft, ob das Ergebnis leer ist oder nicht.
Wie passt man zu einem Paar aus Groß- und Kleinschreibung?
quelle
MATLAB, 76 Bytes
Octave,827977 BytesDies könnte das erste Mal sein, dass ich gesehen habe, dass MATLAB tatsächlich kürzer als Octave ist (um ein ganzes Byte)!
Neue Antwort in MATLAB:
Antwort in Oktave:
Gespeichert
dreifünf Bytes dank flawr.~nnz(c)
ist kürzer alsisempty(c)
und'Aa'
zwei Bytes kürzer als[0,32]
.Probieren Sie die Octave-Version online aus!
Erläuterung:
c=input('')
bittet den Benutzer um Eingabe. Wir definierenk='Aa'
als ein Zeichenarray.while k++<1e5
While - Schleife , wo beide Elemente in:k
jeweils Iteration inkrementiert,Aa
,Bb
,Cc
und so weiter. Die Schleife wird fortgesetzt, bis das größte Element vorhanden ist1e5
, das für die meisten Zeichenfolgen ausreichend hoch sein sollte. Es kann auf erhöht werden,9e9
ohne die Byteanzahl zu erhöhen .Wir werden die
strrep
Funktion schrittweise ab der Mitte ausführen.Bei Verwendung von erhalten
mod(k,64)
wir Folgendes, wenn wir das Ende des Alphabets erreichen (wenn wirk
zurück in Zeichen konvertieren ):Wie Sie sehen, gibt es dazwischen einige Symbole, die sich jedoch umschließen und wieder mit dem Alphabet beginnen, jetzt jedoch zuerst mit den Kleinbuchstaben. Dies ist ein sehr kurzer Weg, um beide
Aa
und zu überprüfenaA
.['',65+mod(k,64)]
Verkettet die numerischen Werte aus demmod
-call mit einer leeren Zeichenfolge und konvertiert die Zahlen in Zeichen.strrep
wird verwendet, um Elemente aus dem String zu entfernenc
und zurückzugeben. Es wird nach allen Vorkommenk
in der Zeichenfolge gesucht und durch eine leere Zeichenfolge ersetzt.Nach
1e5
Iterationen haben wir entweder eine leere Zeichenfolge oder eine nicht leere Zeichenfolge. Wir prüfen, ob Elemente in derc
Verwendung sindnnz(c)
. Wir kehren zurücknot(nnz(c))
,1
wenn es leer ist und0
Zeichen übrig sindc
quelle
Minkolang 0,15 , 30 Bytes
Probieren Sie es hier aus!
Erläuterung
Minkolangs torische Natur wird hier genutzt, um die Notwendigkeit einer äußeren Schleife zu beseitigen. Die allgemeine Idee hier ist, zu überprüfen, ob die oberen beiden Elemente des Stapels 32 Einheiten voneinander entfernt sind (dh, sie sind ein Paar aus Groß- und Kleinbuchstaben), und wenn ja, beide zu entfernen. Da dies sozusagen "in Echtzeit" erfolgt, wird das Verschachteln von Paaren ordnungsgemäß gehandhabt.
quelle
Haskell, 62 Bytes
Probieren Sie es online aus
Gutschrift an flawr für die
abs
und Laikoni für diefromEnum
Karte .Die Hilfsfunktion verwendet
%
eine bereits vereinfachte Zeichenfolgel
und stellt das Symbol voran,a
bevor das Ergebnis vereinfacht wird. Beginntl
mit dem umgekehrten Zeichen zua
, brechen sie ab. Ansonstena
wird einfach vorangestellt. Zu diesem Zeitpunkt ist keine weitere Vereinfachung erforderlich.Die Hauptfunktion
f
stellt jedes Zeichen der Reihe nach über a voran und vereinfacht esfoldr
. Dann wird geprüft, ob das Ergebnis leer ist.Um zu überprüfen, ob zwei Zeichen entgegengesetzte Groß- / Kleinschreibung haben und daher abgebrochen werden sollten, prüfen Sie, ob sich ihre ASCII-Werte um 32 unterscheiden. Jedes Element wird von verarbeitet,
fromEnum
bevor es an übergeben wird%
.quelle
05AB1E , 17 Bytes
Probieren Sie es online!
Erläuterung
quelle
Haskell ,
98 97 8581 BytesDies ist nur eine naive Implementierung, die wiederholt versucht, benachbarte Buchstaben abzubrechen, bis keine Änderung mehr vorliegt, und dann das Ergebnis daraus bestimmt.
Vielen Dank an @nimi für -12 Bytes und @xnor für weitere -4 Bytes!
Probieren Sie es online! oder Überprüfen Sie alle Beispiele!
quelle
f=null.until(\a->r a==a)r.map fromEnum
sollte zwei Bytes speichern.(\a->r a==a)
kann sein((==)=<<r)
.=r l
uml
reicht die Idee ist es nur einen Ersatz pro Lauf zu machen.=<<
, scheint wie Magie XD=<<
ist wie>>=
aber mit den Argumenten getauscht. Der Ausdruck kommt oft in der Form((==)=<<r)
"ist unveränderlich unterr
" vor.Mathematica, 102 Bytes
Unbenannte Funktion, die eine alphabetische Zeichenfolge als Eingabe verwendet und
True
oder zurückgibtFalse
.Das Herzstück der Implementierung ist das Erstellen einer Funktion, mit der ein stornierendes Paar wie
"Pp"
oder"gG"
aus einem String gelöscht wird. Der Ausdruck{Join[a=Alphabet[],A=ToUpperCase@a],A~Join~a}
erzeugt ein geordnetes Paar von Zeichenlisten, wobei die erste Liste{"a","b",...,"Z"}
und die zweite Liste sind{"A","B",...,"z"}
. Dann#<>#2&~MapThread~
wird eine Liste erstellt, in der die entsprechenden Elemente dieser beiden Listen verkettet wurden, d{"aA","bB",...,"Zz"}
. H. Der spaßige Ausdruck erzeugt""|##&@@
dann (durch die Magie der Argumentfolge##
) eine Liste von Alternativen"" | "aA" | "bB" | ... | "Zz"
; SchließlichStringDelete[...]
ist es eine Funktion, die jedes Vorkommen einer dieser Alternativen aus einer Zeichenfolge löscht.Es genügt jetzt, diese Funktion wiederholt auf die Eingabezeichenfolge anzuwenden, bis sich das Ergebnis nicht mehr ändert, was durch erreicht wird
~FixedPoint~#
, und dann zu testen, ob das Ergebnis die leere Zeichenfolge mit ist""==
.quelle
JavaScript (ES6), 73 Byte
Im Gegensatz zu .NET hat JavaScript keine Möglichkeit, die Groß- / Kleinschreibung während einer Übereinstimmung zu deaktivieren. Stattdessen müssen wir alle Teilzeichenfolgen von Buchstaben, bei denen die Groß- / Kleinschreibung wiederholt wird, unempfindlich finden und dann alle nicht übereinstimmenden Paare benachbarter Zeichen löschen, die zu diesem Zeitpunkt vorhanden sein müssen ein Paar aus Groß- und Kleinschreibung.
quelle
Perl, 28 Bytes
Erläuterung:
Mit Perl kann ein dynamisch generierter regulärer Ausdruck in einen regulären Standardausdruck eingefügt werden.
Das
.
passt zu allem.Das
(??{
ist der Beginn der erzeugten regex.Die
$&
Variable enthält die gesamte bisher übereinstimmende Zeichenfolge, die in diesem Fall genau die.
übereinstimmende ist.Der
^
Operator führt je nach den Werten der Operanden entweder ein numerisches xoder oder ein String xoder aus. In diesem Fall ist es string xor.Dies
' '
ist nur eine Zeichenfolge, die ein Leerzeichen enthält, das günstigerweise den ASCII-Wert (oder Unicode!) 32 hat. Wenn ein Leerzeichen mit einem Zeichen im Bereich von az oder AZ xor-tiert wird, wechselt es von Groß- zu Kleinbuchstaben oder umgekehrt umgekehrt.Das
})
ist das Ende des erzeugten regulären Ausdrucks.1 while s/whatever//
sucht wiederholt nach einem Muster und ersetzt es durch die leere Zeichenfolge.$_
ist die Standardvariable. Diese Variable ist das, worauf Perl Spaß macht und aufregende Dinge, wenn Sie keine andere Variable angeben. Hier verwende ich es, um einen wahrheitsgemäßen oder falschen Wert zurückzugeben, da eine Zeichenfolge mit der Länge Null falsch ist und eine Zeichenfolge mit der Länge ungleich Null, die nicht gleich"0"
ist, wahr ist. Ich gehe auch davon aus, dass die Eingabezeichenfolge ursprünglich darin platziert wurde.Probieren Sie es hier aus
quelle
!
vor dem Finale hinzu$_
. Wenn es für Sie in Ordnung ist, diese Einstellung beizubehalten, können Sie 4 Byte einsparen, indem Sie sie aufs/.(??{$&^' '})//&&redo
+1 Byte für das-p
Flag ändern . Es funktioniert in einer Subroutine nicht so, wie Sie es jetzt haben, weil{ code }
es eigentlich keine Schleife ist (also&&redo
nicht funktioniert), sondern-p
es in einewhile
Schleife einfügt.' '
mit$"
. Schauen Sie sich das an, um zu sehen, wie der Code aussieht.Prolog (SWI) , 151 Bytes
Es dauert lange, bis die längeren falschen Fälle aufgrund von Backtracking ausgeführt werden.
Probieren Sie es online!
Ungolfed
quelle
MATL , 20 Bytes
Probieren Sie es online! Oder überprüfen Sie alle Testfälle (es dauert eine Weile).
Erläuterung
quelle
Mathematica, 65 Bytes
quelle
JavaScript (Node.js) , 47 Byte
Probieren Sie es online!
quelle
Python 3 , 71 Bytes
Probieren Sie es online!
quelle