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.
@loke Actually I like your "compute-rect2.kt" better
@sjb Credit should go to @snowyfox who got me on the right path for that. 🙂
I also considered your solution that only requires to check for duplicates. It's neat, but I didn't implement it because I couldn't convince myself the duplicate check is efficient enough. Yes, I'm overthinking this, as that solution seems to be O(n log(n)) which is close enough to O(n) that it really shouldn't matter much.
@loke @sjb hmm, that would be changing the rules of the game though. I could also say that if the array happens to be sorted in the first place then you can do it in constant time. I was expecting something like "in my garbage collected language, allocating memory is as fast as accessing it"... "and/or accessing it is as slow as allocating"...
@namark @loke @snowyfox If you have to create a temporary copy of the array to do the sort (i.e. the original array is preserved), you end up with O(N) memory use anyway with the sort, and potentially larger because it's not just bit flags