Perl Weekly Challenge: Who’s Kolakoski?

Posted on by

Perl Weekly Challenge 356‘s tasks are “Kolakoski Sequence” and “Who Wins”. Not being as fluent with the OEIS as I ought to be, my first thought was “Who?”

And, naturally, my musical brain went to The Who. So let’s take the tube back out of town to the Perl Weekly Challenge!

Task 1: Kolakoski Sequence

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 information.

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

Approach

According to the cited Wikipedia article, the algorithm for producing this sequence is

The Kolakoski sequence may be generated by an algorithm that, in the i-th iteration, reads the value xi that has already been output as the i-th value of the sequence (or, if no such value has been output yet, sets xi = i). Then, if i is odd, it outputs xi copies of the number 1, while if i is even, it outputs xi copies of the number 2.

So, to rephrase, when $int is 1, we return the sequence 1. Otherwise, we set the character to be added to the sequence (let’s call it $digit) to be 1 if $int is odd or 2 if $int is even. We then look at the $int-th character in the previous sequence: if it’s 1, we add one copy of $digit to the sequence, and if it’s 2, we add two copies of $digit to the sequence.

This will be using substr-like functions to get the $int-th character from the sequence. It’s probably going to be faster if we cache the results of previous calculations, because when we have to calculate kolakoski(8) we’ll already have calculated kolakoski(7), so we shouldn’t have to calculate it again.

What confused me, however, was what count “the count of 1 in the generated sequence” was referring to. Looking at the examples, it appears to be asking for the number of 1 characters in the first $int characters of the sequence.

Of course, because the way the sequence works, we could much more easily calculate the count using (($int - 1) div 2) + 1).

Raku

I’m still agog (since PWC 285) that  the is cached trait is still experimental in Raku. I’m generating the sequence with parens in it because that’s how the examples show them; I wouldn’t have to if I didn’t want to reproduce that output.

use experimental :cached;

sub kolakoski($int) is cached {
  return "(1)" if $int == 1;
  my $digit = ($int % 2) ?? "1" !! "2";
  my $seq   = kolakoski($int - 1);
  my $chars = $seq.comb(/\d/).join("");
  if (substr($chars, $int - 1, 1) eq "1") {
    $seq ~= "($digit)";
  }
  else {
    $seq ~= "($digit$digit)";
  }
  return $seq;
}

sub kolakoskiSequence($int) {
  my $seq   = kolakoski($int);
  my $chars = $seq.comb(/\d/).join("").substr(0, $int);
  my $count = $chars.comb(/1/).elems;
  return ($count, "$seq => $chars");
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
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

Perl

In Perl, of course I used the Memoize module. Unlike Raku, I wasn’t able to filter characters out of strings and perform substr or count the results in a single line, so the kolakoskiSequence function wound up being two lines longer.

use Memoize;
memoize('kolakoski');

sub kolakoski($int) {
  return "(1)" if $int == 1;
  my $digit = ($int % 2) ? "1" : "2";
  my $seq   = kolakoski($int - 1);
  (my $chars = $seq) =~ s/\D//g; # get rid of the parens
  if (substr($chars, $int - 1, 1) eq "1") {
    $seq .= "($digit)";
  }
  else {
    $seq .= "($digit$digit)";
  }
  return $seq;
}

sub kolakoskiSequence($int) {
  my $seq   = kolakoski($int);
  (my $chars = $seq) =~ s/\D//g; # get rid of the parens
  $chars = substr($chars, 0, $int);
  (my $countchars = $chars) =~ s/2//g; # get rid of 2s
  my $count = length($countchars);
  return ($count, "$seq => $chars");
}

View the entire Perl script for this task on GitHub.

Python

Caching in Python comes from @functools.cache.

from functools import cache
import re

@cache
def kolakoski(num):
  if num == 1: return "(1)"
  digit = "1" if (num % 2) == 1 else "2"
  seq   = kolakoski(num - 1)
  chars = re.sub(r'\D', "", seq) # get rid of the parens
  if chars[num - 1:num] == "1":
    seq += f"({digit})" 
  else:
    seq += f"({digit}{digit})"
  return seq

def kolakoski_sequence(num):
  seq   = kolakoski(num)
  chars = (re.sub(r'\D', '', seq))[0:num]
  count = len(re.sub(r'2', '', chars)) # get rid of 2s
  return (count, f"{seq} => {chars}")

View the entire Python script for this task on GitHub.

Elixir

This time, because I needed to do require Integer to access is_odd/1 (because it’s defined as a macro), I decided to see if I could import the other functions I was using… and I found out that I could! By importing the functions/macros I was using, I no longer needed to qualify them when I called them.

import Integer, only: [is_odd: 1] # needed for is_odd/1
import Regex, only: [replace: 3]
import String, only: [slice: 2]

def kolakoski(int) when int == 1, do: "(1)"

  def kolakoski(int) do
    digit = if is_odd(int) do "1" else "2" end
    int   = int - 1
    seq   = kolakoski(int)
    chars = replace(~r/\D/, seq, "") # get rid of the parens
    if slice(chars, int..int) == "1" do
      seq <> "(#{digit})"
    else
      seq <> "(#{digit}#{digit})"
    end
  end

def kolakoski_sequence(int) do
  seq   = kolakoski(int)
  chars = replace(~r/\D/, seq, "") |> slice(0..(int-1))
  {
    replace(~r/2/, chars, "") |> String.length, # get rid of 2s
    "#{seq} => #{chars}"
  }
end

View the entire Elixir script for this task on GitHub.

Task 2: Who Wins

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

In the final week, Team 2 (home) won against 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"

Approach

Since my sports upbringing is rooted in Baseball and nothing else, I needed to ask for help understanding this problem. So, naturally, I turned to someone more versed in sports language than I am: my wife.

Specifically, she helped me understand the “Team 1 hosts the third seeded winner from the previous week” portion of the instructions. Only the first example provided any concrete examples of how that worked, and she confirmed that my suspicion was correct: I needed to rank the winners by their seeding position (in example 1, that would be 2, 4, 6) and then pick the third from that list. Since there’s only three winners in the first week, I feel like I would have understood the instruction more easily if it had been worded “the lowest seeded winner from the previous week”.

So, to figure out the winner, I’m going to start with a list of tuples: (2,7), (3,6), (4,5). For the first three characters of $results, we’ll use that to generate a list of winners from the first week (in example 1, that list would be (2, 6, 4)). We’ll then take the max value from that list (the lowest seeded winner), and put that value up against 1, yielding two more tuples (in example 1, that list would be (1,6), (2,4))…. though, now that I think about it, it’s probably easier to sort the winners and then pop the lowest seed off the list, since that will give us the other tuple we need. We then use the next two characters from $results to generate the final tuple (in example 1, (2, 6)) and then we use the last character in $results to find the winner.

Raku

In Raku, the type we want to use to implement a tuple is List, because it’s an immutable Positional. One of the things we can do with a tuple is unpack its values into individual variables, which Im doing on line 8 so it’s easy to see whether any particular game was won by the $home or $away team. We’re returning the @winners as an Array, however, because we want to modify the sorted list by removing the last element (which is the lowest seeded winner).

In week 3, the @winners array will only have one result. To find out which team lost that week, I grep through the two values in the List that was sent into whoWinsTuples to find the value that doesn’t match $win.

sub whoWinsTuples($results, @tuples) {
  my @winners;
  for $results.comb Z @tuples -> [$result, @tuple] {
    my ($home, $away) = @tuple;
    @winners.push: ($result eq 'H' ?? $home !! $away);
  }
  return @winners.sort;
}

sub whoWins($results is copy) {
  # week 1
  my @tuples = [(2,7), (3,6), (4,5)];
  my @winners = whoWinsTuples($results.substr(0, 3), @tuples);
  $results.substr-rw(0, 3) = ''; # remove the first 3 results
  my $lowest = @winners.pop;

  # week 2
  @tuples = [(1, $lowest), @winners];
  @winners = whoWinsTuples($results.substr(0, 2), @tuples);
  $results.substr-rw(0, 2) = ''; # remove the next 2 results

  # week 3
  @tuples = [ [ @winners ], ];
  @winners = whoWinsTuples($results, @tuples);

  my $win  = @winners[0];
  my $loss = @tuples[0].grep({ $_ != $win }).first;
  return "Team $win defeated Team $loss";
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: $results = "HAHAHH"
Output: Team 2 defeated Team 6

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

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

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

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

Perl

In Perl, however, a List is a literal value and not a variable, and there’s no tuple type, so we’re just using references to arrays to stand in for our tuples. One thing that I’m using a lot between lines 7-10 is the @{[ ... ]} construction, which forces the code inside to be evaluated in list context. It’s necessary because the argument to sort has to be an array, as does the 2nd and 3rd arguments to List::AllUtils’ pairwise.

use List::AllUtils qw( pairwise );

sub whoWinsTuples($results, $tuples) {
  return sort @{[ pairwise {
    my ($home, $away) = @$b;
    $a eq 'H' ? $home : $away
  } @{[split //, $results]}, @$tuples ]};
}

sub whoWins($results) {
  # week 1
  my $tuples = [[2,7], [3,6], [4,5]];
  my @winners = whoWinsTuples(substr($results, 0, 3), $tuples);
  substr($results, 0, 3) = ''; # remove the first 3 results
  my $lowest = pop @winners;

  # week 2
  $tuples = [[1, $lowest], [ @winners ] ];
  @winners = whoWinsTuples(substr($results, 0, 2), $tuples);
  substr($results, 0, 2) = ''; # remove the next 2 results

  # week 3
  $tuples = [ [ @winners ], ];
  @winners = whoWinsTuples($results, $tuples);

  my $win  = $winners[0];
  my $loss = first_value { $_ != $win } @{$tuples->[0]};
  return "Team $win defeated Team $loss";
}

View the entire Perl script for this task on GitHub.

Python

Python, however, has an actual tuple type. By creating the team pairs with parentheses instead of square brackets, they’re instantiated as tuples, not arrays, and there’s a built-in tuple that converts an enumerable (i.e., an array) into an immutable tuple. I’m also using a built-in function I keep forgetting about: next.

def who_wins_tuples(results, tuples):
  results = [ r for r in results ]
  winners = []
  for result, tupl in zip(results, tuples):
    home, away = tupl
    winners.append(home if result == "H" else away)
  return sorted(winners)

def who_wins(results):
  # week 1
  winners = who_wins_tuples(results[0:3], [(2,7), (3,6), (4,5)])
  results = results[3:] # remove the first 3 results
  lowest  = winners.pop()

  # week 2
  tuples  = [ (1, lowest), tuple(winners) ]
  winners = who_wins_tuples(results[0:2], tuples)
  results = results[2:] # remove the next 2 results

  # week 3
  tuples  = [ tuple(winners), ]
  winners = who_wins_tuples(results, tuples)

  win  = winners[0]
  loss = next(( loss for loss in tuples[0] if loss != win ))
  return(f"Team {win} defeated Team {loss}")

View the entire Python script for this task on GitHub.

Elixir

But I really like how Elixir handles Tuples. They’re a built-in data structure, and because of the syntax used to define them, you can unpack tuples right in a function signature (see line 11). Also, there are functions that return tuples, like List.pop_at/3, which returns a tuple of the item removed from a list and the list without the removed item (see line 23).

import Enum,   only: [find: 2, sort: 1, zip_with: 2]
import List,   only: [pop_at: 2, to_tuple: 1]
import String, only: [graphemes: 1, slice: 2]
import Tuple,  only: [to_list: 1]

def who_wins_tuples(results, tuples) do
  results = graphemes(results)
  zip_with([results, tuples], fn [result, { home, away }] ->
    if result == "H" do home else away end
  end) |> sort
end

def who_wins(results) do
  # week 1
  winners = who_wins_tuples(
    slice(results, 0..2),
    [ {2,7}, {3,6}, {4,5} ]
  )
  results = slice(results, 3..6) # remove the first 3 results
  {lowest, winners} = pop_at(winners, -1)

  # week 2
  winners = who_wins_tuples(
    slice(results, 0..1),
    [ {1, lowest}, to_tuple(winners) ]
  )
  results = slice(results, 2..2) # remove the next 2 results

  # week 3
  tuples  = [ to_tuple(winners) ]
  winners = who_wins_tuples(results, tuples)

  win  = hd(winners)
  loss = hd(tuples) |> to_list |> find(fn x -> x != win end)

  "Team #{win} defeated Team #{loss}"
end

View the entire Elixir script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-356/packy-anderson

Leave a Reply