Boustrophedon transform

From Rosetta Code
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: , the boustrophedon transform yields another sequence: , where is likely defined equivalent to .

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:

.

The transformed sequence is defined by (for 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).


Task
  • 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:
  • ( one followed by an infinite series of zeros )
  • ( an infinite series of ones )
  • ( (-1)^n: alternating 1, -1, 1, -1 )
  • ( sequence of prime numbers )
  • ( sequence of Fibonacci numbers )
  • ( 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.


See also


J[edit]

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[edit]

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[edit]

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[edit]

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 List::Util 'head';
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[edit]

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()
            mpz_add(tk,t[i,j-step],t[i-1,j-even(k)])
            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()
                mpz_add(tk,t[i,j+1],t[i-1,j])
                t[i][j] = tk
            end for
        else
            for j=2 to i do
                mpz tk = mpz_init()
                mpz_add(tk,t[i,j-1],t[i-1,j-1])
                t[i][j] = tk
            end for
        end if

Raku[edit]

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[edit]

Library: Wren-math

Basic[edit]

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[edit]

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)