February 16, 2021 3:27 PM
We keep track of both the previous element and the current direction, either climbing up or falling down, and compute the maxima in a single scan of the list:
(define (lmax xs)
(if (null? xs) (error 'lmax "empty")
(let loop ((xs (cdr xs)) (prev (car xs)) (dir 'up) (maxs (list)))
(cond ((null? xs)
(reverse (if (equal? dir 'up) (cons prev maxs) maxs)))
((= prev (car xs)) (loop (cdr xs) prev dir maxs))
((< prev (car xs)) (loop (cdr xs) (car xs) 'up maxs))
((equal? dir 'up) (loop (cdr xs) (car xs) 'down (cons prev maxs)))
(else (loop (cdr xs) (car xs) 'down maxs))))))
Here is the sample problem:
> (lmax '(1 2 1 2 3 4 3 2 3 2 1)) (2 4 3)
You can run the program at https://ideone.com/RduLyR.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
Perl version…
say join ' ', maxima( qw(1 2 1 2 3 4 3 2 3 2 1) ); sub maxima { my @X = @_; push @X, my $left = -1e32; my @sol; while(@X>1) { push @sol,$X[0] if $left < $X[0] && $X[0] > $X[1]; $left = shift @X; } return @sol; }By James Curtis-Smith on February 16, 2021 at 3:46 PM
Here’s a solution in Python. It’s not particularly efficient, as it creates multiple copies of the input list.
from itertools import groupby def local_maxima(l): assert len(l) > 0, 'Input can\'t be empty' # Remove adjacent duplicates and add boundary elements l = [l[0] - 1] + [x for x, _ in groupby(l)] + [l[-1] - 1] return [y for x, y, z in zip(l, l[1:], l[2:]) if x < y and y > z] l = [1, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1] print(local_maxima(l))Output:
By Daniel on February 16, 2021 at 4:41 PM
Cache version
[sourcecode lang="css"]
test ;
q
;
localmaxima(list) ; Output local maxima
n i,next,previous,this
s list=$e(list)-1_” “list” “($e(list,$l(list)-1)-1)
s output=””
f i=2:1:$l(list,” “)-1 {
s this=$p(list,” “,i),previous=$p(list,” “,i-1),next=$p(list,” “,i+1)
i this>previous, this>next s output=output_this” ”
}
q $e(output,1,$l(output)-1)
By Steve on February 16, 2021 at 8:07 PM
Here is a solution in a somewhat functional style using standard R7RS
Scheme and a few well-known helpers form SRFI 1. It provides both
values and locations of the local maxima.
(import (scheme base) (only (srfi 1) circular-list filter-map iota) (scheme write)) (define samples ; ((input . output) ...) '(((1 2 1 2 3 4 3 2 3 2 1) . (1 5 8)) (() . ()) ((1) . (0)) ((1 1) . (0)) ((7 7 7) . (0)) ((7 6 7) . (0 2)) ((7 7 6 7) . (0 3)) ((7 7 7 7 6 7) . (0 5)) ((7 7 7 7 6 7 7) . (0 5)) ((7 7 5 5 6 7 7 6 7 5 7) . (0 5 8 10)) ((7 7 5 5 6 7 7 6 7 5 7 7) . (0 5 8 10)) ((7 7 5 5 6 7 7 6 7 5 7 6) . (0 5 8 10)))) ;; nums -> ((lmax-val lmax-idx) ...) (define (local-maxima nums) (let* ((xs (apply circular-list -inf.0 nums)) (ys (cdr xs)) (zs (cdr ys)) (yi (iota (length nums)))) ;; x, y, z are consecutive nums with -inf.0 as sentinel at both ends (filter-map (lambda (x y z i) ;; is y a local maximum, leftmost in case of plateau? (and (< x y) (<= z y) (list y i))) xs ys zs yi))) (define (local-maxima-values nums) (map car (local-maxima nums))) (define (local-maxima-indexes nums) (map cadr (local-maxima nums))) (define (demo) (display (equal? (map cdr samples) (map local-maxima-indexes (map car samples)))) (newline)) (demo)Output:
By chaw on February 16, 2021 at 8:07 PM
Cache version – Fix formatting
test ; q ; localmaxima(list) ; Output local maxima n i,next,previous,this s list=$e(list)-1_” “list” “($e(list,$l(list)-1)-1) s output=”” f i=2:1:$l(list,” “)-1 { s this=$p(list,” “,i),previous=$p(list,” “,i-1),next=$p(list,” “,i+1) i this>previous, this>next s output=output_this” ” } q $e(output,1,$l(output)-1)s list=”1 2 1 2 3 4 3 2 3 2 1″
w !,list,!,$$localmaxima(list)
1 2 1 2 3 4 3 2 3 2 1
2 4 3
By bookofstevegraham on February 16, 2021 at 8:09 PM
@James Curtis-Smith
I’m unfamiliar with Perl. I tried typing your program into a file and executing it:
$ perl -e localmaxima.pl
Steve@DESKTOP-0SFLH1S MINGW64 ~/Desktop
$ perl -E localmaxima.pl
Steve@DESKTOP-0SFLH1S MINGW64 ~/Desktop
$ perl localmaxima.pl
syntax error at localmaxima.pl line 1, near “say join”
Execution of localmaxima.pl aborted due to compilation errors.
I also tried typing it into the interpreter, but couldn’t figure out how to execute it.
Any tips?
Thanks, Steve
By bookofstevegraham on February 16, 2021 at 8:58 PM
Changed the program (localmaxima.pl) to the following, and executing “./localmaxima.pl” returned the expected values:
#!/usr/bin/perl
print join ‘ ‘, maxima( qw(1 2 1 2 3 4 3 2 3 2 1) );
sub maxima {
my @X = @_;
push @X, my $left = -1e32;
my @sol;
while(@X>1) {
push @sol,$X[0] if $left < $X[0] && $X[0] > $X[1];
$left = shift @X;
}
return @sol;
}
Sure enjoy learning new languages and seeing new solutions.
Thanks, all.
Steve
By bookofstevegraham on February 17, 2021 at 1:16 AM
@James Curtis-Smith and @bookofstevegraham: What do your programs return when given (1 3 3 1) as input? They should return a local maximum of (3).
By programmingpraxis on February 17, 2021 at 2:49 PM
@programmingpraxis: Good catch – Didn’t know you read Cache/Mumps! I was allowing for mountain peaks as maxima, but not buttes.
Revised program and tests
>zl test zp s qt="""" for list="1 2 1 2 3 4 3 2 3 2 1","1 3 3 1","","1","1 1","7 7 7","7 6 7","7 7 6 7","7 7 7 7 6 7","7 7 7 7 6 7 7","7 7 5 5 6 7 7 6 7 5 7","7 7 5 5 6 7 7 6 7 5 7 7", "7 7 5 5 6 7 7 6 7 5 7 6" w !!,qt,list,qt,!,qt,$$localmaxima^test(list),qt test ; q ; localmaxima(list) ; Output local maxima n i,next,previous,this s list=$e(list)-1_" "_list_" "_($e(list,$l(list)-1)-1),output="" f i=2:1:$l(list," ")-1 { s this=$p(list," ",i),previous=$p(list," ",i-1),next=$p(list," ",i+1) i this>previous,this'<next s output=output_this_" " } q $e(output,1,$l(output)-1)“1 2 1 2 3 4 3 2 3 2 1”
“2 4 3”
“1 3 3 1”
“3”
“”
“”
“1”
“1”
“1 1”
“1”
“7 7 7”
“7”
“7 6 7”
“7 7”
“7 7 6 7”
“7 7”
“7 7 7 7 6 7”
“7 7”
“7 7 7 7 6 7 7”
“7 7”
“7 7 5 5 6 7 7 6 7 5 7”
“7 7 7 7”
“7 7 5 5 6 7 7 6 7 5 7 7”
“7 7 7 7”
“7 7 5 5 6 7 7 6 7 5 7 6”
“7 7 7 7”
By bookofstevegraham on February 17, 2021 at 3:26 PM
@bookofstevegraham: Actually, I don’t speak cache/mumps. but it’s not too hard to figure out that you have a statement “if this > previous and this > next then output this” which handles peaks but not plateaus.
The problem is my fault, not yours. The description mentions plateaus, but not clearly, and I didn’t give an example of an input that contains plateaus. If my example had been (1 2 1 2 3 4 3 2 3 3 3 2 1) the situation would have been obvious.
By programmingpraxis on February 17, 2021 at 4:01 PM
@programmingpraxis: Good points. Thanks for your efforts: They have provided many hours of enjoyment and learning.
By bookofstevegraham on February 17, 2021 at 7:22 PM
Here’s a Haskell version. We take advantage of
Nothingbeing less thanJust xfor allx(assumingxis comparable). Also, the functiondivvyis such thatdivvy 3 1 [1..5]equals[[1,2,3],[2,3,4],[3,4,5]].import Data.List (group) import Data.List.Split (divvy) import Data.Maybe (mapMaybe) locmax :: Ord a => [a] -> [a] locmax xs = map head $ group $ mapMaybe midMax $ divvy 3 1 ys where ys = [Nothing] ++ map Just xs ++ [Nothing] midMax [x, y, z] = if x <= y && y >= z then y else Nothing main :: IO () main = do print $ locmax ([] :: [()]) print $ locmax [5] print $ locmax [5, 4] print $ locmax [5, 6] print $ locmax [5, 5, 5, 6, 6] print $ locmax [1, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1]By Globules on February 18, 2021 at 5:56 AM
A solution in Racket:
;e: local maxima to be indicated in square brackets like so: (1 [2] 1 2 3 [4] 3 2 [3] 2 1) (define (loc-max input) (foldl (λ (val init) (let ((last (car init)) (next (if (null? (cdadr init)) null (cadadr init)))) (let ((tmp (if (and (or (null? last) (<= last val)) (or (null? next) (< next val))) "[~a]" "~a"))) (list val (cdadr init) (cons (format tmp val) (caddr init)))))) (list null input null) input)) (define (local-maxima input) (display (string-join (reverse (caddr (loc-max input))) #:before-first "(" #:after-last ")")))Examples:
By Kevin on February 20, 2021 at 3:03 AM