Kolakoski sequence: Difference between revisions
Content added Content deleted
Drkameleon (talk | contribs) (Added Arturo implementation) |
|||
Line 873: | Line 873: | ||
Possible Kolakoski sequence? false</pre> |
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}}== |
=={{header|Julia}}== |
||
{{trans|C}} |
{{trans|C}} |