Hintergrund
Der größte gemeinsame Divisor (kurz gcd ) ist eine bequeme mathematische Funktion, da er viele nützliche Eigenschaften hat. Eines davon ist Bézouts Identität : Wenn d = gcd(a, b)
, dann gibt es ganze Zahlen x
und y
solche, die es gibt d = x*a + y*b
. In dieser Herausforderung besteht Ihre Aufgabe darin, diese Eigenschaft mit einfacher ASCII-Grafik zu visualisieren.
Eingang
Ihre Eingaben bestehen aus zwei positiven ganzen Zahlen a
und b
werden in einem angemessenen Format angegeben. Sie können auch unäre Eingaben vornehmen (Wiederholungen eines einzelnen druckbaren ASCII-Zeichens Ihrer Wahl), müssen jedoch konsistent sein und für beide Eingaben dasselbe Format verwenden. Die Eingaben können in beliebiger Reihenfolge und gleich sein.
Ausgabe
Ihre Ausgabe ist eine Zeichenfolge mit s
einer Länge lcm(a, b) + 1
( lcm steht für das niedrigste gemeinsame Vielfache). Die Zeichen von stehen s
für Ganzzahlen von 0
bis lcm(a, b)
. Das Zeichen s[i]
ist ein Kleinbuchstabe, o
wenn i
es ein Vielfaches von a
oder ist b
, und .
ansonsten ein Punkt . Beachten Sie, dass Null ein Vielfaches jeder Zahl ist. Aufgrund von Bézouts Identität wird es nun mindestens ein Zeichenpaar geben, o
in s
dessen Abstand genau ist gcd(a, b)
. Das am weitesten links stehende Paar wird durch O
s in Großbuchstaben ersetzt . Dies ist die endgültige Ausgabe.
Beispiel
Betrachten Sie die Eingänge a = 4
und b = 6
. Dann haben wir gcd(a, b) = 2
und lcm(a, b) = 12
, so wird die Länge s
sein 13
. Die Vielfachen von a
und b
werden wie folgt hervorgehoben:
0 1 2 3 4 5 6 7 8 9 10 11 12
o . . . o . o . o . . . o
Es gibt zwei Paare von o
s mit Abstand zwei, aber wir werden nur die ganz linken durch O
s ersetzen , so dass die endgültige Ausgabe erfolgt
o...O.O.o...o
Regeln und Wertung
Sie können ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.
Testfälle
1 1 -> OO
2 2 -> O.O
1 3 -> OOoo
4 1 -> OOooo
2 6 -> O.O.o.o
2 3 -> o.OOo.o
10 2 -> O.O.o.o.o.o
4 5 -> o...OO..o.o.o..oo...o
8 6 -> o.....O.O...o...o.o.....o
12 15 -> o...........O..O........o.....o.....o........o..o...........o
19 15 -> o..............o...o..........o.......o......o...........o..o..............OO.............o....o.........o........o.....o............o.o..............o.o............o.....o........o.........o....o.............oo..............o..o...........o......o.......o..........o...o..............o
.
,o
oderO
.) Oder muss es sein1
? Oder0
?Antworten:
Jolf, 52 Bytes
Ich werde diesen Code in zwei Teile aufteilen.
Probieren Sie es hier aus!
quelle
Julia,
11111010710396 BytesDies ist eine Funktion, die zwei Ganzzahlen akzeptiert und eine Zeichenfolge zurückgibt.
Ungolfed:
Dank nimi ein Byte gespart!
quelle
Retina ,
112109999491 BytesIch denke, das ist nicht sehr konkurrenzfähig, aber die Zahlentheorie in der Netzhaut macht immer Spaß. :)
Nimmt Eingaben als unäre Zahlen unter Verwendung
.
der unären Ziffer an.Probieren Sie es online aus.
Erläuterung
Dies fügt ein
.
und ein Leerzeichen vor der Eingabe ein. Dies wird letztendlich zur Ausgabe.Dies stellt das LCM von
a
undb
vor den String. Da wir bereits eine.
dort haben, werden wir am Ende mitlcm(a,b)+1
. Dies wird durch wiederholtes Voranstellen erreichtb
, solangea
dieses neue Präfix nicht geteilt wird. Wir erfassena
in einer Gruppe eins und prüfen dann, ob wir den Anfang der Zeichenfolge erreichen können, indem wir mindestens einmal mit dieser Erfassung übereinstimmen.b
wird dann über den selten verwendeten in den String eingefügt, der nach dem Match$'
alles in die Ersetzung einfügt .Dieser stimmt mit Zeichen an Positionen überein, die durch
a
oder geteilt sindb
. Dabei wird die Tatsache ausgenutzt, dass das Ergebnis symmetrisch ist: dalcm(a,b)
durch beide geteilt wirda
undb
nach links gegangen wird, indem Instanzen vona
oder subtrahiert werden, wasb
dasselbe Muster ergibt, als wenn nach rechts gegangen0
wird, indem sie addiert werden. Der erste Lookahead erfasst einfacha
undb
. Der zweite Lookahead prüft, ob vor dem ersten Leerzeichen ein Vielfaches von jedema
oder mehrerenb
Zeichen steht.Wie auf Wikipedia angegeben, ist es neben Bézouts Identität auch so
Dies impliziert, dass die GCD der kürzesten Lücke zwischen zwei
o
Sekunden in der Ausgabe entspricht. Wir müssen uns also überhaupt nicht darum kümmern, die GCD zu finden. Stattdessen suchen wir nur die erste Instanz der kürzesten Lücke.o(\.*)o
Stimmt mit einer Kandidatenlücke überein und erfasst deren Breite in Gruppe 1. Dann versuchen wir, das erste Leerzeichen zu erreichen, indem wir zwischen einem Rückverweis auf Gruppe 1 undo
s wechseln (mit optionalen zusätzlichen.
s). Wenn es weiter rechts eine kürzere Lücke gibt, wird diese nicht übereinstimmen, da wir diese Lücke mit der Rückreferenz nicht überwinden können. Sobald alle weiteren Lücken mindestens so groß wie die aktuelle sind, stimmt dies überein. Wir erfassen das Ende des LCM-Strings in Gruppe 2 und passen den Rest des Strings an.*
. Wir schreiben den Großbuchstaben zurückO
s (mit der Lücke dazwischen) sowie den Rest der LCM-Zeichenfolge, aber alles verwerfen, beginnend mit dem Leerzeichen, um zu entfernena
undb
vom Endergebnis.quelle
(\.*)
=>(a*)
.
später ersetzen , was vier Bytes kostet (und das Entfernen der Escape-Zeichen spart nur 3).𝔼𝕊𝕄𝕚𝕟 50 Zeichen / 90 Bytes
Try it here (Firefox only).
Es muss einen Weg geben, weiter Golf zu spielen!
Erläuterung
Dies ist ein grundlegender Zwei-Phasen-Algorithmus. Es ist eigentlich ganz einfach.
Phase 1
Zunächst erstellen wir einen Bereich von 0 bis LCM + 1. Dann mappen wir darüber und prüfen, ob einer der Eingänge ein Faktor des aktuellen Elements im Bereich ist. In diesem Fall ersetzen wir diesen Eintrag durch ein
o
; ansonsten ersetzen wir es durch a.
. Wenn wir uns dazu gesellen, erhalten wir eine Reihe von O's und Punkten, die wir in die zweite Phase überführen können.Phase 2
Dies ist nur eine große Ersetzungsfunktion. Eine Regex wird als erstellt
o[dots]o
, wobei die Anzahl der Punkte vom GCD-1 bestimmt wird. Da dieser reguläre Ausdruck nicht global ist, stimmt er nur mit dem ersten Vorkommen überein. Danach wird die Übereinstimmung durchO[dots]O
eine toUpperCase-Funktion ersetzt.quelle
MATL , 72 Bytes
Verwendet Version 6.0.0 , die älter als diese Herausforderung ist. Der Code läuft in Matlab und in Octave.
Beispiel
Erläuterung
Ich habe keine Ahnung, wie es funktioniert. Ich habe nur zufällig Zeichen eingegeben. Ich denke, es gibt eine Faltung.
Bearbeiten: Probieren Sie es online! Der Code im Link wurde geringfügig geändert, um Änderungen in der Sprache Rechnung zu tragen (Stand: 2. Juni 2016).
quelle
Japt , 83 Bytes
Noch nicht voll bespielt ... Und will nicht bespielt werden: /
quelle
r
anstelle von verwenden$.replace($
?Javascript,
170164161153145141136 BytesDas ist ziemlich lonnnggggg ....
Demo , explizit definierte Variablen, da der Interpreter den strikten Modus verwendet.
quelle
i%a<1||i%b<1?'o':'.'
durchi%a&&i%b?'.':'o'
[...Array((d=a*b/(c=(g=(a,b)=>b?g(b,a%b):a)(a,b)))+1).keys()].map(i=>i%a&&i%b?'.':'o')
spart Ihnen zwei Bytes. (Ich habe auch versucht, Zeichenfolgenindizierung zu verwenden, um das '.' Und 'o' zu erstellen, aber das kostet tatsächlich zwei Bytes.)Python 2,
217200191 BytesDies ist ein wenig stumpf, aber es funktioniert. Irgendwelche Golf - Tipps geschätzt werden,
vor allem , wenn Sie wissen , wie das behebenGot it!s[i] = s[v] = "o"
Problem , das ich gestoßen, wo das würde überschreiben „O“ sUngolfed:
quelle