comparing three solutions to week 228 of https://theweeklychallenge.org/blog/perl-weekly-challenge-228/

perf_measurement.raku

#!/usr/bin/env raku

#|[
Task 2: Empty Array
- You are given an array of integers in which all elements are unique.
- Write a script to perform the operation:
  - If the first element is the smallest then remove it otherwise move it to the end.
  until the array is empty and return the total count of operations.
]
sub task2_rcmlz(@input) {
  my UInt $operations = 0;
  my @working = @input;

  for @input.sort -> $element { 
    my $pos = @working.first($element, :k);
    @working = @working.rotate($pos);
    @working.shift;
    $operations += $pos;
  }
  return $operations + @input.elems;
}

sub task2_liz(*@input) {
    my uint $operations;

    while @input {
        my $target = @input.shift;
        @input.push($target) with @input.first(* < $target);
        ++$operations;
    }
    $operations
}

sub task2_rcmlz_dp(@input) { # O(n^2)

  # later replace with @input.sort(:k).antipairs; when Raku was updated to version ?
  my %rank-and-position = &sort_rank(@input).antipairs;

  my $n = @input.elems;
  my @rotation_dp[$n];
  my @position_dp[$n];

  # DP initial values
  for ^$n -> $rank {
      @position_dp[$rank] = %rank-and-position{$rank};
      @rotation_dp[$rank] = 0;
  }
  
  # DP initially smallest element moved to front
  @rotation_dp[0] = @position_dp[0];
  @position_dp[0] = 0;

  # DP calc positions of all relevant elements and rotations caused by current 
  # min-rank element based on rotation of last round
  for 1..^$n -> $min-rank {
      my $predecessor-rank = $min-rank - 1;
      for $min-rank..^$n -> $rank {
          @position_dp[$rank] = (@position_dp[$rank] - @rotation_dp[$predecessor-rank] - $predecessor-rank) mod ($n - $predecessor-rank) + $predecessor-rank;
      }
      @rotation_dp[$min-rank] = @position_dp[$min-rank] - $min-rank;
  }
  return @rotation_dp.sum + $n;
}

sub sort_rank(@input) {
  my @output;
  my $rank = 0;

  for @input.sort -> $element {
    my $pos = @input.first($element, :k);
    @output[$pos] = $rank;
    $rank++;
  }

  return @output;
}

my @input = (^4000).pick(*);
my $start;

for &task2_rcmlz, &task2_rcmlz_dp, &task2_liz -> &fun {
  $start = now;
  say &fun(@input) ~ " in " ~ (now - $start).Int ~ " sec ";   
}

use Test;

my @testcases = (
	  {input => [1], output => 1, description=>"single"},
	  {input => (1, 2), output => 2, description=>"double sorted"},
	  {input => (2, 1), output => 3, description=>"double unsorted"},
	  {input => (1, 2, 3), output => 3, description=>"tripple sorted"},
	  {input => (2, 1, 3), output => 5, description=>"tripple unsorted"},
	  {input => (3, 4, 2, 5), output => 7, description=>"unsorted"},
	  {input => (3, 1, 0, 2), output => 8, description=>"unsorted"},
	  {input => (0, 2, 1, 3), output => 6, description=>"unsorted"},
	  {input => (4, 2, 0, 1, 3), output => 9, description=>"unsorted"},
  	{input => (0, 4, 1, 3, 2), output => 8, description=>"unsorted"},

  	#Operation 1: move 3 to the end: (4, 2, 3)
	  #Operation 2: move 4 to the end: (2, 3, 4)
	  #Operation 3: remove element 2: (3, 4)
	  #Operation 4: remove element 3: (4)
	  #Operation 5: remove element 4: ()
	  {input => (3, 4, 2), output => 5, description=>"unsorted"},

  	#Operation 1: remove element 1: (2, 3)
	  #Operation 2: remove element 2: (3)
	  #Operation 3: remove element 3: ()
    {input => (1, 2, 3), output => 3, description=>"sorted"},
);
is task2_rcmlz($_<input>), $_<output>, $_<description> for @testcases;
is task2_rcmlz_dp($_<input>), $_<output>, $_<description> for @testcases;
is task2_liz($_<input>.flat), $_<output>, $_<description> for @testcases;