Task — Array formation

You are given two lists: @source and @target. Write a script to see if you can build the exact @target by putting these smaller lists from @source together in some order. You cannot break apart or change the order inside any of the smaller lists in @source.

Examples

Example 1
Input: @source = ([2,3], [1], [4])
       @target = (1, 2, 3, 4)
Output: true
Use in the order: [1], [2,3], [4]

Example 2
Input: @source = ([1,3], [2,4])
       @target = (1, 2, 3, 4)
Output: false

Example 3
Input: @source = ([9,1], [5,8], [2])
       @target = (5, 8, 2, 9, 1)
Output: true
Use in the order: [5,8], [2], [9,1]

Example 4
Input: @source = ([1], [3])
       @target = (1, 2, 3)
Output: false
Missing number: 2

Example 5
Input: @source = ([7,4,6])
       @target = (7, 4, 6)
Output: true
Use in the order: [7, 4, 6]

Analysis

I can see two ways of doing this. The first solution involves adding one item from @source to a trial concatenation. If that matches the corresponding items in @target, repeat, adding the other items from @source one by one until either they all match @target or you've tried all of the remaining source items and none match.

This has to be done recursively, because once you hit a mismatch it is still possible that by backtracking you will find a match. For example:

@source = ([2], [1], [3, 4]); @target = (2, 1, 4, 3)

Your trial solution goes [2], [1] but then fails because the target contains [...4, 3] and you've only got [3, 4] left.

The backtracking could be done using recursion, or by pushing and popping the key variables on a stack. Recursion in Perl can be quite slow, so I would try the stack option if performance was an issue.

The second solution, which is the one I have submitted, simply permutes all the possible arrangements of the source items and checks them to see if they join to form the target. This is fairly simple and concise to code, but will start getting slow if there are a lot of items in @source.

I'll be interested to see how others approach this challenge.

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2025-10-20
use utf8;     # Week 344 - task 2 - Array formation
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;
use Algorithm::Combinatorics 'permutations';

array_formation([[2, 3], [1], [4]], [1, 2, 3, 4]);
array_formation([[1, 3], [2], [4]], [1, 2, 3, 4]);
array_formation([[9, 1], [5, 8], [2]], [5, 8, 2, 9, 1]);
array_formation([[1], [3]], [1, 2, 3]);
array_formation([[1], [2], [3], [4]], [1, 2, 3]);
array_formation([[3, 5], [2, 6, 5], [4, 1, 5], [3, 1], [9]], [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]);

sub array_formation {
    
    my (@source, @target, $iter, $c, @trial, $j, $explain, $source_text, $source_count);
    
    # initialise
    @source = @{$_[0]};
    @target = @{$_[1]};
    $source_text .= '[' . join(', ', @{$source[$_]}) . ']' for 0 .. $#source;
    $source_text =~ s|\Q][|], [|g for 0 .. $#source;    
    say qq{\nInput:  \@source = ($source_text)\n        \@target = (} . join(', ', @target) . ')';
    
    # must be same number of numbers in source and target
    $source_count += @{$_} for @source;
    if ($source_count == @target) {
    
        $iter = permutations(\@source);
            
        # loop over all perms of source sub-arrays
        ITER: while ($c = $iter->next) {
            @trial = ();
            $explain = '';
            
            # concatenate the sources
            for (@$c) {
                push @trial, @{$_};
                $explain .= '(' . join(', ', @{$_}) . '), ';
            }
            
            # check if the concatenated sources match the target
            for $j (0 .. $#target) {
                next ITER unless $trial[$j] == $target[$j];
            }
            
            # they do!
            say qq[Output: true -- ] . substr($explain, 0, -2);
            return;     
        }
    }
    say qq[Output: false];
}

Output

Input:  @source = ([2, 3], [1], [4])
        @target = (1, 2, 3, 4)
Output: true -- (1), (2, 3), (4)

Input:  @source = ([1, 3], [2], [4])
        @target = (1, 2, 3, 4)
Output: false

Input:  @source = ([9, 1], [5, 8], [2])
        @target = (5, 8, 2, 9, 1)
Output: true -- (5, 8), (2), (9, 1)

Input:  @source = ([1], [3])
        @target = (1, 2, 3)
Output: false

Input:  @source = ([1], [2], [3], [4])
        @target = (1, 2, 3)
Output: false

Input:  @source = ([3, 5], [2, 6, 5], [4, 1, 5],
    [3, 1], [9]) 
        @target = (3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5)
Output: true -- (3, 1), (4, 1, 5), (9), (2, 6, 5), (3, 5)