Fork me on GitHub

Project Notes

#496 findJoeys

Using perl to find synonyms hiding within their alter ego: cassidoo’s interview question of the week (2026-11-16).

Notes

The interview question of the week (2026-11-16):

A kangaroo word contains a shorter synonym (its “joey”) whose letters appear in order, but not necessarily consecutively. Given a lowercase word and a list of its synonyms (non-empty), return all the joeys in the list’s original order. The synonyms are provided, you don’t need to determine whether two words mean the same thing. Unless you really want to.

Examples:

findJoeys("blossom", ["flower", "bloom"]);
// ["bloom"]

findJoeys("chocolate", ["cocoa", "candy"]);
// ["cocoa"]

findJoeys("cat", ["feline"]);
// []

Thinking about the Problem

My first thought is to recall the translate function that is supported in many languages such as Perl, Python, and Ruby. It basically allows mapping of selected characters, and removal of anything that does not map.

So if we map the source word using the synonym as the translation map, and the resulting string matches the synonym … we have found it hiding in the source word.

Strictly speaking, the practical way to do this in most languages is to map every character that is not in the synonym to “”. For example in Perl:

$ perl -e 'my $text = "blossom"; $text =~ tr/flower//cd; print $text . "\n";'
loo
$ perl -e 'my $text = "blossom"; $text =~ tr/bloom//cd; print $text . "\n";'
bloom

Or Ruby:

$ ruby -e 'puts "blossom".tr("^flower", "")'
loo
$ ruby -e 'puts "blossom".tr("^bloom", "")'
bloom

Initial Solution

Let’s do this with Perl’s Transliteration Quote-Like Operators.

The main thing to note is that tr compiles the translation, so we need to use an eval to prepare the translation at runtime. e.g. isWithin checks if the synonym is found in the given word:

sub isWithin {
  my ($word, $synonym) = @_;
  eval "\$word =~ tr/\Q$synonym\E//cd";
  die $@ if $@;
  return $word eq $synonym ? 1 : 0;
}

We can now write findJoeys as just a loop, accumulating any synonyms that are found within the source word:

sub findJoeys {
  my ($word, $synonyms) = @_;
  my @results = ();
  foreach my $synonym (@$synonyms) {
    if (isWithin($word, $synonym)) {
      push @results, $synonym;
    }
  }
  return @results;
}

And that seems to work pretty well:

$ ./challenge.pl
Usage: perl challenge.pl <word> <csv-synonyms>
$ ./challenge.pl "blossom" "flower, bloom"
# given word=blossom, synonyms=[flower, bloom], result is:
[bloom]
$ ./challenge.pl "chocolate" "cocoa, candy"
# given word=chocolate, synonyms=[cocoa, candy], result is:
[cocoa]
$ ./challenge.pl "cat" "feline"
# given word=cat, synonyms=[feline], result is:
[]

Tests

I’ve setup some validation in challenge.t:

$ prove -t challenge.t
challenge.t .. ok
All tests successful.
Files=1, Tests=5,  0 wallclock secs ( 0.01 usr  0.00 sys +  0.01 cusr  0.00 csys =  0.02 CPU)
Result: PASS

Final Code

See challenge.pl for the final code.

#!/usr/bin/env perl
#
use strict;
use warnings;

sub isWithin {
  my ($word, $synonym) = @_;
  eval "\$word =~ tr/\Q$synonym\E//cd";
  die $@ if $@;
  return $word eq $synonym ? 1 : 0;
}

sub findJoeys {
  my ($word, $synonyms) = @_;
  my @results = ();
  foreach my $synonym (@$synonyms) {
    if (isWithin($word, $synonym)) {
      push @results, $synonym;
    }
  }
  return @results;
}

if (!caller()) {
  if (@ARGV != 2) {
    print STDERR "Usage: perl challenge.pl <word> <csv-synonyms>\n";
    exit 1;
  }
  my $word = $ARGV[0];
  my @synonyms = map { s/^\s+|\s+$//g; $_ } split(',', $ARGV[1]);

  print STDERR "# given word=$word, synonyms=[" . join(', ', @synonyms) . "], result is:\n";

  my @result = findJoeys($word, \@synonyms);
  print "[" . join(', ', @result) . "]\n";
}

1;

Credits and References

About LCK#496
Perlcassidoo

This page is a web-friendly rendering of my project notes shared in the LittleCodingKata GitHub repository.

Project Source on GitHub Return to the LittleCodingKata Catalog
About LittleCodingKata

LittleCodingKata is my collection of programming exercises, research and code toys broadly spanning things that relate to programming and software development (languages, frameworks and tools).

These range from the trivial to the complex and serious. Many are inspired by existing work and I'll note credits and references where applicable. The focus is quite scattered, as I variously work on things new and important in the moment, or go back to revisit things from the past.

This is primarily a personal collection for my own edification and learning, but anyone who stumbles by is welcome to borrow, steal or reference the work here. And if you spot errors or issues I'd really appreciate some feedback - create an issue, send me an email or even send a pull-request.

Follow the Blog follow projects and notes as they are published in your favourite feed reader