Einzelne Züge
Das Brett ist ein unendliches 2-dimensionales quadratisches Gitter, wie ein unbegrenztes Schachbrett. Ein Teil mit dem Wert N (ein N-Mover ) kann sich zu einem beliebigen Quadrat bewegen, das genau die Quadratwurzel von N von seinem aktuellen Quadrat entfernt ist (euklidischer Abstand von Mitte zu Mitte gemessen).
Zum Beispiel:
- Ein 1-Mover kann sich auf ein beliebiges Feld bewegen, das horizontal oder vertikal angrenzt
- Ein 2-Mover kann sich auf jedes diagonal benachbarte Quadrat bewegen
- Ein 5-Mover bewegt sich wie ein Schachritter
Beachten Sie, dass sich nicht alle N-Mover bewegen können. Ein 3-Mover kann sein aktuelles Quadrat niemals verlassen, da keines der Quadrate auf dem Brett einen Abstand von genau Wurzel 3 zum aktuellen Quadrat hat.
Mehrere Züge
Wenn man sich wiederholt bewegen darf, können einige Steine ein beliebiges Feld auf dem Brett erreichen. Zum Beispiel können sowohl ein 1-Mover als auch ein 5-Mover dies tun. Ein 2-Mover kann sich nur diagonal bewegen und nur die Hälfte der Quadrate erreichen. Eine Figur, die sich nicht bewegen kann, wie ein 3-Mover, kann keines der Quadrate erreichen (das Startquadrat wird nicht als "erreicht" gezählt, wenn keine Bewegung stattfindet) .
Die Bilder zeigen, welche Quadrate erreicht werden können. Weitere Details zum Hover. Klicken für größeres Bild.
- Quadrate, die in einem oder mehreren Zügen erreicht werden können, sind schwarz markiert
- Felder, die in genau einem Zug erreicht werden können, werden durch rote Steine dargestellt
(außer dem 3-Mover, der sich nicht bewegen kann).
Welchen Anteil des Boards kann ein bestimmter N-Mover erreichen?
Eingang
- Eine positive ganze Zahl N
Ausgabe
- Der Anteil des Boards, den ein N-Mover erreichen kann
- Dies ist eine Zahl von 0 bis 1 (beide inklusive)
- Für diese Herausforderung ist die Ausgabe als Bruch in niedrigsten Ausdrücken wie 1/4 zulässig
Für die Eingabe 10
sind also beide 1/2
und 0.5
akzeptable Ausgaben. Die Ausgabe als separater Zähler und Nenner ist ebenfalls zulässig, um Sprachen einzuschließen, die weder Gleitkomma noch Brüche unterstützen. Zum Beispiel 1 2
oder [1, 2]
.
Für die Ganzzahlausgaben (0 und 1) sind folgende Formate zulässig:
- Für 0:
0
,0.0
,0/1
,0 1
,[0, 1]
- 1:
1
,1.0
,1/1
,1 1
,[1, 1]
Wertung
Das ist Code Golf. Die Punktzahl ist die Länge des Codes in Bytes. Für jede Sprache gewinnt der kürzeste Code.
Testfälle
Im Format input : output as fraction : output as decimal
1 : 1 : 1
2 : 1/2 : 0.5
3 : 0 : 0
4 : 1/4 : 0.25
5 : 1 : 1
6 : 0 : 0
7 : 0 : 0
8 : 1/8 : 0.125
9 : 1/9 : 0.1111111111111111111111111111
10 : 1/2 : 0.5
13 : 1 : 1
16 : 1/16 : 0.0625
18 : 1/18 : 0.05555555555555555555555555556
20 : 1/4 : 0.25
25 : 1 : 1
26 : 1/2 : 0.5
64 : 1/64 : 0.015625
65 : 1 : 1
72 : 1/72 : 0.01388888888888888888888888889
73 : 1 : 1
74 : 1/2 : 0.5
80 : 1/16 : 0.0625
81 : 1/81 : 0.01234567901234567901234567901
82 : 1/2 : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1 : 1
146 : 1/2 : 0.5
148 : 1/4 : 0.25
153 : 1/9 : 0.1111111111111111111111111111
160 : 1/32 : 0.03125
161 : 0 : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0 : 0
164 : 1/4 : 0.25
241 : 1 : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4 : 0.25
245 : 1/49 : 0.02040816326530612244897959184
260 : 1/4 : 0.25
261 : 1/9 : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2 : 0.5
292 : 1/4 : 0.25
293 : 1 : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1 : 1
326 : 0 : 0
360 : 1/72 : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2 : 0.5
369 : 1/9 : 0.1111111111111111111111111111
370 : 1/2 : 0.5
449 : 1 : 1
450 : 1/18 : 0.05555555555555555555555555556
488 : 1/8 : 0.125
489 : 0 : 0
490 : 1/98 : 0.01020408163265306122448979592
520 : 1/8 : 0.125
521 : 1 : 1
522 : 1/18 : 0.05555555555555555555555555556
544 : 1/32 : 0.03125
548 : 1/4 : 0.25
549 : 1/9 : 0.1111111111111111111111111111
584 : 1/8 : 0.125
585 : 1/9 : 0.1111111111111111111111111111
586 : 1/2 : 0.5
592 : 1/16 : 0.0625
593 : 1 : 1
596 : 1/4 : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2 : 0.5
611 : 0 : 0
612 : 1/36 : 0.02777777777777777777777777778
613 : 1 : 1
624 : 0 : 0
625 : 1 : 1
quelle
Antworten:
JavaScript (Node.js) ,
144138125747370 ByteProbieren Sie es online!
-4 byte danke @Arnauld!
Ursprünglicher Ansatz, 125 Bytes
Probieren Sie es online!
Inspiriert von dem Video Pi, das sich in erstklassigen Regelmäßigkeiten von 3Blue1Brown versteckt.
Berechnen Sie für jeden Primfaktor in der Faktorisierung der Zahl :pn f( pn)
Multiplizieren Sie all diese Funktionswerte.
Aktualisieren
Dank der Bemühungen von Mitarbeitern von Math.SE wird der Algorithmus jetzt durch einen Beweis untermauert
quelle
Mathematica, 80 Bytes
Dieser Code beruht hauptsächlich auf einem mathematischen Theorem. Die Grundidee ist, dass der Code die Dichte eines Gitters bei einem bestimmten Generatorsatz abfragt.
Genauer gesagt, wir erhalten eine Sammlung von Vektoren - nämlich diejenigen, deren Länge im Quadrat N ist - und werden gebeten, die Dichte der Menge möglicher Summen dieser Vektoren im Vergleich zu allen ganzzahligen Vektoren zu berechnen. Die Mathematik geht davon aus, dass wir immer zwei Vektoren (und deren Gegenteil) finden können, die die gleiche Menge wie die ursprüngliche Sammlung "erzeugen" (dh deren Summen sind). LatticeReduce macht genau das.
Wenn Sie nur zwei Vektoren haben, können Sie sich vorstellen, ein identisches Parallelogramm zu zeichnen, das an jedem erreichbaren Punkt zentriert ist, dessen Kantenlänge jedoch die angegebenen Vektoren sind, sodass die Ebene durch diese Parallelogramme vollständig gekachelt wird. (Stellen Sie sich zum Beispiel ein Gitter mit "Diamant" -Formen für n = 2 vor). Die Fläche jedes Parallelogramms ist die Determinante der beiden erzeugenden Vektoren. Der gewünschte Anteil der Ebene ist der Kehrwert dieses Bereichs, da jedes Parallelogramm nur einen erreichbaren Punkt enthält.
Der Code ist eine recht einfache Implementierung: Generieren Sie die Vektoren, verwenden Sie LatticeReduce, nehmen Sie die Determinante und nehmen Sie dann den Kehrwert. (Es kann aber wahrscheinlich besser Golf gespielt werden)
quelle
d@n_:=Boole[#!={}]/Det@LatticeReduce@#&@Select[Range[-n,n]~Tuples~2,#.#==n&]
Sauber ,
189185172171 BytesProbieren Sie es online!
Findet jede Position, die auf dem
n
Quadrat mit der Seitenlänge in der Ecke des Ursprungs im ersten Quadranten erreichbar ist, und dividiert dann durchn^2
, um den Teil aller Zellen zu ermitteln, die erreichbar sind.Das funktioniert, weil:
n
Quadrats mit Seitenlänge betrachtet werden. Jedes Quadrat ist an einem erreichbaren Punkt vom Ursprung aus in einer Ecke angeordnet, als wäre es der Ursprung.++ +- -+ --
, sodass die überlappenden Kacheln durch Spiegeln und Drehen auf die anderen drei Quadranten ausgedehnt werden können.quelle
Retina 0.8.2 ,
12682 BytesProbieren Sie es online! Link enthält Testfälle. Erläuterung:
In Unary konvertieren.
Wiederholt durch Primfaktoren der Form teilen
4k+1
.Wenn das Ergebnis weder ein Quadrat noch ein doppeltes Quadrat ist, ist das Ergebnis Null.
Berechnen Sie den Kehrwert als Dezimalbruch.
quelle
Regex (ECMAScript, wechselseitig aus),
256163157948382 Bytes-93 Bytes dank Neil
-6 Bytes dank Neil
-63 Bytes durch Division ohne Erfassung des Divisors
-11 Bytes dank Grimys simultaner optionaler Division durch Konstante und Quadratwurzel
-1 Bytes durch Verschieben der End-Match-Bedingung und dank Grimy als zweite Alternative die Erfassung von Werten in die Schleife zurückgeben
Dies verwendet die gleiche Mathematik wie die JavaScript-Antwort von Shieru Asakoto .
Die Eingabe ist unär. Da ein reiner Regex nur einen Teilstring vom Eingang (dh eine natürliche Zahl, die kleiner oder gleich dem Eingang ist) oder "keine Übereinstimmung" als Ausgabe zurückgeben kann, gibt dieser Regex den Kehrwert des Anteils der Karte zurück, den ein N-Mover hat kann erreichen. Da der Kehrwert von 0 unendlich ist, wird in diesem Fall "keine Übereinstimmung" zurückgegeben.
SPOILER-WARNUNG : Für die Quadratwurzel verwendet dieser Regex eine Variante des verallgemeinerten Multiplikationsalgorithmus. Dies ist nicht offensichtlich und kann ein lohnendes Rätsel sein, das Sie selbst lösen können . Weitere Informationen finden Sie in der Erklärung zu dieser Form des Algorithmus unter Suchen einer Rocco-Nummer .
^(?=((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5|((xx?)(\8*))(?=(\7*)\9+$)\7*$\10)+$)\1
Probieren Sie es online!
Probieren Sie es online! (nur die Testfälle)
Regex (ECMAScript + (? *), Wechselseitige Ausgabe),
207138132BytesWird durch Division überholt, ohne den Divisor zu erfassen (dh ist jetzt identisch mit dem oben genannten).
Regex (ECMAScript 2018, wechselseitige Ausgabe),
212140134BytesWird durch Division überholt, ohne den Divisor zu erfassen (dh ist jetzt identisch mit dem oben genannten).
Regex (ECMAScript, Bruchausgabe), 80 Bytes
In dieser Version wird der Zähler in
\10
(Null, wenn nicht gesetzt / NPCG) und der Nenner in zurückgegeben\7
.Im Gegensatz zur reziproken Ausgabeversion:
Der große Nachteil einer solchen Ausgabespezifikation ist, dass sie nicht im Programm selbst enthalten ist.
((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5)*((((x)x?)(\9*))(?=(\8*)\11+$)\8*$\12|x)
Probieren Sie es online!
Probieren Sie es online! (nur die Testfälle)
quelle
(((xx?)(\9*))(?=(\8*)\10+$)\8*$\11)
überprüft wird, ob N oder N / 2 ein Quadrat ist.Jelly ,
2524 BytesEine monadische Verbindung unter Verwendung der Primfaktor-Route.
Probieren Sie es online!
Wie?
Vorherige 25 war:
Volles Programm Brute Forcer
; Möglicherweiselängerer Codeals die Route mit dem Primfaktor (ich könnte es später versuchen).Probieren Sie es online!
Beginnt , indem das Herstellen der einzelnen Bewegungen als Koordinaten dann wiederholt sich von allen Stellen erreicht die Ergebnisse akkumuliert, wobei modulo
n
jeder Koordinate (zu beschränken , um einen
durchn
Quadrant) und halten solche , die verschieden sind , bis ein fester Punkt erreicht wird; dann dividiert schließlich die Zählung durchn^2
quelle
05AB1E ,
272625 BytesPort von @ShieruAsakotos JavaScript-Antwort , also stelle sicher, dass du ihn auch positiv bewertest!
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Erläuterung:
quelle
APL (Dyalog Extended) , 21 Byte
Dieses Programm benutzt die Primfaktor Route. Ich bin Adám, dzaima, H.PWiz, J.Sallé und ngn zu Dank verpflichtet. Der APL-Obstgarten ist ein großartiger Ort, um APL zu lernen, und sie sind immer bereit zu helfen
Probieren Sie es online!
Ungolfing
Teil 2 dieses Codes ist derselbe wie in der folgenden Dyalog Unicode-Version, und deshalb werde ich mich in dieser Erläuterung darauf konzentrieren
⍭*1≠4|⍭
APL (Dyalog Unicode) ,
41403635 Byte SBCSDieses Programm benutzt die Primfaktor Route. Ich habe beim Schreiben ein paar Tricks gelernt und bin Adám, dzaima, H.PWiz, J.Sallé und ngn zutiefst verbunden. Der APL-Obstgarten ist ein großartiger Ort, um APL zu lernen, und sie sind immer bereit zu helfen (andernfalls wäre dieser Beitrag niemals in Gang gekommen :)
Edit: -1 Byte von ngn. -2 Bytes von Adám und -2 weitere von ngn. -1 Byte von ngn.
Probieren Sie es online!
Ungolfing
Dies ist ein Programm in zwei Teilen:
quelle