15
\$\begingroup\$

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

\$\endgroup\$
7
  • \$\begingroup\$ This post was in the Sandbox; posted 218 days ago but deleted later on; revised and undeleted for feedback one day ago. \$\endgroup\$ – hyper-neutrino May 18 at 5:56
  • \$\begingroup\$ How do you execute the code by hand? (Builds computer out of Lego) \$\endgroup\$ – A username May 18 at 6:17
  • 2
    \$\begingroup\$ @Ausername carefully (relevant xkcd) \$\endgroup\$ – hyper-neutrino May 18 at 6:20
  • \$\begingroup\$ Wow. (Useless filler because that's all I can say) \$\endgroup\$ – A username May 18 at 6:29
  • \$\begingroup\$ 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. \$\endgroup\$ – A username May 18 at 7:21

10 Answers 10

5
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Best thing is that it looks simple, unlike the JS answers which are unreadable. \$\endgroup\$ – Recursive Co. May 18 at 10:06
  • \$\begingroup\$ 116 bytes \$\endgroup\$ – dingledooper May 18 at 22:44
4
\$\begingroup\$

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.

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

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!

\$\endgroup\$
3
\$\begingroup\$

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.

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

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
1
\$\begingroup\$

Charcoal, 46 bytes

≔Eζ∨±∨›⌊θ⌊ι›⌈θ⌈ιLΦη∨›⌊λ⌊ι›⌈λ⌈ιεW⁻ευ⊞υ⌈ιIEυ⌕Aει

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

≔Eζ∨±∨›⌊θ⌊ι›⌈θ⌈ιLΦη∨›⌊λ⌊ι›⌈λ⌈ιε

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.

W⁻ευ⊞υ⌈ι

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

IEυ⌕Aει

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

\$\endgroup\$
1
\$\begingroup\$

Core Maude, 594 571 bytes

fmod D is pr NAT . sort D . op _x_ : Nat Nat -> D[ctor]. endfm view D from TRIV
to D is sort Elt to D . endv fmod C is inc LIST{Set{D}}*(sort List{Set{D}}to
L). vars A B C : D . vars N M P Q : Nat . vars S T U X Y : L . op p : D L
L -> L . op f : D D L -> Nat . eq X empty Y = X Y . 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 x M,A,(P
x Q,S))= s f(N x M,A,S)if N >= P /\ M >= Q . eq f(N x M,P x Q,S)= if N <
P or M < Q then s | S | else 0 fi[owise]. endfm

Example Session

             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Tue May 18 23:37:06 2021
Maude> fmod D is pr NAT . sort D . op _x_ : Nat Nat -> D[ctor]. endfm view D from TRIV
Maude> to D is sort Elt to D . endv fmod C is inc LIST{Set{D}}*(sort List{Set{D}}to
Maude> L). vars A B C : D . vars N M P Q : Nat . vars S T U X Y : L . op p : D L
> L -> L . op f : D D L -> Nat . eq X empty Y = X Y . 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 x M,A,(P
> x Q,S))= s f(N x M,A,S)if N >= P /\ M >= Q . eq f(N x M,P x Q,S)= if N <
> P or M < Q then s | S | else 0 fi[owise]. endfm
Maude> red p(3 x 5, (2 x 4, 2 x 5, 3 x 4, 3 x 6, 4 x 5, 4 x 6), (2 x 4, 3 x 5, 4 x 6, 2 x 7, 3 x 6, 4 x 5)) .
Advisory: <standard input>, line 4 (fmod C): collapse at top of X empty Y may cause it to match more than you expect.
reduce in C : p(3 x 5, (2 x 4, 2 x 5, 3 x 4, 3 x 6, 4 x 5, 4 x 6), (2 x 4, 3 x 5, 4 x 6, 2 x 7, 3 x 6, 4 x 5)) .
rewrites: 2384 in 2ms cpu (2ms real) (801075 rewrites/second)
result NeList{Set{D}}: (3 x 5) (3 x 6, 4 x 5) (4 x 6) (2 x 4, 2 x 7)

Ungolfed

fmod D is
    pr NAT .
    sort D .
    op _x_ : Nat Nat -> D [ctor] .
endfm

view D from TRIV to D is
    sort Elt to D .
endv

fmod C is
    inc LIST{Set{D}} * (
        sort List{Set{D}} to L
    ) .

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

    op p : D L L -> L .
    op f : D D L -> Nat .

    eq X empty Y = X Y .

    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 x M, A, (P x Q, S)) = s f(N x M, A, S) if N >= P /\ M >= Q .
    eq f(N x M, P x Q, S) = if N < P or M < Q then s | S | else 0 fi [owise] .
endfm

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, using the infix function x. 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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.