Recaman's sequence: Difference between revisions
Content added Content deleted
(→{{header|jq}}: second solution) |
|||
Line 1,310: | Line 1,310: | ||
=={{header|jq}}== |
=={{header|jq}}== |
||
⚫ | |||
{{works with|jq}} |
{{works with|jq}} |
||
'''Works with gojq, the Go implementation of jq''' |
'''Works with gojq, the Go implementation of jq''' |
||
Two jq solutions are provided here. The first is a monolithic "all-in-one" approach |
|||
in which a single function or procedure does all the work in one pass. This approach |
|||
has the disadvantage of neither providing or using reusable components. |
|||
The second solution is a stream-oriented one that separates the generation of the |
|||
sequence from other computations. This approach can be just as efficient as the |
|||
monolithic approach, but for the sake of illustration, the solution offered |
|||
here provides separate functions for generation and for each of the three specific tasks. |
|||
=== Monolithic approach=== |
|||
⚫ | |||
The main point of potential interest in this implementation is that |
The main point of potential interest in this implementation is that |
||
Line 1,370: | Line 1,381: | ||
Terms up to a[328002] are needed to generate 0 to 1000 inclusive. |
Terms up to a[328002] are needed to generate 0 to 1000 inclusive. |
||
</pre> |
</pre> |
||
=== A stream-oriented solution=== |
|||
<lang jq> |
|||
# Output: the stream of elements in the Recaman sequence, beginning with 0. |
|||
def recaman: |
|||
0, |
|||
foreach range(1; infinite) as $i ({used: {"0": true}, current: 0}; |
|||
(.current - $i) as $next |
|||
| .current = (if ($next < 1 or .used[$next|tostring]) then $next + 2 * $i else $next end) |
|||
| .used[.current|tostring] = true; |
|||
.current ); |
|||
# emit [.i, $x] for duplicated terms using IO==0 |
|||
def duplicated(s): |
|||
foreach s as $x ({used: {}, i: -1}; |
|||
.i += 1 |
|||
| ($x|tostring) as $xs |
|||
| if .used[$xs] then .emit = [.i, $x] else .used[$xs] = true end; |
|||
select(.emit) | .emit); |
|||
# Input: $required |
|||
# Output: the number of items that must be generated in order that all the integers |
|||
# in the closed interval [0 .. $required] be found. |
|||
# |
|||
def covers(s): |
|||
. as $required |
|||
| first(foreach s as $x ( { i: -1, found: {}, nfound: 0}; |
|||
.i += 1 |
|||
| ($x|tostring) as $xs |
|||
| if .found[$xs] then . |
|||
elif $x <= $required |
|||
then .found[$xs] = true | .nfound += 1 |
|||
| if .nfound > $required then .emit=.i else . end |
|||
else . |
|||
end; |
|||
select(.emit).emit) );</lang> |
|||
'''The three tasks:''' |
|||
<lang jq> |
|||
"First 15:", limit(15; recaman), |
|||
"\First duplicated:", first(duplicated(recaman)), |
|||
"\Index of first element to include 0 to 1000 inclusive:", |
|||
(1000|covers(recaman)) |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
First 15: |
|||
0 |
|||
1 |
|||
3 |
|||
6 |
|||
2 |
|||
7 |
|||
13 |
|||
20 |
|||
12 |
|||
21 |
|||
11 |
|||
22 |
|||
10 |
|||
23 |
|||
9 |
|||
First duplicated: |
|||
[24,42] |
|||
Index of first element to include 0 to 1000 inclusive: |
|||
328002 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |