Calculate Lempel-Ziv complexity of beatmap note intervals

osu_lz.pl

use 5.01;
use warnings;
use strict;
use Data::Dump;

for my $bm (glob "beatmaps/*") {
   say "\n### " . substr($bm, 9) . " ###";
   my $deltas = beatmap_deltas($bm);
   say "Length: " . sum($deltas) / 1000 . "s";
   say "Intervals: " . ($#$deltas + 1);
   say "Lempel-Ziv: " . (my $lz = lempel_ziv($deltas));
   say "LZ / Intervals: " . (sprintf "%.2f (%%)", my $ratio = 100 * $lz / ($#$deltas + 1));
}

sub beatmap_deltas {
   open my $fh, "<", shift or warn $! and return;
   my $prev;
   my $label = '';
   my @deltas;

   while (my $line = <$fh>) {
      if ($line =~ /^\[(.+)\]/) {
         $label = $1;
      }
      elsif ($label eq 'HitObjects' and $line =~ /^[^,]+,[^,]+,(\d+)/) {
         if ($prev) {
            my $delta = $1 - $prev;
            # We consider deltas longer than 4 seconds to be breaks
            push @deltas, $delta if $delta < 4000;
         }
         $prev = $1;
      }
   }

   \@deltas;
}

sub lempel_ziv {
   my @S = @{ +shift };
   my $i = 0;
   my $C = 1;
   my $u = 1;
   my $v = 1;
   my $vmax = $v;
   while ($u + $v <= $#S) {
      # We consider intervals within 2ms of each other equal
      if (abs($S[$i + $v] - $S[$u + $v]) <= 2) {
         $v += 1;
      }
      else {
         $vmax = $v if $v > $vmax;
         $i += 1;
         if ($i == $u) {
            $C += 1;
            $u += $vmax;
            $v = 1;
            $i = 0;
            $vmax = $v;
         }
         else {
            $v = 1;
         }
      }
   }
   $C += 1 if $v != 1;

   return $C;
}

sub sum {
   my $n = 0;
   $n += $_ for @{ +shift };
   $n;
}