11
\$\begingroup\$

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

5 Answers 5

6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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)
\$\endgroup\$
6
  • \$\begingroup\$ Have golfed it even further down to 151 if you're interested: pastebin.com/1pbwax6s \$\endgroup\$ Commented May 11, 2014 at 17:58
  • \$\begingroup\$ simple changes, but very effective. thanks! \$\endgroup\$
    – wrongu
    Commented May 11, 2014 at 18:10
  • \$\begingroup\$ I think you could cut it down even further by removing the l and v variables and changing the insert to a slice assignment. \$\endgroup\$ Commented May 11, 2014 at 21:32
  • \$\begingroup\$ I'm sure the golf could be shorter. Honestly I just expected comments on the first one if anything! \$\endgroup\$
    – wrongu
    Commented May 11, 2014 at 23:47
  • \$\begingroup\$ I wrote up an explanation anyway and updated the post :) \$\endgroup\$
    – wrongu
    Commented May 12, 2014 at 3:11
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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