Boustrophedon transform: Difference between revisions
→{{header|jq}}
(Added Sidef) |
|||
Line 478:
1,000th element: 13714256926920345740 ... 19230014799151339821 (2566 digits)
</pre>
=={{header|jq}}==
{{Works with|jq}}
'''Works with gojq, the Go implementation of jq'''
'''Adapted from [[#Wren|Wren]]'''
<syntaxhighlight lang="jq">
### Generic functions
# The stream of Fibonacci numbers beginning with 1, 1, 2, ...
def fibs:
def f: [0,1] | recurse( [.[1], add] );
f | .[1];
# The stream of factorials beginning with 1, 1, 2, 6, 24, ...
def factorials:
def f: recurse( [.[0] + 1, .[0] * .[1]] );
[1, 1] | f | .[1];
# An array of length specified by .
def array($value): [range(0; .) | $value];
### The Boustrophedon transform
def boustrophedon($a):
($a|length) as $k
| ($k | array(0)) as $list
| {b: $list,
cache: [range(0;$k) | $list] }
| .b[0] = $a[0]
# input {b, cache}
| def T($k; $n):
if $n == 0 then .result = $a[k]
elif .cache[$k][$n] > 0 then .result = .cache[$k][$n]
else T($k; $n-1)
| .result as $r1
| T($k-1; $k-$n)
| ($r1 + .result) as $r
| .cache[$k][$n] = $r
| .result = $r
end;
reduce range(1; $k) as $n (.; .b[$n] = (T($n; $n) | .result))
| .b ;
### Exercises
"1 followed by 0's:",
boustrophedon( [1] + (14 | array(0)) ),
"\nAll 1's:",
boustrophedon(15|array(1)),
"\nAlternating 1, -1",
boustrophedon( [range(0;7) | 1, -1] + [1] ),
"\nPrimes:",
boustrophedon([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]),
"\nFibonacci numbers:",
boustrophedon([limit(15; fibs)]),
"\nFactorials:",
boustrophedon([limit(15; factorials)])
</syntaxhighlight>
{{output}}
<pre>
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]
</pre>
=={{header|Julia}}==
| |||