Task — Kolakoski sequence

You are given an integer, $int > 3. Write a script to generate the Kolakoski Sequence of length $int and return the count of 1 in the generated sequence. Please follow the Wikipedia page for more information.

Examples

Example 1
Input: $int = 4
Output: 2
(1)(22)(11)(2) => 1221

Example 2
Input: $int = 5
Output: 3
(1)(22)(11)(2)(1) => 12211

Example 3
Input: $int = 6
Output: 3
(1)(22)(11)(2)(1)(22) => 122112

Example 4
Input: $int = 7
Output: 4
(1)(22)(11)(2)(1)(22)(1) => 1221121

Example 5
Input: $int = 8
Output: 4
(1)(22)(11)(2)(1)(22)(1)(22) => 12211212

Analysis

This is slightly mind-blowing for a Monday morning, but coding the helpful algorithm from the Wikipedia page is straightforward.

My solution generates a million terms in the sequence in a couple of seconds and reports 499,886 ones.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2026-01-12
use utf8;     # Week 356 - task 1 - Kolakoski sequence
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

kolakoski_sequence(4);
kolakoski_sequence(10);
kolakoski_sequence(100);

sub kolakoski_sequence {
    
    my ($length, @sequence, $i, $ones, $this);
    
    # initialise
    $length = $_[0];
    @sequence = (1, 2, 2);
    $ones = 1;
    
    # add items to sequence until it reaches $length
    for ($i = 3; @sequence < $length; $i ++) {
        
        # find next digit to add (1 or 2)
        $this = $i & 1 ? 1 : 2;
        
        # add one or two of that digit
        push(@sequence, $this) for 1 .. $sequence[$i - 1];
        
        # count the ones
        $ones += $sequence[$i - 1] if $this == 1;
    }
    
    # report
    say qq[\nInput:  \$length = $length];
    say qq[Output: \$sequence = ] . join('', @sequence) . 
        qq[\n        containing $ones ones];
}

Output

Input:  $length = 4
Output: $sequence = 12211
        containing 3 ones

Input:  $length = 10
Output: $sequence = 1221121221
        containing 5 ones

Input:  $length = 100
Output: $sequence = 1221121221221121122121121221121121221
221121221211211221221121221221121121221211221221121221221
121122
        containing 49 ones