Re: Find Length Of Longest Ascending/Descending Sequence

[ambrus]

Let me try to make a solution without looking at the other replies.

I apologize in advance, for such an APL-style solution translates to very ugly code in perl. It would look nicer in haskell or some ml or apl language, but I'll stick to perl in this reply. In fact the code looks a bit like some of my prolog homework, where more than half of the code is defining several generic list handling functions.

use warnings; use strict;

my $s = @ARGV ? $ARGV[0] : "82665409266027476709324472";

use List::Util qw"min";
sub zip {
    my($p, $x, $y) = @_;
    map { scalar &$p($$x[$_], $$y[$_]) } 0 .. min(@$x - 1, @$y - 1);
}
sub zipadj2 { 
    my($p, @y) = @_;
    zip $p, [@y[0 .. @y - 2]], [@y[1 .. @y - 1]];
}
sub scanr1 (&@) {
    my($p, @y) = @_;
    my @r = my $m = pop @y;
    for my $y (reverse @y) {
        unshift @r, ($m = &$p($y, $m));
    }
    @r;
}
sub maxind {
    my(@y) = @_;
    my($p, $m) = (0, $y[0]);
    for my $i (1 .. @y - 1) {
        if ($m < $y[$i]) { ($p, $m) = ($i, $y[$i]); }
    }
    wantarray ? ($p, $m) : $p;
}

my @s = split //, $s;
my @d = map { do { no integer; $_ % 10 } } 
    zipadj2 sub { my($a, $w) = @_; $a - $w }, @s;
my $lu = sub { 
    my($k) = @_;
    my($p, $m) = maxind scanr1 sub { my($x, $y) = @_; $x * (1 + $y) },
+ 
        map { $k == $_ } @d;
    $p, $m + 1;
};
my($p1, $l1) = &$lu(1); # decreasing
my($p9, $l9) = &$lu(9); # increasing
my($p, $l) = $l9 <= $l1 ? ($p1, $l1) : ($p9, $l9);
print "The longest subsequence you want starts at position ", $p, 
    " and has length ", $l, " and its contents are (",
    join("", @s[$p .. $p + $l - 1]), ").\n";
my $v = $s;
substr $v, $p + $l, 0, ")";
substr $v, $p, 0, "(";
print "In context, it's here: ", $v, ".\n";

__END__

Update: thanks for the test cases, wind.

Update: It turns out, it comes out pretty ugly and long in Haskell too. (Maybe that's because I don't have too much practice in Haskell.)

import Data.Char (digitToInt, intToDigit);
import Data.List (elemIndex);
import Data.Maybe (fromJust);
import System (getArgs);

egin :: String;
egin = "82665409266027476709324472";

zipadj2 :: (a -> a -> b) -> [a] -> [b];
zipadj2 p y = zipWith p (init y) (tail y);

main = do {    
    args <- getArgs;
    let { 
        ss = head (args ++ [egin]); 
        s = map digitToInt ss;
        d = map (flip mod 10) (zipadj2 (-) s);
        gr x y = x * succ y;
        lu k = let {
            h = scanr1 gr (map (fromEnum . (k ==)) d :: [Int]);
            mh = maximum h;
        } in (fromJust (elemIndex mh h), succ mh);
        pl1@(_, l1) = lu 1;
        pl9@(_, l9) = lu 9;
        (p, l) = if l9 <= l1 then pl1 else pl9;
        fs = map intToDigit;
    };
    putStr ("The longest subsequence you want starts at position " ++ 
        show p ++ " and has length " ++ show l ++ " and its contents a
+re (" ++
        fs (take l (drop p s)) ++ ").\n" ++ 
        "In context, it's here: " ++
        fs (take p s) ++ "(" ++ fs (take l (drop p s)) ++ ")" ++
        fs (drop l (drop p s)) ++ ".\n");
};