Ich habe mich kürzlich über die Graphentheorie, insbesondere Hypercubes , informiert und über interessante Möglichkeiten nachgedacht, Pfade darauf zu konstruieren. Folgendes habe ich mir ausgedacht.

Wie Sie vielleicht wissen, können Sie einen n-dimensionalen Hyperwürfel konstruieren, indem Sie alle n-Tupel, die aus 1und 0als Eckpunkte bestehen, nehmen und verbinden, wenn sie sich in einer Ziffer unterscheiden. Wenn Sie diese Binärziffern als Ganzzahl interpretieren, erhalten Sie ein Diagramm mit gut nummerierten Eckpunkten. Zum Beispiel für n=3:

Angenommen, Sie möchten einen Spaziergang auf diesem Hyperwürfel machen und am Scheitelpunkt beginnen 0. Wie bestimmen Sie nun, welchen Scheitelpunkt Sie als Nächstes besuchen möchten? Die Regel, die ich mir ausgedacht habe, ist, die Nummer ades Scheitelpunkts, auf dem Sie sich befinden, zu nehmen, sein mod(a,n)s-Bit umzudrehen (nullbasierte Indizierung) und zum resultierenden Scheitelpunkt zu wechseln. Formal kann diese Regel rekursiv definiert werden als

a[m+1] = xor(a[m], 2^mod(a[m],n)).

Wenn Sie diese Regel befolgen, bleiben Sie immer auf dem Würfel und bewegen sich entlang der Kanten. Der resultierende Pfad sieht folgendermaßen aus

Wie Sie sehen können, werden Sie im Kreis gehen! Tatsächlich endet Ihr Pfad in allen Dimensionen und für alle Startpunkte in einer Schleife. Zum Beispiel für n=14und a[0]=0es sieht so aus

Für den begeisterten Ambler ist die Länge seiner geplanten Route eine wichtige Information. Ihre Aufgabe ist es also, eine Funktion oder ein Programm zu schreiben, das die Hypercube-Dimension und nden Startscheitelpunkt a[0]als Eingabe verwendet und die Anzahl der Scheitelpunkte in der resultierenden Schleife ausgibt.

Testfälle

n   a[0]   Output
-----------------
3   0      6
14  0      50
5   6      8
17  3      346

Regeln

• Standardlücken sind verboten
• Ausgabe / Eingabe kann in jedem geeigneten Format erfolgen
• Sie können davon ausgehen a[0], dass es sich um einen gültigen Scheitelpunkt handelt

Wertung

Der kürzeste Code in Bytes gewinnt.

Wenn Sie weitere Informationen zu diesem Thema haben, würde ich mich freuen zu hören!

Gelee, 9 Bytes

%⁴2*^µÐḶL

Nimmt zwei Befehlszeilenargumente.

%⁴2*^µÐḶL        A monadic link. Inputs: a_0. b also taken from command line.
%⁴2*^              Variadic link. Input: a
%⁴                   a modulo b. ⁴ is second input, b.
  2*                 Get 2 to that power
    ^                and bitwise xor with a.
     µ             Start a new, monadic link (input: a_0)
      ÐḶ             All elements of the cycle created when the preceding link
                     is applied repeatedly, starting with a_0.
        L            Length.

Probieren Sie es hier aus .

Haskell, 124

import Data.Bits
(y:z:w)%(x:s)|x==y||x==z=[i|(i,r)<-zip[1..]s,r==x]!!0|0<1=w%s
g n=(tail>>=(%)).iterate(\a->xor a$2^mod a n)

Dies findet den Kreis durch den Zwei-Zeiger-Algorithmus, der in unterschiedlichen Geschwindigkeiten herumläuft, und verwendet / missbraucht Haskells Ansatz für Listen stark (zum Beispiel sind die beiden Zeiger tatsächlich Listen).

gist die Funktion, die die Antwort berechnet. Geben Sie es nund dann a[0]und es wird die Nummer an Sie zurückgeben (beachten Sie, dass ndefiniert werden sollte, um vom Typ Intzu sein, um Typmehrdeutigkeiten zu vermeiden).

JavaScript (ES6), 69 Byte

(n,a)=>{g=m=>m^1<<m%n;for(c=1,b=a;(b=g(g(b)))!=(a=g(a));)c++;return c}

Gibt 18812 für (23, 10) zurück.

MATL , 38 37 28 Bytes

xi`vt0)2y1G\^Z~yywP=fn~]2M1$

Dies funktioniert in der aktuellen Version (15.0.0) der Sprache.

Probieren Sie es online aus !

Erläuterung

x       % take first input: n. Delete (gets copied into clipboard G)
i       % take second input: initial value of a
`       % do...while loop
  v     %   concatenate all stack contents vertically
  t0)   %   duplicate. Get last element of that array: current a
  2     %   push 2
  y     %   duplicate second-top element in stack: current a
  1G    %   push first input (n)
  \     %   a modulo n
  ^     %   2 raised to that
  Z~    %   xor of that with current a
  yy    %   duplicate top two elements in stack: array of old a's and new a
  w     %   swap: move array of old a's to top
  P     %   reverse that array. So first entry is most recent a (before current)
  =f    %   indices of old values that equal current value. There may be 0 or 1
  n~    %   is it empty?
]       % if so, continue with a new iteration
2M      % push array of indices. It contains exactly 1 index
1$      % set 1 input for implicit display function, so it only displays the index

Pyth, 22 17 Bytes

Lx^2%bQbl.uyNuyGE

Erläuterung:

Lx^2%bQbl.uyNuyGE     Implicit: Q=first line n. E=second line a[0].
Lx^2%bQb              y = lambda b: do one iteration
                      Then
             uyGE     Apply y until a previous result is found.
                      This makes sure we're in the cycle.
         .uyN         Then apply y again until a previous result is found.
                      Keep all intermediate values but not the repeat.
        l             Get the length; i.e. the length of the cycle.

Probieren Sie es hier aus .