# Golf a Numerical Growing Braid

## 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


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


# MATL, 1817 16 bytes

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


Input is 0-based.

### 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

• 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 – Peter Taylor Dec 22 '16 at 8:33
• @PeterTaylor Thanks for the idea. In this case varying the initial vector and dividing the input by 2 seems to be more byte-costly – Luis Mendo Dec 22 '16 at 10:49

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.

## 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.

• Bitwise operators FTW: [f[n-2|1],f[n],f[n-1&-2]]. – Neil Dec 22 '16 at 1:23
• @Neil That's pretty neat, thanks! – Doorknob Dec 22 '16 at 2:34

# 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!

# 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].


# 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

• How is this 58 bytes? I count 114.. am I missing something? – briantist Dec 22 '16 at 0:37
• @briantist TI-Basic commands are one or two bytes long. e.g. Prompt is a 2-byte command. – JungHwan Min Dec 22 '16 at 0:43
• @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. – briantist Dec 22 '16 at 0:45
• To see which tokens are one or two bytes, you can check tibasicdev.wikidot.com/tokens – Timtech Dec 22 '16 at 1:23
• @JungHwanMin Prompt  is only one byte. But thanks for explaining the concept of tokens :) – Timtech Dec 22 '16 at 1:23

# 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.

# 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.

# 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.


# 05AB1E, 17 bytes

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


Try it online!

# 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

# 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)


# 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.

## 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.

# 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


# 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.