You wake up and find out that your computer has been stolen! You have a few sensors and scanners, but unfortunately, the footage is incomplete, so you want to find and rank your suspects for further investigation.
Your computer is a rectangle, and your camera caught a bunch of people walking around with packages; however, there's a gift shop near your house so you can't be sure (and the camera footage doesn't seem to show if anyone went into your house). Based on that information, you want to determine who most likely stole your computer.
You will be given the dimensions of your computer and a list of (rectangular) gifts at the store by their dimensions. You will also be given a list of packages that people are holding as rectangle dimensions.
You are then to rank them by suspicion. A gift is said to fit in a package if its width and height are less than or equal to the package's width and height respectively, or height and width respectively. That is, basically whether or not it is a smaller rectangle, but with right-angle rotations allowed. If someone's package cannot fit your computer, then they have absolutely no suspicion. Otherwise, the more gifts they can fit, the less suspicious (basically, if they're carrying a larger package, it's more likely that they are just carrying a large gift rather than your computer).
(A formal way to describe this I guess would be: given a rectangle A, a list of rectangles B, and a list of rectangles C, sort C in increasing order of how many rectangles in B fit in each item, or infinity if A cannot fit in it, sort it to the end; then, group equal elements)
The input needs to contain the dimensions of your computer, the dimensions of all of the gifts, and the dimensions of each person's package. You can take these in any reasonable format.
Out of all gifts and your computer, no two items will have the same dimensions. No two people will have the same package dimensions. Both of these conditions are true even with rotation (so, no 2x3 and 3x2 gifts).
The output should be a two-dimensional list, where each sub-list contains people with the same suspicion level (order does not matter within a sub-list), and the sub-lists are sorted by suspicion level either up or down. You can output this in any reasonable format; as a 2D list, lines of lists, lines of space-separated values, etc.
You may either represent a person by their package dimensions (in either order, because it's unique), or by their index in the input list (you can choose any n-indexing).
You may either output all totally unsuspicious people as the last sublist or exclude them entirely (must be consistent). You may not have any empty sublists.
Let your computer have dimensions
[3, 5]. Let the gifts have dimensions
[2, 4], [2, 5], [3, 4], [3, 6], [4, 5], [4, 6]. Let the people have packages of dimensions
[2, 4], [3, 5], [4, 6], [2, 7], [3, 6], [4, 5].
First, let's see who isn't suspicious.
[2, 4] and
[2, 7] cannot fit
[3, 5] because the width is too small (
2 < min(3, 5)).
Next, let's count.
[3, 5] can fit
[2, 4], [2, 5], [3, 4], [3, 5]. Thus, their suspicion is 4 (3 gifts plus your computer), which turns out to be the most suspicious.
[3, 6] can fit
[2, 4], [2, 5], [3, 4], [3, 5], [3, 6], so their suspicion is 5.
[4, 5] can fit
[2, 4], [2, 5], [3, 4], [3, 5], [4, 5], so their suspicion is also 5.
[4, 7] can fit
[2, 4], [2, 5], [3, 4], [3, 5], [3, 6], [4, 5], [4, 6], so their suspicion is 7. Since they could be carrying any of the gifts, they are the least suspicious.
Thus, a valid output would be
[, [4, 5], , [0, 3]] (including the non-suspicious people in at the end in a sublist, in 0-indexing).
A reference implementation is provided here. The input contains three sections; the first is the computer, the second is the gifts, and the third is the packages. The output contains a brief explanation of each suspicion level, and at the end, it provides four valid output formats. These are not the only valid ones, but they would be valid.
Rules and Specifications
- No dimensions will be smaller than 1, and all dimensions are integers. There may be no people or no gifts.
- You may demand the dimensions to be inputted in any order. Since the orientation does not matter anywhere in this challenge, you can choose any reasonable and consistent way of inputting these two numbers.
- Standard loopholes apply, as always.
- Since your computer was stolen, you'll need to write and run your code by hand. Since shorter code runs faster obviously1, and you need to do it manualy, you need to make your code as short as possible. Thus, the shortest code in bytes wins (this is a code-golf challenge).
1this is a joke