Coding Exercise.

Group lines by their slope.

You’ve been given several lines. You’re interested in finding how many lines share the same slope. You’re tasked with writing a method that does exactly that. — For example, if you have two lines with a slope of 2.0, and one line with a slope of 1.0, the result is { { 2.0 Slope Line, 2 }, { 1.0 Slope Line, 1 } }. The coding exercise is here.

Requirements

Compute how many lines share the same slope, grouped by Line.

A line will never be made up of two points that share the same x coordinate. Test Cases

Your code will be run through a series of test cases. Consider edge-cases, such as an empty list of inputs.

Use Cases

Line line{
  {
      .X = 4, .Y = 3,
  },
  {
      .X = 2, .Y = 2
  },
};
Line line2{
  {
      .X = 8, .Y = 8,
  },
  {
      .X = 4, .Y = 4
  },
};
const auto groups = GroupPoints({ line, line2 });

My Implementation

#include <vector>
#include <unordered_map>
#include <algorithm>

struct Point {
    int X{};
    int Y{};

    bool operator==(const Point& other) const{
        return X == other.X && Y == other.Y;     
    }     
};

struct Line {
    Point A;
    Point B;
    double GetSlope() const {
        return (A.Y - B.Y) / static_cast<double>(A.X - B.X);
    }

    bool operator==(const Line& other) const{
        return GetSlope() == other.GetSlope();    
    }
};

namespace std{
    template<>
    struct hash<Point>{
        std::size_t operator()(const Point& point) const{
            std::size_t h1 = hash<int>{}(point.X);
            std::size_t h2 = hash<int>{}(point.Y);
            return (h1 << 1) ^ (h2);
        }
    };

    template<>
    struct hash<Line>{
        std::size_t operator()(const Line& line) const{
            return std::hash<double>{}(line.GetSlope());
        }
    };
}

using Lines = std::vector<Line>;
using Slope = double;
using Bucket = std::pair<Slope,std::vector<Line>>;

namespace dev{
    template<typename ForwardIterator, typename T>
    ForwardIterator first_equal_to_or_less_than(ForwardIterator first, ForwardIterator last, T key){
        auto it = std::upper_bound(first, last, key);
        return it == first ? last : --it;
    }
 }

std::unordered_map<Line, int> GroupPoints(const Lines& lines) {

    std::unordered_map<Line, int> groups;
    std::unordered_map<Slope, int> slope_count;
    if(lines.empty())
        return groups;

    std::for_each(lines.begin(), lines.end(), [&](const Line& line) mutable{
        ++groups[line];
    });

    return groups;     
}

int main()
{
    Line line1
    {
        {
            .X = 4, .Y = 3,
        },
        {
            .X = 2, .Y = 2
        },
    };
    Line line2
    {
        {
            .X = 8, .Y = 8,
        },
        {
            .X = 4, .Y = 4
        },
    };
    const auto groups = GroupPoints({line1, line2});
    for(auto& group : groups){
        auto [line, num_of_lines] = group;
        Point A = line.A;
        Point B = line.B;
        std::println("Line ({},{})--({},{})", A.X, A.Y, B.X, B.Y);
        std::println("Freq = {}", num_of_lines);
    }
    return 0;
}

Compiler Explorer

References

Coding exercises on getcracked.io