16 January 2026

Challenge 356

Self-Generating Games

• Task 1: Kolakoski Sequence
• Task 2: Who Wins

Task 1: Kolakoski Sequence

Submitted by: Mohammad Sajid Anwar

---

You are given an integer, $int > 3.

Write a script to generate the Kolakoski Sequence of given length $int and return the count of 1 in the generated sequence. Please follow the wikipedia page for more informations.

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

---

Solution

One way to generate the Kolakosi sequence of \(n\) runs follows this procedure:

The generated sequence is split into two parts:

• a head containing all elements that have already been used to generate a run and
• a tail from the remaining elements that have been generated, but not used as length yet.

To augment the sequence by one run,

• find the element of the next run from the length of the head. Select 1 for even and 2 for odd length
• find the run length as the first element from the tail
• append the new run to the tail
• move the first character from the tail to the end of the head
• the procedures starts with head (1, 2) and tail (2)

Afterwards, the generated ones need to be counted, which is a nice subtlety as the leading one is not generated and thus does not count.

A level of caching may be added:
The sequence of \(k \le n\) runs can easily be extracted from the longer sequence, as the length of the \(k\)-runs sequence is the sum over the first \(k\) elements. Once a sequence is generated, it can be used to process all shorter sequences. The longest generated sequence will be kept.

If the cached sequence has a head as least as long as \(k\), it may be used unaltered. Otherwise as many runs need to be added as the head is shorter than \(k\).

The procedure is applicable to any non-negative number \(k\) of runs.

J

Creating a class Kolakosi.

A Kolokosi sub-sequence is stored as an array of the boxed head and the boxed tail.

The verb run adds one additional run to the cached sequence.

The verb count counts the generated 1’s in x runs from a sufficiently large sub-sequence y

The method ones augments the cached sequence as needed by calling run the required number of times and then returns the number of generated ones in the specified number of runs.

coclass 'Kolakosi'
create =: 3 : 'sequence =: (1, 2); 2'
destroy =: codestroy
run =: ((, {.@]) ; }.@] , {.@] # >:@(2&|)@#@[)&>/
count =: +/@(1&(e.~))@(3&}.)@([ (+/@{. {. ]) ;@])
ones =: 3 : 0
    sequence =: run^:(0&>.@(y&-)@#@>@{.@]) sequence
    y count sequence
)

cocurrent 'base'
K =: 0 conew 'Kolakosi'
echo ones__K 6

For visualization, here are the intermediate results from calling run several times on the initial sequence, resulting in 6 runs:

  run^:(<5) 1 2; 2

head	tail
1 2	2
1 2 2	1 1
1 2 2 1	1 2
1 2 2 1 1	2 1
1 2 2 1 1 2	1 2 2

See the full solution.

Perl

The Perl solution was derived from its J counterpart, got the caching added, which in turn was adapted into the J solution.

use strict;
use warnings;
use List::Util 'sum0';

sub kolakosi ($k) {
    state $head = [1, 2];
    state $tail = [2];
    state $run = sub {
        push @$tail, (@$head % 2 + 1) x $tail->[0];
        push @$head, shift @$tail;
    };
    $run->() for @$head .. $k - 1;
    my $len = sum0 $head->@[0 .. $k - 1];
    scalar grep $_ == 1, (@$head, @$tail)[3 .. $len - 1];
}

See the full solution to task 1.

Task 2: Who Wins

Submitted by: Simon Green

---

It’s NFL playoff time. Since the 2020 season, seven teams from each of the league’s two conferences (AFC and NFC) qualify for the playoffs based on regular season winning percentage, with a tie-breaking procedure if required. The top team in each conference receives a first-round bye, automatically advancing to the second round.

The following games are played. Some times the games are played in a different order. To make things easier, assume the order is always as below.

• Week 1: Wild card playoffs
  • Team 1 gets a bye
  • Game 1: Team 2 hosts Team 7
  • Game 2: Team 3 hosts Team 6
  • Game 3: Team 4 hosts Team 5
• Week 2: Divisional playoffs
  • Game 4: Team 1 hosts the third seeded winner from the previous week.
  • Game 5: The highest seeded winner from the previous week hosts the second seeded winner.
• Week 3: Conference final
  • Game 6: The highest seeded winner from the previous week hosts the other winner You are given a six character string containing only H (home) and A away which has the winner of each game. Which two teams competed in the the conference final and who won?

Example 1

NFC Conference 2024/5. Teams were Detroit, Philadelphia, Tampa Bay,
Los Angeles Rams, Minnesota, Washington and Green Bay.
Philadelphia - seeded second - won.

Input: $results = "HAHAHH"
Output: "Team 2 defeated Team 6"

In Week 1, Team 2 (home) won against Team 7, Team 6 (away) defeated Team 3 and
Team 4 (home) were victorious over Team 5. This means the second week match ups
are Team 1 at home to Team 6, and Team 2 hosted Team 4.

In week 2, Team 6 (away) won against Team 1, while Team 2 (home) beat Team 4.
The final week was Team 2 hosting Team 6

Example 2

AFC Conference 2024/5. Teams were Kansas City, Buffalo, Baltimore, Houston,
Los Angeles Charges, Pittsburgh and Denver.
Kansas City - seeded first - won.

Input: $results = "HHHHHH"
Output: "Team 1 defeated Team 2"

Example 3

AFC Conference 2021/2. Teams were Tennessee, Kansas City, Buffalo, Cincinnati,
Las Vegas, New England and Pittsburgh.
Cincinnati - seeded fourth - won.

Input: $results = "HHHAHA"
Output: "Team 4 defeated Team 2"

Example 4

NFC Conference 2021/2. Teams were Green Bay, Tampa Bay, Dallas, Los Angeles Rams,
Arizona, San Francisco and Philadelphia.
The Rams - seeded fourth - won.

Input: $results = "HAHAAH"
Output: "Team 4 defeated Team 6"

Example 5

NFC Conference 2020/1. Teams were Green Bay, New Orleans, Seattle, Washington,
Tampa Bay, Los Angeles Rams and Chicago.
Tampa Bay - seeded fifth - won.

Input: $results = "HAAHAA"
Output: "Team 5 defeated Team 1"

---

Solution

This was a difficult one. Not so much in implementing a solution, but in understanding the procedure. Tried some interpretations until the examples were reproduced.

The solution is basically a chain of index and sort operations on a matrix containing the setup for week 1.

Using the results as indices into the starting matrix produces the winners of week 1, which are then sorted and arranged into the matrix for week 2. Indexing and sorting again reveals the finalists on which the final result can be applied.

To unify the process, team 1 is set as a participant in week 1 playing against itself and therefore always reaching week 2. Accordingly, a dummy result is prepended to the results.

Perl

Here indexND is used extract elements from a matrix into an array and index1d to arrange an array as a matrix.

use strict;
use warnings;
use PDL;
use PDL::NiceSlice;

sub who_wins {
    my $result = long 0, split //, shift =~ tr/HA/01/r;
    state $week1 = long [1, 1], [2, 7], [3, 6], [4, 5];
    state $iweek2 = long [0, 3], [1, 2];
    my $s1 = cat(sequence(4), $result(0:3))->xchg(0, 1);
    my $s2 = cat(sequence(2), $result(4:5))->xchg(0, 1);
    my $s3 = $result(6) ? indx(1, 0) : indx(0, 1);

    $week1->xchg(0, 1)->indexND($s1)->qsort->index1d($iweek2)->xchg(0, 1)
        ->indexND($s2)->qsort->index1d($s3);
}

See the full solution to task 2.

J

The verb { (“From”) can be used for all kinds of index operations.

require 'format/printf'

WhoWins =: 3 : 0
    result =. 0, y e. 'A'
    week1 =. (1, 1), (2, 7), (3, 6) ,: 4, 5
    iweek2 =. 0 3,: 1 2
    s1 =. ;/ (i.4) ,. (i.4) { result
    s2 =. ;/ (i.2) ,. (4 + i.2) { result
    s3 =. 6 { result
    |.^:s3 /:~ s2 { iweek2 { /:~ s1 { week1
)

'Team %d defeated Team %d' printf WhoWins 'HAHAHH'

The dissected processing of example 1:

See the full solution to task 2.