Task — Matchstick square

You are given an array of integers, @ints. Write a script to find if it is possible to make a square using all the sticks in the given array where $ints[ì] is the length of i'th stick.

Examples

Example 1
Input: @ints = (1, 2, 2, 2, 1)
Output: true
Top: $ints[1] = 2
Bottom: $ints[2] = 2
Left: $ints[3] = 2
Right: $ints[0] and $ints[4] = 2

Example 2
Input: @ints = (2, 2, 2, 4)
Output: false

Example 3
Input: @ints = (2, 2, 2, 2, 4)
Output: false

Example 4
Input: @ints = (3, 4, 1, 4, 3, 1)
Output: true

Analysis

From the examples I am assuming that we are required to use all the matches in making a square. My first thought was that recursion would be needed. However, my second thought is that that isn't necessary. Here is my logic.

First of all, I can immediately return 'false' if the sum of all the matchstick lengths is not a multiple of 4, because clearly if the sides of a square are integers, say of length s, the sum of those must be 4s.

I can also return false if any of the sticks is more than s long, since all the sides are only s long.

I then sort the matchsticks, longest to shortest. For the first side of the square I start with the longest stick. I then try adding each successive stick, one at a time, until I find one that does no more than complete the side. So supposing that s is 5 and the longest matchstick is 3, I try 3 + 3 - too long, 3 + 2 - just right. If it were 3 + 1 - not long enough - I repeat the process, hoping to find another 1.

And then I repeat the process for sides 2 and 3. I don't need to do side 4 because what's left is necessarily exactly s long, but in fact I do do it in my code, just to make it simple to print our the composition of all 4 sides.

Because I reverse-sorted the sticks at the start, my algorithm will also prefer, say, a stick length 3 over a 2 and a 1. This works, because any other side that needs to fill a gap of 3 can use the 2 and the 1. If I'd used the 2 and 1 instead of the 3, there's a risk that the 2 and 1 fit in different other sides, so the 3 would not fit.

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2024-11-18
use utf8;     # Week 296 - task 2 - Matchstick square
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

matchstick_square(1, 2, 2, 2, 1);
matchstick_square(1, 3, 3, 3, 4, 5, 8, 9);
matchstick_square(20, 9, 3, 3, 7, 9, 3, 3, 7, 3, 3, 1, 3, 3, 7);
matchstick_square(5, 10, 5);
matchstick_square(2, 2, 2, 2, 4, 3);

sub matchstick_square {
    
    my (@ints, $sum, $no_good, @side, $m, $s, $try, $size, @result);
    
    # initialise
    @ints = @_;
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . ')';
    @ints = reverse sort {$a <=> $b} @ints;
    $no_good = 0;
    
    # see if the sum of the sticks is a multiple of 4 and that
    # the longest stick is no longer than a side of the square
    $sum += $_ for @ints;
    $size = int($sum / 4);
    if ($sum > 0 and $sum == 4 * $size and $ints[0] <= $size) {
        
        # loop over the 4 sides of the square
        for $s (0 .. 3) {
            $side[$s] = 0;
            
            # try to construct this side with the remaining matches
            for $m (0 .. $#ints) {
                next unless $ints[$m];
                $try = $side[$s] + $ints[$m];
                next if $try > $size;
                $side[$s] = $try;
                $result[$s] .= $ints[$m] . '+';
                $ints[$m] = 0;
                last if $side[$s] == $size;
            }
            
            # can't do it
            $no_good = 1 if $side[$s] ne $size;
            last if $no_good;
        }
        
        # report success
        unless ($no_good) {
            $result[$_] = substr($result[$_], 0, -1) for 0 .. 3;
            say qq[Output: true - sides are ] . join(', ', @result);
            return;
        }
    }
    # ... or failure
    say qq[Output: false];
}

Output

Input:  @ints = (1, 2, 2, 2, 1)
Output: true - sides are 2, 2, 2, 1+1

Input:  @ints = (1, 3, 3, 3, 4, 5, 8, 9)
Output: true - sides are 9, 8+1, 5+4, 3+3+3

Input:  @ints = (20, 9, 3, 3, 7, 9, 3, 3, 7, 3, 3, 1, 3, 
   3, 7)
Output: true - sides are 20+1, 9+9+3, 7+7+7, 3+3+3+3+3+3+3

Input:  @ints = (5, 10, 5)
Output: false

Input:  @ints = (2, 2, 2, 2, 4, 3)
Output: false