Skip to content

Instantly share code, notes, and snippets.

@wrongu

wrongu/braid.md

Last active Aug 29, 2015
Embed
What would you like to do?
Braid Algorithm

This is an explanation of my answer to the code golf question "Algorithmic Braiding - for mother's day". The problem asks this:

Your task is to create a program that, when given a number of strands and number of iterations of a braid, will tell where each strand goes.

We'll call the number of strands N and the number of iterations I. Let's start by looking at some simple outputs. The classic example is 3 strands:

1 2 3
 \     iteration 1
2 1 3
   /   iteration 2
2 3 1
 \     iteration 3
3 2 1

That's interesting - after N iterations, we've exactly reversed the order! (This makes sense because we've now touched all N strands, and the pattern involves moving the outside to the middle, then slowly pushing them back out).

Next is a sanity check with N=5 and N=7. I've labelled each column with a letter to avoid confusing too many numbers.

A B C D E     A B C D E F G
1 2 3 4 5     1 2 3 4 5 6 7
2 3 1 4 5     2 3 4 1 5 6 7
2 3 5 1 4     2 3 4 7 1 5 6
3 5 2 1 4     3 4 7 2 1 5 6
3 5 4 2 1     3 4 7 6 2 1 5
5 4 3 2 1     4 7 6 3 2 1 5
5 4 1 3 2     4 7 6 5 3 2 1
4 1 5 3 2     7 6 5 4 3 2 1
4 1 2 5 3     7 6 5 1 4 3 2
1 2 4 5 3     6 5 1 7 4 3 2
1 2 3 4 5     6 5 1 2 7 4 3
              5 1 2 6 7 4 3
              5 1 2 3 6 7 4
              1 2 3 5 6 7 4
              1 2 3 4 5 6 7

Ok so we've at least confirmed that after 2*N iterations, the cycle will repeat. Sanity checked. But another very interesting pattern has appeared! Looking at each column (ignore the middle one for a minute), we see this pattern:

(N=3) 1 1 2 2 3 3 [repeat]
(N=5) 1 1 2 2 3 3 5 5 4 4 [repeat]
(N=7) 1 1 2 2 3 3 4 4 7 7 6 6 5 5 [repeat]
(N=?) 1 1 2 2 ... N/2+1 N/2+1 N N N-1 N-1 N-2 N-2 ... N/2+2 N/2+2

In other words, we count up to half of N (rounding up), then count down for the rest. The rest of this will work with just the N=5 example and make some extrapolations from there. Let's create an array P which holds these values, and a function f(p) which computes the value of P at index p:

f(p) = { p          if p <= N/2+1
       { N-p+N/2+1  otherwise
-or-
f(p) = { p          if p <= N/2+1
       { 3N/2-p+1   otherwise

P = [f(p) for p in range(1,N+1)] # P = [1 2 3 5 4]
P = reduce(lambda array, pair: array+pair, [[x,x] for x in p]) # duplicate each entry and append them all together
-or-
P = [f(p/2) for p in range(1,2*N+1)] # using integer division to get duplicates in one step

To summarize, up to now we've come up with a repeating pattern for all but the central column, which we will continue to ignore for a while longer. Given the array P, surely we can just index into it to find where each strand is at iteration i.

strand s after i iterations = P[(start(s) + i) % 2N]
where start(s) is the starting index into P of strand s

Now for start(s).. For this we'll try some ASCII visualizations. Here, I've labelled where each column A-E starts in the cycle:

   A     1     D
    1         4
      
 2               4
 
 2               5
B                 E
    3         5
         3
        C

That's actually not too bad. A B C E D uses the same ordering function as 1 2 3 5 4, so we'll just reuse that logic. Confusing, I know, but remember that A-E are just an alias for columns 1-5. Note that everything gets doubled since |P|=2N.

           { 2*s-1     if s <= N/2+1
start(s) = { 3N-2*s+2  otherwise

Awesome - we have an O(1) solution for each column except the middle one! So let's finally take a closer look at the middle:

(N=3) 2 1 3 [repeat]
(N=5) 3 1 5 2 4 [repeat]
(N=7) 4 1 7 2 6 3 5 [repeat]

Here's the cool part:

v           v           v           v           v           v
3 3 5 5 4 4 1 1 2 2 3 3 5 5 4 4 1 1 2 2 3 3 5 5 4 4 1 1 2 2 3 3 5 5 4 4

Those are extremely well spaced-out. In fact, they are 6 spaces apart when N=5 and 8 spaces apart when N=7. Pattern found!

since middle index is N/2+1..
middle(i) = P[start((N/2+1) + (N+1) * i) % 2N]

So that's pretty much it. I was inconsistent about zero-indexing and some other formatting, but hopefully you now get the general idea of how to compute the position of strands in a braid after some number of iterations. Go tell all your friends.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment