Kolakoski sequence: Difference between revisions
→{{header|jq}}
Drkameleon (talk | contribs) (Added Arturo implementation) |
|||
Line 873:
Possible Kolakoski sequence? false</pre>
=={{header|jq}}==
This section is based on a kolakoski generator that continues
indefinitely.
Thanks to jq's backtracking semantics,
we only need a "cycle" generator
that cycles indefinitely often:
<lang jq>def cycle:
def c: .[], c;
c;</lang>
<lang jq>
# Input: an array
# Output: the corresponding kolakoski sequence.
# This version of the kolakoski generator is optimized to the extent
# that it avoids storing the full sequence by removing the first item
# in the .s array at each iteration.
def kolakoski:
foreach cycle as $next ( {s: []};
# ensure the next element occurs .s[0] times
.s += [$next]
| .extra = [range(0; .s[0]-1) as $i | $next]
| .s = .s[1:] + .extra
;
$next, .extra[] ) ;
def kolakoski($len): limit($len; kolakoski);
def iskolakoski:
def rle:
. as $seq
| reduce range(1;length) as $i ({rle:[], count:1};
if $seq[$i] == $seq[$i - 1]
then .count += 1
else .rle = .rle + [.count]
| .count = 1
end)
| .rle;
rle | . == .[0 : length] ;
</lang>
Testing
<lang jq>
def tests: [[[1, 2], 20], [[2, 1] ,20], [[1, 3, 1, 2], 30], [[1, 3, 2, 1], 30]];
tests[] as [$a, $n]
| $a
| [kolakoski($n)] as $k
| "First \($n) of kolakoski sequence for \($a):", $k, "check: \($k | if iskolakoski then "✓" else "❌" end )", ""
</lang>
{{out}}
Invocation: jq -nr -f kolakoski.jq
<pre>
First 20 of kolakoski sequence for [1,2]:
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1]
check: ✓
First 20 of kolakoski sequence for [2,1]:
[2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2]
check: ✓
First 30 of kolakoski sequence for [1,3,1,2]:
[1,3,3,3,1,1,1,2,2,2,1,3,1,2,2,1,1,3,3,1,2,2,2,1,3,3,1,1,2,1]
check: ✓
First 30 of kolakoski sequence for [1,3,2,1]:
[1,3,3,3,2,2,2,1,1,1,1,1,3,3,2,2,1,1,3,2,1,1,1,1,3,3,3,2,2,1]
check: ✓
</pre>
=={{header|Julia}}==
{{trans|C}}
| |||