/
ch-2.raku
54 lines (40 loc) · 1.16 KB
/
ch-2.raku
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
sub task2 ( @ns_original --> Int ) {
my @ns = @ns_original;
sub remove_max ( --> UInt ) {
return @ns.splice( @ns.maxpairs[0].key, 1 )[0];
}
while @ns >= 2 {
my $y = remove_max();
my $x = remove_max();
push @ns, $y - $x if $x != $y;
}
return @ns[0] // 0;
}
# Thanks to Yves "demerphq" Orton for bringing this efficient
# technique to my attention in his comments here:
# https://blogs.perl.org/users/bruce_gray/2023/02/twc-205-exclusive-third-or-first.html
use BinaryHeap;
sub task2_h ( @ns --> Int ) {
my BinaryHeap::MaxHeap $heap .= new(@ns); # Always pops the maximum value.
loop {
my $y = $heap.pop;
return $y if not $heap;
my $x = $heap.pop;
$heap.push($y - $x) if $x != $y;
return 0 if not $heap;
}
}
my @tests =
( 1, ( 2, 7, 4, 1, 8, 1 ) ),
( 1, ( 1, ) ),
( 0, ( 1, 1 ) ),
( 2, ( 30, 15, 7, 3, 2, 1 ) ),
( 3, ( 30, 15, 7, 3, 2 ) ),
( 1, ( 30, 15, 7, 3, 2, 1, 1 ) ),
;
use Test;
plan 2 * @tests;
for @tests -> ( $expected, @in ) {
is task2( @in), $expected;
is task2_h(@in), $expected;
}