9
\$\begingroup\$

I recently read up on graph theory, especially hypercubes and thought about interesting ways to construct paths on them. Here's what I came up with.

As you might know, you can construct an n-dimensional hypercube by taking all n-tuples consisting of 1 and 0 as vertices and connect them, iff they differ in one digit. If you interpret these binary digits as an integer number, you end up with a graph with nicely numerated vertices. For example for n=3:

enter image description here

Let's say you want to take a walk on this hypercube and start at the vertex 0. Now, how do you determine which vertex you want to visit next? The rule I came up with is to take the number a of the vertex you are on, flip its mod(a,n)s bit (zero-based indexing) and go to the resulting vertex. Formally this rule can be recursively defined as

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

By following this rule, you will always stay on the cube and travel along the edges. The resulting path looks like this

enter image description here

As you can see, you will walk in a circle! In fact, in all dimensions and for all starting points your path will end up in a loop. For example for n=14 and a[0]=0 it looks like this

enter image description here

For the avid ambler, the length of his planned route is quite a crucial information. So, your job is to write a function or a program that takes the hypercube dimension n an the starting vertex a[0] as inputs and output the number of vertices in the resulting loop.

Test cases

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

Rules

  • Standard loopholes are forbidden
  • Output/Input may be in any suitable format
  • You may assume a[0] to be a valid vertex

Scoring

Shortest code in bytes wins.

If you have any additional information on this topic, I'd be glad to hear!

\$\endgroup\$
  • \$\begingroup\$ Given the rule a[m+1] = xor(a[m], 2^mod(a[m],n)), it's irrelevant if the vertices belong to a hypercube, right? \$\endgroup\$ – Luis Mendo Mar 19 '16 at 16:21
  • \$\begingroup\$ Right. If a[m] was on the hypercube, a[m+1] will be too. And as you can assume a[0] to be a valid vertex, you pretty much don't need to care about any hypercube stuff and just follow the rule. \$\endgroup\$ – murphy Mar 19 '16 at 16:27
  • 1
    \$\begingroup\$ Where are the hyper ants? \$\endgroup\$ – Bassdrop Cumberwubwubwub Mar 21 '16 at 10:35
4
\$\begingroup\$

Jelly, 9 bytes

%⁴2*^µÐḶL

Takes two command-line arguments.

%⁴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.

Try it here.

\$\endgroup\$
2
\$\begingroup\$

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)

This finds the circle by the two-pointers-going-around-in-different-speeds algorithm, and heavily uses/abuses Haskell's approach to lists (for example, the two pointers are actually lists).

g is the function that computes the answer. give it n and then a[0] and it will return the number to you (note that n should be defined to be of type Int to avoid type ambiguity).

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 69 bytes

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

Returns 18812 for (23, 10).

\$\endgroup\$
1
\$\begingroup\$

MATL, 38 37 28 bytes

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

This works in current version(15.0.0) of the language.

Try it online!

Explanation

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
\$\endgroup\$
  • \$\begingroup\$ @lirtosiast True! Thanks. Edited \$\endgroup\$ – Luis Mendo Mar 20 '16 at 22:49
1
\$\begingroup\$

Pyth, 22 17 bytes

Lx^2%bQbl.uyNuyGE

Explanation:

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.

Try it here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.