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 }