C# Minimum difference in a list

Question

I want to find minimum difference in a list of xy point data. (can contain duplicate x values and y values)

Example:
List<Point> differenceList = new List<Point>() { (10,0), (10,20), (20,30), (12,61) };

Expected result

X difference = 2 
Y difference = 20 

is it possible to do this elegantly may be using linq/lambda expressions? Thanks!

Answer 1

class Point
{
    public int X { get; set; }
    public int Y { get; set; }
    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }
}

class Program
{
    static void Main(string[] args)
    {
        List<Point> differenceList =
            new List<Point>()
            {
                new Point(40, 60), 
                new Point(10, 20),
                new Point(20, 30), 
                new Point(12, 61) };

        var q = from p1 in differenceList
                from p2 in differenceList
                let distance = Math.Abs(p1.X - p2.X)
                where !object.ReferenceEquals(p1, p2)
                select new { Point1 = p1, Point2 = p2, Distance = distance };

        var minimum = q.OrderBy(r => r.Distance).First();
        Console.WriteLine(
            "X difference = " +
            minimum.Distance +
            " (which is " +
            Math.Max(minimum.Point1.X, minimum.Point2.X) +
            " - " +
            Math.Min(minimum.Point1.X, minimum.Point2.X) + ")");

        Console.ReadLine();
    }
}

You could write the query and selecting the minimum in a single statement like this:

var minimum = (from p1 in differenceList
                from p2 in differenceList
                let distance = Math.Abs(p1.X - p2.X)
                where !object.ReferenceEquals(p1, p2)
                orderby distance
                select new { Point1 = p1, Point2 = p2, Distance = distance }).First();

The query for y is nearly the same and trivial

EDIT

Solution for a collection that contains duplicates and is using System.Windows.Point:

class Program
{
    static void Main(string[] args)
    {
        List<Point> differenceList =
            new List<Point>()
        {
            new Point(40, 60), 
            new Point(10, 20),
            new Point(20, 30), 
            new Point(12, 61),
            new Point(10, 20)};

        var q = from p1 in differenceList
                from p2 in differenceList
                let distance = Math.Abs(p1.X - p2.X)
                where !p1.Equals(p2)
                select new { Point1 = p1, Point2 = p2, Distance = distance };

        var minimum = q.OrderBy(r => r.Distance).First();
        Console.WriteLine(
            "X difference = " +
            minimum.Distance +
            " (which is " +
            Math.Max(minimum.Point1.X, minimum.Point2.X) +
            " - " +
            Math.Min(minimum.Point1.X, minimum.Point2.X) + ")");

        Console.ReadLine();
    }
}

Answer 2

Here's another implementation of how you could do it:

private static int MinimumDifference(List<int> numbers)
{
    numbers.Sort();
    var temp = numbers[1] - numbers[0];
    for (var i = 1; i < numbers.Count - 1; i++)
        if (numbers[i + 1] - numbers[i] < temp)
            temp = numbers[i + 1] - numbers[i];
    return temp;
}

To call the method you do this:

var minX = MinimumDifference(differenceList.Select(p => p.X).ToList())
var minY = MinimumDifference(differenceList.Select(p => p.Y).ToList())

Answer 3

"elegantly" is a big word... Elegance is in the eye of the beholder. This will work. I won't explain it to you because you didn't show what you did before asking.

class Point
{
    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }

    public int X;
    public int Y;
}

List<Point> differenceList = new List<Point>() { new Point(40, 60), new Point(10, 20), new Point(20, 30), new Point(12, 61) };

Func<Point, int> getPointX = p => p.X;
Func<Point, int> getPointY = p => p.Y;

Func<Func<Point, int>, int> finder = getter =>
{
    var temp = differenceList.OrderBy(getter).ToList();
    var min = temp.Zip(temp.Skip(1), (p, q) => getter(q) - getter(p)).Min();
    return min;
};

var minX = finder(getPointX);
var minY = finder(getPointY);

I'll add that if you want the p and q values that gives you the minimum difference then elegance will go out of the window. Sadly it isn't easy in LINQ to extract the minimum "object" if that object doesn't implement IComparable.

If you really want the full data, fortunately Tuple<> implements IComparable, then you have:

Func<Func<Point, int>, Tuple<int, int, int>> finder = getter =>
{
    var temp = differenceList.OrderBy(getter).ToList();
    var min = temp.Zip(temp.Skip(1), (p, q) => Tuple.Create<int, int, int>(getter(q) - getter(p), getter(q), getter(p))).Min();
    return min;
};

var minX = finder(getPointX);
var minY = finder(getPointY);

Console.WriteLine("X difference = {0} (which is {1} - {2})", minX.Item1, minX.Item2, minX.Item3);
Console.WriteLine("Y difference = {0} (which is {1} - {2})", minY.Item1, minY.Item2, minY.Item3);