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.

Loved behind the scene story about the slow resposnse of using regex. You get DIY tool as bonus as always. Thanks for sharing knowledge with us.

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];
}

26 lines of code

Output from script

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