The weekly challenge 340 - Task 1: Duplicate Removals
1 #!/usr/bin/env perl 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-340/#TASK1 3 # 4 # Task 1: Duplicate Removals 5 # ========================== 6 # 7 # You are given a string, $str, consisting of lowercase English letters. 8 # 9 # Write a script to return the final string after all duplicate removals have been made. Repeat duplicate removals on the given string until we no longer can. 10 # 11 # # A duplicate removal consists of choosing two adjacent and equal letters and removing them. 12 # 13 ## Example 1 14 ## 15 ## Input: $str = 'abbaca' 16 ## Output: 'ca' 17 ## 18 ## Step 1: Remove 'bb' => 'aaca' 19 ## Step 2: Remove 'aa' => 'ca' 20 # 21 # 22 ## Example 2 23 ## 24 ## Input: $str = 'azxxzy' 25 ## Output: 'ay' 26 ## 27 ## Step 1: Remove 'xx' => 'azzy' 28 ## Step 2: Remove 'zz' => 'ay' 29 # 30 # 31 ## Example 3 32 ## 33 ## Input: $str = 'aaaaaaaa' 34 ## Output: '' 35 ## 36 ## Step 1: Remove 'aa' => 'aaaaaa' 37 ## Step 2: Remove 'aa' => 'aaaa' 38 ## Step 3: Remove 'aa' => 'aa' 39 ## Step 4: Remove 'aa' => '' 40 # 41 # 42 ## Example 4 43 ## 44 ## Input: $str = 'aabccba' 45 ## Output: 'a' 46 ## 47 ## Step 1: Remove 'aa' => 'bccba' 48 ## Step 2: Remove 'cc' => 'bba' 49 ## Step 3: Remove 'bb' => 'a' 50 # 51 # 52 ## Example 5 53 ## 54 ## Input: $str = 'abcddcba' 55 ## Output: '' 56 ## 57 ## Step 1: Remove 'dd' => 'abccba' 58 ## Step 2: Remove 'cc' => 'abba' 59 ## Step 3: Remove 'bb' => 'aa' 60 ## Step 4: Remove 'aa' => '' 61 # 62 ############################################################ 63 ## 64 ## discussion 65 ## 66 ############################################################ 67 # 68 # We can use a regular expression with backreference: Replace a single 69 # character followed by itself with an empty string while this still 70 # works. 71 72 use v5.36; 73 74 duplicate_removals('abbaca'); 75 duplicate_removals('azxxzy'); 76 duplicate_removals('aaaaaaaa'); 77 duplicate_removals('aabccba'); 78 duplicate_removals('abcddcba'); 79 80 sub duplicate_removals ($str) { 81 say "Input: $str"; 82 while($str =~ s/(.)\1//) { } 83 say "Output: $str"; 84 }