Algorithmic braiding - for mother's day

Question

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 code-golf, so the shortest code wins!

Answer 1

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

Answer 2

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)

Answer 3

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.

Answer 4

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

Answer 5

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