Boustrophedon transform: Difference between revisions
Content added Content deleted
(Added Sidef) |
|||
Line 478: | Line 478: | ||
1,000th element: 13714256926920345740 ... 19230014799151339821 (2566 digits) |
1,000th element: 13714256926920345740 ... 19230014799151339821 (2566 digits) |
||
</pre> |
</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}}== |
=={{header|Julia}}== |