Electrons bouncing in a wire

Question

Imagine a "wire" that has n spaces. Imagine further that there are "electrons" in that wire. These electrons only live for one unit of time. Any spaces in the wire that are adjacent to exactly one electron become an electron. In Game of Life terminology, this is B1/S.

For example, this is a wire of length 10, with period 62.

Rules

• Input, n, is a single, positive integer.
• Output must be a single integer denoting the period of a wire of length n.
• The starting state is a single electron at one end of the wire.
• The period does not necessarily include the starting state. Some lengths never return to the starting state, but all of them are periodic.
• A static wire (i.e., one without electrons) has period 1.
• Boundary conditions are not periodic. That is, the wire is not toroidal in any way.

Test cases

Special thanks to orlp for producing this list. (I have verified it up to n=27.)

1 1
2 2
3 1
4 6
5 4
6 14
7 1
8 14
9 12
10 62
11 8
12 126
13 28
14 30
15 1
16 30
17 28
18 1022
19 24
20 126
21 124
22 4094
23 16
24 2046
25 252
26 1022
27 56
28 32766
29 60
30 62
31 1
32 62
33 60
34 8190
35 56
36 174762
37 2044
38 8190
39 48
40 2046
41 252
42 254
43 248
44 8190
45 8188

You can see test cases for n=2 through 21 here with my Game-of-Life-esque simulator: Variations of Life.

---

EDIT: the sequence here has been published as A268754!

Answer 1

Python 2, 148 142 87 bytes

n=input()
p=l=1
t=1
h=2
while t!=h:
 if p==l:t,l,p=h,0,p*2
 h=h/2^h*2%2**n;l+=1
print l

Uses Brent's cycle detection algorithm, and thus actually runs fast.

---

I have also written an animation in Python (both 2 & 3 work). It needs pyglet to run. You can view the animation by running:

python -m pip install --user pyglet
curl -s https://gist.githubusercontent.com/orlp/f32d158130259cbae0b0/raw/ | python

(Feel free to download the gist and inspect the code before running.) You can press the + and - keys to increase/decrease the n being visualized.

---

And finally, for those interested in exploring this number sequence further, here is a readable version (this was used to generate the test cases above):

# Brent's cycle detection, modified from wikipedia.
def electron_period(n):
    wire_mask = (1 << n) - 1
    power = lam = 1
    tortoise, hare = 1, 2
    while tortoise != hare:
        if power == lam:
            tortoise = hare
            power *= 2
            lam = 0
        hare = ((hare << 1) ^ (hare >> 1)) & wire_mask
        lam += 1
    return lam

Answer 2

Mathematica, 127 bytes

p@n_:=Tr[#2-#]&@@Position[#,Last@#]&@NestWhileList[1~Table~n~ArrayPad~1*18~CellularAutomaton~#&,{1}~ArrayPad~{1,n},Unequal,All]

---

Explanation

Rule 18:

{0,0,0} -> 0
{0,0,1} -> 1
{0,1,0} -> 0
{0,1,1} -> 0
{1,0,0} -> 1
{1,0,1} -> 0
{1,1,0} -> 0
{1,1,1} -> 0

---

Test cases

p/@Range[10]
(* {1,2,1,6,4,14,1,14,12,62} *)

Answer 3

Python 2, 68 bytes

f=lambda n,k=1,l=[]:k in l and-~l.index(k)or f(n,k/2^k*2%2**n,[k]+l)

The cycle detection could be better, but the iterative step is nice.

k -> k/2^k*2%2**n

By representing the array as a binary number k, the update can be done by taking the XOR of k shifted one left with /2 and one right with *2, then truncating to n bytes as %2**n.

Answer 4

Pyth, 39 36 bytes

L++Zmx@[e-mail].[,Z1ZQ)xJyeJ

Uses the "cumulative fixed-point" function to iterate until just before a configuration recurs, and returns all intermediate configurations as a list of lists. This works because the rules are deterministic and the configuration of the next generation is a function of the current configuration. This means that once the same configuration appears again the automata have completed a cycle.

After reaching that (the last iteration of the cycle), it calls the next-gen function one last time on the last element of the "history" list, to obtain the next configuration (which is the starting configuration of a cycle), and find its index in the history. Now the period is simply the length ( 1 + index of cycle end) minus the index of cycle commencement.

In pythonic pseudocode:

                  Z = 0
                  Q = eval(input())
L                 def y(b):                # generates next-gen from current(param)
  ++Zm                return [Z] + map(    # adds head zero padding
    x@bd@bhhd             lambda d: b[d] ^ b[1+ 1+ d],  # xor the states of adjacent cells
    Q                     range(Q))        # implicit range in map
    Z                     + [Z]            # adds end zero padding
-lJ.uyN.[,Z1ZQ)   J = repeatTilRecur(lambda N,Y:y(N), padRight([Z,1],Z,Q)); print( len(J) -
                  # N:value; Y:iteration count
  JxJyeJ              J.index( y( J[-1] ) ) )

The test suite takes too much time that the server will kill it, so you'll need to use the regular program and test it one by one, or install Pyth (if you haven't) and use a script to test it.

Answer 5

Python 3 2, 134 121 118 bytes

Q=input()
h=[]
n=[0,1]+Q*[0]
while n not in h:h+=[n];n=[0]+[n[d]^n[d+2] for d in range(Q)]+[0]
print len(h)-h.index(n)

Basically the same as my Pyth answer, but adapted it somewhat because of lack of certain built-in functions in Python.

Ungolfed version:

length = input()
history = []
new = [0] + [1] + length*[0]
while new not in history:
    history += [new]
    new = [0] + [new[cell]^new[cell+2] for cell in range(length)] + [0]
print len(history) - history.index(new)

Answer 6

Jelly, 19 18 17 bytes

H^Ḥ%®
2*©Ç‘СUµiḢ

This code computes the first 2ⁿ states, so it's not particularly fast or memory efficient...

Try it online! or verify the first 16 test cases.

Alternate version, 13 bytes (non-competing)

Versions of Jelly that postdate this challenge have built-in loop detection, enabling a solution that is both shorter and more efficient.

H^Ḥ%®
2*©ÇÐḶL

This handles the last test case with ease. Try it online!

How it works

2*©Ç‘СUµiḢ    Main link. Input: n (integer)

2*             Compute 2 ** n.
  ©            Store the result in the register.
     С        Do the following:
   Ç             Apply the helper link, which updates the state, ...
    ‘            2 ** n + 1 times.
               Collect all 2 ** n + 2 intermediate results in a list.
       U       Upend; reverse the list of results.

        µ      Begin a new, monadic chain. Argument: R (list of results)
          Ḣ    Yield and remove the first element of R (final state).
         i     Find its first index in the remainder or R.
               This is the length of the loop.

H^Ḥ%®        Helper link. Argument: s (state, integer)

H            Halve s. This yields a float, but ^ will cast to integer.
  Ḥ          Double s.
 ^           Compute (s ÷ 2) ^ (s × 2).
    ®        Retrieve the value stored in the register (2 ** n).
   %         Compute ((s ÷ 2) ^ (s × 2)) % (2 ** n).

Note that the helper link is applied to 2ⁿ in the first iteration, which does not encode a valid state. However, ((2ⁿ ÷ 2) ^ (2ⁿ × 2)) % 2ⁿ = (2^{n - 1} + 2^{n + 1}) % 2ⁿ = 2^{n - 1}, which is one of the possible starting states.

Since we loop 2ⁿ + 1 times, we are guaranteed to encounter a state twice, making the loop detection successful.

Answer 7

CJam, 41 34 31 27 25 bytes

Thanks to Dennis for saving 3 bytes. Borrowing an idea from his Jelly answer saved another 4.

2ri#_){__4*^2/W$%}*]W%(#)

Test it here.

Explanation

I'm representing the wire simply as an integer (whose bits indicate the positions of the electrons) instead of using an actual list of bits. The state is the updated via fairly simple bitwise computations.

To find the period we collect all intermediate results on the stack, run the simulation for 2^n-1+1 steps, and then determine the period as the number of elements since the last occurrence of the final state(plus 1).

Here's a breakdown of the code:

2ri#   e# Compute 2^n. This has a 1 in the n+1-th bit and zeroes below it. This is
       e# itself not a valid state but will be turned into 2^(n-1) by the first
       e# update.
_)     e# Duplicate and increment to get number of steps to simulate.
{      e# Repeat that many times...
  __   e#   Duplicate the last state twice.
  4*   e#   Multiply by 4, shifting all bits to the left by two positions.
  ^    e#   XOR - we only keep keep those cells where we have exactly one 1-bit
       e#   between both copies, i.e. those that neighboured a single electron
       e#   but shifted up by one position. We don't need handle the survival rule
       e#   explicitly, since electrons can never be adjacent in the first place.
  2/   e#   Divide by 2 shifting all bits back to the right again.
  W$   e#   Copy the initial number 2^n.
  %    e#   Modulo - this simply sets the first bit to 0.
}*
]      e# Wrap all states in an array.
W%     e# Reverse it.
(      e# Pull off the latest state.
#      e# Find its position in the remainder of the array.
)      e# Increment.

Answer 8

MATL, 38 37 36 35 bytes

1Oi(`t0Y)5BX+8L)1=vt6#Xut0)=fdt?w}A

This uses a loop that keeps computing new states until the new state equals any of the preceding ones. Each state is a vector of zeros and ones. These vectors are stored as rows of a growing 2D array.

Computation of each new state is done by convolving the current state with the sequence [1,0,1], keeping only the central part, and setting to 0 any entry that is not 1.

EDIT (May 13, 2016) The code in the following link has been slightly modified in accordance with changes introduced in the language after this answer was written

Try it online!

1Oi(            % create initial vector [1,0,0,...,0], with size equal to input
`               % do...while loop
  t0Y)          %   duplicate. Get last row of array: most recent vector
  5BX+8L)       %   compute new vector by convolving the most recent one
                %   with [1,0,1] and keeping only the central part
  1=            %   set ones to 1, rest to 0
  v             %   append to 2D array
  t6#Xu         %   compute vector of unique numeric labels, so that equal rows
  t0)=f         %   indices of entries whose value equals that of the last entry.
                %   This will contain the index of the last entry and possibly
                %   another index, in which case we've found a repetition
  d             %   this will either be empty (which is falsy) or contain the
                %   period, which is a nonzero number (and thus truthy)
  t?            %   duplicate. If non-empty (and nonzero)
    w           %     swap to put the 2D-array at the top of the stack. This is
                %     falsy, because it contains at least one zero, even in the
                %     n=1 case (the array is initiallized to 0 in that case)
                %     So the loop will terminate, with the period left on the stack
  }             %   else
    A           %     this transforms the empty array at the top of the stack
                %     into a true value, so that the loop will continue
                %   implicitly end if
                % implicitly end loop
                % implicitly display stack contents (period)

Answer 9

JavaScript (ES6) 99 104

n=>eval("a=[...Array(n)];k={};for(a[0]=i=1;!k[a=a.map((v,i)=>v?0:a[i-1]^a[i+1])];k[a]=i++);i-k[a]")

Test

f = n=>eval("a=[...Array(n)];k={};for(a[0]=i=1;!k[a=a.map((v,i)=>v?0:a[i-1]^a[i+1])];k[a]=i++);i-k[a]")

console.log = x => O.textContent += x + '\n';

;[...Array(45)].map((_, i) => console.log(++i + ' ' + f(i)))

<pre id=O></pre>

Answer 10

Haskell, 170 bytes

x!p gives the element at index p if in bounds, else 0. n calculates the next step. g i gives the ith step. c x gives the period, if starting with x. f wraps it all together.

n x|l<-length x-1=[mod(x!(p-1)+x!(p+1))2|p<-[0..l],let y!q|q<0=0|q>=l=0|1<2=y!!p]
c x=[i-j|i<-[1..],j<-[0..i-1],let g k=iterate n x!!k,g i==g j]!!0
f n=c$1:map(*0)[2..n]

(Note: posted from phone that has the hugs interpreter, which is not full featured, so might have typos.)

Answer 11

Perl 6, 81 bytes

{my@h=my$w=2;@h.push($w=$w/2+^$w*2%2**$_)while 2>@h.grep($w);[R-] @h.grep($w,:k)}

Expanded and ungolfed a bit

-> $n {
    my @history = my $wire = 2;
    while 2 > @history.grep($wire) {
        @history.push($wire = $wire/2 +^ $wire*2 % 2**$n)
    }
    [R-] @history.grep($wire,:k)
}

A bit of explanation:

• [op] reduces the list using op. For example [+] @list will sum @list
• R is a meta-op that reverses the arguments given to an op. For example 1 R- 3 will result in 2.

Answer 12

C++, 211 bytes

Golfed

#include <bitset>
#include <cstdio>
#define B std::bitset<1<<10>
B m,t(1),h(2);int main() {int p,l;for(scanf("%d",&p);p--;m.set(p));
for(p=l=1;t!=h;h=(h>>1^h<<1)&m,l++)p==l?t=h,p*=2,l=0:0;return !printf("%d",l);}

With added whitespace for readability

#include <bitset>
#include <cstdio>
#define B std::bitset<1<<10>
B m,t(1),h(2);
int main() {    
    int p,l;
    for(scanf("%d",&p);p--;m.set(p));
    for(p=l=1;t!=h;h=(h>>1^h<<1)&m,l++)p==l?t=h,p*=2,l=0:0;    
    return !printf("%d",l);
}

Good practice for C++'s bitset; and a great education learning about Brent's cycle detection algorithm (as used by @orlp)

Answer 13

Pyth, 95 bytes

J.[ZQ[1)K_1=bYW<K0=NY aN?hJZ?htJ1ZFTr1tlJ aN?@JTZ?x@JhT@JtT1Z) aN?eJZ?@J_2 1Z=JN=KxbJ abJ;-tlbK

You can try it out here.

Answer 14

Pyth, 29 bytes

J^2QL%x/b2*b2JK.uyN1;-lKxKyeK

• Try it online!
• Test suite

Uses the algorithm a(n+1) = ((a(n) << 1)^(a(n) >> 1)) % (2 ** N).

Answer 15

Ruby, 72 bytes

Anonymous function.

->n{s=[w=1];c=p
(j=s.index w=w*2%2**n^w/2
j ?c=s.size-j:s<<w)while !c
c}