Task — Boomerang

You are given an array of points, (x, y). Write a script to find out if the given points are a boomerang. A boomerang is a set of three points that are all distinct and not in a straight line.

Examples

Example 1
Input: @points = ( [1, 1], [2, 3], [3,2] )
Output: true

Example 2
Input: @points = ( [1, 1], [2, 2], [3, 3] )
Output: false

Example 3
Input: @points = ( [1, 1], [1, 2], [2, 3] )
Output: true

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

Example 5
Input: @points = ( [1, 1], [2, 1], [3, 1] )
Output: false

Example 6
Input: @points = ( [0, 0], [2, 3], [4, 5] )
Output: true

Analysis

My generic approach is to find the equation of the straight line joing points 1 and 2, and to test whether point 3 is on that line. If it isn't, then the points form a boomerang.

To get the equation of the line joining points 1 and 2:

$y = $m * $x + $c

I start by calculating

$m = ($y2 - $y1) / ($x2 - $x1)

and from that derive

$c = $y1 - $m * $x1

The test for being a boomerang is then

$y3 != $m * $x3 + $c

- true for a boomerang, false if all three points are on the same line.

There are some special cases. Firstly, the above method fails if
$x1 == $x2, that is, if point 2 is precisely vertically above or below point 1. The test for being a boomerang is then $x3 != $x2.

The test also fails if the points are not distinct, in which case the boomerang status is false.

And lastly, there may be some floating point equality involved, so rather than $a == $b I have used abs($a - $b) < 1e-30 which is far above normal engineering precision.

The above approach is simple and meets the stated requirements of the challenge. However, were this a real-world exercise I would approach it differently because of the potential imprecision of the floating point operations, which becomes significant, for example, if the first two points are relatively close and the third much further away.

I believe a better approach would be to regard the three points as forming a triangle. I would use the longest side as a baseline, and then calculate the length of the line perpendicular to the baseline that passed through the third point. If that line was shorter than some criterion - say 1% of the baseline length - then the points would be deemed a non-boomerang.

Of course, all this is probably irrelevant to the boomerang manufacturing industry, but it is a practical issue in the construction of large artefacts such as buildings, roads, tunnels and airport runways.

Try it 

Try running the script with any input:

Your @points =

example: [1, 2], [3, 4], [5, 6]

⤡

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2024-10-28
use utf8;     # Week 293 - task 2 - Boomerang
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

boomerang([1, 1], [2, 3], [3, 2]); # boomerang
boomerang([1, 1], [2, 2], [3, 3]); # straight line
boomerang([1, 1], [1, 2], [1, 3]); # vertical line
boomerang([1, 1], [1, 2], [2, 3]); # vertical with kink
boomerang([-7, -7], [0, 0], [7, 8]); # boomerang
boomerang([4, 3], [-5, 4], [-2, -2]);

# try ones with very small angle
boomerang([0, 0], [1, 1], [1000, 1000.001]);

sub boomerang {
    
    my ($x1, $x2, $x3, $y1, $y2, $y3, $m, $c, $y0);
    
    ($x1, $y1) = ($_[0]->[0], $_[0]->[1]);
    ($x2, $y2) = ($_[1]->[0], $_[1]->[1]);
    ($x3, $y3) = ($_[2]->[0], $_[2]->[1]);
    say qq[\nInput:  ([$x1, $y1], [$x2, $y2], [$x3, $y3])];
    
    # are the points distinct?
    if (($x1 == $x2 && $y1 == $y2) || ($x1 == $x3 && $y1 == $y3) || ($x2 == $x3 && $y2 == $y3)) {
        say qq[Output: false (points are not distinct)];
        return;
    }

    # general case
    if ($x1 != $x2) {
    
        # get equation y = mx + c of the line joining points 1 and 2
        $m = ($y2 - $y1) / ($x2 - $x1);
        $c = $y1 - $m * $x1;
            
        # see if point 3 is on the line
        $y0 = $m * $x3 + $c;
        
        say qq[Output: ] . (abs($y3 - $y0) < 1e-30 ? 'false' : 'true');
        
    # if point 1 to point 2 is a vertical line
    } else {
        say qq[Output: ] . (abs($x2 - $x3) < 1e-30 ? 'false' : 'true');
    }
        

}

Output

Input:  ([1, 1], [2, 3], [3, 2])
Output: true

Input:  ([1, 1], [2, 2], [3, 3])
Output: false

Input:  ([1, 1], [1, 2], [1, 3])
Output: false

Input:  ([1, 1], [1, 2], [2, 3])
Output: true

Input:  ([-7, -7], [0, 0], [7, 8])
Output: true

Input:  ([4, 3], [-5, 4], [-2, -2])
Output: true

Input:  ([0, 0], [1, 1], [1000, 1000.001])
Output: true