Weekly Challenge: Zigzag notes

Weekly Challenge 389

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. Unless otherwise stated, Copilot (and other AI tools) have NOT been used to generate the solution. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Reorder Notes

You are given an array [composer, notes, permutation], reconstruct the melody by using each permutation value as the destination position of the corresponding note. Use no explicit for, foreach, or while loops. Output each result as COMPOSER => reordered notes.

ASSUMPTION: Input is valid; the notes array and permutation array have identical lengths, and the permutation contains each position from 1 to N exactly once.

My solution

For input from the command line, I take the first value as the composer. The first half of the remaining values are the notes list (array in Perl), with the remainder making up the positions list. As it's 2016, I use ♭ and ♯ for flat and sharp, but it will accept b and # as well.

This becomes fun when you can't use for and while loops. For this I start by checking the assumptions that the input is valid. I check that the lengths of notes and positions are the same, the notes are valid, and the positions list has each value from 1 to the length of the list.

As I can't use a for loops, I use the filter function. This returns a generator, so I wrap it in the list() function to see if there are any issues

def reorder_notes(composer: str, notes: list[str], positions: list[int]) -> str:
    if len(notes) != len(positions):
        raise ValueError("The two lists must be the same length")
    if list(filter(lambda note: not re.search("^[A-G][♯♭#b]?$", note), notes)):
        raise ValueError("Invalid note")
    if list(filter(lambda i: i not in positions, range(1, len(positions) + 1))):
        raise ValueError("Missing position")

With that done, I convert the two lists into a dictionary (hash in Perl). The key is the position and the value is the note.

    music = dict(zip(positions, notes))

The last step is to sort the keys of the music dictionary (by their position) and using the map function to return the note at that position.

    ordered_music = list(map(lambda note: music[note], sorted(music)))
    return composer.upper() + " => " + " ".join(ordered_music)

The Perl solution follows the same logic, and makes use of the any, mesh and zip functions from List::Util. The most tricky part was checking the @positions array is valid. In the end, I use the zip function with two arrays, the first is the expected values and the second is the values provided sorted numerically.

use List::Util qw(any mesh zip);

sub main (@args) {
    my $composer  = shift(@args);
    my $split_pos = ( $#args + 1 ) / 2;
    my @notes     = @args[ 0 .. $split_pos - 1 ];
    my @positions  = @args[ $split_pos .. $#args ];

    if ( $#notes != $#positions ) {
        die "The two lists must be the same length\n";
    }
    if ( any { $_ !~ /^[A-G][♯♭#b]?$/ } @notes ) {
        die "Invalid note\n";
    }
    if ( any { $_->[0] != $_->[1] }
        zip( [ 1 .. $#notes + 1 ], [ sort { $a <=> $b } @positions ] ) )
    {
        die "Missing position\n";
    }

    my %music = mesh \@positions, \@notes;

    my @ordered_music = map { $music{$_} } sort { $a <=> $b } keys %music;
    say uc($composer) . " => " . join( " ", @ordered_music );
}

Examples

$ ./ch-1.py Bach C D E F♯ G A B 7 1 6 2 5 3 4
BACH => D F♯ A B G E C

$ ./ch-1.py Beethoven C D F♯ G A♭ 1 3 5 2 4
BEETHOVEN => C G D A♭ F♯

$ ./ch-1.py Brahms C D♭ E♭ F G A♭ B♭ C D 9 3 7 1 8 5 2 6 4
BRAHMS => F B♭ D♭ D A♭ C E♭ G C

$ ./ch-1.py Bruckner G F♯ B♭ C D E♭ F 4 7 2 6 1 5 3
BRUCKNER => D B♭ F G E♭ C F♯

$ ./ch-1.py Berg C♯ 1
BERG => C♯

Task 2: ZigZag Subarray

You are given an array of integers.

Write a script to find the length of the longest contiguous subarray where the numbers alternate between strictly increasing and strictly decreasing (a ZigZag pattern).

A sequence of numbers $A = [a0, a1, …, ak] with length $k >= 1 is considered a ZigZag sequence if every adjacent pair alternates direction: a_0 < a_1 > a_2 < a_3 > ... OR a_0 > a_1 < a_2 > a_3 < ...

NOTE: A single element (length 1) or any two distinct elements (length 2) are automatically valid ZigZag sequences. Equal adjacent numbers (e.g., 5, 5) break the pattern.

My solution

I start this challenge by defining a function called get_change. It takes the list (array in Perl) ints, and a position p. It returns the difference between ints[p] and ints[p+1]. If the second value is higher it returns h, s if the values are the same or l if it is lower.

def get_change(ints, p):
    i = ints[p]
    j = ints[p + 1]
    if i == j:
        return "s"
    return "h" if j > i else "l"

The main function converts all the differences in values to a string of h, s and l. It then uses a regular expression to find all sub-strings matching h?(lh)+ or l?(hl)+ or a single h or l. It returns the longest sub-string length plus 1, or 1 if all the values are the same.

def zigzag_subway(ints: list[int]) -> int:
    pattern = "".join(get_change(ints, i) for i in range(len(ints) - 1))

    return max(
        (
            len(match.group(0)) + 1
            for match in re.finditer("(h?(?:lh)+|l?(?:hl)+|[hl])", pattern)
        ),
        default=1,
    )

The Perl solution follows the same logic.

use List::Util 'max';

sub get_change( $ints, $p ) {
    my $i = $ints->[$p];
    my $j = $ints->[ $p + 1 ];
    if ( $i == $j ) {
        return "s";
    }
    return $j > $i ? "h" : "l";
}

sub main (@ints) {
    my $pattern = join "", map { get_change( \@ints, $_ ) } ( 0 .. $#ints - 1 );

    say max(
        map ( { length($_) + 1 } $pattern =~ /(h?(?:lh)+|l?(?:hl)+|[hl])/g ),
        1 );
}

Examples

$ ./ch-2.py 9 4 2 10 7 8 8 1 9
5

$ ./ch-2.py 1 7 4 9 2 5
6

$ ./ch-2.py 1 2 3 4 5
2

$ ./ch-2.py 4 4 4
1

$ ./ch-2.py 10 20 15 12 18
3