The weekly challenge 394 - Task 1: Alternate Case

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-394/#TASK1
  3 #
  4 # Task 1: Alternate Case
  5 # ======================
  6 #
  7 # You are given a string containing an equal number of uppercase and lowercase English letters.
  8 #
  9 # Write a script to the minimum number of adjacent character swaps needed to
 10 # turn the given string into an alternate case string.
 11 #
 12 ## Example 1
 13 ##
 14 ## Input: $str = "aAbB"
 15 ## Output: 0
 16 #
 17 ## Example 2
 18 ##
 19 ## Input: $str = "AAbb"
 20 ## Output: 1
 21 ##
 22 ## Swap 1: "AbAb"
 23 #
 24 ## Example 3
 25 ##
 26 ## Input: $str = "AAAbbb"
 27 ## Output: 3
 28 ##
 29 ## Swap 1: "AAbAbb"
 30 ## Swap 2: "AbAAbb"
 31 ## Swap 3: "AbAbAb"
 32 #
 33 ## Example 4
 34 ##
 35 ## Input: $str = "aABb"
 36 ## Output: 1
 37 ##
 38 ## Swap 1: "aAbB"
 39 #
 40 ## Example 5
 41 ##
 42 ## Input: $str = "bBBAaa"
 43 ## Output: 2
 44 ##
 45 ## Swap 1: "BbBAaa"
 46 ## Swap 2: "BbBaAa"
 47 #
 48 ############################################################
 49 ##
 50 ## discussion
 51 ##
 52 ############################################################
 53 #
 54 # We have two cases, either we need to swap the first character or we don't.
 55 # We calculate the amount of swaps required for both cases (in the former case
 56 # we need to add the necessary swaps to swap the first character). Then we pick
 57 # the minimum of the two.
 58 # The amount of swaps necessary is simple: Find the next character that doesn't
 59 # match the current character's case, then swap it forward to the place next to
 60 # the current character the appropriate amount of steps. We just speed this up
 61 # by doing that in a single step.
 62 # Repeat this for all characters in the string.
 63 
 64 use v5.36;
 65 
 66 alternate_case("aAbB");
 67 alternate_case("AAbb");
 68 alternate_case("AAAbbb");
 69 alternate_case("aABb");
 70 alternate_case("bBBAaa");
 71 
 72 sub alternate_case($str) {
 73     say "Input: \"$str\"";
 74     my $s1 = _alternate_case($str);
 75     my @chars = split //, $str;
 76     my $next_other;
 77     if(isupper($chars[0])) {
 78         $next_other = find_next_lower(0, @chars);
 79     } else {
 80         $next_other = find_next_upper(0, @chars);
 81     }
 82     @chars = ($chars[$next_other], @chars[0..$next_other-1], @chars[$next_other+1..$#chars]);
 83     my $s2 = ($next_other - 1) + _alternate_case(join("", @chars));
 84     if($s1 > $s2) {
 85         say "Output: $s2";
 86     } else {
 87         say "Output: $s1";
 88     }
 89 }
 90 
 91 sub _alternate_case($str) {
 92     my @chars = split //, $str;
 93     my $start_pointer = -1;
 94     my $next_other;
 95     my $swaps = 0;
 96     while($start_pointer < $#chars) {
 97         $start_pointer++;
 98         last if $start_pointer >= $#chars;
 99         if(isupper($chars[$start_pointer])) {
100             $next_other = find_next_lower($start_pointer, @chars);
101         } else {
102             $next_other = find_next_upper($start_pointer, @chars);
103         }
104         $swaps += ($next_other - $start_pointer - 1);
105         @chars = (@chars[0..$start_pointer], $chars[$next_other], @chars[$start_pointer+1..$next_other-1], @chars[$next_other+1..$#chars]);
106     }
107     return $swaps;
108 }
109 
110 sub isupper($char) {
111     if(ord($char) >= 64 && ord($char) <= 90) {
112         return 1;
113     }
114     return 0;
115 }
116 
117 sub find_next_upper($index, @chars) {
118     $index++;
119     while(! isupper($chars[$index]) ) {
120         $index++;
121     }
122     return $index;
123 }
124 
125 sub find_next_lower($index, @chars) {
126     $index++;
127     while(isupper($chars[$index]) ) {
128         $index++;
129     }
130     return $index;
131 }