Peter
Peter Campbell Smith

Closest sum

Weekly challenge 248 — 18 December 2023

Week 248 - 18 Dec 2023

Task 1

Task — Shortest distance

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).

Examples


Example 1
Input: $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 2
Input: $str = "aaab", $char = "b"
Output: (3,2,1,0)

Analysis

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.

Try it 

Try running the script with any input:



example: supercalifragilisticexpialidocious



example: i

Script


#!/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']); 
}

Output


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 which has been created by
Peter Campbell Smith is hereby placed in the public domain