The weekly challenge 284 - Task 2: Relative Sort

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-284/#TASK2
 3 #
 4 # Task 2: Relative Sort
 5 # =====================
 6 #
 7 # You are given two list of integers, @list1 and @list2. The elements in the
 8 # @list2 are distinct and also in the @list1.
 9 #
10 # Write a script to sort the elements in the @list1 such that the relative
11 # order of items in @list1 is same as in the @list2. Elements that is missing
12 # in @list2 should be placed at the end of @list1 in ascending order.
13 #
14 ## Example 1
15 ##
16 ## Input: @list1 = (2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5)
17 ##        @list2 = (2, 1, 4, 3, 5, 6)
18 ## Ouput: (2, 2, 1, 4, 3, 3, 5, 6, 7, 8, 9)
19 #
20 ## Example 2
21 ##
22 ## Input: @list1 = (3, 3, 4, 6, 2, 4, 2, 1, 3)
23 ##        @list2 = (1, 3, 2)
24 ## Ouput: (1, 3, 3, 3, 2, 2, 4, 4, 6)
25 #
26 ## Example 3
27 ##
28 ## Input: @list1 = (3, 0, 5, 0, 2, 1, 4, 1, 1)
29 ##        @list2 = (1, 0, 3, 2)
30 ## Ouput: (1, 1, 1, 0, 0, 3, 2, 4, 5)
31 #
32 ############################################################
33 ##
34 ## discussion
35 ##
36 ############################################################
37 #
38 # First, we turn the second list into a hash with the integers
39 # as keys and their position inside the array as the values.
40 # Then we run a clever compare function:
41 # - if there is an entry for both numbers to be compared, we just
42 #   compare their position in the original list2.
43 # - if only one of the two numbers has an entry in the hash, sort
44 #   this number first
45 # - if both numbers are missing in list2, then sort by their value
46 
47 use strict;
48 use warnings;
49 
50 relative_sort( [2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5], [2, 1, 4, 3, 5, 6] );
51 relative_sort( [3, 3, 4, 6, 2, 4, 2, 1, 3], [1, 3, 2] );
52 relative_sort( [3, 0, 5, 0, 2, 1, 4, 1, 1], [1, 0, 3, 2] );
53 
54 sub relative_sort {
55    my ($list1, $list2) = @_;
56    print "Input: (" . join(", ", @$list1) . "),\n       (" . join(", ", @$list2) . ")\n";
57    my $int_to_index = {};
58    my $i = 0;
59    foreach my $elem (@$list2) {
60       $int_to_index->{$elem} = $i;
61       $i++;
62    }
63    my @sorted = sort {
64       ( defined($int_to_index->{$a}) && defined($int_to_index->{$b}) &&
65          $int_to_index->{$a} <=> $int_to_index->{$b} ) ||
66       ( defined($int_to_index->{$a}) && -1 ) ||
67       ( defined($int_to_index->{$b}) && 1 ) ||
68       $a <=> $b
69    } @$list1;
70    print "Output: (" . join(", ", @sorted) . ")\n";
71 }