# The Computer Thief

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

1this is a joke

• This post was in the Sandbox; posted 218 days ago but deleted later on; revised and undeleted for feedback one day ago. May 18, 2021 at 5:56
• How do you execute the code by hand? (Builds computer out of Lego) May 18, 2021 at 6:17
• @Ausername carefully (relevant xkcd) May 18, 2021 at 6:20
• Wow. (Useless filler because that's all I can say) May 18, 2021 at 6:29
• The requirement to sort/group is a bit of a pain - about 100 bytes of my mess is the suspicion code and the rest is grouping/sorting. May 18, 2021 at 7:21

# Python 2, 143120 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!

• Best thing is that it looks simple, unlike the JS answers which are unreadable.
– user100690
May 18, 2021 at 10:06
• 116 bytes May 18, 2021 at 22:44

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

• Why use jsfiddle instead of a Stack Snippet?
– Neil
May 18, 2021 at 20:37
• @Ausername Sorry, how is that relevant to Stack Snippets?
– Neil
May 18, 2021 at 21:56
• @Neil because I’m working on my mobile while stack snippets does not support mobile...
– tsh
May 18, 2021 at 23:53

# JavaScript (Node.js),269252 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!

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

• How did you manage to compress the grouping code so much? May 18, 2021 at 8:44
• @Ausername Here is a standalone version of the grouping code I'm using. May 18, 2021 at 8:51
• Nice! I tried to golf this, which is why mine ended up so big. May 18, 2021 at 8:58
• o.filter(a=>a) -> o.flat(0)
– tsh
May 18, 2021 at 9:57

# 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
• You could save 3 bytes using dot: ](</.~/:~.@])(+/%{.) .(*/@:<:"1/) ; Mine takes arguments in the opposite order: gifts left and persons right. I decided to post a comment because you arrived wit the same first, and I stole your division by {. ;). Nov 18, 2021 at 10:59

# 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


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

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

# Core Maude, 594571 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.

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

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.