23
\$\begingroup\$

Braid Description

In this braid, when a strand crosses over the top of another strand it adds the other strand's value to itself and all other strand values pass through. The braid has three strands and each strand begins at 1. The first crossover is the leftmost strand crossing over the middle strand. The next crossover is the rightmost strand crossing over the new middle strand (previously the leftmost strand). These two steps of crossovers repeat. In other words, the first crossover is [a, b, c] -> [b, a+b, c] and the second is [a, b, c] -> [a, b+c, b]. Using these rules here are the first six levels of the braid:

1,1,1
1,2,1
1,3,2
3,4,2
3,6,4
6,9,4

Your task

Write a golfed program or function that accepts an integer as the braid level and outputs the three values for that level of the braid. You must indicate if your levels are zero- or one-based. Input and output may come in any reasonable format and trailing white space is allowed.

Test Cases (1-based)

1 -> 1,1,1

2 -> 1,2,1

5 -> 3,6,4

10 -> 28,41,19
Improve this question
\$\endgroup\$
1

16 Answers 16

Reset to default
7
\$\begingroup\$

MATL, 18 17 16 bytes

7Bi:"2:4PB@EX!Y*

Input is 0-based.

Try it online! Or verify all test cases.

Explanation

Given a row vector [a b c], the next vector is obtained post-matrix-multiplying it by either

[1 0 0;
 0 1 1;
 0 1 0]

or

[0 1 0;
 1 1 0;
 0 0 1]

depending on whether the iteration index is odd or even. For example, the matrix product [1 3 2]*[0 1 0; 1 1 0; 0 0 1] gives [3 4 2]. Then [3,4,2]*[1 0 0; 0 1 1; 0 1 0] gives [3 6 4], and so on.

Note also that the second matrix equals the first rotated 180 degrees, which can be exploited to save a few bytes.

7        % Push 7
B        % Convert to binary. Gives [1 1 1]. This is the initial level
i        % Take input n
:        % Push range [1 2 ... n]
"        % For each
  5      %   Push 5
  I:     %   Push range [1 2 3]
  -      %   Subtract, element-wise: gives [4 3 2]
  B      %   Convert to binary. This gives the matrix [1 0 0; 0 1 1; 0 1 0]
  @      %   Push current iteration index
  E      %   Multiply by 2. Gives 2 in the firt iteration, 4 in the second etc
  X!     %   Rotate matrix 90 degrees either 2 or 0 times
  Y*     %   Matrix multiply
         % End. Implicitly display
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Have you considered pairing the steps? That way you have one matrix [[0, 1, 0], [1, 1, 1], [1, 1, 0]] and the different starting positions are quite similar for even and odd n \$\endgroup\$
    – Peter Taylor
    Commented Dec 22, 2016 at 8:33
  • \$\begingroup\$ @PeterTaylor Thanks for the idea. In this case varying the initial vector and dividing the input by 2 seems to be more byte-costly \$\endgroup\$
    – Luis Mendo
    Commented Dec 22, 2016 at 10:49
5
\$\begingroup\$

Haskell, 51 bytes

f p@(a,b,c)=p:(b,a+b,c):f(b,a+b+c,a+b)
(f(1,1,1)!!)

This uses 0-based indexing. Usage example: (f(1,1,1)!!) 10 -> (28,60,41).

f creates the infinite list of braid triples and (f(1,1,1)!!) picks the nth one. f itself is a simple recursion which makes a list of its argument, followed by the left crossover and a recursive call with left and right crossover.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Ruby, 60 57 bytes

->n{f=->x{x<2?1:f[x-1]+f[x-3]};[f[n-2|1],f[n],f[n-1&-2]]}

The levels are 1-based.

Based on the following formula:

f(-1) = 1
f(0)  = 1
f(1)  = 1
f(x)  = f(x-1) + f(x-3)

braid(x) = {
    [f(x-1), f(x), f(x-2)]  if x is even,
    [f(x-2), f(x), f(x-1)]  if x is odd
}

Thanks to Neil for 3 bytes off with some nifty bitwise shenanigans.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Bitwise operators FTW: [f[n-2|1],f[n],f[n-1&-2]]. \$\endgroup\$
    – Neil
    Commented Dec 22, 2016 at 1:23
  • \$\begingroup\$ @Neil That's pretty neat, thanks! \$\endgroup\$
    – Doorknob
    Commented Dec 22, 2016 at 2:34
4
\$\begingroup\$

Python 2, 57 bytes

f=lambda n,a=1,b=1,c=1:1/n*(c,b,a)or f(n-1,b,b+c,a)[::-1]

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly, 14 bytes

Ḋ+\;Ḣ
6BÇ⁸¡Ṛ⁸¡

Try it online!

How it works

6BÇ⁸¡Ṛ⁸¡  Main link. Argument: n (integer)

6B        Convert 6 to binary, yielding [1, 1, 0], which is the braid at index 0.
  Ç⁸¡     Call the helper link n times.
     Ṛ⁸¡  Reverse the resulting array n times.


Ḋ+\;Ḣ     Helper link. Argument: [a, b, c] (integer array)

Ḋ         Dequeue, yielding [b, c].
 +\       Cumulative sum, yielding [b, b+c].
   ;Ḣ     Concatenate with the head of [a, b, c], yielding [b, b+c, a].
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

TI-Basic, 58 bytes

One-based.

Prompt N
{1,1,1
For(I,1,Ans
If fPart(I/2
Then
{Ans(2),Ans(1)+Ans(2),Ans(3
Else
{Ans(1),Ans(2)+Ans(3),Ans(2
End
End
Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ How is this 58 bytes? I count 114.. am I missing something? \$\endgroup\$
    – briantist
    Commented Dec 22, 2016 at 0:37
  • \$\begingroup\$ @briantist TI-Basic commands are one or two bytes long. e.g. Prompt is a 2-byte command. \$\endgroup\$
    – JungHwan Min
    Commented Dec 22, 2016 at 0:43
  • \$\begingroup\$ @JungHwanMin cool, did not realize. I had a feeling there was something I wasn't seeing. I'll leave my comment for others who are unfamiliar. \$\endgroup\$
    – briantist
    Commented Dec 22, 2016 at 0:45
  • 2
    \$\begingroup\$ To see which tokens are one or two bytes, you can check tibasicdev.wikidot.com/tokens \$\endgroup\$
    – Timtech
    Commented Dec 22, 2016 at 1:23
  • \$\begingroup\$ @JungHwanMin Prompt is only one byte. But thanks for explaining the concept of tokens :) \$\endgroup\$
    – Timtech
    Commented Dec 22, 2016 at 1:23
2
\$\begingroup\$

PowerShell 2+, 75 bytes

1-based index

$a=1,1,0;1..$args[0]|%{$d=(0,2)[$_%2];$a[1],$a[$d]=($a[1]+$a[$d]),$a[1]};$a

Try it online! or Try all Test Cases!

The loop always runs once so for the case of braid level 1 I simply start with an array of 1,1,0 so the result of the algorithm with make it 1,1,1.

$a[1] is always the middle, then I just determine whether the other element index ($d) is going to be 0 or 2 based on whether the current level is even or odd. PowerShell supports multiple assignments at once so swapping becomes as easy as $x,$y=$y,$x which is basically what I'm doing with the array elements, just embedding the addition within that assignment.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Javascript (ES6), 55 bytes

x=>(f=y=>y<2?1:f(y-1)+f(y-3),[f(x-2|1),f(x),f(x-1&-2)])

repl.it

1-based

This is just a port of @Doorknob's Ruby answer with @Neil's awesome bitwise golf.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Befunge, 64 bytes

110p100p1&v
01:\_v#:-1<\p00<v\+g
..g.@>_10g
\1-:!#^_\:00g+\v>10p

Try it online!

Explanation

110p                Initialise a to 1 (at location 1;0).  
    100p            Initialise c to 1 (at location 0;0).
        1           Initialise b to 1 (on the stack, since it'll be most frequently used).
         &v         Read n from stdin and turn down.

          <         The main loop starts here, executing right to left.
        -1          Decrement n.
    _v#:            Duplicate and check if zero; if not, continue left.
   \                Swap b to the top of the stack, leaving n below it.
01:            g    Make a duplicate copy, and read a from memory (at location 1;0). 
              +     Add a to b, the result becoming the new b.
            v\      Swap the original b to the top of the stack and turn down.
            >10p    Turn around and save the original b as a (at location 1;0).
\1-                 Swap n back to the top of the stack and decrement.
   :!#^_            Duplicate and check if zero; if not continue right.
        \           Swap b to the top of the stack, leaving n below it.
         :00g       Make a duplicate copy, and read c from memory (at location 0;0).
             +      Add c to b, the result becoming the new b.
              \v    Swap the original b to the top of the stack and turn down.
            p00<    Turn around and save the original b as c (at location 0;0).
           \        Swap n back to the top of the stack.
          <         And repeat the loop from the beginning.

      >             If either of the zero tests succeed, we end up on line 3 going right.
       _            This just drops the n that is now zero, and continues to the right.
        10g         Read the final value of a (at location 1;0).
..                  Output a along with the b that was already on the stack.
  g                 Read the final value of c (the 0;0 location is implied).
   .@               Output c and exit.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 17 bytes

6bSIF¬¸s¦.pOì}¹FR

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Java 8, 121

This uses one-based levels:

(int l)->{int a=1,b=a,c=a,i=a;while(i<l)if(i++%2>0){b^=a;a^=b;b=(a^b)+a;}else{b^=c;c^=b;b=(c^b)+c;}return a+","+b+","+c;}

Ungolfed, with test program:

import java.util.function.IntFunction;

public class GolfANumericalGrowingBraid {

  public static void main(String[] args) {
    for (int level : new int[] { 1, 2, 5, 10 }) {
      output((int l) -> {
        int a = 1, b = a, c = a, i = a;
        while (i < l) {
          if (i++ % 2 > 0) {
            b ^= a;
            a ^= b;
            b = (a ^ b) + a;
          }
          else {
            b ^= c;
            c ^= b;
            b = (c ^ b) + c;
          }
        }
        return a + "," + b + "," + c;
      } , level);
    }
  }

  private static void output(IntFunction<String> function, int level) {
    System.out.println(function.apply(level));
  }
}

Output:

1,1,1
1,2,1
3,6,4
28,41,19

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

GameMaker Language, 113 bytes

One-indexed, based on Doorknob's recursive solution. Please don't ask why you can't initialize a primitive array all at once in GameMaker, I really don't know...

Main program (69 bytes):

a=argument0 if a mod 2c=1b[0]=a(a-c-1)b[1]=a(a)b[2]=a(a+c-2)return b

Subprogram a (46 bytes):

a=argument0 if a<2return 1return a(a-1)+a(a-3)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 60 bytes

{(1 xx 3,->[\a,\b,\c]{$++%2??(a,b+c,b)!!(b,b+a,c)}...*)[$_]}

Zero-based.

Straight-forwardly generated the lazy infinite sequence, and then indexes it.
There are likely better approaches.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Clojure, 98 bytes

#(ffirst(drop %(iterate(fn[[v[a b c d]]][[(v a)(+(v b)(v c))(v d)][b a d c]])[[1 1 0][0 1 2 1]])))

Keeps track of current value v and from which positions the summation should be made for next round. Starts one state before the [1 1 1] to have 1-based indexing.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

C# 88 86 Bytes

f(int n,int a=1,int b=1,int c=1)=>n>1?n--%2>0?f(n,b,a+b,c):f(n,a,b+c,b):a+","+b+","+c;

Explanation

f(int n,int a=1,int b=1,int c=1)=>  //Using an expression bodied function to allow for defaults and remove return statement
    n>1?                            //recurse or return result
        n--%2>0?                    //get odd or even then decrement n
            f(n,b,a+b,c)            //odd recursion
           :f(n,a,b+c,b)            //even recursion
       :a+","+b+","+c;              //build output
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 68 bytes

If[#<3,{1,#,1},{{#,+##2,#2}&,{#2,#+#2,#3}&}[[Mod[#,2,1]]]@@#0[#-1]]&

Straightforward recursive definition of an unnamed function, taking a positive integer argument and returning an ordered list of three integers.

Improve this answer
\$\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.