The weekly challenge 390 - Task 2: Order Characters

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-390/#TASK2
  3 #
  4 # Task 2: Order Characters
  5 # ========================
  6 #
  7 # You are given a string $s (containing only alphabetic characters) and an
  8 # integer $k > 0.
  9 #
 10 # Write a script to choose one of the first $k letters of given string and
 11 # append it at the end of the string. You keep doing this until you have
 12 # lexicographically smallest string and return the string.
 13 #
 14 ## Example 1
 15 ##
 16 ## Input: $str = "dbca", $k = 1
 17 ## Output: "adbc"
 18 ##
 19 ## Move 1: "bcad"
 20 ## Move 2: "cadb"
 21 ## Move 3: "adbc"
 22 #
 23 ## Example 2
 24 ##
 25 ## Input: $str = "geeks", $k = 2
 26 ## Output: "eegks"
 27 ##
 28 ## First 2 letters: "g", "e"
 29 ##
 30 ## Move 1: "gekse" (move second letter "e")
 31 ## Move 2: "gksee" (move second letter "e")
 32 ## Move 3: "kseeg"
 33 ## Move 4: "seegk"
 34 ## Move 5: "eegks"
 35 #
 36 ## Example 3
 37 ##
 38 ## Input: $str = "cbaed", $k = 3
 39 ## Output: "abcde"
 40 ##
 41 ## First 3 letters: "c", "b", "a"
 42 ##
 43 ## Move 1: "cbeda"  (move "a")
 44 ## Move 2: "cedab"  (move "b")
 45 ## Move 3: "edabc"  (move "c")
 46 ## Move 4: "eabcd"  (move "d")
 47 ## Move 5: "abcde"  (move "e")
 48 #
 49 ## Example 4
 50 ##
 51 ## Input: $str = "fedcba", $k = 4
 52 ## Output: "abcdef"
 53 ##
 54 ## First 4 letters: "f", "e", "d", "c"
 55 ##
 56 ## Move 1: "fdcbae" (move "e")
 57 ## Move 2: "dcbaef" (move "f")
 58 ## Move 3: "dcbefa" (move "a")
 59 ## Move 4: "dcefab" (move "b")
 60 ## Move 5: "defabc" (move "c")
 61 ## Move 6: "efabcd" (move "d")
 62 ## Move 7: "fabcde" (move "e")
 63 ## Move 8: "abcdef" (move "f")
 64 #
 65 ## Example 5
 66 ##
 67 ## Input: $str = "perl", $k = 1
 68 ## Output: "erlp"
 69 ##
 70 ## Move 1: "erlp" (move "p")
 71 #
 72 ## Example 6
 73 ##
 74 ## Input: $str = "oloolooo", $k = 1
 75 ## Output: "looloooo"
 76 #
 77 ## Example 7
 78 ##
 79 ## Input: $str = "oloooolo", $k = 1
 80 ## Output: "looloooo"
 81 #
 82 ############################################################
 83 ##
 84 ## discussion
 85 ##
 86 ############################################################
 87 #
 88 # If k=1, we can pick the lexicographically smallest character in
 89 # the string and move it to the front; if this character appears
 90 # to be in the string multiple times, we can use the lexicographically
 91 # smallest string of all of the options where that character is at
 92 # the front.
 93 # If k=2, we can pick the lowest character and move it to the end,
 94 # then pick the first or second character until the second smallest
 95 # character comes to the front, then we pick the second character
 96 # until the first appears again, then move the smallest and second
 97 # smallest character to the end and pick 1 or 2 until we find the
 98 # third smallest character etc. That way, we can always sort the
 99 # whole string by smallest character.
100 # If k>2 we can do the same, albeit potentially slightly faster.
101 # So for k=1, we create all variations with the smallest character
102 # at the beginning and pick the lexicographically smallest one of
103 # these options, for k>=2 we sort the characters in the string
104 # lexicographically.
105 
106 use v5.36;
107 
108 order_characters("dbca", 1);
109 order_characters("geeks", 2);
110 order_characters("cbaed", 3);
111 order_characters("fedcba", 4);
112 order_characters("perl", 1);
113 order_characters("oloolooo", 1);
114 order_characters("oloooolo", 1);
115 
116 sub order_characters($str, $k) {
117     say "Input: \"$str\", $k";
118     my @chars = sort split //, $str;
119     if($k >= 2) {
120         return say "Output: \"" . join("", @chars) . "\"";
121     }
122     my $start_char = $chars[0];
123     my @options = ();
124     foreach my $i (0..length($str)-1) {
125         my $tmp = substr($str, $i, length($str) - $i);
126         $tmp .= substr($str, 0, $i) if $i;
127         push @options, $tmp;
128     }
129     my @sorted_options = sort @options;
130     say "Output: \"$sorted_options[0]\"";
131 }