Algorithmic braiding - for mother's day

Task:

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. Rules are as follows:

• The number of strands will always be odd, and between 3 and 6000 (inclusive)
• When you start, the strands will be divided into 2 (almost) equal bunches, the `left` and the `right`. The `left` will have one more strand when you start.

For an input of 7:

``````/ / / / \ \ \
1 2 3 4 5 6 7
``````
• Every iteration, the outermost strand of the side with more strands will be put in the center facing the opposite direction. The center is defined as between opposite facing strands: `////middle\\\`.

1 iteration of input 7 (strand 1 was moved to the center):

``````/ / / \ \ \ \
2 3 4 1 5 6 7
``````

Example:

Input:

``````3 4
``````

Computations:

``````1 2 3
\
2 1 3
/
2 3 1
\
3 2 1
/
3 1 2
``````

Output:

``````3 1 2
``````

Rules:

• You do not need to display the slashes for strand direction, only the numbers.
• You only need to display the numbers after the last iteration.
• Your output will be space-deliminated ids of the strands
• Input will be in the form: `strands [space] iterations`
• The number of strands will always be odd, and 3<=x<=6000
• This is , so the shortest code wins!
-
Would it not be 3 to 5999 as 6000 is not odd so you will not have 'up to 6000'? – kitcar2000 May 11 '14 at 15:19
so the output for `11 2` would be `2345611178910`? – Martin Ender May 11 '14 at 15:24
@Howard Your submission broke my change – TheDoctor May 11 '14 at 15:57
@TheDoctor My answer was there before your change. – Howard May 11 '14 at 16:01
I think your example should read `123 -> 213 -> 231 -> 321 -> 312`. – Howard May 11 '14 at 16:05

5 Answers

GolfScript, 33 characters

``````~\),(@{:^1\$[=]:y-.,2//y*^~}*;' '*
``````

The input must be provided on stdin.

Examples (you may test online):

``````> 7 1
2 3 4 1 5 6 7

> 3 4
3 1 2

> 11 2
2 3 4 5 6 11 1 7 8 9 10
``````
-

Python: 179 240, 152 characters

First, the 179

For `N` strands and `i` iterations, this answer uses `O(1)` space and `O(N)` time. I simply compute the end position of each strand, never iterating over the intermediate positions!

big edit: golfed this answer by changing conditionals to boolean algebra. I also wrote a lengthy explanation of how it works. TL;DR: formulaic patterns, modulo division.

``````from sys import *
N,i=map(int,stdin.readline().split())
h,t=N/2,3*N
f=lambda p:(p>N)*(t/2-(p&-2))+p/2+1
for s in xrange(N):print f((2*s+1+(s>h)*(t-4*s-2)+i*(N+1-N*(s!=h)))%(2*N)),
``````

Now the 152

This is more reasonably golfed python. (edit: thanks to Alex Thornton for editing from 165 to 152)

``````from sys import*;l=map;r=range;n,m=l(int,stdin.readline().split());b=r(1,n+1)
for k in r(m):v=b.pop((0,n-1)[k%2]);b.insert(n/2,v)
print' '.join(l(str,b)
``````
-
Have golfed it even further down to 151 if you're interested: pastebin.com/1pbwax6s – Alex Thornton May 11 '14 at 17:58
simple changes, but very effective. thanks! – rangu May 11 '14 at 18:10
I think you could cut it down even further by removing the `l` and `v` variables and changing the `insert` to a slice assignment. – user2357112 May 11 '14 at 21:32
I'm sure the golf could be shorter. Honestly I just expected comments on the first one if anything! – rangu May 11 '14 at 23:47
I wrote up an explanation anyway and updated the post :) – rangu May 12 '14 at 3:11

Python 2 (109) / Python 3 (121)

Python 2

``````s,n=map(int,raw_input().split())
b=range(s)
for i in range(n):b[s/2:s/2]=[b.pop(0-i%2)]
for x in b:print x+1,
``````

Python 3

``````s,n=map(int,input().split())
b=list(range(s))
for i in range(n):b[s//2:s//2]=[b.pop(0-i%2)]
for x in b:print(x+1,end=' ')
``````

The code must have been bribed by Python 2 to showcase its golfing advantages over Python 3: ranges being lists, division rounding down to an int, print not starting a newline. The weird `0-i%2` is because `-i%2` evaluates as `(-i)%2`.

There's probably a more efficient approach than iterating, namely computing each final result directly. The braiding operation has period 2*s, so it can't be that complicated.

-

Ruby, 105

Just a lot of set manipulation. Push, pop, reverse and shift! I tried not converting inputs to integers, but it added about 20 characters.

``````n,i=\$*.map(&:to_i)
f=l=(1..n).to_a
t=r=l.pop(n/2).reverse
i.times{f,t=t<<f.shift,f}
\$><<(l+r.reverse)*' '
``````

`l` and `r` (`left` and `right`) are the "thread" queues. `right` is reversed so we start pulling from the outside.

`t` and `f` (`to` and `from`) start off as `right` and `left`, respectively, but as we go we keep swapping them so we can always shift the last "thread" from `from` and push it to `to` (`f,t=t<<f.shift,f`). This saves a LOT of space.

Then we just re-reverse `right` at the end.

Changelog:

2.2 105 oh yeah, map can take a proc

2.1 108 And actually, just flip things as part of manipulation.

2.0 116 don't use that temporary array. Instead use two pointer variables we can manipulate and keep re-pointing. Then only display the end

1.0 123 initial idea

-

Java, 270 chars

golfed:

``````import java.util.*;class B{public static void main(String[] a){int n=Integer.valueOf(a[0]),t=Integer.valueOf(a[1]),i=0;List<Integer> r=new ArrayList<Integer>();for(;i<n;i++){r.add(i+1);}for(i=0;i<t;i++){int k=i%2==0?0:n-1;r.add(n/2,r.remove(k));}System.out.println(r);}}
``````

un-golfed:

``````import java.util.*;
public class Braid {
public static void main(String[] args) {
int num = Integer.valueOf(args[0]);
int iterations = Integer.valueOf(args[1]);

//populate array
List<Integer> arr = new ArrayList<Integer>();
for (int i=0; i < num; i++) {
arr.add(i+1);
}
for (int i=0; i < iterations; i++) {
int index = i%2==0?0:num-1;
arr.add(num/2, arr.remove(index));
}
System.out.println(arr);
}
}
``````

Run online

-