La escuela se muda (Día 1)

21

Reto tomado con permiso de mi concurso de desafío de código universitario


Desde hace algunos años, el número de estudiantes en mi escuela ha estado creciendo constantemente. Primero, el número de estudiantes aumentó por aula, pero luego fue necesario convertir algunos espacios para que algunos grupos dieran clases allí, como las gradas del gimnasio o, este último curso, hasta la sala de escobas.

El año pasado, las autoridades académicas obtuvieron el presupuesto para construir un nuevo edificio y comenzaron las obras. Por fin han terminado y el nuevo edificio ya se puede utilizar, por lo que podemos movernos (el antiguo edificio será rehabilitado y se utilizará para otra función), pero nos ha atrapado a mitad del curso. El director quiere saber si la mudanza será posible sin dividirse o unirse a grupos, o si algunos estudiantes tienen que cambiar de grupo.

Reto

Dada la cantidad de estudiantes de los grupos actuales y las nuevas aulas (capacidad), arroje un valor verdadero si es posible asignar un aula diferente, con capacidad suficiente, a cada uno de los grupos actuales, o un valor falsey de lo contrario.

Casos de prueba

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

Notas

  • Puede tomar la entrada en cualquier formato razonable
  • Puede dar salida a cualquier valor Truthy / Falsey- ( 1/0, True/False, etc ...)
Luis felipe De jesus Munoz
fuente
55
Caso de prueba sugerido:g=[1,2,3], c=[1,1,2,3]
TFeld
¿Tienes permiso para publicarlo aquí?
Adám
2
@ Adám Sí. Le pregunté a mi maestro (quién es el responsable del concurso) y él dijo que no hay problema. Lo único es que es un desafío cada día
Luis felipe De jesus Munoz
¿Es 0un valor válido para grupos o aulas?
nimi
1
@Shaggy Cualquier valor falso / verdadero
Luis felipe De jesus Munoz

Respuestas:

14

Brachylog , 4 bytes

Siempre es agradable ver un desafío y saber que brachylog va a vencer a todos. Toma las clases actuales como entrada y las nuevas aulas como salida; Saldrá verdadero si encuentra una manera de adaptarse a los estudiantes, falso de lo contrario

p≤ᵐ⊆

Explicación

El código tiene 3 partes de las cuales el orden en realidad no importa

≤ᵐ --> 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

Pruébalo en línea!

Kroppeb
fuente
4

Pyth, 11 bytes

.AgM.t_DMQ0

Toma la entrada como una lista de listas, el tamaño del aula primero, el tamaño del grupo segundo. Pruébelo en línea aquí , o verifique todos los casos de prueba a la vez aquí .

.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
Sok
fuente
4

Jalea , 9 bytes

Toma las aulas como primer argumento y los grupos como segundo argumento.

Œ!~+Ṡ‘ḌẠ¬

Pruébalo en línea!

Comentado

NB: Esto Ṡ‘ḌẠ¬es demasiado largo. Pero sospecho que este no es el enfoque correcto de todos modos.

Œ!~+Ṡ‘ḌẠ¬  - 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
Arnauld
fuente
4

Japt , 9 bytes

ñÍí§Vñn)e

Pruébelo o ejecute todos los casos de prueba en 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

Pruébelo o ejecute todos los casos de prueba en 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
Lanudo
fuente
Por curiosidad, ¿por qué hay un byte incorporado en 2 - nIn Japt? ¿Qué tipo de casos de uso tiene para justificar que sea un byte incorporado de 1 byte?
Kevin Cruijssen
1
Buena pregunta, @KevinCruijssen. Íes un acceso directo para n2<space>y fue creado para usar con cadenas, convirtiéndolas de números base-2 a base-10 (una necesidad bastante común). Sin embargo, el nmétodo, cuando se aplica a un número, resta ese número del argumento del método (predeterminado = 0). Entonces, aunque restar de 0sería suficiente para ordenar la matriz en orden inverso, usar el atajo me ahorra un byte ñn<space>. También podría haberlo usado al ordenar, Vpero no habría guardado ningún byte, ya que todavía necesitaría un espacio, en lugar del ), para cerrar el ímétodo.
Shaggy
3

MATL , 10 bytes

yn&Y@>~!Aa

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

Considere las entradas [20, 10, 30], [20, 20, 50, 40]como un ejemplo. La pila se muestra de abajo hacia arriba.

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
Luis Mendo
fuente
3

05AB1E , 14 12 8 bytes

€{í0ζÆdP

Puerto de @Sok 's Pyth respuesta , así que asegúrese de que le Upvote así!

Toma la entrada como una lista de listas, con la lista de aula como primer elemento y la lista de grupo como segundo elemento.

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

€{         # 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)

Antigua respuesta de 12 bytes:

æε{I{0ζÆdP}à

Primero toma la lista del aula y luego la lista del grupo.

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

æ             # 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)
Kevin Cruijssen
fuente
1
Jeje Me sorprendió gratamente que Pyth hubiera derrotado a 05AB1E para variar, pero resulta que fue el algoritmo después de todo: oP
Sok
1
@Sok Perdón por decepcionarte. ; p Pero gracias por los -4 bytes. : D
Kevin Cruijssen
3

C # (compilador interactivo de Visual C #) , 77 74 bytes

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

Pruébalo en línea!

Código comentado:

// 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()
dana
fuente
1
No pude encontrar una frase razonable para ello. ¡Buen trabajo!
Encarnación de la ignorancia
2

Bash + herramientas GNU, 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

toma las habitaciones de los estudiantes como primer y segundo argumento, ya que los números de cadena delimitados por la nueva línea devuelven el estado de salida 1 para verdadero o 0 para falso

Nahuel Fouilleul
fuente
2

Perl 5 -pal , 67 62 bytes

@NahuelFouilleul ahorró 5 bytes con una reorganización y un grep

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

Pruébalo en línea!

Versión de 67 bytes

Toma la lista de tamaños de clase separados por espacios en la primera línea y la lista de tamaños de habitaciones separados por espacios en la siguiente.

Xcali
fuente
-5 bytes
Nahuel Fouilleul
2

Lisp común, 74 bytes

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

No minificado

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

Pruébalo

Tenga en cuenta que sort cambia permanentemente la lista y pop vuelve a vincular la variable al siguiente elemento.

En efecto, esto solo verifica recursivamente que el grupo de estudiantes más grande pueda caber en la sala más grande. Hay 3 casos base:

  1. No estudiantes - devolver T
  2. Estudiantes, pero no habitaciones - regreso NIL
  3. Estudiantes y habitaciones, pero el grupo de estudiantes más grande es más grande que la habitación más grande: regrese NIL
Charlim
fuente
1

Python 2 , 71 67 64 bytes

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

Pruébalo en línea!

TFeld
fuente
En Python 3, puede eliminar el zip(...)para guardar 5 bytes.
mypetlion
1

Retina 0.8.2 , 50 bytes

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

Pruébalo en línea! El enlace incluye un conjunto de pruebas. Toma dos listas de grupos y salas (el conjunto de pruebas se usa ;como separador de listas). Explicación:

\d+
$*

Convierte a unario.

%O^`1+

Invierta la clasificación de cada lista por separado.

%`$
,

Agregue una coma a cada lista.

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

Verifique que cada uno de los números en la primera lista pueda coincidir con el número apropiado en la segunda lista. Cada vez \3contiene las habitaciones previamente combinadas y, por lo tanto, el siguiente grupo \2debe poder encajar en la habitación siguiente. Los (?>\3?)Trata el caso de la primera habitación cuando no hay habitaciones anteriores todavía.

Neil
fuente
1

Carbón , 28 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Toma una lista de listas de salas y grupos y salidas -si las salas pueden acomodar a los grupos. Explicación:

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

Repita mientras se puede asignar un grupo a una habitación.

UMθΦκ⁻ν⌕κ⌈κ

Elimine la sala y el grupo más grandes de sus listas.

¬⊟θ

Compruebe que no quedan grupos sin asignar.

Neil
fuente
1

JavaScript, 56 bytes

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

Intentalo

Lanudo
fuente
Falla para grupos de 7y 9en clases de 8y 10.
Neil
Gracias por señalar eso, @Neil. ¡Me preguntaba si el tipo desnudo no volvería a morderme el culo! Tendré que volver a mi solución original hasta que pueda encontrar tiempo para volver a intentarlo.
Shaggy
1

Perl 6 , 34 bytes

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

Pruébalo en línea!

Toma la entrada como una lista de dos listas, los grupos y las aulas, y devuelve una unión de ninguno que se puede boolificar a verdadero / falso.

Explicación:

{                                }   # 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
Jo King
fuente
1

Ruby , 57 bytes

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

Pruébalo en línea!

Toma cpara clases, rpara habitaciones. Comprueba todas las permutaciones de habitaciones en lugar de usar sort, porque la ordenación inversa cuesta demasiados bytes. Sin embargo, todavía parece bastante largo ...

Kirill L.
fuente
1

C # (compilador interactivo de Visual C #) , 105 93 91 82 81 79 77 76 74 bytes

¡Ahora coincide con el puntaje de dana!

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

Lanza un error si es falso, nada si es verdadero.

-12 bytes gracias a @Destrogio!

Pruébalo en línea!

Explicación

//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;
}
Encarnación de la ignorancia
fuente
93 bytes - ¡ Pruébelo en línea!
Destroigo
1
@Destrogio Gracias!
Encarnación de la ignorancia
0

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;}

Pruébalo en línea!

Con un pequeño consejo útil de Kevin Cruijssen y simplemente otra mirada sobre mi código, ¡puedo disminuir mi puntaje en un 9% con solo reemplazar tres palabras en inglés!

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;}

Pruébalo en línea!

X1M4L
fuente
Tendrás que incluir el import java.util.*;en tu conteo de bytes. Sin embargo, puede jugar golf a 144 bytes en Java 8, o 140 en Java 10 reemplazando el booleancon var.
Kevin Cruijssen
PD: Si necesitas true/ falseen tu código, 1>0/ 0>1son alternativas más cortas . :)
Kevin Cruijssen
De hecho, ¡recordé incluir los 24 bytes adicionales en mi cuenta! (Creo que fue usted quien me informó de esa regla hace meses XD), ¡pero gracias por el consejo! voy a darle una oportunidad!
X1M4L
3
Esto falla el último caso de prueba.
Shaggy
Acerca de su versión de 166 bytes: aunque la pregunta indica que puede devolver 1/0y supongo que está bien en este caso, tenga en cuenta que en Java, a diferencia de Python, JavaScript, C, etc. 1/0, generalmente no se consideran salidas de verdad / falsey válidas . Y en mi primer comentario mencioné una versión de 144 bytes . :) Aunque, ahora también es inválido porque no funciona para el último caso de prueba, como lo menciona @Shaggy .
Kevin Cruijssen
0

PowerShell , 80 bytes

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

Pruébalo en línea!

Menos guión de prueba de golf:

$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"
}
mazzy
fuente