Zufälliges Golf des Tages # 6: Würfeln Sie einen d20

17

Über die Serie

Zunächst einmal können Sie dies wie jede andere Code-Golf-Herausforderung behandeln und beantworten, ohne sich Gedanken über die Serie zu machen. Es gibt jedoch eine Rangliste für alle Herausforderungen. Sie finden die Rangliste zusammen mit einigen weiteren Informationen über die Serie im ersten Beitrag .

Obwohl ich eine Menge Ideen für die Serie habe, sind die zukünftigen Herausforderungen noch nicht in Stein gemeißelt. Wenn Sie Vorschläge haben, teilen Sie mir dies bitte auf dem entsprechenden Sandbox-Post mit .

Loch 6: Wirf einen W20

Ein sehr häufiger Würfel in RPGs mit Tischplatte ist der zwanzigseitige Würfel (ein Ikosaeder , allgemein bekannt als d20 ). Es ist deine Aufgabe, einen solchen Würfel zu werfen. Wenn Sie jedoch nur eine Zufallszahl zwischen 1 und 20 zurückgeben würden, wäre dies ein bisschen trivial. Deine Aufgabe ist es also, ein zufälliges Netz für einen bestimmten Würfel zu generieren.

Wir werden das folgende Netz verwenden:

Bildbeschreibung hier eingeben

Es ist ein Dreiecksstreifen, so dass es leicht als Liste von ganzen Zahlen dargestellt werden kann. ZB wenn Sie die Eingabe erhalten:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Das würde dem folgenden Würfel entsprechen (lustige Tatsache: Dies ist das von Magic verwendete Netz : die Lebensmarken der Sammlung / Spin-down-Würfel).

Bildbeschreibung hier eingeben

Dies ist jedoch nicht das einzige Netz, das diesen Würfel darstellt. Je nachdem, wie wir die Gesichter abrollen, gibt es 60 verschiedene Netze. Hier sind zwei weitere:

[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]

Oder grafisch (der Einfachheit halber habe ich die Gesichtsbeschriftungen nicht gedreht):

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Die Herausforderung

Ausgehend von einer Liste von Ganzzahlen, die einen Würfel (wie oben beschrieben) darstellen, und einer Ganzzahl Nwerden Nunabhängig voneinander einheitlich zufällige d20-Netze ausgegeben , die dem gegebenen Würfel entsprechen. (Das heißt, jedes der 60 möglichen Netze sollte die gleiche Wahrscheinlichkeit haben, generiert zu werden.)

Aufgrund der technischen Einschränkungen von PRNGs ist eine perfekte Gleichmäßigkeit natürlich nicht möglich. Um die Gleichmäßigkeit Ihrer Einreichung zu beurteilen, werden die folgenden Vorgänge als perfekt gleichmäßige Verteilungen ergebend angesehen:

  • Beziehen einer Nummer von einem PRNG (über einen beliebigen Bereich), von dem dokumentiert wird, dass sie (ungefähr) einheitlich ist.
  • Abbildung einer gleichmäßigen Verteilung über eine größere Menge von Zahlen auf eine kleinere Menge durch Modulo oder Multiplikation (oder eine andere Operation, die Werte gleichmäßig verteilt). Die größere Menge muss mindestens das 1024-fache der möglichen Werte der kleineren Menge enthalten.

Unter diesen Voraussetzungen muss Ihr Algorithmus eine vollkommen gleichmäßige Verteilung ergeben.

Ihr Programm sollte in der Lage sein, 100 Netze in weniger als einer Sekunde zu generieren (versuchen Sie also nicht, zufällige Netze zu generieren, bis eines dem oben angegebenen Würfel entspricht).

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Die Ein- und Ausgabe kann in einem beliebigen praktischen, eindeutigen, flachen Listenformat erfolgen. Sie können davon ausgehen, dass es sich bei den Nennwerten des d20 um eindeutige positive Ganzzahlen handelt, die zum natürlichen Ganzzahltyp Ihrer Sprache passen.

Dies ist Codegolf, daher gewinnt die kürzeste Übermittlung (in Byte). Und natürlich wird die kürzeste Einreichung pro Benutzer auch in die Gesamt-Bestenliste der Serie aufgenommen.

Beispielausgaben

Für die Eingabe

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Die 60 möglichen Netze (vorausgesetzt, ich habe keinen Fehler gemacht) sind in keiner bestimmten Reihenfolge:

[11, 10, 9, 18, 19, 20, 13, 12, 3, 2, 1, 8, 7, 17, 16, 15, 14, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[8, 7, 17, 18, 9, 10, 2, 1, 5, 6, 15, 16, 20, 19, 11, 12, 3, 4, 14, 13]
[3, 12, 13, 14, 4, 5, 1, 2, 10, 11, 19, 20, 16, 15, 6, 7, 8, 9, 18, 17]
[3, 4, 5, 1, 2, 10, 11, 12, 13, 14, 15, 6, 7, 8, 9, 18, 19, 20, 16, 17]
[11, 19, 20, 13, 12, 3, 2, 10, 9, 18, 17, 16, 15, 14, 4, 5, 1, 8, 7, 6]
[4, 14, 15, 6, 5, 1, 2, 3, 12, 13, 20, 16, 17, 7, 8, 9, 10, 11, 19, 18]
[2, 10, 11, 12, 3, 4, 5, 1, 8, 9, 18, 19, 20, 13, 14, 15, 6, 7, 17, 16]
[4, 5, 1, 2, 3, 12, 13, 14, 15, 6, 7, 8, 9, 10, 11, 19, 20, 16, 17, 18]
[10, 2, 1, 8, 9, 18, 19, 11, 12, 3, 4, 5, 6, 7, 17, 16, 20, 13, 14, 15]
[3, 2, 10, 11, 12, 13, 14, 4, 5, 1, 8, 9, 18, 19, 20, 16, 15, 6, 7, 17]
[7, 8, 1, 5, 6, 15, 16, 17, 18, 9, 10, 2, 3, 4, 14, 13, 20, 19, 11, 12]
[13, 12, 11, 19, 20, 16, 15, 14, 4, 3, 2, 10, 9, 18, 17, 7, 6, 5, 1, 8]
[16, 15, 14, 13, 20, 19, 18, 17, 7, 6, 5, 4, 3, 12, 11, 10, 9, 8, 1, 2]
[15, 16, 17, 7, 6, 5, 4, 14, 13, 20, 19, 18, 9, 8, 1, 2, 3, 12, 11, 10]
[20, 13, 12, 11, 19, 18, 17, 16, 15, 14, 4, 3, 2, 10, 9, 8, 7, 6, 5, 1]
[5, 4, 14, 15, 6, 7, 8, 1, 2, 3, 12, 13, 20, 16, 17, 18, 9, 10, 11, 19]
[10, 11, 12, 3, 2, 1, 8, 9, 18, 19, 20, 13, 14, 4, 5, 6, 7, 17, 16, 15]
[4, 3, 12, 13, 14, 15, 6, 5, 1, 2, 10, 11, 19, 20, 16, 17, 7, 8, 9, 18]
[19, 20, 13, 12, 11, 10, 9, 18, 17, 16, 15, 14, 4, 3, 2, 1, 8, 7, 6, 5]
[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[8, 1, 5, 6, 7, 17, 18, 9, 10, 2, 3, 4, 14, 15, 16, 20, 19, 11, 12, 13]
[18, 9, 8, 7, 17, 16, 20, 19, 11, 10, 2, 1, 5, 6, 15, 14, 13, 12, 3, 4]
[12, 3, 2, 10, 11, 19, 20, 13, 14, 4, 5, 1, 8, 9, 18, 17, 16, 15, 6, 7]
[2, 3, 4, 5, 1, 8, 9, 10, 11, 12, 13, 14, 15, 6, 7, 17, 18, 19, 20, 16]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]
[9, 8, 7, 17, 18, 19, 11, 10, 2, 1, 5, 6, 15, 16, 20, 13, 12, 3, 4, 14]
[16, 17, 7, 6, 15, 14, 13, 20, 19, 18, 9, 8, 1, 5, 4, 3, 12, 11, 10, 2]
[17, 7, 6, 15, 16, 20, 19, 18, 9, 8, 1, 5, 4, 14, 13, 12, 11, 10, 2, 3]
[1, 5, 6, 7, 8, 9, 10, 2, 3, 4, 14, 15, 16, 17, 18, 19, 11, 12, 13, 20]
[9, 18, 19, 11, 10, 2, 1, 8, 7, 17, 16, 20, 13, 12, 3, 4, 5, 6, 15, 14]
[16, 20, 19, 18, 17, 7, 6, 15, 14, 13, 12, 11, 10, 9, 8, 1, 5, 4, 3, 2]
[5, 1, 2, 3, 4, 14, 15, 6, 7, 8, 9, 10, 11, 12, 13, 20, 16, 17, 18, 19]
[8, 9, 10, 2, 1, 5, 6, 7, 17, 18, 19, 11, 12, 3, 4, 14, 15, 16, 20, 13]
[13, 20, 16, 15, 14, 4, 3, 12, 11, 19, 18, 17, 7, 6, 5, 1, 2, 10, 9, 8]
[6, 15, 16, 17, 7, 8, 1, 5, 4, 14, 13, 20, 19, 18, 9, 10, 2, 3, 12, 11]
[6, 5, 4, 14, 15, 16, 17, 7, 8, 1, 2, 3, 12, 13, 20, 19, 18, 9, 10, 11]
[7, 6, 15, 16, 17, 18, 9, 8, 1, 5, 4, 14, 13, 20, 19, 11, 10, 2, 3, 12]
[19, 18, 17, 16, 20, 13, 12, 11, 10, 9, 8, 7, 6, 15, 14, 4, 3, 2, 1, 5]
[14, 15, 6, 5, 4, 3, 12, 13, 20, 16, 17, 7, 8, 1, 2, 10, 11, 19, 18, 9]
[17, 18, 9, 8, 7, 6, 15, 16, 20, 19, 11, 10, 2, 1, 5, 4, 14, 13, 12, 3]
[6, 7, 8, 1, 5, 4, 14, 15, 16, 17, 18, 9, 10, 2, 3, 12, 13, 20, 19, 11]
[14, 13, 20, 16, 15, 6, 5, 4, 3, 12, 11, 19, 18, 17, 7, 8, 1, 2, 10, 9]
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[7, 17, 18, 9, 8, 1, 5, 6, 15, 16, 20, 19, 11, 10, 2, 3, 4, 14, 13, 12]
[15, 6, 5, 4, 14, 13, 20, 16, 17, 7, 8, 1, 2, 3, 12, 11, 19, 18, 9, 10]
[9, 10, 2, 1, 8, 7, 17, 18, 19, 11, 12, 3, 4, 5, 6, 15, 16, 20, 13, 14]
[2, 1, 8, 9, 10, 11, 12, 3, 4, 5, 6, 7, 17, 18, 19, 20, 13, 14, 15, 16]
[12, 13, 14, 4, 3, 2, 10, 11, 19, 20, 16, 15, 6, 5, 1, 8, 9, 18, 17, 7]
[17, 16, 20, 19, 18, 9, 8, 7, 6, 15, 14, 13, 12, 11, 10, 2, 1, 5, 4, 3]
[18, 17, 16, 20, 19, 11, 10, 9, 8, 7, 6, 15, 14, 13, 12, 3, 2, 1, 5, 4]
[18, 19, 11, 10, 9, 8, 7, 17, 16, 20, 13, 12, 3, 2, 1, 5, 6, 15, 14, 4]
[11, 12, 3, 2, 10, 9, 18, 19, 20, 13, 14, 4, 5, 1, 8, 7, 17, 16, 15, 6]
[15, 14, 13, 20, 16, 17, 7, 6, 5, 4, 3, 12, 11, 19, 18, 9, 8, 1, 2, 10]
[19, 11, 10, 9, 18, 17, 16, 20, 13, 12, 3, 2, 1, 8, 7, 6, 15, 14, 4, 5]
[12, 11, 19, 20, 13, 14, 4, 3, 2, 10, 9, 18, 17, 16, 15, 6, 5, 1, 8, 7]
[20, 16, 15, 14, 13, 12, 11, 19, 18, 17, 7, 6, 5, 4, 3, 2, 10, 9, 8, 1]
[13, 14, 4, 3, 12, 11, 19, 20, 16, 15, 6, 5, 1, 2, 10, 9, 18, 17, 7, 8]
[5, 6, 7, 8, 1, 2, 3, 4, 14, 15, 16, 17, 18, 9, 10, 11, 12, 13, 20, 19]
[14, 4, 3, 12, 13, 20, 16, 15, 6, 5, 1, 2, 10, 11, 19, 18, 17, 7, 8, 9]

Ersetzen Sie für jedes andere Netz einfach jedes Vorkommen von idurch die ith-Zahl in der Eingabe (wobei i1-basiert ist).

Verwandte Herausforderungen

Bestenliste

Der erste Beitrag der Serie generiert eine Rangliste.

Um sicherzustellen, dass Ihre Antworten angezeigt werden, beginnen Sie jede Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

## Language Name, N bytes

Wo Nist 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

(Die Sprache wird derzeit nicht angezeigt, aber das Snippet erfordert und analysiert sie. In Zukunft werde ich möglicherweise eine Bestenliste nach Sprachen hinzufügen.)

Martin Ender
quelle
In Bezug auf unsere Diskussion habe ich das Wort "muss" hinzugefügt, um es klarer zu machen. Ich denke, das schließt die Lücke, die ich ausgenutzt habe. Trotzdem finde ich den Ansatz, den ich verwendet habe (obwohl er ungültig ist), interessant.
Level River St
Das ist fast genau wie mein Sandbox-Post!
Freitag,
@RikerW Das habe ich mir gedacht, als du es in eine Sandbox gelegt hast. ;) (Zu der Zeit war meine direkt unter deiner. Ich dachte, diese hat deine inspiriert.) Deine ist natürlich viel einfacher (was wahrscheinlich eine gute Sache ist).
Martin Ender
Ich habe deins nie gesehen. Das ist komisch, ich dachte, ich habe alle auf der ersten Seite gelesen. Aber nein, ich habe meine unabhängig gemacht.
Freitag,
Sollte das nicht "entfalte eine d20" heißen?
Titus

Antworten:

7

Ruby, 160 Bytes (Rev. B)

17 Bytes gespart dank Vorschlägen von Martin Büttner.

->a,n{n.times{k=rand 60
%w{ABCD@GHIJKLMNEFPQRSO PFENOSRQHG@DCMLKJIAB GFPQHIA@DENOSRJKBCML}.map{|b|k.times{a=b.chars.map{|i|a[i.ord-64]}}}
k>29&&a.reverse!
p a}}

Ruby, 177 Bytes (Rev. A)

->n,a{n.times{k=rand(60)
h=->b{k.times{|j|a=(0..19).map{|i|a[b[i].ord-64]}}}
h['ABCD@GHIJKLMNEFPQRSO']
h['PFENOSRQHG@DCMLKJIAB']
h['GFPQHIA@DENOSRJKBCML']
k>29&&a.reverse!
p a}}

Erläuterung

Es ist möglich, alle möglichen Orientierungen durch Rotationen um eine Fläche (3-fach), einen Scheitelpunkt (5-fach) und zwei Kanten (2-fach) zu erzeugen. Aber nicht irgendein Gesicht und Kanten. Die Achsen müssen die richtige Beziehung haben und die Rotationen müssen in der richtigen Reihenfolge ausgeführt werden, sonst können seltsame Dinge passieren.

So habe ich es gemacht (obwohl ich verstehe, dass Martin es anders gemacht hat.)

Alle Orientierungen eines Tetraeders können durch Kombinationen der folgenden drei Symmetrieoperationen erzeugt werden:

a) Drehung um zwei 2-fache Achsen rechts durch die Mittelpunkte der Kanten (diese stehen im rechten Winkel zueinander. Wenn wir sie miteinander multiplizieren, entdecken wir eine dritte 2-fache Achse durch das verbleibende Kantenpaar.)

b) Drehung um eine 3-fache Achse diagonal zu den 2-fachen Achsen, die durch einen Scheitelpunkt und eine Fläche verläuft.

Die Symmetrie des Ikosaeders ist eine Obermenge der des Tetraeders. In der folgenden Abbildung von https://en.wikipedia.org/wiki/Icosahedron definieren die gelben und roten Flächen zwei verschiedene Tetraeder (oder alternativ ein einzelnes Oktaeder), während die beiden blauen Flächen gemeinsame Kanten in drei Paaren bei sind rechte Winkel (und auf den Flächen eines Würfels liegen.)

Alle Ausrichtungen des Ikosaeders können durch die oben erwähnten Symmetrieoperationen plus einer zusätzlichen 5-fachen Operation erzeugt werden.

Bildbeschreibung hier eingeben

Die Rotationen um drei der vier oben genannten Achsen werden durch die magischen Ketten zwischen den ''Markierungen dargestellt. Die Drehung um die zweite 2-fache Achse ist unterschiedlich und kann einfach durch Umkehren des Arrays erfolgen a[].

Ungolfed im Testprogramm:

f=->a,n{
  n.times{                     #Iterate n times, using the result from the previous iteration to generate the next
    k=rand(60)                 #pick a random number

    h=->b{                     #helper function taking a string representing a transformation
      k.times{|j|              #which is performed on a using the number of times according to k
        a=(0..19).map{|i|a[b[i].ord-64]}
      }
    }

    #Rotate about axes k times (one 5-fold, one 3-fold, two 2-fold)
    #The first three axes have coprime rotation orders
    #And the rotations themselves take care of the modulus operation so no need to add it.
    #The second 2-fold rotation is equivalent to reversing the order
    #And is applied to the last 30 numbers as it is not coprime with the first 2-fold rotation.

    h['ABCD@GHIJKLMNEFPQRSO']  #rotate k times about 5-fold axis
    h['PFENOSRQHG@DCMLKJIAB']  #rotate k times about 3-fold axis
    h['GFPQHIA@DENOSRJKBCML']  #rotate k times about 2-fold axis
    k>29&&a.reverse!
    p a
  }
}

z=(1..20).map{|i|i} 
f[z,50]

Alternative Lösung 131 Bytes (Ungültig aufgrund des binären Random-Walk-Ansatzes, ergibt nur eine annähernd korrekte Verteilung.)

->a,n{(n*99).times{|i|s=['@DEFGHIABCMNOPQRJKLS','ABCD@GHIJKLMNEFPQRSO'][rand(2)] 
a=(0..19).map{|i|a[s[i].ord-64]}
i%99==98&&p(a)}}

Dies ist ein Scramble (ähnlich wie die Programme, die zum Scramble von Rubiks Cube verwendet werden.)

Die spezifischen Rotationen, die ich benutze, sind zwei der offensichtlichsten:

-Eine Drehung um 120 Grad (um die Flächen 1 und 20 gemäß dem ersten Diagramm)

-Eine 72-Grad-Drehung (um die Eckpunkte, die 1,2,3,4,5 und 16,17,18,19,20 gemäß dem ersten Diagramm gemeinsam haben.)

Wir werfen 99 Mal eine Münze und führen jedes Mal eine dieser beiden Umdrehungen durch, je nachdem, ob es sich um Kopf oder Zahl handelt.

Beachten Sie, dass ein Wechsel dieser deterministisch zu ziemlich kurzen Sequenzen führt. Beispielsweise kann mit den richtigen Rotationssensoren eine 180-Grad-Rotation mit einer Periode von nur 2 erzeugt werden.

Level River St
quelle
Es scheint, als würde das Werfen einer Münze zum Auswählen einer Operation einer Binomialverteilung näher kommen als einer Gleichverteilung.
Sparr
@Sparr das wäre der Fall, wenn der Zustandsraum größer wäre als der Random Walk. In diesem Fall kann eine zufällige Wanderung mit nur 6 Schritten bis zu 2 ^ 6 = 64 Möglichkeiten eröffnen (ich habe sie nicht gezählt), und unser Zustandsraum beträgt nur 60. Nach 99 Schritten (2 ^ 99 verschiedene Pfade) Alles sollte mindestens so gleichmäßig verteilt sein wie eine einzelne Stichprobe des PRNG, mit dem die Zahlen generiert wurden.
Level River St
@ MartinBüttner Danke für die Tipps, ich habe die angewendet, die funktionieren. b.mapfunktioniert nicht direkt, ich muss b.chars.mapes funktionieren lassen (BTW, das auf meinem Computer nicht funktioniert, da ich Ruby 1.9.3 habe, aber es funktioniert auf Ideone.) Es ist eine faire Einsparung. Ich glaube nicht, dass das Ändern der magischen Zeichenfolgen für nicht druckbare Zeichen -64funktioniert , um den Willen zu retten : %w{}Interpretationen \n(sowie Leerzeichen) als Trennzeichen zwischen den generierten Zeichenfolgen im Array. Ich habe keine Ahnung, was es mit anderen nicht druckbaren ASCII-Zeichen tun wird.
Level River St
@Martin das war schwieriger als ich erwartet hatte - zuerst war ich verblüfft, als mein Code nicht richtig funktionierte, dann machte ich eine Pause und erkannte plötzlich, dass die 2-fache und die 3-fache Symmetrie die gleiche gegenseitige Beziehung haben mussten wie auf einem Tetraeder (ich musste die dreieckige Fläche, um die ich mich drehte, durch eine andere dreieckige Fläche ersetzen.)
Level River St
1
Herzlichen Glückwunsch zum ersten Benutzer mit dem neu freigeschalteten Geometrieausweis . :)
Martin Ender
2

IA-32 Maschinencode, 118 Bytes

Hexdump:

60 33 c0 51 8b 74 24 28 8b fa 6a 05 59 f3 a5 e8
21 00 00 00 20 c4 61 cd 6a 33 00 84 80 ad a8 33
32 00 46 20 44 8e 48 61 2d 2c 33 32 4a 00 21 20
a7 a2 90 8c 00 5b b1 04 51 0f c7 f1 83 e1 1f 49
7e f7 51 8b f2 56 8d 7c 24 e0 b1 14 f3 a4 5f 8b
f3 ac 8b ee d4 20 86 cc e3 0a 56 8d 74 04 e0 f3
a4 5e eb ed 59 e2 db 8b dd 59 e2 cc 59 83 c2 14
e2 91 61 c2 04 00

Es ist ein bisschen lang, deshalb gehen einige Erklärungen zuerst. Früher habe ich fast den gleichen Algorithmus wie die vorhandenen Antwort von Stufe River St . Um meine Antwort zu ändern, habe ich andere grundlegende Permutationen verwendet, die nicht unbedingt eine intuitive geometrische Bedeutung haben, aber irgendwie bequemer sind.

Der Code muss grundsätzlich eine Permutation generieren, die eine sequentielle Anwendung der folgenden ist:

  1. Eine Permutation der Ordnung 3, die ich nenne p3, hat 0 ... 2 mal angewendet
  2. Eine Permutation der Ordnung 2, die ich nenne q2, hat 0 oder 1 Mal angewendet
  3. Eine Permutation der Ordnung 5, die ich nenne p5, hat 0 ... 4 mal angewendet
  4. Eine andere Permutation der Ordnung 2, die ich nenne p2, hat 0 oder 1 Mal angewendet

Für diese Permutationen gibt es viele Möglichkeiten. Einer von ihnen ist wie folgt:

p3 = [0   4   5   6   7   8   9   1   2   3  13  14  15  16  17  18  10  11  12  19]
q2 = [4   5   6   7   0   1   2   3  13  14  15  16  17   8   9  10  11  12  19  18]
p5 = [6   7   0   4   5  14  15  16  17   8   9   1   2   3  13  12  19  18  10  11]
p2 = [1   0   7   8   9  10  11   2   3   4   5   6  16  17  18  19  12  13  14  15]

Diese Wahl ist besser als andere, da die Permutationen hier lange Reihen von sequentiellen Indizes aufweisen, die durch Lauflängencodierung komprimiert werden können - nur 29 Bytes für die 4 Permutationen.

Um die Erzeugung von Zufallszahlen zu vereinfachen, habe ich für alle die Potenzen (wie oft jede Permutation angewendet wird) im Bereich von 1 ... 30 gewählt. Dies führt zu viel zusätzlicher Arbeit im Code, da z. B. p3jedes Mal eine Identitätspermutation entsteht, wenn sie dreimal mit sich selbst multipliziert wird. Auf diese Weise ist der Code jedoch kleiner. Solange der Bereich durch 30 teilbar ist, wird die Ausgabe gleichmäßig verteilt.

Außerdem sollten die Leistungen positiv sein, damit die Lauflängendecodierungsoperation mindestens einmal ausgeführt wird.

Der Code hat 4 verschachtelte Schleifen; Die Gliederung ist wie folgt:

void doit(int n, uint8_t* output, const uint8_t input[20])
{    
    uint8_t temp[20];

    n_loop: for i_n = 0 ... n
    {
        memcpy(output, input, 20);
        expr_loop: for i_expr = 0 ... 3
        {
            power = rand(1 ... 30);
            power_loop: for i_power = 0 ... power
            {
                memcpy(temp, output, 20);
                output_index = 0;
                perm_loop: do while length > 0
                {
                    index = ...; // decode it
                    length = ...; // decode it
                    memcpy(output + output_index, temp + index, length);
                    output_index += length;
                }
            }
        }
        output += 20;
    }
}

Ich hoffe, dieser Pseudocode ist klarer als der folgende Inline-Assembler-Code.

_declspec(naked) void __fastcall doit(int n, uint8_t* output, const uint8_t* input)
{
    _asm {
        pushad
        xor eax, eax

        n_loop:
            push ecx

            ; copy from input to output
            mov esi, [esp + 0x28]
            mov edi, edx
            push 5
            pop ecx
            rep movsd

            call end_of_data
#define rl(index, length) _emit(length * 32 + index)
            rl(0, 1)
            rl(4, 6)
            rl(1, 3)
            rl(13, 6)
            rl(10, 3)
            rl(19, 1)
            _emit(0)

            rl(4, 4)
            rl(0, 4)
            rl(13, 5)
            rl(8, 5)
            rl(19, 1)
            rl(18, 1)
            _emit(0)

            rl(6, 2)
            rl(0, 1)
            rl(4, 2)
            rl(14, 4)
            rl(8, 2)
            rl(1, 3)
            rl(13, 1)
            rl(12, 1)
            rl(19, 1)
            rl(18, 1)
            rl(10, 2)
            _emit(0)

            rl(1, 1)
            rl(0, 1)
            rl(7, 5)
            rl(2, 5)
            rl(16, 4)
            rl(12, 4)
            _emit(0)

            end_of_data:
            pop ebx ; load the address of the encoded data
            mov cl, 4

            expr_loop:
                push ecx

                make_rand:
                rdrand ecx
                and ecx, 31
                dec ecx
                jle make_rand

                ; input: ebx => encoding of permutation
                ; output: ebp => encoding of next permutation
                power_loop:
                    push ecx

                    ; copy from output to temp
                    mov esi, edx
                    push esi
                    lea edi, [esp - 0x20]
                    mov cl, 20
                    rep movsb
                    pop edi

                    ; ebx => encoding of permutation
                    ; edi => output
                    mov esi, ebx
                    perm_loop:
                        ; read a run-length
                        lodsb
                        mov ebp, esi

                        _emit(0xd4)             ; divide by 32, that is, split into
                        _emit(32)               ; index (al) and length (ah)
                        xchg cl, ah             ; set ecx = length; also makes eax = al
                        jecxz perm_loop_done    ; zero length => done decoding
                        push esi
                        lea esi, [esp + eax - 0x20]
                        rep movsb
                        pop esi
                        jmp perm_loop

                    perm_loop_done:
                    pop ecx
                    loop power_loop

                mov ebx, ebp
                pop ecx
                loop expr_loop

            pop ecx
            add edx, 20
            loop n_loop

        popad
        ret 4
    }
}

Einige unterhaltsame Implementierungsdetails:

  • Ich habe eingerückte Assembler verwendet, wie in Hochsprachen. sonst wäre der Code ein unverständliches Durcheinander
  • Ich verwende callund greife anschließend popauf Daten (codierte Permutationen) zu, die im Code gespeichert sind
  • Mit dem jecxzBefehl kann ich bequemerweise ein Null-Byte als Abschluss für den Lauflängendecodierungsprozess verwenden
  • Glücklicherweise ist die Zahl 30 (2 * 3 * 5) fast eine Zweierpotenz. Dadurch kann ich mithilfe eines Kurzcodes eine Zahl im Bereich 1 ... 30 generieren:

            and ecx, 31
            dec ecx
            jle make_rand
    
  • Ich verwende einen "Allzweck-Divisions" -Befehl ( aam), um ein Byte in Bitfelder (3-Bit-Länge und 5-Bit-Index) zu trennen. Zum Glück an dieser Stelle im Code, cl = 0so profitiere ich von beiden "Seiten"xchg

anatolyg
quelle