21
\$\begingroup\$

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...)
\$\endgroup\$
  • 5
    \$\begingroup\$ Suggested testcase: g=[1,2,3], c=[1,1,2,3] \$\endgroup\$ – TFeld Feb 6 at 14:14
  • \$\begingroup\$ Do you have permission to post it here? \$\endgroup\$ – Adám Feb 6 at 15:06
  • 2
    \$\begingroup\$ @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 \$\endgroup\$ – Luis felipe De jesus Munoz Feb 6 at 15:10
  • \$\begingroup\$ Is 0 a valid value for groups or classrooms? \$\endgroup\$ – nimi Feb 6 at 16:45
  • 1
    \$\begingroup\$ @Shaggy Any falsey/truthy value \$\endgroup\$ – Luis felipe De jesus Munoz Feb 6 at 18:40

23 Answers 23

14
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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

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

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
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Kevin Cruijssen Feb 7 at 7:51
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Shaggy Feb 7 at 8:09
3
\$\begingroup\$

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!

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

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

Haskell, 40 bytes

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

Try it online!

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

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Hehe I was pleasantly surprised that Pyth had beaten 05AB1E for a change, but turns out it was the algorithm after all :oP \$\endgroup\$ – Sok Feb 7 at 9:10
  • 1
    \$\begingroup\$ @Sok Sorry to disappoint you. ;p But thanks for the -4 bytes. :D \$\endgroup\$ – Kevin Cruijssen Feb 7 at 9:15
3
\$\begingroup\$

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()
\$\endgroup\$
  • 1
    \$\begingroup\$ I wasn't able to find a reasonable one-liner for it. Nice job! \$\endgroup\$ – Embodiment of Ignorance Feb 7 at 6:21
2
\$\begingroup\$

Haskell, 66 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

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!

\$\endgroup\$
  • \$\begingroup\$ In Python 3, you can remove the zip(...) to save 5 bytes. \$\endgroup\$ – mypetlion Feb 6 at 18:33
1
\$\begingroup\$

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.

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

Charcoal, 28 bytes

W∧⌊講⌈§θ¹⌈§θ⁰UMθΦκ⁻ν⌕κ⌈κ¬⊟θ

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:

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

Repeat while a group can be assigned to a room.

UMθΦκ⁻ν⌕κ⌈κ

Remove the largest room and group from their lists.

¬⊟θ

Check that there are no unallocated groups remaining.

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

JavaScript, 56 bytes

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

Try it

\$\endgroup\$
  • \$\begingroup\$ Fails for groups of 7 and 9 in classes of 8 and 10. \$\endgroup\$ – Neil Feb 6 at 21:01
  • \$\begingroup\$ 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. \$\endgroup\$ – Shaggy Feb 6 at 23:23
1
\$\begingroup\$

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

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

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

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;
}
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Feb 6 at 14:14
  • \$\begingroup\$ PS: If you do need true/false in your code, 1>0/0>1 are shorter alternatives. :) \$\endgroup\$ – Kevin Cruijssen Feb 6 at 14:15
  • \$\begingroup\$ 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! \$\endgroup\$ – X1M4L Feb 6 at 14:18
  • 3
    \$\begingroup\$ This fails the last test case. \$\endgroup\$ – Shaggy Feb 6 at 14:29
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Feb 6 at 14:37
0
\$\begingroup\$

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"
}
\$\endgroup\$
0
\$\begingroup\$

R, 65 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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