ZigZag Reorder with Raku

This is my response to The Weekly Challenge #389.

Input: $melody = ['Bach', [qw(C D E F# G A B)], [7, 1, 6, 2, 5, 3, 4]]
Output: BACH => D F# A B G E C

Note 1 (C)  moves to position 7.
Note 2 (D)  moves to position 1.
Note 3 (E)  moves to position 6.
Note 4 (F#) moves to position 2.
Note 5 (G)  moves to position 5.
Note 6 (A)  moves to position 3.
Note 7 (B)  moves to position 4.

Input: $melody = ['Beethoven', [qw(C D F# G Ab)], [1, 3, 5, 2, 4]]
Output: BEETHOVEN => C G D Ab F#

Note 1 (C)  stays at position 1.
Note 2 (D)  moves to position 3.
Note 3 (F#) moves to position 5.
Note 4 (G)  moves to position 2.
Note 5 (Ab) moves to position 4.

Input: $melody = [ 'Brahms', [qw(C Db Eb F G Ab Bb C D)], \
    [9, 3, 7, 1, 8, 5, 2, 6, 4]]
Output: BRAHMS => F Bb Db D Ab C Eb G C

Input: $melody = [ 'Bruckner', [qw(G F# Bb C D Eb F)], \
    [4, 7, 2, 6, 1, 5, 3]]
Output: BRUCKNER => D Bb F G Eb C F#

Input: $melody = ['Berg', [qw(C#)], [1]]
Output: BERG => C#

#! /usr/bin/env raku

unit sub MAIN ($composer, $notes, $order, :v(:$verbose));

my @notes = $notes.words;
my @order = $order.words.map: * - 1;

say ": Order @order[]" if $verbose;

my @result;
@result[@order] = @notes;

say "{ $composer.uc } => @result[]";

[3] Three strings. (Not in a string instrument sense, though.)

[5] Split the notes string into individual notes (with words).

See docs.raku.org/routine/words for more information about words.

[6] Split the order string as well, and use map to subtract one from each index value - so that we can use them as array indices. (They are given with 1 as the lowest value, and arrays start at index 0.)

See docs.raku.org/routine/map for more information about map.

[10] The result will end up here.

[11] We use an array slice (a list of indices) on the left hand side, to assign the notes to the correct position.

[13] Print the composer (upper cased with uc) and the reordered notes.

See docs.raku.org/routine/uc for more information about uc.

Running it:

$ ./reorder-notes "Bach" "C D E F# G A B" "7 1 6 2 5 3 4"
BACH => D F# A B G E C

$ ./reorder-notes "Beethoven" "C D F# G Ab" "1 3 5 2 4"
BEETHOVEN => C G D Ab F#

$ ./reorder-notes "Brahms" "C Db Eb F G Ab Bb C D" "9 3 7 1 8 5 2 6 4"
BRAHMS => F Bb Db D Ab C Eb G C

$ ./reorder-notes "Bruckner" "G F# Bb C D Eb F" "4 7 2 6 1 5 3"
BRUCKNER => D Bb F G Eb C F#

$ ./reorder-notes "Berg" "C#" "1"
BERG => C#

Looking good.

With verbose mode:

$ ./reorder-notes -v "Bach" "C D E F# G A B" "7 1 6 2 5 3 4"
: Order 6 0 5 1 4 2 3
BACH => D F# A B G E C

$ ./reorder-notes -v "Beethoven" "C D F# G Ab" "1 3 5 2 4"
: Order 0 2 4 1 3
BEETHOVEN => C G D Ab F#

$ ./reorder-notes -v "Brahms" "C Db Eb F G Ab Bb C D" "9 3 7 1 8 5 2 6 4"
: Order 8 2 6 0 7 4 1 5 3
BRAHMS => F Bb Db D Ab C Eb G C

$ ./reorder-notes -v "Bruckner" "G F# Bb C D Eb F" "4 7 2 6 1 5 3"
: Order 3 6 1 5 0 4 2
BRUCKNER => D Bb F G Eb C F#

$ ./reorder-notes -v "Berg" "C#" "1"
: Order 0
BERG => C#

Input: @nums = (9, 4, 2, 10, 7, 8, 8, 1, 9)
Output: 5

ZigZag subarray: (4, 2, 10, 7, 8)

Input: @nums = (1, 7, 4, 9, 2, 5)
Output: 6

ZigZag subarray: (1, 7, 4, 9, 2, 5)

Input: @nums = (1, 2, 3, 4, 5)
Output: 2

ZigZag subarray: (1, 2)

Input: @nums = (4, 4, 4)
Output: 1

Input: @nums = (10, 20, 15, 12, 18)
Output: 3

ZigZag subarray: (10, 20, 15)

#! /usr/bin/env raku

unit sub MAIN (*@nums is copy where @nums.elems > 0
                 && all(@nums) ~~ Int,
               :v(:$verbose));

my @all = gather
{
  my $direction;                      
  my @path = @nums.shift.Int,;

  for @nums -> $curr
  {
    my $new-direction = ( $curr <=> @path[*-1] ).Int;

    print ": ({ @path.join(",") }) + $curr d:$new-direction \
      o:{ $direction // "-"}" if $verbose;

    if @path.elems == 1
    {
      if $new-direction == 0
      {
        @path      = $curr.Int,;
        $direction = Nil;
	
        say " equal" if $verbose;
      }
      else
      {
        @path.push($curr.Int);
        $direction = $new-direction;

        say " init" if $verbose;
      }
    }
    elsif $new-direction == 0
    {
      take @path.join(" ");

      @path      = $curr.Int,;
      $direction = Nil;

      say " break=" if $verbose;
    }
    elsif $new-direction == $direction
    {
      take @path.join(" ");

      @path      = @path[*-1], $curr.Int;
      $direction = $new-direction;
      
      say " break~" if $verbose;
    }
    else
    {
      @path.push($curr.Int);
      $direction = $new-direction;
      
      say " " ~ ($new-direction == 1 ?? "up" !! "down")
        if $verbose;
    }
  }

  take @path.join(" ") if @path.elems;
}

if $verbose
{
  say ": subarrays: " ~ @all.raku;
  say ": sizes: " ~ @all>>.words>>.elems.raku;
};

say @all>>.words>>.elems.max;

[3] A slurpy array of integers, with at least 1 element.

[7] Using gather/take to collect all the legal (zigzag wise) subarrays.

See my Raku Gather, I Take article or docs.raku.org/language/control#gather/take for more information about gather/take.

[9] The direction of the last step (in @path). It is Nil if @path has 1 element (i.e. no path leading up to it).

[10] Initialise the path with the first value. The Int coercer is there to make verbose mode nicer looking. The trailing comma is the list operator.

[12] Iterate over the rest (after we retrieved the first one in [10]) of the input.

[14] Get the new direction, with the numeric comparison operator <=>. The result is an enum, so we coerce that to integers (-1, 0 and 1).

See https://docs.raku.org/routine/%26lt%3B%3D%26gt%3B for more information about the numeric comparison operator <=>.

[19] The first iteration.

[21] The same direction (and thus the same value)?

[23] Reset the path. (We could have kept it "as is", as we have the same value, but this is more explicit.)

[24] No previous path with a direction.

[30] Not the same direction, so add the value to the path.

[31] And set the direction.

[36] The same value?

[38] Return the current path (with take).

I have chosen to return the path as a space separated string, to avoid the problem of single values versus a nested data structure.

[40] Set the path to the new value only.

[41] A path with one value does not have a direction.

[45] The same direction?

[47] Return the path, as we cannot have two values in the same direction.

[49] Set the path to the last value in the old path (as it can be reused), pluss the new one.

[54] A different direction?

[56] Add the value to the path.

[64] Return the path buffer at the end, if non-empty.

[73] Split all the paths into arrays (with words), compute the number of elements in each, and print the highest one with max.

Running it:

$ ./zigzag-subarray -v 9 4 2 10 7 8 8 1 9
5

$ ./zigzag-subarray -v 1 7 4 9 2 5
6

$ ./zigzag-subarray -v 1 2 3 4 5
2

$ ./zigzag-subarray -v 4 4 4
1

$ ./zigzag-subarray -v 10 20 15 12 18
3

Looking good.

With verbose mode:

$ ./zigzag-subarray -v 9 4 2 10 7 8 8 1 9
: (9) + 4 d:-1 o:- init
: (9,4) + 2 d:-1 o:-1 break~
: (4,2) + 10 d:1 o:-1 up
: (4,2,10) + 7 d:-1 o:1 down
: (4,2,10,7) + 8 d:1 o:-1 up
: (4,2,10,7,8) + 8 d:0 o:1 break=
: (8) + 1 d:-1 o:- init
: (8,1) + 9 d:1 o:-1 up
: subarrays: ["9 4", "4 2 10 7 8", "8 1 9"]
: sizes: (2, 5, 3)
5

$ ./zigzag-subarray -v 1 7 4 9 2 5
: (1) + 7 d:1 o:- init
: (1,7) + 4 d:-1 o:1 down
: (1,7,4) + 9 d:1 o:-1 up
: (1,7,4,9) + 2 d:-1 o:1 down
: (1,7,4,9,2) + 5 d:1 o:-1 up
: subarrays: ["1 7 4 9 2 5"]
: sizes: (6,)
6

$ ./zigzag-subarray -v 1 2 3 4 5
: (1) + 2 d:1 o:- init
: (1,2) + 3 d:1 o:1 break~
: (2,3) + 4 d:1 o:1 break~
: (3,4) + 5 d:1 o:1 break~
: subarrays: ["1 2", "2 3", "3 4", "4 5"]
: sizes: (2, 2, 2, 2)
2

$ ./zigzag-subarray -v 4 4 4
: (4) + 4 d:0 o:- equal
: (4) + 4 d:0 o:- equal
: subarrays: ["4"]
: sizes: (1,)
1

$ ./zigzag-subarray -v 10 20 15 12 18
: (10) + 20 d:1 o:- init
: (10,20) + 15 d:-1 o:1 down
: (10,20,15) + 12 d:-1 o:-1 break~
: (15,12) + 18 d:1 o:-1 up
: subarrays: ["10 20 15", "15 12 18"]
: sizes: (3, 3)
3

And that's it.