p5-util

Download the raw code.

# From http://rosettacode.org/wiki/Longest_common_subsequence#Perl_6
# Be advised: I was not the original author of this code; I adapted and
# refactored it to match the way I would have written it, but it may count
# as plagiarism to you.

sub lcs ( Str $xstr, Str $ystr ) {
    my @xs = $xstr.comb;
    my @ys = $ystr.comb;

    my @lengths = map { [ 0 xx (1+@ys) ] }, ^(1+@xs);

    for @xs.keys X @ys.keys -> $i, $j {
        @lengths[$i+1][$j+1] = @xs[$i] eq @ys[$j]
            ??   @lengths[$i][$j]+1
            !! ( @lengths[$i][$j+1], @lengths[$i+1][$j] ).max;
    }

    my ( $x, $y ) = ( +@xs, +@ys );
    my @r = gather while $x and $y {
        my    $len_xy = @lengths[$x][$y];
        if    $len_xy == @lengths[$x-1][$y  ] { $x-- }
        elsif $len_xy == @lengths[$x  ][$y-1] { $y-- }
        else {
            take @xs[$x-1];
            $x--;
            $y--;
        }
    }

    return @r.reverse.join('');
}

my ( $s1, $s2 ) = $*IN.lines;
say lcs( $s1, $s2 );

Readability

Short and sweet, and readable.

Consistency

I think line 20 is either too aligned vertically with its two subsequent lines, or not enough. Depending how you see it.

There's a nice symmetry going on at the naming level with $xstr, @xs, and $x (and $ystr, @ys, and $y). It almost makes $i and $j feel a bit lonely and out-of-place.

Clarity of intent

No real complaint here. The DP table approach is not explained in the program, but there's a link to the original code, which is fine.

Algorithmic efficiency

This algorithm is O(n₁n₂), where n₁ and n₂ are the lengths of $xstr and $ystr, respectively. That's not extremely fast compared to what could be acheived in this task.

Idiomatic use of Perl 6

I think this is the first gather while that I've seen. (It has to be that and not for because we're counting down two things at once, and the order of the counting-down depends on the data.)

That's a lazy use of $*IN.lines on line 33. I'm not sure whether that practice should be encouraged, but it definitely works.

Brevity

Nice and short.