/
ch-2.pl
executable file
·54 lines (49 loc) · 1.54 KB
/
ch-2.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#!/usr/bin/env perl
use v5.30;
use Data::Dumper;
use experimental qw/signatures/;
sub array_degree (@input)
{
my %cnt;
my %loc;
my $min_len = scalar @input;
my $max = 0;
for my $i ( 0 .. $#input )
{
my $c = $input[$i];
# build a mapping of input element to count
$cnt{$c}++;
$max = $cnt{$c} if ( $cnt{$c} > $max );
# build a mapping of input element to array of indexes where that element is found
# this could be tightened up by keeping only the first and last element
push @{ $loc{$c} }, $i;
}
my @sol_index;
while ( my ( $key, $value ) = each %cnt )
{
if ( $value == $max )
{
# For all input elements appearing max times,
# find the shortest delta between first and last appearance.
# Minimal solutions will extend from first to last of a given element
my $loc = $loc{$key};
my ( $first, $last ) = ( $loc->[0], $loc->[-1] );
my $len = $last - $first;
if ( $len < $min_len )
{
$min_len = $len;
@sol_index = ( $first, $last );
}
}
}
@input[ $sol_index[0] .. $sol_index[1] ];
}
{
use Test::More;
is_deeply [ array_degree( 1, 3, 3, 2 ) ], [ 3, 3 ];
is_deeply [ array_degree( 1, 2, 1, 3 ) ], [ 1, 2, 1 ];
is_deeply [ array_degree( 1, 3, 2, 1, 2 ) ], [ 2, 1, 2 ];
is_deeply [ array_degree( 1, 1, 2, 3, 2 ) ], [ 1, 1 ];
is_deeply [ array_degree( 2, 1, 2, 1, 1 ) ], [ 1, 2, 1, 1 ];
done_testing;
}