Generate Pascal's Braid

This is Pascal's Braid:

 1 4  15  56   209   780    2911    10864     40545      151316      564719
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841
1 4  15  56   209   780    2911    10864     40545      151316      564719


I totally made that up. Blaise Pascal didn't have a braid as far as I can tell, and if he did it was probably made of hair instead of numbers.

It's defined like this:

1. The first column has a single 1 in the middle.
2. The second column has a 1 at the top and at the bottom.
3. Now we alternate between putting a number in the middle or two copies of a number at the top and bottom.
4. If the number goes on the top or the bottom, it will be the sum of the two adjacent numbers (e.g. 56 = 15 + 41). If you tilt your head a little, this is like a step in Pascal's triangle.
5. If the number goes in the middle, it will be the sum of all three adjacent numbers (e.g. 41 = 15 + 11 + 15).

Your task will be to print (some part of) this braid.

Input

You should write a program or function, which receives a single integer n, giving the index of the last column to be output.

You may choose whether the first column (printing only a single 1 on the middle line) corresponds to n = 0 or n = 1. This has to be a consistent choice across all possible inputs.

Output

Output Pascal's Braid up to the nth column. The whitespace has to match exactly the example layout above, except that you may pad the shorter line(s) to the length of the longer line(s) with spaces and you may optionally output a single trailing linefeed.

In other words, every column should be exactly as wide as the number (or pair of equal numbers) in that column, numbers in successive columns should not overlap and there should be no spaces between columns.

You may either print the result to STDOUT (or the closest alternative), or if you write a function you may return either a string with the same contents or a list of three strings (one for each line).

Further Details

You may assume that n won't be less than the index of the first column (so not less than 0 or 1 depending on your indexing). You may also assume that the last number in the braid is less than 256 or the largest number representable by your language's native integer type, whichever is greater. So if your native integer type can only store bytes, you can assume that the largest n is 9 or 10 (depending on whether you use 0- or 1-based n) and if it can store signed 32-bit integers, n will be at most 33 or 34.

Standard rules apply. The shortest code wins.

OEIS

Here are a few relevant OEIS links. Of course, these contain spoilers for different ways to generate the numbers in the braid:

Test Cases

These test cases use 1-base indexing. Each test case is four lines, with the first being the input and the remaining three being the output.

1

1

---
2
1
1
1
---
3
1
1 3
1
---
5
1 4
1 3 11
1 4
---
10
1 4  15  56   209
1 3 11  41  153
1 4  15  56   209
---
15
1 4  15  56   209   780    2911
1 3 11  41  153   571   2131    7953
1 4  15  56   209   780    2911
---
24
1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841
1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560

• The format seems like a bit chameleon to me. Commented Jul 20, 2016 at 15:49
• @LeakyNun I tried this challenge while it was in the sandbox, and I spent about half as many bytes on calculating the braid as printing it. This seems like an excellent balance to me for an ascii-art challenge. Commented Jul 20, 2016 at 15:52
• @LeakyNun I was hoping that both the sequence generation and the ASCII art are important components of the challenge, because most languages will probably be better at one of those two, so I figured it would be interesting to mix them up. And it introduces an additional component where it's not obvious whether it's better to generate top/bottom and middle separately or to generate the entire thing and then separate out the bisections. Commented Jul 20, 2016 at 15:52
• Commented Jul 20, 2016 at 18:56
• Nobody has written a solution in Pascal yet. This makes me sad.
– user45178
Commented Jul 21, 2016 at 17:52

Pyth, 44 bytes

The number generation took 20 bytes, and the formatting took 24 bytes.

jsMC+Led.e.<bkC,J<s.u+B+hNyeNeNQ,1 1Qm*;ldJ


Try it online!

jsMC+Led.e.<bkC,J<s.u+B+hNyeNeNQ,1 1Qm*;ldJ   input as Q
.u          Q,1 1           repeat Q times, starting with [1,1],
collecting all intermediate results,
current value as N:
(this will generate
more than enough terms)
+hNyeN                  temp <- N[0] + 2*N[-1]
+B      eN                temp <- [temp+N[-1], temp]

now, we would have generated [[1, 1], [3, 4], [11, 15], [41, 56], ...]

jsMC+Led.e.<bkC,J<s                 Qm*;ldJ
s                            flatten
<                  Q          first Q items
J                              store in J
m    dJ   for each item in J:
convert to string
l      length
*;       repeat " " that many times

jsMC+Led.e.<bkC,
C,     transpose, yielding:
[[1, ' '], [1, ' '], [3, ' '], [4, ' '], [11, '  '], ...]
(each element with as many spaces as its length.)
.e            for each sub-array (index as k, sub-array as b):
.<bk            rotate b as many times as k

[[1, ' '], [' ', 1], [3, ' '], [' ', 4], [11, '  '], ...]

jsMC+Led
+Led              add to each sub-array on the left, the end of each sub-array
C                  transpose
sM                   sum of each sub-array (reduced concatenation)
j                     join by new-lines

• That is the largest Pyth program I've ever seen. Commented Jul 20, 2016 at 21:45

Python 2, 120 bytes

a=1,1,3,4
n=input()
y=0
exec"y+=1;t='';x=0;%sprint t;"%(n*"a+=a[-2]*4-a[-4],;v=a[x];t+=[v,len(v)*' '][x+y&1];x+=1;")*3


Try it on Ideone.

MATL, 38 bytes

1ti:"yy@oQ*+]vG:)!"@Vt~oX@o?w]&v]&hZ}y


Try it online!

Computing an array with the (unique) numbers takes the first 17 bytes. Formatting takes the remaining 21 bytes.

Explanation

Part 1: generate the numbers

This generates an array with the numbers from the first and second rows in increasing order: [1; 1; 3; 4; 11; 15; ...]. It starts with 1, 1. Each new number is iteratively obtained from the preceding two. Of those, the second is multiplied by 1 or 2 depending on the iteration index, and then summed to the first to produce the new number.

The number of iterations is equal to the input n. This means that n+2 numbers are generated. Once generated, the array needs to be trimmed so only the first n entries are kept.

1t      % Push 1 twice
i:      % Take input n. Generage array [1 2 ... n]
"       % For each
yy    %   Duplicate the two most recent numbers
@o    %   Parity of the iteration index (0 or 1)
Q     %   Add 1: gives 1 for even iteration index, 2 for odd
*+    %   Multiply this 1 or 2 by the most recent number in the sequence, and add
%    to the second most recent. This produces a new number in the sequence
]       % End for each
v       % Concatenate all numbers in a vertical array
G:)     % Keep only the first n entries


Part 2: format the output

For each number in the obtained array, this generates two strings: string representation of the number, and a string of the same length consisting of character 0 repeated (character 0 is displayed as a space in MATL). For even iterations, these two strings are swapped.

The two strings are then concatenated vertically. So n 2D char arrays are produced as follows (using · to represent character 0):

·
1

1
·

·
3

4
·

··
11

15
··


These arrays are then concatenated horizontally to produce

·1·4··15
1·3·11··


Finally, this 2D char array is split into its two rows, and the first is duplicated onto the top of the stack. The three strings are displayed in order, each on a different line, producing the desired output

!       % Transpose into a horizontal array [1 1 3 4 11 15 ...]
"       % For each
@V    %   Push current number and convert to string
t~o   %   Duplicate, negate, convert to double: string of the same length consisting
%   of character 0 repeated
X@o   %   Parity of the iteration index (1 or 0)
?     %   If index is odd
w   %     Swap
]     %   End if
&v    %   Concatenate the two strings vertically. Gives a 2D char array representing
%   a "numeric column" of the output (actually several columns of characters)
]       % End for
&h      % Concatenate all 2D char arrays horizontally. Gives a 2D char array with the
% top two rows of the output
Z}      % Split this array into its two rows
y       % Push a copy of the first row. Implicitly display


Haskell, 101 bytes

a=1:1:t
t=3:4:zipWith((-).(4*))t a

Example

PS C:\Tools\Scripts\golfing> .\pascal-braid.ps1 27
1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560       7865521        29354524
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841       5757961       21489003
1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560       7865521        29354524


PHP 265 bytes

<?php $i=$argv[1];$i=$i?$i:1;$a=[[],[]];$s=['',''];$p='';for($j=0;$j<$i;$j++){$y=($j+1)%2;$x=floor($j/2);$v=$x?$y?2*$a[0][$x-1]+$a[1][$x-1]:$a[0][$x-1]+$a[1][$x]:1;$s[$y].=$p.$v;$a[$y][$x]=$v;$p=str_pad('',strlen($v),' ');}printf("%s\n%s\n%s\n",$s[0],$s[1],$s[0]);


Un-golfed:

$a = [[],[]];$s = ['',''];

$p = '';$i=$argv[1];$i=$i?$i:1;
for($j=0;$j<$i;$j++) {
$y = ($j+1) % 2;
$x = floor($j/2);

if( $x == 0 ) {$v = 1;
} else {
if( $y ) {$v = 2 * $a[0][$x-1] + $a[1][$x-1];
} else {
$v =$a[0][$x-1] +$a[1][$x]; } }$s[$y] .=$p . $v;$a[$y][$x] = $v;$p = str_pad('', strlen($v), ' '); } printf("%s\n%s\n%s\n",$s[0], $s[1],$s[0]);


Python 278 bytes

import sys,math;a=[[],[]];s=['',''];p='';i=int(sys.argv[1]);i=1 if i<1 else i;j=0
while j<i:y=(j+1)%2;x=int(math.floor(j/2));v=(2*a[0][x-1]+a[1][x-1] if y else a[0][x-1]+a[1][x]) if x else 1;s[y]+=p+str(v);a[y].append(v);p=' '*len(str(v));j+=1
print ("%s\n"*3)%(s[0],s[1],s[0])


Ruby, 120 bytes

Returns a multiline string.

Try it online!

->n{a=[1,1];(n-2).times{|i|a<<(2-i%2)*a[-1]+a[-2]}
z=->c{a.map{|e|c+=1;c%2>0?' '*e.to_s.size: e}*''}
[s=z[0],z[1],s]*$/}  Matlab, 223 characters, 226 bytes function[]=p(n) r=[1;1];e={(' 1 ')',('1 1')'} for i=3:n;r(i)=sum((mod(i,2)+1)*r(i-1)+r(i-2));s=num2str(r(i));b=blanks(floor(log10(r(i)))+1);if mod(i,2);e{i}=[b;s;b];else e{i}=[s;b;s];end;end reshape(sprintf('%s',e{:}),3,[])  Ungolfed and commented: function[]=p(n) r=[1;1]; % start with first two e={(' 1 ')',('1 1')'} % initialize string output as columns of blank, 1, blank and 1, blank, 1. for i=3:n; % for n=3 and up! r(i)=sum((mod(i,2)+1)*r(i-1)+r(i-2)); % get the next number by 1 if even, 2 if odd times previous plus two steps back s=num2str(r(i)); % define that number as a string b=blanks(floor(log10(r(i)))+1); % get a number of space characters for that number of digits if mod(i,2); % for odds e{i}=[b;s;b]; % spaces, number, spaces else % for evens e{i}=[s;b;s]; % number, spaces, number end; end reshape(sprintf('%s',e{:}),3,[]) % print the cell array of strings and reshape it so it's 3 lines high  PHP, 135124123 120 bytes <?while($i<$argv[1]){${s.$x=!$x}.=${v.$x}=$a=$i++<2?:$v1+$v+$x*$v;${s.!$x}.=str_repeat(' ',strlen($a));}echo"$s
$s1$s";


taking advantage of implicit typecasts and variable variables
a third of the code (37 bytes) goes into the spaces, 64 bytes altogether used for output

breakdown

$i=0;$x=false; $v=$v1=1; $s=$s1='';    // unnecessary variable initializations
for($i=0;$i<$argv[1];$i++)  // $i is column number -1 {$x=!$x; //$x = current row: true (1) for inner, false (empty string or 0) for outer
// calculate value
$a=$i<2?               // first or second column: value 1
:$v1+(1+$x)*$v // inner-val + (inner row: 1+1=2, outer row: 1+0=1)*outer-val ;${s.$x}.=${v.$x}=$a;    // replace target value, append to current row
${s.!$x}.=str_repeat(' ',strlen($a)); // append spaces to other row } // output echo "$s\n$s1\n$s";


Batch, 250 bytes

@echo off
set s=
set d=
set/ai=n=0,j=m=1
:l
set/ai+=1,j^^=3,l=m+n*j,m=n,n=l
set t=%s%%l%
for /l %%j in (0,1,9)do call set l=%%l:%%j= %%
set s=%d%%l%
set d=%t%
if not %i%==%1 goto l
if %j%==1 echo %d%
echo %s%
echo %d%
if %j%==2 echo %s%


Since the first and third lines are the same, we just have to build two strings. Here d represents the string that ends with the last entry and s represents the string that ends with spaces; the last four lines ensure that they are printed in the appropriate order. i is just the loop counter (it's slightly cheaper than counting down from %1). j is the toggle between doubling the previous number before adding it to the current number to get the next number. m and n contain those numbers. l, as well as being used as a temporary to calculate the next number, also gets its digits replaced with spaces to pad out s; s and d are exchanged each time via the intermediate variable t.