School moving out (Day 1)

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...)
• Suggested testcase: g=[1,2,3], c=[1,1,2,3] Feb 6 '19 at 14:14
• Do you have permission to post it here?
Feb 6 '19 at 15:06
• @Adám Yes. I asked my teacher (who is the one in charge of the contest) and he said there is no problem. The only thing is that it is one challenge each day Feb 6 '19 at 15:10
• Is 0 a valid value for groups or classrooms?
– nimi
Feb 6 '19 at 16:45
• @Shaggy Any falsey/truthy value Feb 6 '19 at 18:40

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!

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


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


Japt, 9 bytes

ñÍí§Vñn)e

ñÍí§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

ñÍ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

• Out of curiosity, why is there a single-byte builtin for 2 - n In Japt? What kind of use-cases does it have to justify it being a 1-byte builtin? Feb 7 '19 at 7:51
• Good question, @KevinCruijssen. Í is a shortcut for n2<space> and was created for use with strings, converting them from base-2 to base-10 numbers (a fairly common need). However, the n method, when applied to a number, subtracts that number from the method's argument (default=0). So here, although subtracting from 0 would suffice for sorting the array in reverse order, using the shortcut saves me a byte over ñn<space>. I could have also used it when sorting V but it wouldn't have saved any bytes as I'd still need a space, instead of the ), to close the í method. Feb 7 '19 at 8:09

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!

MATL, 10 bytes

yn&Y@>~!Aa


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


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


Try it online!

05AB1E, 1412 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.

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)


æε{I{0ζÆdP}à


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

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)

• Hehe I was pleasantly surprised that Pyth had beaten 05AB1E for a change, but turns out it was the algorithm after all :oP
– Sok
Feb 7 '19 at 9:10
• @Sok Sorry to disappoint you. ;p But thanks for the -4 bytes. :D Feb 7 '19 at 9:15

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

• I wasn't able to find a reasonable one-liner for it. Nice job! Feb 7 '19 at 6:21

import Data.List
q=sortOn(0-)
x#y=and$zipWith(<=)(q x)$q y++(0<$x)  Try it online! 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 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. • -5 bytes Feb 6 '19 at 20:42 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 Python 2, 7167 64 bytes lambda g,c:s(g)==s(map(min,zip(s(g)[::-1],s(c)[::-1]))) s=sorted  Try it online! • In Python 3, you can remove the zip(...) to save 5 bytes. Feb 6 '19 at 18:33 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. 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. JavaScript, 56 bytes s=>c=>s.sort(g=(x,y)=>y-x).every((x,y)=>c.sort(g)[y]>=x)  Try it • Fails for groups of 7 and 9 in classes of 8 and 10. – Neil Feb 6 '19 at 21:01 • Thanks for pointing that out, @Neil. I wondered if the naked sort wouldn't come back to bite me in the ass! I'll have to roll back to my original solution until I can find time to try again. Feb 6 '19 at 23:23 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  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... C# (Visual C# Interactive Compiler), 10593918281797776 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; }  • 93 bytes - Try it online! Feb 6 '19 at 20:40 • @Destrogio Thanks! Feb 6 '19 at 21:00 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! • You'll have to include the import java.util.*; in your byte-count. You can however golf it to 144 bytes in Java 8, or 140 in Java 10 by replacing the boolean with var. Feb 6 '19 at 14:14 • PS: If you do need true/false in your code, 1>0/0>1 are shorter alternatives. :) Feb 6 '19 at 14:15 • actually, i did remember to include the extra 24 bytes into my count! (i believe it was you informed that me of that rule months ago XD), but thank you for the tip! ill give it a shot! Feb 6 '19 at 14:18 • This fails the last test case. Feb 6 '19 at 14:29 • About your 166-byte version: although the question state you can return 1/0 and I guess it's fine in this case, please note that in Java unlike Python, JavaScript, C, etc. 1/0 are usually not considered as valid truthy/falsey outputs. And in my first comment I mentioned a 144-bytes version. :) Although, it's now also invalid because it doesn't work for the last test case, as mentioned by @Shaggy. Feb 6 '19 at 14:37 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"
}


R, 65 bytes

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


Try it online!