Task — String chain

You are given an array of strings. Write a script to find out if the given strings can be chained to form a circle. Print 1 if found otherwise 0.

A string $S can be put before another string $T in the circle if the last character of $S is same as first character of $T, and the last character of the last string is the same as the first character of the first string.

Examples

Example 1
Input: @S = ("abc", "dea", "cd")
Output: 1 as we can form a circle e.g. "abc", "cd", "dea".

Example 2
Input: @S = ("ade", "cbd", "fgh")
Output: 0 as we can't form a circle.

Analysis

My first thought was to extract the first $a and last $z letter of each word, and construct a hash:

$hash{$a} += 1; $hash{$z} -= 1

Then check that all the hash values are 0, ie every first letter occurs exactly as often as every last letter. That works for most sets of words, but it fails for some tricky sets such as:

aaa, bbb, ccc, ddd - 4 single element circles
axb, bxc, cxa, mxn, nxo, oxm - 2 3-letter circles

Instead I went for a recursive approach, starting with $words[0] and adding end-to-start matches until all the words were included, and then checking the last word matched end-to-start with the first.

That ensures a single circle, and also copes with edge cases like
a, a, a.

Mildly interesting, perhaps, is the use of

splice @array, $start, $count

which deletes $count elements of @array starting at the one with index $start. I use that to remove each element of @words once it is added to @chain.

It's not easy, though, to find a circular sentence that makes sense.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-05-31
use utf8;     # Week 115 - task 1 - String chain
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

string_chain('abc', 'dea', 'cd');
string_chain('ade', 'cbd', 'fgh');
string_chain('horse', 'tortoise', 'tooth', 'egg', 'elephant', 'grant');
string_chain('a', 'a', 'a');
string_chain('axb', 'bxc', 'cxa', 'mxn', 'nxo', 'oxm');
string_chain('banana', 'a', 'ebb', 'artichoke');
string_chain('happy', 'lavish', 'smell', 'yaks');

sub string_chain {
    
    my (@words, $word, @chain);
    
    # initialise
    @words = @_;
    say qq[\nInput:  ] . join(q[, ], @words);

    # add first word to chain
    $chain[0] = $words[0];
    splice @words, 0, 1;
    
    say qq[Output: 0 - no circle found] unless make_chain(\@chain, \@words);
}

sub make_chain {
    
    my (@chain, @words, $must_start_with, @new_words, @new_chain, $j);
    
    @chain = @{$_[0]};    # chained words so far
    @words = @{$_[1]};    # words not yet in chain
    
    # if used all the words
    $must_start_with = substr($chain[-1], -1);
    if (keys @words == 0) {
        
        # success if the end matches the start
        if ($must_start_with eq substr($chain[0], 0, 1)) {
            say qq[Output: 1 = ] . join(' + ', @chain);
            return 1;
            
        # else not a possible order 
        } else {
            return 0;
        }
    
    # try adding another word
    } else {
        for $j (0 .. $#words) {
            
            # must have correct first letter
            next unless substr($words[$j], 0, 1) eq $must_start_with;
            
            # move this word into chain and recurse
            @new_words = @words;
            splice @new_words, $j, 1;
            @new_chain = @chain;
            push @new_chain, $words[$j];
            
            return 1 if make_chain(\@new_chain, \@new_words);
        }
        
        # no possible next word
        return 0;
    }   
}
    

last updated 2026-03-28 — 27 lines of code

Output

Input:  abc, dea, cd
Output: 1 = abc + cd + dea

Input:  ade, cbd, fgh
Output: 0 - no circle found

Input:  horse, tortoise, tooth, egg, elephant, 
   grant
Output: 1 = horse + egg + grant + tortoise + elephant + 
   tooth

Input:  a, a, a
Output: 1 = a + a + a

Input:  axb, bxc, cxa, mxn, nxo, oxm
Output: 0 - no circle found

Input:  banana, a, ebb, artichoke
Output: 1 = banana + a + artichoke + ebb

Input:  happy, lavish, smell, yaks
Output: 1 = happy + yaks + smell + lavish