Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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!
share|improve this question
3  
Would it not be 3 to 5999 as 6000 is not odd so you will not have 'up to 6000'? –  kitcar2000 May 11 at 15:19
    
so the output for 11 2 would be 2345611178910? –  Martin Büttner May 11 at 15:24
1  
@Howard Your submission broke my change –  TheDoctor May 11 at 15:57
1  
@TheDoctor My answer was there before your change. –  Howard May 11 at 16:01
1  
I think your example should read 123 -> 213 -> 231 -> 321 -> 312. –  Howard May 11 at 16:05

5 Answers 5

up vote 7 down vote accepted

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
share|improve this answer

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)
share|improve this answer
    
Have golfed it even further down to 151 if you're interested: pastebin.com/1pbwax6s –  Alex Thornton May 11 at 17:58
    
simple changes, but very effective. thanks! –  rangu May 11 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 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 at 23:47
    
I wrote up an explanation anyway and updated the post :) –  rangu May 12 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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.