Una bolsa , también llamada multiset, es una colección desordenada. Puede llamarlo un conjunto que permite duplicados, o una lista (o una matriz) que no está ordenada / indexada. En este desafío, se le pide que implemente operaciones de bolsa: prueba de suma, diferencia, multiplicación, división, conteo e igualdad.
Operaciones
Las operaciones especificadas pueden no ser convencionales.
- Además combina dos bolsas en una, conservando el número total de cada valor
[1,2,2,3] + [1,2,4] = [1,1,2,2,2,3,4] - la diferencia elimina de una bolsa cada elemento de otra bolsa, o no hace nada si no existe tal elemento
[1,2,2,4] - [1,2] = [2,4][1,2,3] - [2,4] = [1,3] - multiplicación multiplica cada elemento en la bolsa.
[1,2,3,3,4] * 3 = [1,1,1,2,2,2,3,3,3,3,3,3,4,4,4]2 * [1,3] = [1,1,3,3] - la división es poco común: cada n elementos iguales se colocan en n bolsas nuevas iguales, los elementos que no pueden formar un grupo n permanecen en la bolsa. Devuelva cualquiera de las n bolsas nuevas.
[1,1,2,2,2] / 2 = [1,2][1,2,2,3,3,3] / 3 = [3] - contar cuenta cuántas bolsas divisorias se pueden producir a partir de la bolsa de dividendos
[1,1,2,2,2,2,3,3,3] c [1,2,3] = 2 - la prueba de igualdad verifica si dos bolsas tienen los mismos números de cada elemento
[1,2,2,3] == [3,2,1,2] = truthy[1,2,3] == [1,2,2,3] = falsy(también se puede usar=para esto)
Si está utilizando sus propios símbolos para los operadores, especifique.
Formatos
Las bolsas se mostrarán como listas del formulario [1,1,2,3,4]. Puede usar cualquier otro soporte que no sea cuadrado, o incluso usar comillas, o nada en absoluto. Los elementos serán enteros (matemáticamente, no necesariamente int) para el propósito de esta pregunta. Las bolsas no tienen que ser clasificadas.
El formato de entrada será dos bolsas o una bolsa y un número entero, con un operador. Puede especificar su propio formato siempre que contenga estos tres.
El formato de salida debe ser una sola bolsa del mismo formato.
Reglas
- no puede utilizar funciones, operaciones o bibliotecas integradas (incluida la biblioteca estándar) que ya las implementa; Sin embargo, está bien usar la concatenación y multiplicación de listas, ya que son, por definición, operaciones de lista, no operaciones de bolsa (que básicamente hacen lo mismo)
- se aplican las lagunas estándar
- la respuesta más corta gana
Casos de prueba
[1,2,2,3] + [1,2,4]
[1,1,2,2,2,3,4]
[1,2,2,4] - [1,2]
[2,4]
[1,2,3] - [2,4]
[1,3]
[1,2,3,3,4] * 3
[1,1,1,2,2,2,3,3,3,3,3,3,4,4,4]
2 * [1,3]
[1,1,3,3]
[1,1,2,2,2] / 2
[1,2]
[1,2,2,3,3,3] / 3
[3]
[1,1,2,2,2,2,3,3,3] c [1,2,3]
2
[3,2,1,2] == [1,2,2,3]
truthy
[1,2,3] == [1,2,2,3]
falsy
fuente
Respuestas:
05AB1E,
9287838277 bytesDivisión por operación
Explicación
Adición
Coloque una bolsa en otra y aplánelas en una bolsa.
Multiplicación
Asegúrese de que el número esté en la parte superior de la pila. Llama a esto X.
Duplica la bolsa X veces y únete a una bolsa.
Contar
Para cada elemento en la bolsa divisoria, cuente el número de ocurrencias en la bolsa de dividendos.
El recuento mínimo será la cantidad de bolsas que podemos hacer.
Igualdad
Clasifique ambas bolsas y verifique si son iguales.
División
Cuente cuántas veces ocurre cada elemento único en la bolsa.
Si ocurre al menos tantas veces como el divisor. Guarde (nr_of_copies_total // divisor) copias en la bolsa.
Diferencia
Para cada elemento en el sustraendo, ordénelo al frente del minuendo.
Si el sustraendo actual es igual al primer elemento del minuendo, retírelo del minuendo.
fuente
APL (155)
Esto define un operador
∆'bolsa', que define las operaciones de bolsa para funciones determinadas. Es decir+∆, sería la suma. Luego lee una línea del teclado y la evalúa como una expresión APL.Las funciones son:
+∆, además-∆, resta×∆multiplicación÷∆división⊂∆, contando≡∆, equivalencia (aunque debido al golf cualquier función no reconocida hará equivalencia)Explicación:
∆←{...}: define un operador∆:O←⍺⍺: almacena la función dada enO(⎕CRno funcionará⍺⍺directamente)O←⎕CR'O': obtener la representación de cadena de esa función'+'=O...:: además⍺,⍵: une las dos listasR[⍋R←...]: y ordena el resultado'-'=O:: para la resta,⍺{...}⍵: ejecuta la siguiente función recursiva:⍵≡⍬:⍺: si el sustraendo está vacío, devuelve el minuendo⍺/⍨(⍳⍴⍺)≢⍺⍳⊃⍵∇1↓⍵: de lo contrario, elimine el primer elemento del sustraendo tanto del sustraendo como del minuendo e intente nuevamente(⍬=⍴⍵)∧K←'×'=O:para la multiplicación, y si el argumento correcto no es una bolsa:⍵/⍺: replica cada elemento en el argumento izquierdo por el argumento derechoK:: ... y si el argumento correcto es una bolsa:⍺/⍵: replica cada elemento en el argumento derecho por el argumento izquierdo (esto es para que la multiplicación sea conmutativa)'÷'=O:: para la división,⍵≤⍺∘.+⍺: ver qué elementos en ⍺ ocurren al menos ⍵ veces,⍺/⍨: seleccione los de ⍺,∪: y eliminar todos los duplicados de esa lista'⊂'=O:: para contar,⍵{...}⍺: ejecuta la siguiente función recursiva:(∪⍺)≢∪⍵:0: si una lista contiene elementos que la otra no, el resultado es 01+⍺∇⍵-∆⍺: de lo contrario, reste el dividendo del divisor, intente nuevamente e incremente el resultado.⋄: si ninguno de los anteriores, realice la prueba de equivalencia:⍺[⍋⍺]≡⍵[⍋⍵]: ordenar ambas listas y ver si son iguales⎕: lee una expresión del teclado, la evalúa y genera el resultado.Casos de prueba:
fuente
[2,2,2,2,2,2]/3debería ceder[2,2], pero la tuya parece ceder[2].∆, el usuario será arrojado al REPL nativo de APL, donde∆ahora es válido. Creo que puede guardar algunos bytes moviendo la resta hasta el final, ya que es la única que requiere dos líneas. En lugar de⎕CR, use*para simbolizar recuento, yO←⍺⍺2luego,2=O:para más,1=Opara mult,0=O:para equiv,7<O:para recuento y0<O:para div (con implícito0>O:para subtr).JavaScript (ES6), 260 bytes
Toma 3 parámetros. El primer parámetro es una matriz, el segundo es un operador, el tercero depende del operador. Se requieren bolsas para contener enteros no negativos.
Sin golf:
fuente
Octava,
253244226 bytesEsta función debe estar en un archivo. Para escribir la función en la ventana de comandos debe usar
endfunctionoend.Gracias a Luis Mendo por guardar 18 bytes.
Las operaciones son:
Ejemplo de uso:
Sin golf:
fuente
Mathematica
387347300284 bytesLigeramente desvanecido (también conocido como versión antigua), no tenía soporte completo para las pruebas de igualdad (devolvió valores verdaderos, pero se dejó sin evaluar para las bolsas que no coinciden).
Implementa el tipo de datos requerido con la cabeza
b.Primero
bse define para serOrderless. Cualquier objeto pasado al kernel con headbordenará automáticamente sus argumentos. Entonces, incluso sib[3,2,1]se escribe, el evaluador nunca verá otra cosa que no seab[1,2,3].La suma se define trivialmente como unir los elementos.
Se define una regla especial para la diferencia de dos bolsas (se explica a continuación). La versión anterior tenía un símbolo auxiliar para expresiones de forma
-bag.Luego, la multiplicación (siempre que
nsea un número entero positivo) se define de forma recursiva como lan*b[...] = b[...] + (n-1)*b[...]que eventualmente se reducirá a una suma simple.La regla especial para
b[...] - b[...]cuenta el número de elementos distintos en la suma de las bolsas y resta la bolsa que se restará dos veces de ese resultado. Más fácil de explicar:Arriba hay una lista de
Keys->Values.KeyValueMapconTablecrea listas de cadaKeyValuevez. (TambiénMax[...,0]hay un allí para no intentar la creación de tablas de longitud negativa). Esto sale como:que se aplana y
Listse reemplaza la cabeza conb.La división por números enteros es algo similar en las funciones utilizadas, es simplemente la división en pisos de los recuentos de elementos por el número entero.
División por conjuntos o contando He cambiado desde la implementación original. Ahora se hace recursivamente de la siguiente manera. Digamos, dividimos la bolsa
b1porb2(que en el código de golf soncyarespectivamente. Si(b1-b2) + b2 == b1, entonces agregue 1 y agregue a eso el resultado de la división(b1-b2)/b2. Si no, devuelva 0 y salga de la recursión.Si las bolsas coinciden, las incorporadas
==danTrue. La última línea fuerza aFalsesi no lo hacen.Casos de prueba:
fuente
Q: 219 caracteres
apara la suma,spara la diferencia (resta),mpara la multiplicación,dpara la división,cpara contar,epara la igualdad.El algoritmo de adición es obvio, solo uniendo las bolsas.
La función de resta indexa en la bolsa de entrada (representada como una matriz) con todo el rango de índice, excepto los primeros
níndices de cada clase de equivalencia formada por igualdad con cada elemento eny, dondenestá el número de copias de ese representantey. Manejo de posibles duplicados enyconvierte un verdadero monstruo de una función.La función de multiplicación toma
xvalores de cada unoy, en el caso de queysea un solo valor, en lugar de una matriz, simplemente los replica.La función de división produce los valores cuya cuenta en la matriz es mayor que
y, y luego elimina los duplicados.La función de conteo calcula los conteos de cada elemento
yy luego devuelve el mínimo.Dos bolsas son iguales si sus representaciones ordenadas son iguales.
fuente
Ruby, respuesta de definición de clase,
323291 bytesLa mayoría solo quería hacer
Baguna clase real debido a la flexibilidad de Ruby con las clases. En este caso, hereda deArrayporque es más corto que tener que inicializar una matriz interna y tratar con las otras cosas.Probablemente haré una respuesta de golf más seria que use una función para lidiar con las operaciones mañana. Estoy muy cansado y me divertí demasiado con esto
divertí a pesar de que tuve que discutir con la definición de la clase numérica para comenzar a. ELOGIA LA FUNCIÓN DE COBERTURA PARA HACERLO, ASÍ QUE NO NECESITO MENSAJAR LAS DEFINICIONES DE CLASE DE NÚMEROSNumber * Bagtrabajar correctamentePruébalo en línea! (El espacio en blanco no importa en Ruby, por lo que el código está un poco oculto allí).
fuente
Ruby, 201 bytes
Como prometí en mi otra respuesta, aquí hay una que usa funciones en lugar de construir una nueva clase. Estoy tan cerca de romper la marca de 200 bytes ... Pruébelo en línea
Utiliza los mismos códigos de operación que @Neil en su respuesta de JavaScript, y el mismo orden de argumentos (lhs, opcode, rhs)
El código:
fuente
C ++,
555551 bytes(saltos de línea agregados para facilitar la lectura; solo se requiere y se cuenta la primera línea nueva)
Explicación
Implementamos nuestra bolsa como un mapa de (valor, recuento). Las operaciones básicas se pueden implementar manipulando los recuentos; la resta y la división de enteros también necesitan eliminar cualquier elemento cuyo recuento llegue a cero, de modo que
std::map::operator==funcionará como prueba de igualdad.El siguiente código expandido es una versión genérica de lo anterior, y mucho menos golf: usamos un valor separado
s()para exprimir cualquier valor de conteo cero, e implementamosconstoperaciones en términos de operadores de asignación en la forma idiomática de C ++. También usamoss()para hacer la multiplicación al0devolver una bolsa verdaderamente vacía (probada agregando(B{1}*0 != B{})amain()); el original falla esta prueba, y no está claro si es un requisito.Pruebas
fuente
Python 2.7 - 447B (tamaño de archivo)
Este es mi primer intento en Codegolf, espero que satisfaga. Necesitaba 2h. (Pero todavía soy un principiante en Python)
Editar: Gracias a "Kevin Lau - no Kenny" por señalar estos:
Editar: Además, ahorré espacio al reemplazar las funciones con lambdas y nuevas líneas e indentaciones con más puntos y comas.
Código:
controles:
Salida:
Podría intentarlo en otro momento con establecer como base algún tiempo. Editar: Tal vez incluso lo intente solo con funciones.
fuente
self, algo comoSlo haría igual de bien. Otro truco es que lasortedfunción incorporada hace exactamente lo que desea de su nueva funcións, por lo que puede renunciar a la definición de la función (ya que solo la usa una vez). Nunca necesita__radd__porque nunca agrega bolsas con bolsas, aunque todavía las necesita__rmul__. Finalmente, solo necesita un espacio de sangría en lugar de cuatro, lo que reduce un poco su recuento de bytes