# The weekly challenge 248 - Task 1: Shortest Distance

1 #!/usr/bin/env perl 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-248/#TASK1 3 # 4 # Task 1: Shortest Distance 5 # ========================= 6 # 7 # You are given a string and a character in the given string. 8 # 9 # Write a script to return an array of integers of size same as length of the 10 # given string such that: 11 # 12 # distance[i] is the distance from index i to the closest occurence of 13 # the given character in the given string. 14 # 15 # The distance between two indices i and j is abs(i - j). 16 # 17 ## Example 1 18 ## 19 ## Input: $str = "loveleetcode", $char = "e" 20 ## Output: (3,2,1,0,1,0,0,1,2,2,1,0) 21 ## 22 ## The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed). 23 ## The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3. 24 ## The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2. 25 ## For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, 26 ## but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1. 27 ## The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2. 28 # 29 ## Example 2 30 ## 31 ## Input: $str = "aaab", $char = "b" 32 ## Output: (3,2,1,0) 33 # 34 ############################################################ 35 ## 36 ## discussion 37 ## 38 ############################################################ 39 # 40 # Let's split the input string into its characters and fill an 41 # array from that. Then we create a map using the positions of 42 # all occurrences of the wanted character. Now we walk the array 43 # and take the minimum of all possible differences found to 44 # elements from the map, or -1 if the map is empty (this is 45 # just extra error handling in case someone throws a character 46 # into the function that doesn't exist in the string, we just 47 # return -1 for all characters in that case). 48 49 use strict; 50 use warnings; 51 use List::Util qw(min); 52 53 shortest_distance("loveleetcode", "e"); 54 shortest_distance("aaab", "b"); 55 shortest_distance("aaab", "c"); 56 57 sub shortest_distance { 58 my ($string, $char) = @_; 59 print "Input: '$string', '$char'\n"; 60 my @str_chars = split //, $string; 61 my @map; 62 foreach my $i (0..$#str_chars) { 63 push @map, $i if $str_chars[$i] eq $char; 64 } 65 my @result = (); 66 foreach my $i (0..$#str_chars) { 67 push @result, min( map { abs($i - $_), } @map ) // -1; 68 } 69 print "Output: (" . join(",", @result) . ")\n"; 70 }