I just wrote some code I'm not proud of, but I just wanted to get shit done. However, I now turn to the collective wisdom of the fediverse to ask for the simplest algorithm to do the following:
Given a list of pairs of numbers (row and column indexes), check that all the numbers form a rectangle with no duplicates, and if so, return the position of the top-left element as well as the width and height of the rectangle. If not, return null.
To make things easier, I'm linking to my code below. However, I'm certain this is not the ideal solution. What is the cleanest algorithm to achieve this?
https://gist.github.com/lokedhs/5b71a8f3874429bb3ec434106396fca0
@loke Find the min x,y and max x,y, check the total number of elements equals the area of the rectangle (max x-min x+1)*(max y-min y+1).
The only remaining problem is to check there are no repeats, so sort the list of (x,y) lexicographically and look for duplicate pairs that will now be adjacent.
@sjb I meant min/max is the first and last elements
@namark I don't think that works because there could be an element out-of-bounds in Y that is lexicographically in the middle of the sequence in (X,Y), so you'd need an additional loop to find the bounds at least in one axis.
@sjb oh nooo, what a bummer, then nothing I said makes sense, I was so excited to write this, now I have to come up with something else.
@sjb I mean you could have min and max variables and calculate them in the your sorting loop, min/max-ing the same thing multiple times is not an issue, but that's just a cop-out.
@namark Yes, and all that remains is getting the min/max values and checking it is consistent with a rectangle, should work.