# Boustrophedon transform

Boustrophedon transform is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
 This page uses content from Wikipedia. The original article was at Boustrophedon transform. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

A boustrophedon transform is a procedure which maps one sequence to another using a series of integer additions.

Generally speaking, given a sequence: ${\displaystyle (a_0, a_1, a_2, \ldots)}$, the boustrophedon transform yields another sequence: ${\displaystyle (b_0, b_1, b_2, \ldots)}$, where ${\displaystyle b_0}$ is likely defined equivalent to ${\displaystyle a_0}$.

There are a few different ways to effect the transform. You may construct a boustrophedon triangle and read off the edge values, or, may use the recurrence relationship:

${\displaystyle T_{k,0} = a_k}$
${\displaystyle T_{k,n} = T_{k,n-1} + T_{k-1,k-n}}$
${\displaystyle \text{with }}$
${\displaystyle \quad k,n \in \mathbb{N}}$
${\displaystyle \quad k \ge n > 0}$.

The transformed sequence is defined by ${\displaystyle b_n = T_{n,n}}$ (for ${\displaystyle T_{2,2}}$ and greater indices).

You are free to use a method most convenient for your language. If the boustrophedon transform is provided by a built-in, or easily and freely available library, it is acceptable to use that (with a pointer to where it may be obtained).

• Write a procedure (routine, function, subroutine, whatever it may be called in your language) to perform a boustrophedon transform to a given sequence.
• Use that routine to perform a boustrophedon transform on a few representative sequences. Show the first fifteen values from the transformed sequence.
Use the following sequences for demonstration:
• ${\displaystyle (1, 0, 0, 0, \ldots)}$ ( one followed by an infinite series of zeros )
• ${\displaystyle (1, 1, 1, 1, \ldots)}$ ( an infinite series of ones )
• ${\displaystyle (1, -1, 1, -1, \ldots)}$ ( (-1)^n: alternating 1, -1, 1, -1 )
• ${\displaystyle (2, 3, 5, 7, 11, \ldots)}$ ( sequence of prime numbers )
• ${\displaystyle (1, 1, 2, 3, 5, \ldots)}$ ( sequence of Fibonacci numbers )
• ${\displaystyle (1, 1, 2, 6, 24, \ldots)}$ ( sequence of factorial numbers )

Stretch

If your language supports big integers, show the first and last 20 digits, and the digit count of the 1000th element of each sequence.

## ALGOL 68

Basic task - assumes LONG INT is large enough, e.g. 64 bits, 39 bits would do...

BEGIN # apply a Boustrophedon Transform to a few sequences                   #
# returns the sequence generated by transforming s                       #
PROC boustrophedon transform = ( []LONG INT s )[]LONG INT:
BEGIN
[]LONG INT a = s[ AT 0 ];      # a is s with lower bound revised to 0 #
[ 0 : UPB a, 0 : UPB a ]LONG INT t;
t[ 0, 0 ] := a[ 0 ];
FOR k TO UPB a DO
t[ k, 0 ] := a[ k ];
FOR n TO k DO
t[ k, n ] := t[ k, n - 1 ] + t[ k - 1, k - n ]
OD
OD;
[ 0 : UPB a ]LONG INT b;
FOR n FROM 0 TO UPB b DO b[ n ] := t[ n, n ] OD;
b
END # boustrophedon transform # ;
# prints the transformed sequence generated from a                       #
PROC print transform = ( STRING name, []LONG INT a )VOID:
BEGIN
[]LONG INT b = boustrophedon transform( a );
print( ( name, " generates:", newline ) );
FOR i FROM LWB b TO UPB b DO print( ( " ", whole( b[ i ], 0 ) ) ) OD;
print( ( newline ) )
END # print transform # ;
BEGIN # test cases                                                       #
print transform( "1, 0, 0, 0, ..."
, []LONG INT( 1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 )
);
print transform( "1, 1, 1, 1, ..."
, []LONG INT( 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1 )
);
print transform( "1, -1, 1, -1, ..."
, []LONG INT( 1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1 )
);
print transform( "primes"
, []LONG INT( 2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 )
);
print transform( "fibnonacci numbers"
, []LONG INT( 1,  1,  2,  3,  5,  8, 13, 21, 34, 55, 89, 144, 233, 377, 610 )
);
[ 0 : 14 ]LONG INT factorial;
factorial[ 0 ] := 1;
FOR i TO UPB factorial DO factorial[ i ] := i * factorial[ i - 1 ] OD;
print transform( "factorial numbers",  factorial )
END
END
Output:
1, 0, 0, 0, ... generates:
1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981
1, 1, 1, 1, ... generates:
1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574
1, -1, 1, -1, ... generates:
1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530
primes generates:
2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691
fibnonacci numbers generates:
1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189
factorial numbers generates:
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547


## J

Implementation:
b=: {{
M=: (u i.y),.(y-0 1)$x:_ B=:{{ if. x<y do.0 else. i=. <x,y if. _>i{M do. i{M else. r=. (x B y-1)+(x-1) B x-y r[M=: r i} M end. end. }}"0 (<0 1)|:B/~i.y }}  Task examples:  =&0 b 15 1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981 1"0 b 15 1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574 _1x&^ b 15 1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530 p: b 15 2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691 phi=: -:>:%:5 {{ <.0.5+(phi^y)%%:5 }} b 15 0 1 3 8 25 85 334 1497 7635 43738 278415 1949531 14893000 123254221 1098523231 !@x: b 15 1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547  ### Alternate implementation Instead of relying on recursion and memoization, we can deliberately perform the operations in the correct order: B=: {{ M=. |:y#,:u i.y for_i.(#~>:/"1)1+(,#:i.@*)~y-1 do. M=. M (<i)}~(M{~<i-0 1)+M{~<(-/\i)-1 0 end. M|:~<1 0 }}  Here, we start with a square matrix with the a values in sequence in the first column (first line). Then we fill in the remaining needed T values in row major order (for loop). Finally, we extract the diagonal (last line). Usage and results are the same as before. ## Julia using Primes function bous!(triangle, k, n, seq) n == 1 && return BigInt(seq[k]) triangle[k][n] > 0 && return triangle[k][n] return (triangle[k][n] = bous!(triangle, k, n - 1, seq) + bous!(triangle, k - 1, k - n + 1, seq)) end boustrophedon(seq) = (n = length(seq); t = [zeros(BigInt, j) for j in 1:n]; [bous!(t, i, i, seq) for i in 1:n]) boustrophedon(f, range) = boustrophedon(map(f, range)) fib(n) = (z = BigInt(0); ccall((:__gmpz_fib_ui, :libgmp), Cvoid, (Ref{BigInt}, Culong), z, n); z) tests = [ ((n) -> n < 2, 1:1000, "One followed by an infinite series of zeros -> A000111"), ((n) -> 1, 1:1000, "An infinite series of ones -> A000667"), ((n) -> isodd(n) ? 1 : -1, 1:1000, "(-1)^n: alternating 1, -1, 1, -1 -> A062162"), ((n) -> prime(n), 1:1000, "Sequence of prime numbers -> A000747"), ((n) -> fib(n), 1:1000, "Sequence of Fibonacci numbers -> A000744"), ((n) -> factorial(BigInt(n)), 0:999, "Sequence of factorial numbers -> A230960") ] for (f, rang, label) in tests println(label) arr = boustrophedon(f, rang) println(Int64.(arr[1:15])) s = string(arr[1000]) println(s[1:20], " ... ", s[end-19:end], " ($(length(s)) digits)\n")
end

Output:
One followed by an infinite series of zeros -> A000111
[1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, 22368256, 199360981]
61065678604283283233 ... 63588348134248415232 (2369 digits)

An infinite series of ones -> A000667
[1, 2, 4, 9, 24, 77, 294, 1309, 6664, 38177, 243034, 1701909, 13001604, 107601977, 959021574]
29375506567920455903 ... 86575529609495110509 (2370 digits)

(-1)^n: alternating 1, -1, 1, -1 -> A062162
[1, 0, 0, 1, 0, 5, 10, 61, 280, 1665, 10470, 73621, 561660, 4650425, 41441530]
12694307397830194676 ... 15354198638855512941 (2369 digits)

Sequence of prime numbers -> A000747
[2, 5, 13, 35, 103, 345, 1325, 5911, 30067, 172237, 1096319, 7677155, 58648421, 485377457, 4326008691]
13250869953362054385 ... 82450325540640498987 (2371 digits)

Sequence of Fibonacci numbers -> A000744
[1, 2, 5, 14, 42, 144, 563, 2526, 12877, 73778, 469616, 3288428, 25121097, 207902202, 1852961189]
56757474139659741321 ... 66135597559209657242 (2370 digits)

Sequence of factorial numbers -> A230960
[1, 2, 5, 17, 73, 381, 2347, 16701, 134993, 1222873, 12279251, 135425553, 1627809401, 21183890469, 296773827547]
13714256926920345740 ... 19230014799151339821 (2566 digits)


## Perl

Not really fulfilling the conditions of the stretch goal, but heading a little way down that path.

Translation of: Raku
Library: ntheory
use v5.36; use experimental <builtin for_list>;
use ntheory <factorial lucasu nth_prime>;
use bigint;

sub abbr ($d) { my$l = length $d;$l < 41 ? $d : substr($d,0,20) . '..' . substr($d,-20) . " ($l digits)" }
sub sum  (@a) { my $sum = Math::BigInt->bzero();$sum += $_ for @a;$sum }

sub boustrophedon_transform (@seq) {
my @bt;
my @bx = $seq[0]; for (my$c = 0; $c < @seq;$c++) {
@bx = reverse map { sum head $_+1,$seq[$c], @bx } 0 ..$c;
push @bt, $bx[0]; } @bt } my$upto = 100; #1000 way too slow
for my($name,$seq) (
'1 followed by 0\'s A000111', [1, (0) x $upto], 'All-1\'s A000667', [ (1) x$upto],
'(-1)^n             A062162', [1, map { (-1)**$_ } 1..$upto],
'Primes             A000747', [   map { nth_prime $_ } 1..$upto],
'Fibbonaccis        A000744', [   map { lucasu(1, -1, $_) } 1..$upto],
'Factorials         A230960', [1, map { factorial $_ } 1..$upto]
) {
my @bt = boustrophedon_transform @$seq; say "\n$name:\n" . join ' ', @bt[0..14];
say "100th term: " . abbr $bt[$upto-1];
}

Output:
1 followed by 0's A000111:
1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981
100th term: 45608516616801111821..68991870306963423232 (137 digits)

All-1's           A000667:
1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574
100th term: 21939873756450413339..30507739683220525509 (138 digits)

(-1)^n             A062162:
1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530
100th term: 94810791122872999361..65519440121851711941 (136 digits)

Primes             A000747:
2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691
100th term: 98967625721691921699..78027927576425134967 (138 digits)

Fibbonaccis        A000744:
1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189
100th term: 42390820205259437020..42168748587048986542 (138 digits)

Factorials         A230960:
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547
100th term: 31807659526053444023..65546706672657314921 (157 digits)

## Phix

without js -- see below
include mpfr.e

string stretchres = ""
procedure test(sequence ds)
{string desc, sequence s} = ds
integer n = length(s)
sequence t = apply(true,repeat,{0,tagset(n)}),
r15 = repeat("?",15), r1000 = "??"
for k=0 to n-1 do
integer i = k+1, {lo,hi,step} = iff(odd(k)?{k,1,-1}:{2,i,+1})
t[i,step] = s[i]
for j=lo to hi by step do
mpz tk = mpz_init()
t[i][j] = tk
end for
if i<=15 then
r15[i] = mpz_get_str(t[i][-step])
elsif i=1000 then
r1000 = mpz_get_short_str(t[i][-step])
end if
end for
printf(1,"%s:%s\n",{desc,join(r15)})
stretchres &= sprintf("%s[1000]:%s\n",{desc,r1000})
end procedure

function f1000(integer f, sequence v)
sequence res = mpz_inits(1000)
papply(true,f,{res,v})
return res
end function

constant tests = {{"1{0}",mpz_inits(1000,1&repeat(0,999))},
{"{1}",mpz_inits(1000,repeat(1,1000))},
{"+-1",mpz_inits(1000,flatten(repeat({1,-1},500)))},
{"pri",mpz_inits(1000,get_primes(-1000))},
{"fib",f1000(mpz_fib_ui,tagset(1000))},
{"fac",f1000(mpz_fac_ui,tagstart(0,1000))}}
papply(tests,test)
printf(1,"\n%s",stretchres)

Output:
1{0}:1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981
{1}:1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574
+-1:1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530
pri:2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691
fib:1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189
fac:1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547

1{0}[1000]:61065678604283283233...63588348134248415232 (2,369 digits)
{1}[1000]:29375506567920455903...86575529609495110509 (2,370 digits)
+-1[1000]:12694307397830194676...15354198638855512941 (2,369 digits)
pri[1000]:13250869953362054385...82450325540640498987 (2,371 digits)
fib[1000]:56757474139659741321...66135597559209657242 (2,370 digits)
fac[1000]:13714256926920345740...19230014799151339821 (2,566 digits)


As was noted somewhat obscurely in p2js/mappings ("When step may or may not be negative...") and now more clearly noted in the for loop documentation, for p2js compatibility the inner loop would have to be something like:

with javascript_semantics
...
if odd(k) then
for j=k to 1 by -1 do
mpz tk = mpz_init()
t[i][j] = tk
end for
else
for j=2 to i do
mpz tk = mpz_init()
t[i][j] = tk
end for
end if


## Raku

sub boustrophedon-transform (@seq) { map *.tail, (@seq[0], {[[\+] flat @seq[++$], .reverse]}…*) } sub abbr ($_) { .chars < 41 ?? $_ !! .substr(0,20) ~ '…' ~ .substr(*-20) ~ " ({.chars} digits)" } for '1 followed by 0\'s A000111', (flat 1, 0 xx *), 'All-1\'s A000667', (flat 1 xx *), '(-1)^n A062162', (flat 1, [\×] -1 xx *), 'Primes A000747', (^∞ .grep: &is-prime), 'Fibonaccis A000744', (1,1,*+*…*), 'Factorials A230960', (1,|[\×] 1..∞) ->$name, $seq { say "\n$name:\n" ~ (my $b-seq = boustrophedon-transform$seq)[^15] ~ "\n1000th term: " ~ abbr $b-seq[999] }  Output: 1 followed by 0's A000111: 1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981 1000th term: 61065678604283283233…63588348134248415232 (2369 digits) All-1's A000667: 1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574 1000th term: 29375506567920455903…86575529609495110509 (2370 digits) (-1)^n A062162: 1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530 1000th term: 12694307397830194676…15354198638855512941 (2369 digits) Primes A000747: 2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691 1000th term: 13250869953362054385…82450325540640498987 (2371 digits) Fibonaccis A000744: 1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189 1000th term: 56757474139659741321…66135597559209657242 (2370 digits) Factorials A230960: 1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547 1000th term: 13714256926920345740…19230014799151339821 (2566 digits) ## Wren Library: Wren-math ### Basic import "./math" for Int var boustrophedon = Fn.new { |a| var k = a.count var cache = List.filled(k, null) for (i in 0...k) cache[i] = List.filled(k, 0) var b = List.filled(k, 0) b[0] = a[0] var T T = Fn.new { |k, n| if (n == 0) return a[k] if (cache[k][n] > 0) return cache[k][n] return cache[k][n] = T.call(k, n-1) + T.call(k-1, k-n) } for (n in 1...k) b[n] = T.call(n, n) return b } System.print("1 followed by 0's:") var a = [1] + ([0] * 14) System.print(boustrophedon.call(a)) System.print("\nAll 1's:") a = [1] * 15 System.print(boustrophedon.call(a)) System.print("\nAlternating 1, -1") a = [1, -1] * 7 + [1] System.print(boustrophedon.call(a)) System.print("\nPrimes:") a = Int.primeSieve(200)[0..14] System.print(boustrophedon.call(a)) System.print("\nFibonacci numbers:") a[0] = 1 // start from fib(1) a[1] = 1 for (i in 2..14) a[i] = a[i-1] + a[i-2] System.print(boustrophedon.call(a)) System.print("\nFactorials:") a[0] = 1 for (i in 1..14) a[i] = a[i-1] * i System.print(boustrophedon.call(a))  Output: 1 followed by 0's: [1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, 22368256, 199360981] All 1's: [1, 2, 4, 9, 24, 77, 294, 1309, 6664, 38177, 243034, 1701909, 13001604, 107601977, 959021574] Alternating 1, -1 [1, 0, 0, 1, 0, 5, 10, 61, 280, 1665, 10470, 73621, 561660, 4650425, 41441530] Primes: [2, 5, 13, 35, 103, 345, 1325, 5911, 30067, 172237, 1096319, 7677155, 58648421, 485377457, 4326008691] Fibonacci numbers: [1, 2, 5, 14, 42, 144, 563, 2526, 12877, 73778, 469616, 3288428, 25121097, 207902202, 1852961189] Factorials: [1, 2, 5, 17, 73, 381, 2347, 16701, 134993, 1222873, 12279251, 135425553, 1627809401, 21183890469, 296773827547]  ### Stretch Library: Wren-big Library: Wren-fmt import "./math" for Int import "./big" for BigInt import "./fmt" for Fmt var boustrophedon1000 = Fn.new { |a| var k = a.count var cache = List.filled(k, null) for (i in 0...k) { cache[i] = List.filled(k, null) for (j in 0...k) cache[i][j] = BigInt.zero } var T T = Fn.new { |k, n| if (n == 0) return a[k] if (cache[k][n] > BigInt.zero) return cache[k][n] return cache[k][n] = T.call(k, n-1) + T.call(k-1, k-n) } return T.call(999, 999) } System.print("1 followed by 0's:") var a = ([1] + [0] * 999).map { |i| BigInt.new(i) }.toList var bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a ($d digits)", bs, bs.count) System.print("\nAll 1's:") a = ([1] * 1000).map { |i| BigInt.new(i) }.toList bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a ($d digits)", bs, bs.count) System.print("\nAlternating 1, -1") a = ([1, -1] * 500).map { |i| BigInt.new(i) }.toList bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a ($d digits)", bs, bs.count) System.print("\nPrimes:") a = Int.primeSieve(8000)[0..999].map { |i| BigInt.new(i) }.toList bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a ($d digits)", bs, bs.count) System.print("\nFibonacci numbers:") a[0] = BigInt.one // start from fib(1) a[1] = BigInt.one for (i in 2..999) a[i] = a[i-1] + a[i-2] bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a ($d digits)", bs, bs.count) System.print("\nFactorials:") a[0] = BigInt.one for (i in 1..999) a[i] = a[i-1] * i bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a (\$d digits)", bs, bs.count)

Output:
1 followed by 0's:
1000th term: 61065678604283283233...63588348134248415232 (2369 digits)

All 1's:
1000th term: 29375506567920455903...86575529609495110509 (2370 digits)

Alternating 1, -1
1000th term: 12694307397830194676...15354198638855512941 (2369 digits)

Primes:
1000th term: 13250869953362054385...82450325540640498987 (2371 digits)

Fibonacci numbers:
1000th term: 56757474139659741321...66135597559209657242 (2370 digits)

Factorials:
1000th term: 13714256926920345740...19230014799151339821 (2566 digits)