{{ message }}

Instantly share code, notes, and snippets.

# wrongu/braid.md

Last active Aug 29, 2015
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.