Closest sum

Weekly challenge 248 — 18 December 2023

Week 248 - 18 Dec 2023

Task 1

You are given a string and a character in the given string. Write a script to return an array of integers of size same as length of the given string such that distance[i] is the distance from index i to the closest occurence of the given character in the given string. The distance between two indices i and j is abs(i - j).

Example 1Input: $str = "loveleetcode", $char = "e" Output: (3,2,1,0,1,0,0,1,2,2,1,0) The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed). The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3. The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2. For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1. The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.Example 2Input: $str = "aaab", $char = "b" Output: (3,2,1,0)

I feel sure someone will come up with a one-liner, but I chose simply to pass twice along
the string, once forwards and once backwards, setting a counter to zero every time I met a `$char`

and incrementing it when I didn't.

For each string position, the desired result is the smaller of the counter value going forwards or backwards.

#!/usr/bin/perl use v5.26; # The Weekly Challenge - 2023-12-18 use utf8; # Week 248 task 1 - Shortest distance use strict; # Peter Campbell Smith use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge shortest_distance('loveleetcode', 'e'); shortest_distance('We wish you a merry christmas and a happy new year!', 'a'); shortest_distance('zoos contain animals', 'z'); shortest_distance('tornadoes have a vortex', 'x'); shortest_distance('xylophones and zithers', 'q'); sub shortest_distance { my ($string, $char, @letters, $last, @count, @dist, $j, $count, $i, $k); ($string, $char) = @_; # initialise @letters = split('', $string); $last = @letters - 1; $dist[$_] = 999 for 0 .. $last; $count = 999; # go along string forwards and backwards for $k (0, 1) { for $j (0 .. $last) { $i = $k ? $j : $last - $j; # if we've found a $char reset count to 0 if ($letters[$i] eq $char) { $count = $dist[$i] = 0; # or save the distance to the nearest $char } else { $count ++; $dist[$i] = $count if $count < $dist[$i]; } } } say qq[\nInput: \@string = '$string', \$char = '$char']; say qq[Output: ] . ($dist[0] != 999 ? join(', ', @dist) : qq['$char' does not occur in '$string']); }

Input: @string = 'loveleetcode', $char = 'e' Output: 3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0 Input: @string = 'We wish you a merry christmas and a happy new year!', $char = 'a' Output: 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 7, 6, 5, 4, 3, 2, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 1, 0, 1, 2, 3, 4, 5, 5, 4, 3, 2, 1, 0, 1, 2 Input: @string = 'zoos contain animals', $char = 'z' Output: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 Input: @string = 'tornadoes have a vortex', $char = 'x' Output: 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 Input: @string = 'xylophones and zithers', $char = 'q' Output: 'q' does not occur in 'xylophones and zithers'

The content of
this website
is licensed by
Peter
Campbell Smith under a
Creative Commons Attribution 4.0 International Licence