The Computer Thief

Question

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.

Challenge

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)

Input

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).

Output

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.

Worked Example

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 [[1], [4, 5], [2], [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 obviously¹, 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}

Answer 1

Python 2, 143 120 119 bytes

-20 bytes by assuming the smaller dimension is always given first.
-1 bytes thanks to dingledooper!

Takes input as computer, gifts, packages from STDIN. Outputs as a list of of lists of package dimensions in descending suspicion levels. Does not include unsuspicious packages.

c,g,p=input()
r=[[]for _ in g+p]
for y in p:A,B=y;x=[a-A<1>b-B for a,b in[c]+g];r[sum(x)]+=[y]*x[0]
print filter(len,r)

Try it online!

Answer 2

JavaScript (ES2021), 113 bytes

(d,g,p)=>p.map(([W,H],i)=>(o[-[d,...g].map(([w,h])=>t+=w>W|h>H&&h>W|w>H,t=0)[0]|t]??=[]).push(i),o=[])&&o.flat(0)

No TIO available.

https://jsfiddle.net/2s9xobkd/

Based on Arnauld‘s solution.

Answer 3

JavaScript (Node.js),269 252 248 bytes

([x,y],p,g)=>[...(h=p.map(([X,Y],i)=>[i,(X>Y?Y:X)<(x>y?y:x)||g.map(([W,H])=>t+=(X>W|Y>H)&(Y>W|X>H),t=1)&&t]).sort((a,b)=>a[1]-b[1]).reduce((r,a,i)=>i&&a[1]==(I=r[r.length-1])[0][1]?(I.push(a),r):[...r,[a]],[]).map(x=>x.map(y=>y[0]))).slice(1),h[0]]

Very slightly less messy.

Try it online!

Answer 4

JavaScript (ES10),  129  124 bytes

-5 bytes by swithing to ES10 and using .flat(0), as suggested by @tsh

Expects ([computer_w, computer_h], gifts, packages).

(d,g,p)=>p.map(([W,H],i)=>(o[g.map(y=>t+=3*(F=([w,h])=>w>W|h>H&&h>W|w>H)(d)|!F(y),t=0)|t]=o[t]||[]).push(i),o=[])&&o.flat(0)

Try it online!

How?

For each package with dimensions \$(W,H)\$ and for each gift with dimensions \$(w,h)\$ among \$N\$ distinct gifts:

• we add 3 points to the package score if it can't fit the computer
• we add 1 point to the package score if it can fit both the computer and the gift
• we don't add any point to the package score if it can fit the computer but not the gift

So the score of a package that can't fit the computer is always \$3N\$ and the score of a package that can fit it is in \$[0\dots N]\$.

Higher scores are less suspicious.

Answer 5

J, 36 bytes

Takes packages as left argument and computer, gifts as right argument:

[(</.~/:~.@])[:({."1%~1#.])*/@:>:"1/

Try it online!

How it works

• */@:>:"1/ a table of "can package fit computer/gift?"
• 1#.] sum columns: the numbers of computer/gifts a package can fit
• {."1%~ divided by 0 iff the package cannot fit the computer, otherwise divided by 1. So unsuspicious people get a score of infinity, because that's how division works. :-)
• </.~ group the people by their scores
• ~.@] the unique scores
• /: order the groups by the unique scores, lower scores first

Answer 6

Jelly, 10 bytes

>Ẹ¥þ-SḢ?€Ġ

Try it online!

A dyadic link taking the computer and gifts as a single list [computer, gift, gift, …] as the left argument and the packages as the right argument. Returns a list of sublists in in increasing order of suspicion starting with those who are not suspicious at all. Like Jelly does normally, this uses 1-indexing.

Explanation

  ¥þ       | For each pairing of computer/gift and package:
>          | - Greater than (vectorises)
 Ẹ         | - Any
      Ḣ?€  | For each package, is the head (i.e. computer) too big?
    -      | - If yes, -1
     S     | - If no, the sum of the remaining gifts that don’t fit
         Ġ | Group indices by their values in ascending order

Answer 7

R, 84 81 bytes

function(i,j)split(seq(a=x<-apply(j,2,function(a,s=!colSums(a<i))sum(s/s[1]))),x)

Try it online!

Takes input as two matrices: \$i\$ holds items (computer dimensions in the first column, gift dimensions in subsequent columns), \$j\$ holds package dimensions.

Output is a list (from most suspicious to non-suspicious) with 1-indexed people IDs.

Thanks for -3 bytes to Nick Kennedy.

Answer 8

Charcoal, 46 bytes

≔Ｅζ∨±∨›⌊θ⌊ι›⌈θ⌈ιＬΦη∨›⌊λ⌊ι›⌈λ⌈ιεＷ⁻ευ⊞υ⌈ιＩＥυ⌕Ａει

Try it online! Link is to verbose version of code. Explanation:

≔Ｅζ∨±∨›⌊θ⌊ι›⌈θ⌈ιＬΦη∨›⌊λ⌊ι›⌈λ⌈ιε

For each package, count the number of gifts that don't fit in the package, or -1 if the computer doesn't fit in the package.

Ｗ⁻ευ⊞υ⌈ι

Sort in descending order of the numbers of gifts that don't fit.

ＩＥυ⌕Ａει

Output the indices of packages grouped by the numbers of gifts that don't fit.

Answer 9

Core Maude, 594 571 472 bytes

in linear
mod C is inc LIST{Set{IndexPair}}*(sort IndexPair to D). vars A B C : D
. vars N M P Q : Nat . vars S T U X Y :[D]. op p : D D D ~> D . op f : D D D
~> Nat . eq X empty = X . ceq p(A,S,X(B,C,T)Y)= p(A,S,X(B,T)C Y)if f(C,A,S)>
f(B,A,S). ceq p(A,S,X(B,T)(C,U)Y)= p(A,S,X T(B,C,U)Y)if f(B,A,S)>= f(C,A,S). eq
p(A,S,X)= X[owise]. ceq f((N,M),A,((P,Q),S))= s f((N,M),A,S)if N >= P /\ M >=
Q . eq f((N,M),(P,Q),S)= if N < P or M < Q then s | S | else 0 fi[owise]. endm

Example Session

Maude> red p(
>     (3, 5),
>     ((2, 4), (2, 5), (3, 4), (3, 6), (4, 5), (4, 6)),
>     ((2, 4), (3, 5), (4, 6), (2, 7), (3, 6), (4, 5))
> ) .
Advisory: <standard input>, line 7 (mod C): collapse at top of X empty may
    cause it to match more than you expect.
result NeList{Set{IndexPair}}: (3,5) (3,6, 4,5) (4,6) (2,4, 2,7)

Ungolfed

in linear

mod C is
    inc LIST{Set{IndexPair}} * (
        sort IndexPair to D
    ) .

    vars A B C : D .
    vars N M P Q : Nat .
    vars S T U X Y : [D] .

    op p : D D D ~> D .
    op f : D D D ~> Nat .

    eq X empty = X .

    ceq p(A, S, X (B, C, T) Y) = p(A, S, X (B, T) C Y) if f(C, A, S) > f(B, A, S) .
    ceq p(A, S, X (B, T) (C, U) Y) = p(A, S, X T (B, C, U) Y) if f(B, A, S) >= f(C, A, S) .
    eq p(A, S, X) = X [owise] .

    ceq f((N, M), A, ((P, Q), S)) = s f((N, M), A, S) if N >= P /\ M >= Q .
    eq f((N, M), (P, Q), S) = if N < P or M < Q then s | S | else 0 fi [owise] .
endm

This program accepts input as a three-argument function p:

1. The dimensions of the computer
2. The set of dimensions of the gifts
3. The set of dimensions of the people's packages

All dimensions must be given smaller side first as comma-separated pairs. The second and third arguments must be comma-separated sets of dimensions (since order doesn't matter and there are guaranteed no repeats).

The output format is list of sets. Each set represents a group of the packages at that "suspicion level". I chose output the dimensions rather than the indexes because Maude doesn't have a reasonable indexed array module.

---

Edit. Completely rewritten to save 23 bytes.

Saved 99 bytes by replacing the bespoke dimension module D with IndexPair from the linear.maude standard library.

Answer 10

Haskell, 86 bytes

(n#p)c g=filter(>[])[[j|j<-p,c?j,sum[1|k<-g,k?j]==i]|i<-[0..n]]
[x,y]?[z,w]=x<=z&&y<=w

Try it online!

The relevant function is (#), which takes as input the number of packages n and the list of packages p, the computer c and the list of gifts g. It returns a list of groups of packages, sorted from the most suspicious group to the least suspicious group. Each box/item is represented as a list [w,h], with w<=h.