The weekly challenge 249 - Task 2: DI String Match

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-249/#TASK2
 3 #
 4 # Task 2: DI String Match
 5 # =======================
 6 #
 7 # You are given a string s, consisting of only the characters "D" and "I".
 8 #
 9 # Find a permutation of the integers [0 .. length(s)] such that for each
10 # character s[i] in the string:
11 #
12 # s[i] == 'I' ⇒ perm[i] < perm[i + 1]
13 # s[i] == 'D' ⇒ perm[i] > perm[i + 1]
14 #
15 ## Example 1
16 ##
17 ## Input: $str = "IDID"
18 ## Output: (0, 4, 1, 3, 2)
19 #
20 ## Example 2
21 ##
22 ## Input: $str = "III"
23 ## Output: (0, 1, 2, 3)
24 #
25 ## Example 3
26 ##
27 ## Input: $str = "DDI"
28 ## Output: (3, 2, 0, 1)
29 #
30 ############################################################
31 ##
32 ## discussion
33 ##
34 ############################################################
35 #
36 # We just count from 0 to length(s) for each "I" and from
37 # length(s) to 0 for each "D", and in the end add the last
38 # element we didn't use up yet.
39 
40 use strict;
41 use warnings;
42 
43 DI_string_match("IDID");
44 DI_string_match("III");
45 DI_string_match("DDI");
46 
47 sub DI_string_match {
48    my $str = shift;
49    print "Input: '$str'\n";
50    my $upper = length($str);
51    my $lower = 0;
52    my @result = ();
53    foreach my $char (split//,$str) {
54       if($char eq "I") {
55          push @result, $lower++;
56       } else {
57          push @result, $upper--;
58       }
59    }
60    push @result, $lower;
61    print "Output: (", join(", ", @result), ")\n";
62 }