School moving out (Day 1)

Question

^{Challenge Taken with permission from my University Code Challenge Contest}

---

For some years now, the number of students in my school has been growing steadily. First the number of students was increased by classroom, but then it was necessary to convert some spaces for some groups to give classes there, such as the gym stands or, this last course, up to the broom room.

Last year the academic authorities got the budget to build a new building and started the works. At last they have finished and the new building can be used already, so we can move (the old building will be rehabilitated and will be used for another function), but it has caught us halfway through the course. The director wants to know if the move will be possible without splitting or joining groups, or that some students have to change groups.

Challenge

Given the amount of students of the current groups and the new classrooms (capacity), output a truthy value if it is possible to assign a different classroom, with sufficient capacity, to each of the current groups, or a falsey value otherwise.

Test Cases

Input: groups of students => [10, 20, 30], classrooms capacity => [31, 12, 20]
Output: True

Input: groups of students => [10, 20, 30], classrooms capacity => [100, 200]
Output: False

Input: groups of students => [20, 10, 30], classrooms capacity => [20, 20, 50, 40]
Output: True

Input: groups => [30, 10, 30, 5, 100, 99], classrooms => [40, 20, 50, 40, 99, 99]
Output: False

Input: groups => [], classrooms => [10, 10, 10]
Output: True

Input: groups => [10, 10, 10], classrooms => []
Output: False

Input: groups => [], classrooms => []
Output: True

Input: groups => [10, 1], classrooms => [100]
Output: False

Input: groups => [10], classrooms => [100, 100]
Output: True

Input: groups => [1,2,3], classrooms => [1,1,2,3]
Output: True

Notes

• You can take the input in any reasonable format
• You can output any Truthy/Falsey value (1/0, True/False, etc...)
• code-golf

Answer 1

Brachylog, 4 bytes

It's always nice to see a challenge and know brachylog is gonna beat everyone. Takes current classes as input and new classrooms as output; It will output true if it finds a way to fit the students, false otherwise

p≤ᵐ⊆

Explanation

The code has 3 parts of which the order actually doesn't matter

≤ᵐ --> projects each value to a value bigger/equal then input
⊆  --> input is a ordered subsequence of output
p  --> permutes the list so it becomes a unordered subsequence

Try it online!

Answer 2

Pyth, 11 bytes

.AgM.t_DMQ0

Takes input as a list of lists, classroom sizes first, group sizes second. Try it online here, or verify all the test cases at once here.

.AgM.t_DMQ0   Implicit: Q=eval(input())
      _DMQ    Sort each element of Q in reverse
    .t    0   Transpose, padding the shorter with zeroes
  gM          Element wise test if first number >= second number
.A            Are all elements truthy? Implicit print

Answer 3

Jelly, 9 bytes

Takes the classrooms as first argument and the groups as second argument.

Œ!~+Ṡ‘ḌẠ¬

Try it online!

Commented

NB: This Ṡ‘ḌẠ¬ is far too long. But I suspect that this is not the right approach anyway.

Œ!~+Ṡ‘ḌẠ¬  - main link taking the classrooms and the groups e.g. [1,1,2,3], [1,2,3]
Œ!         - computes all permutations of the classrooms    -->  [..., [1,2,3,1], ...]
  ~        - bitwise NOT                                    -->  [..., [-2,-3,-4,-2], ...]
   +       - add the groups to each list; the groups fits   -->  [..., [-1,-1,-1,-2], ...]
             in a given permutation if all resulting values
             are negative
    Ṡ      - take the signs                                 -->  [..., [-1,-1,-1,-1], ...]
     ‘     - increment                                      -->  [..., [0,0,0,0], ...]
      Ḍ    - convert from decimal to integer                -->  [..., 0, ...]
       Ạ   - all truthy?                                    -->  0
        ¬  - logical NOT                                    -->  1

Answer 4

Japt, 9 bytes

ñÍí§Vñn)e

Try it or run all test cases on TIO

ñÍí§Vñn)e     :Implicit input of arrays U=students, V=classrooms
ñ             :Sort U by
 Í            :  Subtracting each integer from 2
  í           :Interleave with
    Vñn       :  V sorted by negating each integer
   §          :  Reduce each pair by checking if the first is <= the second
       )      :End interleaving
        e     :All true?

---

ñÍeȧVn o

Try it or run all test cases on TIO

ñÍeȧVn o     :Implicit input of arrays U=students, V=classrooms
ñ             :Sort U by
 Í            :  Subtracting each integer from 2
  e           :Does every element return true
   È          :When passed through the following function
    §         :  Less than or equal to
     Vn       :  Sort V
        o     :  Pop the last element

Answer 5

Python 2, 49 bytes

Outputs by exit code, fails for falsy input.

g,r=map(sorted,input())
while g:g.pop()>r.pop()>y

Try it online!

Answer 6

MATL, 10 bytes

yn&Y@>~!Aa

Try it online! Or verify all test cases.

Explanation

Consider inputs [20, 10, 30], [20, 20, 50, 40] as an example. Stack is shown bottom to top.

y     % Implicit inputs. Duplicate from below
      % STACK: [20 10 30]
               [20 20 50 40]
               [20 10 30]
n     % Number of elements
      % STACK: [20 10 30]
               [20 20 50 40]
               3
&Y@   % Variations. Gives a matrix, each row is a variation
      % STACK: [20 10 30]
               [20 10 30
                20 20 40
                20 20 40
                ···
                50 40 20]
>~    % Less than? Element-wise with broadcast
      % STACK: [1 1 1
                1 1 1
                1 1 1
                ···
                1 1 0]
!     % Transpose
      % STACK: [1 1 1 ··· 0
                1 1 1 ··· 1
                1 1 1 ··· 1]
A     % All. True for columns that only contain nonzeros
      % STACK: [1 1 1 ··· 0]
a     % Any. True if the row vector contains at least a nonzero. Implicit display
      % STACK: 1

Answer 7

Haskell, 40 bytes

c%l=[1|x<-l,x>=c]
s#g=and[c%s<=c%g|c<-s]

Try it online!

Answer 8

05AB1E, 14 12 8 bytes

€{í0ζÆdP

Port of @Sok's Pyth answer, so make sure to upvote him as well!

Takes the input as a list of lists, with the classroom-list as first item and group-list as second item.

Try it online or verify all test cases.

Explanation:

€{         # Sort each inner list
  í        # Reverse each inner list
   0ζ      # Zip/transpose; swapping rows/columns, with 0 as filler
     Æ     # For each pair: subtract the group from the classroom
      d    # Check if its non-negative (1 if truthy; 0 if falsey)
       P   # Check if all are truthy by taking the product
           # (and output implicitly)

---

Old 12-byte answer:

æε{I{0ζÆdP}à

Takes the classroom-list first, and then the group-list.

Try it online or verify all test cases.

Explanation:

æ             # Take the powerset of the (implicit) classroom-list,
              # resulting in a list of all possible sublists of the classrooms
 ε            # Map each classroom sublist to:
  {           #  Sort the sublist
   I{         #  Take the group-list input, and sort it as well
     0ζ       #  Transpose/zip; swapping rows/columns, with 0 as filler
       Æ      #  For each pair: subtract the group from the classroom
        d     #  Check for everything if it's non-negative (1 if truthy; 0 if falsey)
         P    #  Check if all are truthy by taking the product
          }à  # After the map: check if any are truthy by getting the maximum
              # (and output the result implicitly)

Answer 9

C# (Visual C# Interactive Compiler), 77 74 bytes

a=>b=>a.Count==a.OrderBy(x=>-x).Zip(b.OrderBy(x=>-x),(x,y)=>x>y?0:1).Sum()

Try it online!

Commented code:

// a: student group counts
// b: classroom capacities
a=>b=>
  // compare the number of student
  // groups to...
  a.Count==
  // sort student groups descending
  a.OrderBy(x=>-x)
     // combine with classroom
     // capacities sorted descending
     .Zip(
        b.OrderBy(x=>-x),
        // the result selector 1 when
        // the classroom has enough
        // capacity, 0 when it doesn't
        (x,y)=>x<y?0:1
     )
     // add up the 1's to get the number
     // of student groups who can fit
     // in a classroom
     .Sum()

Answer 10

Haskell, 66 bytes

import Data.List
q=sortOn(0-)
x#y=and$zipWith(<=)(q x)$q y++(0<$x)

Try it online!

Answer 11

Bash + GNU tools, 68 bytes

(sort -nr<<<$2|paste -d- - <(sort -nr<<<$1)|bc|grep -- -)&>/dev/null

69 bytes

(paste -d- <(sort -nr<<<$2) <(sort -nr<<<$1)|bc|grep -- -)&>/dev/null

TIO

takes student rooms as first and second argument as string numbers delimited by newline returns exit status 1 for true or 0 for false

Answer 12

Perl 5 -pal, 67 62 bytes

@NahuelFouilleul saved 5 bytes with a rearrangement and a grep

$_=!grep$_>0,map$_-(sort{$b-$a}@F)[$x++],sort{$b-$a}<>=~/\d+/g

Try it online!

67 bytes version

Takes the space separated list of class sizes on the first line and the space separated list of room sizes on the next.

Answer 13

Common Lisp, 74 bytes

(defun c(s r)(or(not(sort s'>))(and(sort r'>)(<=(pop s)(pop r))(c s r))))

Non-minified

(defun can-students-relocate (students rooms)
  (or (not (sort students #'>))
      (and (sort rooms #'>)
           (<= (pop students)
               (pop rooms))
           (can-students-relocate students rooms))))

Test it

Note that sort permanently mutates the list, and pop rebinds the variable to the next element.

In effect this just recursively checks that the largest student group can fit in the largest room. There are 3 base-cases:

1. No students - return T
2. Students, but no rooms - return NIL
3. Students and rooms, but largest student group larger than largest room - return NIL

Answer 14

Python 2, 71 67 64 bytes

lambda g,c:s(g)==s(map(min,zip(s(g)[::-1],s(c)[::-1])))
s=sorted

Try it online!

Answer 15

Retina 0.8.2, 50 bytes

\d+
$*
%O^`1+
%`$
,
^((1*,)(?=.*¶((?>\3?)1*\2)))*¶

Try it online! Link includes test suite. Takes two lists of groups and rooms (test suite uses ; as list separator). Explanation:

\d+
$*

Convert to unary.

%O^`1+

Reverse sort each list separately.

%`$
,

Append a comma to each list.

^((1*,)(?=.*¶((?>\3?)1*\2)))*¶

Check that each of the numbers in the first list can be matched to the appropriate number in the second list. Each time \3 contains the previously matched rooms and the next group \2 therefore needs to be able to fit into the next room. The (?>\3?) handles the case of the first room when there are no previous rooms yet.

Answer 16

Charcoal, 28 bytes

Ｗ∧⌊講⌈§θ¹⌈§θ⁰ＵＭθΦκ⁻ν⌕κ⌈κ¬⊟θ

Try it online! Link is to verbose version of code. Takes a list of lists of rooms and groups and outputs - if the rooms can accommodate the groups. Explanation:

Ｗ∧⌊講⌈§θ¹⌈§θ⁰

Repeat while a group can be assigned to a room.

ＵＭθΦκ⁻ν⌕κ⌈κ

Remove the largest room and group from their lists.

¬⊟θ

Check that there are no unallocated groups remaining.

Answer 17

JavaScript, 56 bytes

s=>c=>s.sort(g=(x,y)=>y-x).every((x,y)=>c.sort(g)[y]>=x)

Try it

Answer 18

Perl 6, 34 bytes

{none [Z>] $_>>.sort(-*)>>[^.[0]]}

Try it online!

Takes input as a list of two lists, the groups and the classrooms, and returns a None Junction that can be boolified to true/false.

Explanation:

{                                }   # Anonymous code block
           $_>>.sort(-*)             # Sort both lists from largest to smallest
                        >>[^.[0]]    # Pad both lists to the length of the first list
 none                                # Are none of
      [Z>]                           # The groups larger than the assigned classroom

Answer 19

Ruby, 57 bytes

->c,r{r.permutation.any?{|p|c.zip(p).all?{|a,b|b&&a<=b}}}

Try it online!

Takes c for classes, r for rooms. Checks all permutations of rooms instead of using sort, because reverse sorting costs too many bytes. Still looks rather long though...

Answer 20

C# (Visual C# Interactive Compiler), 105 93 91 82 81 79 77 76 74 bytes

Now matches dana's score!

n=>m=>{n.Sort();m.Sort();int i=m.Count-n.Count;i/=n.Any(b=>m[i++]<b)?0:1;}

Throws an error if false, nothing if true.

-12 bytes thanks to @Destrogio!

Try it online!

Explanation

//Function taking in a list, and returning another function
//that takes in a list and doesn't return
n=>m=>{
  //Sort the student groups from smallest to largest
  n.Sort();
  //Sort the classrooms fom smallest capacity to largest
  m.Sort();
  //Initialize a variable that will function as a sort of index
  int i=m.Count-n.Count;
  //And divide that by...
  i/=
    //0 if any of the student groups...
    n.Any(b=>
      //Don't fit into the corresponding classroom and incrementing i in the process
      /*(In the case that a the amount of classrooms are less than the amount of
      student groups, an IndexOutOfRangeException is thrown)*/
      m[i++]<b)?0
    //Else divide by 1
    :1;
}

Answer 21

Java (OpenJDK 8), 183 bytes

a->{int b=a[0].length;Arrays.sort(a[0]);Arrays.sort(a[1]);if(b>a[1].length){return false;}for(int i=0;i<b;i++){if(a[0][i]>a[1][i]){return false;}}return true;}

Try it online!

With a little helpful advice from Kevin Cruijssen and simply another glance over my code myself, I can decrease my score by a whole 9% just by replacing three English words!

Java (OpenJDK 8), 166 bytes

a->{int b=a[0].length;Arrays.sort(a[0]);Arrays.sort(a[1]);if(b>a[1].length){return 0;}for(int i=0;i<b;){if(a[0][i]>a[1][i++]){return 0;}}return 1;}

Try it online!

Answer 22

PowerShell, 80 bytes

param($s,$c)!($s|sort -d|?{$_-gt($r=$c|?{$_-notin$o}|sort|select -l 1);$o+=,$r})

Try it online!

Less golfed test script:

$f = {

param($students,$classrooms)
$x=$students|sort -Descending|where{          
    $freeRoomWithMaxCapacity = $classrooms|where{$_ -notin $occupied}|sort|select -Last 1
    $occupied += ,$freeRoomWithMaxCapacity    # append to the array
    $_ -gt $freeRoomWithMaxCapacity           # -gt means 'greater than'. It's a predicate for the 'where'
}                                             # $x contains student groups not assigned to a relevant classroom
!$x                                           # this function returns a true if $x is empty

}

@(
    ,(@(10, 20, 30), @(31, 12, 20), $true)
    ,(@(10, 20, 30), @(100, 200), $False)
    ,(@(20, 10, 30), @(20, 20, 50, 40), $True)
    ,(@(30, 10, 30, 5, 100, 99), @(40, 20, 50, 40, 99, 99), $False)
    ,(@(), @(10, 10, 10), $True)
    ,(@(10, 10, 10), @(), $False)
    ,(@(), @(), $True)
    ,(@(10, 1), @(100), $False)
    ,(@(10), @(100, 100), $True)
    ,(@(1,2,3), @(1,1,2,3), $True)
) | % {
    $students, $classrooms, $expected = $_
    $result = &$f $students $classrooms
    "$($result-eq$expected): $result"
}

Answer 23

R, 65 bytes

function(g,r)isTRUE(all(Map(`-`,sort(-g),sort(-r)[seq(a=g)])>=0))

Try it online!