Task — Straight line

You are given a list of co-ordinates. Write a script to find out if the given points make a straight line.

Examples

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

Example 2
Input: @list = ([1, 4], [3, 4], [10, 4])
Output: true

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

Example 4
Input: @list = ([1, 1], [1, 1], [1, 1])
Output: true

Example 5
Input: @list = ([1000000, 1000000], [2000000, 2000000],
   [3000000, 3000000])
Output: true

Analysis

Well, this is easy, I thought: y = mx + c should do it. But ...

In most cases, all that is needed is to calculate the gradient, m, and the offset c - the y value where the straight line crosses x = 0. Take any two of the given points, and m and c are given by:

m = (y2 - y1) / (x2 - x1)
c = y - mx

Then look at all the other points, and if all their mx + c = y then all the points are collinear, ie 'true'.

So where are the problems? The first, and easily solved, problem is when every x is the same, so there is no x2 - x1 that isn't zero. However, in this case the points are all in a straight, vertical line so we can return 'true'.

If all the y values are also the same - that is, all the points are the same point - then again the answer is 'true' because any straight line through the point is a valid result.

So we are left with an x2 - x1 which is non-zero and on paper we can easily check that all the points satisfy y = mx + c (ie 'true'), or that one (or more) doesn't (ie 'false').

But this is a case where computers don't always do maths precisely with fractional numbers or very large numbers. You'll see in my code that when comparing a calculated y with a supplied y I've had to accept that they might differ - according to the computer - by 10^-20.

I did wonder about calculating the gradient more precisely by taking the 2 furthest spaced points, but calculating which two are furthest apart involves squaring their coordinates, which risks getting beyond Perl's (or strictly the hardware's) ability to hold exact values.

So a good challenge!

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2025-08-04
use utf8;     # Week 333 - task 1 - Straight line
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

straight_line([2, 1], [2, 3], [2, 5]);
straight_line([1, 4], [3, 4], [10, 4]);
straight_line([0, 0], [1, 1], [2, 3]);
straight_line([1, 1], [1, 1], [1, 1]);
straight_line([1000000, 1000000], [2000000, 2000000], [3000000, 3000000]);
straight_line([0, 0], [1, 1], [99999999, 100000000]);
straight_line([8, -5], [3, -2], [-2, 1]);
straight_line([8, -5], [3, -2], [-2, 1], [-7, 4], [-12, 7]);
straight_line([0, 0], [1, 0], [2, 1], [3, 2]);

sub straight_line {
    
    my (@p, $i, $j, @x, @y, $c, $d, $m, $yy, $same, $vertical, $input, $output);
    
    # initialise
    @p = @_;
    $i = 0;
    $vertical = $same = 1;

    # loop over points
    for $i (0 .. $#p) {
        ($x[$i], $y[$i]) = @{$p[$i]};
        $input .= '[' . sprintf('%d', $x[$i]) . ', ' . sprintf('%d', $y[$i]) . '], ';
        
        # check for points being identical or all the same x
        if ($i > 0) {
            if ($x[$i] != $x[0] or $y[$i] != $y[0]) {
                $same = 0;
                $d = $i;  # a point with diffferent x from x[0]
            }
            $vertical = 0 if $x[$i] != $x[0];
        }
    }
    $output = qq[true: any straight line through ($x[0], $y[0])] if $same;
    $output = qq[true: x = $x[0]] if ($vertical and not $same);
    
    # otherwise calculate gradient and offset (using points 0 and d)
    unless ($output) {
        $m = 0;
        $m = ($y[$d] - $y[0]) / ($x[$d] - $x[0]);
        $c = $y[0] - $m * $x[0];
        
        # check that all points fall on y = mx + c
        for $i (0 .. $#p) {
            $yy = $m * $x[$i] + $c;
        if (abs($yy - $y[$i]) > 1e-15) {
                $output = qq[false: ($x[$i], $y[$i]) is not collinear with points 0 and $d];
                last;
            }
        }
        
        # yes they do!
        $output = qq[true: y = ] . ($m != 0 ? ($m == -1 ? '-x' : ($m != 1 ? "${m}x " : 'x ')) : '') . 
            ($m != 0 ? ($c == 0 ? '' : ($c > 0 ? "+ $c" : '- ' . -$c)) : $c) unless $output;
    }
    
    say qq{\nInput:  \$list = (} . substr($input, 0, -2) . ')';
    say qq[Output: $output];
}

Output

Input:  $list = ([2, 1], [2, 3], [2, 5])
Output: true: x = 2

Input:  $list = ([1, 4], [3, 4], [10, 4])
Output: true: y = 4

Input:  $list = ([0, 0], [1, 1], [2, 3])
Output: false: (1, 1) is not collinear with points 0 and 2

Input:  $list = ([1, 1], [1, 1], [1, 1])
Output: true: any straight line through (1, 1)

Input:  $list = ([1000000, 1000000], [2000000, 2000000],
   [3000000, 3000000])
Output: true: y = x 

Input:  $list = ([0, 0], [1, 1], [99999999, 100000000])
Output: false: (1, 1) is not collinear with points 0 and 2

Input:  $list = ([8, -5], [3, -2], [-2, 1])
Output: true: y = -0.6x - 0.2

Input:  $list = ([8, -5], [3, -2], [-2, 1], [-7, 4], [-12,
   7])
Output: true: y = -0.6x - 0.2

Input:  $list = ([0, 0], [1, 0], [2, 1], [3, 2])
Output: false: (1, 0) is not collinear with points 0 and 3