Optimisation in Programming Contests

Two optimisation assignments at HackerRank that don’t have a correct Perl solution besides mine.

E. Choroba

GoodData

PerlMonks, CPAN, StackOverflow …

choroba@matfyz.cz

Programming Contests & Sites

Similar Pair

Assignment

Given: a tree with nodes 1 .. n, where 1 ≤ n ≤ 105.
A pair of nodes (a, b) is a similar pair if both of the following conditions are true:

  1. Node a is the ancestor of node b
  2. abs(a - b) < k

Input

Number of nodes, difference
List of edges: parent child

Output

Number of similar pairs.

Similar Pair: Naïve Solution

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

*ARGV = *DATA{IO} unless @ARGV || ! -t;

my $diff = (split ' ', <>)[1];

my %tree;
while (<>) {
    my ($parent, $child) = split;
    $tree{$child} = $parent;
}

my $number_of_similar_pairs;
for my $node (keys %tree) {
    my $parent = $tree{$node};
    my @ancestors = $parent;
    while ($tree{$parent}) {
        $parent = $tree{$parent};
        push @ancestors, $parent;
    }
    my @similar = grep abs($_ - $node) <= $diff, @ancestors;
    $number_of_similar_pairs += @similar;
}

say $number_of_similar_pairs;

__DATA__
5 2
3 2
3 1
1 4
1 5

Similar Pair: Naïve Solution Too Slow

Limit for Perl on HackerRank
9 seconds 
#! /bin/bash
(time ./similar-pair-naive.pl similar-pair.in0) 2>&1

Output

248

real	0m3.156s
user	0m3.142s
sys	0m0.004s

Similar Pair: Graph

Similar Pair: Graph (2)

Too large to display the whole graph (17MB PNG)

Similar Pair: Naïve Solution Too Slow (2)

perl -d:NYTProf similar-pair-naive.pl similar-pair.in0
nytprofhtml
17 1 15.3ms for my $node (keys %tree) {
18 56788 35.4ms my $parent = $tree{$node};
19 56788 16.1ms my @ancestors = $parent;
20 56788 38.1ms while ($tree{$parent}) {
21 7272546 1.17s $parent = $tree{$parent};
22 7272546 2.94s push @ancestors, $parent;
23 }
24 56788 931ms my @similar = grep abs($_ - $node) <= $k, @ancestors;
25 56788 232ms $number_of_similar_pairs += @similar;

Nested loops!

Similar Pair: Faster Solution

node ancestor mask count
3 00000 0

Similar Pair: Faster Solution

node ancestor mask count
3 00000 0
00100

Similar Pair: Faster Solution

node ancestor mask count
3 00000 0
2 00100 1

Similar Pair: Faster Solution

node ancestor mask count
3 00000 0
2 00100 1
1 00100 2

Similar Pair: Faster Solution

node ancestor mask count
3 00000 0
2 00100 1
1 00100 2
10100 2

Similar Pair: Faster Solution

node ancestor mask count
3 00000 0
2 00100 1
1 00100 2
4 10100 3

Similar Pair: Faster Solution

node ancestor mask count
3 00000 0
2 00100 1
1 00100 2
4 10100 3
5 10100 4

Similar Pair: Faster Solution

node ancestor mask count
3 00000 0
2 00100 1
1 00100 2
4 10100 3
5 10100 4
00100 4

Similar Pair: Faster Solution

node ancestor mask count
3 00000 0
2 00100 1
1 00100 2
4 10100 3
5 10100 4
00000 4

Similar Pair: Faster Solution

node ancestor mask count
3 00000 0
2 00100 1
1 00100 2
4 10100 3
5 10100 4
Final result 4

Similar Pair: Faster Solution (2)

#! /usr/bin/perl
# use warnings;
use strict;
use List::Util qw{ first };
use integer;

my ($nodes, $diff) = split ' ', <>;

my @children = map [], 0 .. $nodes;
my @parent;

for (<>) {
    my ($parent, $son) = split;
    push @{ $children[$parent] }, 0 + $son;
    $parent[$son] = 0 + $parent;
}

my $node     = first { ! $parent[$_] } 1 .. $nodes;
my $count    = 0;
my $anc_mask = "\0" x $nodes;
my $LENGTH   = $diff * 2 + 1;

while ($node) {
    my $from   = $node - $diff - 1;
    my $length = $LENGTH;
    if ($node <= $diff) {
        $from   = 0;
        $length = $node + $LENGTH - $diff - 1;
    }

    $count += (substr $anc_mask, $from, $length) =~ tr/\1//;

    if (@{ $children[$node] }) {
        substr $anc_mask, $node - 1, 1, "\1";
        $node = shift @{ $children[$node] };

    } else {
        while (my $old_node = $node) {
            last if $node = shift @{ $children[ $parent[$node] ] };

            substr $anc_mask, ($node = $parent[$old_node]) - 1, 1, "\0";
        }
    }
}

print $count, "\n";

Similar Pair: Faster Solution (3)

Naïve

248

real	0m3.156s
user	0m3.142s
sys	0m0.004s

Final

248

real	0m0.147s
user	0m0.146s
sys	0m0.000s

Synchronous Shopping

Similar to the Travelling Salesman Problem

But

Output: The minimal time

Synchronous Shopping: Example

Answer: 30

Shopper 1: 1 → 2 → 4 → 5 30
Shopper 2: 1 → 3 → 5 20

Synchronous Shopping (2)

Assignment

Input

Numbers of shops, roads, goods

Goods sold at particular shops

Roads connecting the shops and their length

5 5 5
1 1
1 2
1 3
1 4
1 5
1 2 10
1 3 10
2 4 10
3 5 10
4 5 10

Synchronous Shopping: Solution

Synchronous Shopping: Solution

Time: 0

Future: 572, 579, 671, 927

Synchronous Shopping: Solution

Time: 572

Future: 579, 671, 792

Synchronous Shopping: Solution

Time: 579

Future: 671, 792

Synchronous Shopping: Solution

Time: 671

Future: 792

Synchronous Shopping: Solution

Time: 792

Synchronous Shopping: Data Structure

I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.

Linus Torvalds 

$shgti{$shop}{$goods_set} = $time;

Synchronous Shopping: Data Structure (2)

✓ Test Case #0 ✓ Test Case #1 ✓ Test Case #2
✓ Test Case #3 ✓ Test Case #4 ✓ Test Case #5
✓ Test Case #6 ✓ Test Case #7 ✓ Test Case #8
✓ Test Case #9 ✓ Test Case #10 ✓ Test Case #11
✓ Test Case #12 ✓ Test Case #13 ⌚ Test Case #14
⌚ Test Case #15 ✓ Test Case #16 ⌚ Test Case #17
⌚ Test Case #18 ✓ Test Case #19 ✓ Test Case #20
⌚ Test Case #21 ⌚ Test Case #22 ⌚ Test Case #23
⌚ Test Case #24 ⌚ Test Case #25 ⌚ Test Case #26
⌚ Test Case #27 ⌚ Test Case #28 ⌚ Test Case #29
⌚ Test Case #30

Synchronous Shopping: Data Structure (3)

✓ Test Case #0 ✓ Test Case #1 ✓ Test Case #2
✓ Test Case #3 ✓ Test Case #4 ✓ Test Case #5
✓ Test Case #6 ✓ Test Case #7 ✓ Test Case #8
✓ Test Case #9 ✓ Test Case #10 ✓ Test Case #11
✓ Test Case #12 ✓ Test Case #13 ⌚ Test Case #14
✓ Test Case #15 ⌚ Test Case #16 ✓ Test Case #17
✓ Test Case #18 ✓ Test Case #19 ✓ Test Case #20
✓ Test Case #21 ✓ Test Case #22 ✓ Test Case #23
✓ Test Case #24 ⌚ Test Case #25 ⌚ Test Case #26
✓ Test Case #27 ⌚ Test Case #28 ✓ Test Case #29
✓ Test Case #30

Synchronous Shopping: Data Structure (4)

If a programmer designs a program, only half the job is done if they have only designed the data structures.

Theng, Jones, and Thimbleby 

$tishg{$time}{$shop}{$goods_set}

Synchronous Shopping: Final Solution

#!/usr/bin/perl
#use warnings;
use strict;
use integer;

use List::Util qw{ sum };

my ($shop_count, $road_count, $goods_count) = split ' ', <>;
my $ALL_GOODS = 2 ** (1 + $goods_count) - 2;

my %shop_sells;
for my $shop (1 .. $shop_count) {
    my (undef, @goods) = split ' ', <>;
    $shop_sells{$shop} = sum(0, map 2 ** $_, @goods);
}

my %road;
for (1 .. $road_count) {
    my ($from, $to, $time) = split ' ', <>;
    $road{$from}{$to} = $road{$to}{$from} = $time;
}

my %road_fast = map +( $_ => [ keys %{ $road{$_} } ] ), keys %road;

my @future = (0);

my %tishg = ( 0 => { 1 => { $shop_sells{1} => undef } } ); # Time Shop Goods
my %shgti = ( 1 => { $shop_sells{1} => 0 } ); # Shop Goods Time
my %final;

my ($start, $end, $middle, $newgoods, $newtime);
my $best_time;
while (1) {
    my $next = shift @future;
    last unless defined $next;
    last if $best_time && $best_time < $next;

    for my $from (keys %{ $tishg{$next} } ) {
        for my $goods (keys %{ $tishg{$next}{$from} }) {
            for my $to (@{ $road_fast{$from} }) {
                $newgoods = $goods | $shop_sells{$to};
                $newtime = $next + $road{$from}{$to};

                next unless ($shgti{$to}{$newgoods} // 1e12) > $newtime;

                $shgti{$to}{$newgoods} = $newtime;
                undef $tishg{$newtime}{$to}{$newgoods};

                if (! @future) {
                    @future = $newtime;

                } else {
                    $start = 0;
                    $end = $#future;
                    while ($start < $end) {
                        $middle = ($start + $end) >> 1;
                        if ($future[$middle] > $newtime) {
                            $end = $middle - 1;

                        } elsif ($future[$middle] < $newtime) {
                            $start = $middle + 1;

                        } else {
                            $start = $end = $middle;
                        }
                    }
                    ++$start if $newtime > $future[$start];
                    if ($start > $#future
                        || $newtime != $future[$start]
                    ) {
                        splice @future, $start, 0, $newtime;
                    }
                }

                if ($to == $shop_count) {
                    push @{ $final{$newtime} }, $newgoods;
                    for my $othertime (keys %final) {
                        for my $othergoods ( @{ $final{$othertime} }) {
                            next unless $ALL_GOODS
                                        == ($newgoods | $othergoods);

                            my $maxtime = $newtime > $othertime
                                       ? $newtime
                                       : $othertime;
                            $best_time = $maxtime
                                if ! defined $best_time
                                || $maxtime < $best_time;
                        }
                    }
                }
            }
        }
    }
}
print $best_time, "\n";

Synchronous Shopping: Final Solution (2)

#!/usr/bin/perl
#use warnings;
use strict;
use integer;

use List::Util qw{ sum };

load_input();

my %road_fast = map +( $_ => [ keys %{ $road{$_} } ] ), keys %road;

my @future = (0);

my %tishg = ( 0 => { 1 => { $shop_sells{1} => undef } } ); # Time Shop Goods
my %shgti = ( 1 => { $shop_sells{1} => 0 } ); # Shop Goods Time
my %final;

my ($start, $end, $middle, $newgoods, $newtime);
my $best_time;
while (1) {
    my $next = shift @future;
    last unless defined $next;
    last if $best_time && $best_time < $next;

    for my $from (keys %{ $tishg{$next} } ) {
        for my $goods (keys %{ $tishg{$next}{$from} }) {
            for my $to (@{ $road_fast{$from} }) {
                $newgoods = $goods | $shop_sells{$to};
                $newtime = $next + $road{$from}{$to};

                next unless ($shgti{$to}{$newgoods} // 1e12) > $newtime;

                $shgti{$to}{$newgoods} = $newtime;
                undef $tishg{$newtime}{$to}{$newgoods};

                if (! @future) {
                    @future = $newtime;

                } else {
                    $start = 0;
                    $end = $#future;
                    while ($start < $end) {
                        $middle = ($start + $end) >> 1;
                        if ($future[$middle] > $newtime) {
                            $end = $middle - 1;

                        } elsif ($future[$middle] < $newtime) {
                            $start = $middle + 1;

                        } else {
                            $start = $end = $middle;
                        }
                    }
                    ++$start if $newtime > $future[$start];
                    if ($start > $#future
                        || $newtime != $future[$start]
                    ) {
                        splice @future, $start, 0, $newtime;
                    }
                }

                if ($to == $shop_count) {
                    push @{ $final{$newtime} }, $newgoods;
                    for my $othertime (keys %final) {
                        for my $othergoods ( @{ $final{$othertime} }) {
                            next unless $ALL_GOODS
                                        == ($newgoods | $othergoods);

                            my $maxtime = $newtime > $othertime
                                       ? $newtime
                                       : $othertime;
                            $best_time = $maxtime
                                if ! defined $best_time
                                || $maxtime < $best_time;
                        }
                    }
                }
            }
        }
    }
}
print $best_time, "\n";

Synchronous Shopping: Final Solution (3)

#!/usr/bin/perl
#use warnings;
use strict;
use integer;

use List::Util qw{ sum };

load_input();

cache_roads();

my @future = (0);

my %tishg = ( 0 => { 1 => { $shop_sells{1} => undef } } ); # Time Shop Goods
my %shgti = ( 1 => { $shop_sells{1} => 0 } ); # Shop Goods Time
my %final;

my ($start, $end, $middle, $newgoods, $newtime);
my $best_time;
while (1) {
    my $next = shift @future;
    last unless defined $next;
    last if $best_time && $best_time < $next;

    for my $from (keys %{ $tishg{$next} } ) {
        for my $goods (keys %{ $tishg{$next}{$from} }) {
            for my $to (@{ $road_fast{$from} }) {
                $newgoods = $goods | $shop_sells{$to};
                $newtime = $next + $road{$from}{$to};

                next unless ($shgti{$to}{$newgoods} // 1e12) > $newtime;

                $shgti{$to}{$newgoods} = $newtime;
                undef $tishg{$newtime}{$to}{$newgoods};

                if (! @future) {
                    @future = $newtime;

                } else {
                    $start = 0;
                    $end = $#future;
                    while ($start < $end) {
                        $middle = ($start + $end) >> 1;
                        if ($future[$middle] > $newtime) {
                            $end = $middle - 1;

                        } elsif ($future[$middle] < $newtime) {
                            $start = $middle + 1;

                        } else {
                            $start = $end = $middle;
                        }
                    }
                    ++$start if $newtime > $future[$start];
                    if ($start > $#future
                        || $newtime != $future[$start]
                    ) {
                        splice @future, $start, 0, $newtime;
                    }
                }

                if ($to == $shop_count) {
                    push @{ $final{$newtime} }, $newgoods;
                    for my $othertime (keys %final) {
                        for my $othergoods ( @{ $final{$othertime} }) {
                            next unless $ALL_GOODS
                                        == ($newgoods | $othergoods);

                            my $maxtime = $newtime > $othertime
                                       ? $newtime
                                       : $othertime;
                            $best_time = $maxtime
                                if ! defined $best_time
                                || $maxtime < $best_time;
                        }
                    }
                }
            }
        }
    }
}
print $best_time, "\n";

Synchronous Shopping: Final Solution (4)

#!/usr/bin/perl
#use warnings;
use strict;
use integer;

use List::Util qw{ sum };

load_input();

cache_roads();

init();

while (1) {
    my $next = shift @future;
    last unless defined $next;
    last if $best_time && $best_time < $next;

    for my $from (keys %{ $tishg{$next} } ) {
        for my $goods (keys %{ $tishg{$next}{$from} }) {
            for my $to (@{ $road_fast{$from} }) {
                $newgoods = $goods | $shop_sells{$to};
                $newtime = $next + $road{$from}{$to};

                next unless ($shgti{$to}{$newgoods} // 1e12) > $newtime;

                $shgti{$to}{$newgoods} = $newtime;
                undef $tishg{$newtime}{$to}{$newgoods};

                if (! @future) {
                    @future = $newtime;

                } else {
                    $start = 0;
                    $end = $#future;
                    while ($start < $end) {
                        $middle = ($start + $end) >> 1;
                        if ($future[$middle] > $newtime) {
                            $end = $middle - 1;

                        } elsif ($future[$middle] < $newtime) {
                            $start = $middle + 1;

                        } else {
                            $start = $end = $middle;
                        }
                    }
                    ++$start if $newtime > $future[$start];
                    if ($start > $#future
                        || $newtime != $future[$start]
                    ) {
                        splice @future, $start, 0, $newtime;
                    }
                }

                if ($to == $shop_count) {
                    push @{ $final{$newtime} }, $newgoods;
                    for my $othertime (keys %final) {
                        for my $othergoods ( @{ $final{$othertime} }) {
                            next unless $ALL_GOODS
                                        == ($newgoods | $othergoods);

                            my $maxtime = $newtime > $othertime
                                       ? $newtime
                                       : $othertime;
                            $best_time = $maxtime
                                if ! defined $best_time
                                || $maxtime < $best_time;
                        }
                    }
                }
            }
        }
    }
}
print $best_time, "\n";

Synchronous Shopping: Final Solution (5)

#!/usr/bin/perl
#use warnings;
use strict;
use integer;

use List::Util qw{ sum };

load_input();

cache_roads();

init();

while (1) {
    my $next = shift @future;
    last unless defined $next;
    last if $best_time && $best_time < $next;

    for my $from (keys %{ $tishg{$next} } ) {
        for my $goods (keys %{ $tishg{$next}{$from} }) {
            for my $to (@{ $road_fast{$from} }) {

                try_new_combination();

                if (! @future) {
                    @future = $newtime;

                } else {
                    $start = 0;
                    $end = $#future;
                    while ($start < $end) {
                        $middle = ($start + $end) >> 1;
                        if ($future[$middle] > $newtime) {
                            $end = $middle - 1;

                        } elsif ($future[$middle] < $newtime) {
                            $start = $middle + 1;

                        } else {
                            $start = $end = $middle;
                        }
                    }
                    ++$start if $newtime > $future[$start];
                    if ($start > $#future
                        || $newtime != $future[$start]
                    ) {
                        splice @future, $start, 0, $newtime;
                    }
                }

                if ($to == $shop_count) {
                    push @{ $final{$newtime} }, $newgoods;
                    for my $othertime (keys %final) {
                        for my $othergoods ( @{ $final{$othertime} }) {
                            next unless $ALL_GOODS
                                        == ($newgoods | $othergoods);

                            my $maxtime = $newtime > $othertime
                                       ? $newtime
                                       : $othertime;
                            $best_time = $maxtime
                                if ! defined $best_time
                                || $maxtime < $best_time;
                        }
                    }
                }
            }
        }
    }
}
print $best_time, "\n";

Synchronous Shopping: Final Solution (6)

#!/usr/bin/perl
#use warnings;
use strict;
use integer;

use List::Util qw{ sum };

load_input();

cache_roads();

init();

while (1) {
    my $next = shift @future;
    last unless defined $next;
    last if $best_time && $best_time < $next;

    for my $from (keys %{ $tishg{$next} } ) {
        for my $goods (keys %{ $tishg{$next}{$from} }) {
            for my $to (@{ $road_fast{$from} }) {

                try_new_combination();

                add_sorted($newtime, \@future);

                if ($to == $shop_count) {
                    push @{ $final{$newtime} }, $newgoods;
                    for my $othertime (keys %final) {
                        for my $othergoods ( @{ $final{$othertime} }) {
                            next unless $ALL_GOODS
                                        == ($newgoods | $othergoods);

                            my $maxtime = $newtime > $othertime
                                       ? $newtime
                                       : $othertime;
                            $best_time = $maxtime
                                if ! defined $best_time
                                || $maxtime < $best_time;
                        }
                    }
                }
            }
        }
    }
}
print $best_time, "\n";

Synchronous Shopping: Final Solution (7)

#!/usr/bin/perl
#use warnings;
use strict;
use integer;

use List::Util qw{ sum };

load_input();

cache_roads();

init();

while (1) {
    my $next = shift @future;
    last unless defined $next;
    last if $best_time && $best_time < $next;

    for my $from (keys %{ $tishg{$next} } ) {
        for my $goods (keys %{ $tishg{$next}{$from} }) {
            for my $to (@{ $road_fast{$from} }) {

                try_new_combination();

                add_sorted($newtime, \@future);

                if ($to == $shop_count) {
                    update_newtime();
                }
            }
        }
    }
}
print $best_time, "\n";

Synchronous Shopping: Final Solution (8)

✓ Test Case #0 ✓ Test Case #1 ✓ Test Case #2
✓ Test Case #3 ✓ Test Case #4 ✓ Test Case #5
✓ Test Case #6 ✓ Test Case #7 ✓ Test Case #8
✓ Test Case #9 ✓ Test Case #10 ✓ Test Case #11
✓ Test Case #12 ✓ Test Case #13 ✓ Test Case #14
✓ Test Case #15 ✓ Test Case #16 ✓ Test Case #17
✓ Test Case #18 ✓ Test Case #19 ✓ Test Case #20
✓ Test Case #21 ✓ Test Case #22 ✓ Test Case #23
✓ Test Case #24 ✓ Test Case #25 ✓ Test Case #26
✓ Test Case #27 ✓ Test Case #28 ✓ Test Case #29
✓ Test Case #30

Regular Expresso 2

...
$Test_String = <STDIN> ;
if($Test_String =~ /$Regex_Pattern/){
    print "true";
} else {
    print "false";
}

You can only edit the ... part.

Regular Expresso: Example

  1. The input is a long string of zeroes and ones.
  2. Your regex has to recognise whether the string encodes two binary numbers in the following way: when you reverse the string and extract the odd digits, you get a number three times greater than the one built from the remaining digits. For example, 
    1110110001 => 00111, 10101
                  7     21
              3 * 7  =  21, accept!

Regular Expresso: Example (2)

use bigint;

sub check {
    my ($bin, $three) = ('0b') x 2;
    my $s = $_;
    while ($s) {
        $three .= chop $s;
        $bin   .= chop $s;
    }
    return oct $three == 3 * oct $bin
}

$Regex_Pattern = qr/(?{ check() })/;

But (?{...}) always matches!

Regular Expresso: Example (3)

We can use the 

(?(condition)yes-pattern|no-pattern)

Regular Expresso: Example (4)

$Regex_Pattern = qr/^(?(?{ check() }) ^ | (*FAIL) )/x;

Regular Expresso: Example (5)

$Regex_Pattern = '^(?(?{c()})^|(*F))'

Regular Expresso: Expected Solution

Homework

In binary, multiplying by 3 is like shift + add.

Acknowledgement

oiskuu@PerlMonks

Thank you.

Questions?

Thank you.

https://e-choroba.eu/17-optimization

TPCiA 2017