Implementar operaciones de bolsa

20

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
busukxuan
fuente
2
¿Quizás relajar el formato de entrada? Por ejemplo, permita tomar la bolsa, la bolsa / número y el operador como argumentos separados, o en un formato libre. De lo contrario, una parte importante del desafío es analizar la entrada, lo que no es particularmente interesante
Luis Mendo
@LuisMendo split-on-space es suficiente para analizar esto, si tienes un lenguaje que pueda evaluar cadenas como listas, ¿no crees? No tengo experiencia en publicar desafíos, así que por favor
ilumíneme
No pude encontrar una meta publicación relevante, pero vea, por ejemplo, la redacción aquí : puede leer el entero como su representación decimal, representación unaria (usando un carácter de su elección), matriz de bytes (endian grande o pequeño) o byte único (si este es el tipo de datos más grande de su idioma) . O aquí : los formatos de entrada y salida son flexibles como de costumbre (matrices, listas, lista de listas, cadenas con separadores razonables, etc. ).
Luis Mendo
@LuisMendo es básicamente gratis ahora. Y sobre el número entero, solo quise decir eso en sentido matemático, no el tipo de datos.
busukxuan
1
@LuisMendo no, los símbolos deben tener sentido, aunque sea un poco. Bueno, puedes usar one = para la prueba de igualdad.
busukxuan

Respuestas:

3

05AB1E, 92 87 83 82 77 bytes

>i‚˜,}¹iи˜Qis}GD})˜,}¹<i³v²y¢O}){0è,}¹Íi{s{Q,}¹Í<iÙv²y¢O³‹_iy}}),}svy†¬yQi¦}}

División por operación

>i                      # if 0
  ‚˜,}                  # addition
¹i                      # if 1
  и˜Qis}GD})˜,}        # multiplication
¹<i                     # if 2
   ³v²y¢O}){0è,}        # count
¹Íi                     # if 3
   {s{Q,}               # equality
¹Í<i                    # if 4
   Ùv²y¢O³÷Fy}}),}      # division
                        # else
   svy†¬yQi¦}}          # difference

Explicación

Adición

‚˜,}

Coloque una bolsa en otra y aplánelas en una bolsa.

Multiplicación

и˜Qis}

Asegúrese de que el número esté en la parte superior de la pila. Llama a esto X.

GD})˜,}

Duplica la bolsa X veces y únete a una bolsa.

Contar

³v²y¢O}){0è,}

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

 {s{Q,}

Clasifique ambas bolsas y verifique si son iguales.

División

Ùv²y¢O³÷Fy}}),}

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

svy†¬yQi¦}} 

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.

Emigna
fuente
9

APL (155)

∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕

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 en O( ⎕CRno funcionará ⍺⍺directamente)
    • O←⎕CR'O': obtener la representación de cadena de esa función
    • '+'=O... :: además
      • ⍺,⍵: une las dos listas
      • R[⍋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 derecho
    • K:: ... 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 0
        • 1+⍺∇⍵-∆⍺: 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:

      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 2 3 +∆ 1 2 4
1 1 2 2 2 3 4
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 2 4 -∆ 1 2
2 4
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 3 -∆ 2 4
1 3
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 3 3 4 ×∆ 3
1 1 1 2 2 2 3 3 3 3 3 3 4 4 4
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      2 ×∆ 1 3
1 1 3 3
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 1 2 2 2 ÷∆ 2
1 2
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 2 3 3 3 ÷∆ 3
3
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 1 2 2 2 2 3 3 3 ⊂∆ 1 2 3
2
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      3 2 1 2 ≡∆ 1 2 2 3
1
      ∆←{O←⍺⍺⋄'+'=O←⎕CR'O':R[⍋R←⍺,⍵]⋄'-'=O:⍺{⍵≡⍬:⍺⋄(⍺/⍨(⍳⍴⍺)≠⍺⍳⊃⍵)∇1↓⍵}⍵⋄(⍬≡⍴⍵)∧K←'×'=O:⍵/⍺⋄K:⍺/⍵⋄'÷'=O:∪⍺⌿⍨⍵≤+/⍺∘.=⍺⋄'⊂'=O:⍵{(∪⍺)≢∪⍵:0⋄1+⍺∇⍵-∆⍺}⍺⋄⍺[⍋⍺]≡⍵[⍋⍵]}⋄⎕
⎕:
      1 2 3 ≡∆ 1 2 2 3
0
marinus
fuente
¡Solución realmente profesional y excelente redacción! +1
¡Tu escrito y explicación es realmente sólida! Sin embargo, una cosa: para la división, creo que la especificación está redactada de una manera que [2,2,2,2,2,2]/3debería ceder [2,2], pero la tuya parece ceder [2].
Value Ink el
No necesita codificar el REPL. Si solo define , 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, y O←⍺⍺2luego, 2=O:para más, 1=Opara mult, 0=O:para equiv, 7<O:para recuento y 0<O:para div (con implícito 0>O:para subtr).
Adám
6

JavaScript (ES6), 260 bytes

(x,o,y,a=a=>a.reduce((r,e,i)=>[...r,...Array(e).fill(i)],[]),b=(a,r=[])=>a.map(e=>r[e]=-~r[e])&&r)=>[z=>a(b(y,z)),z=>y.map(e=>z[e]&&z[e]--)&&a(z),z=>a(z.map(e=>e*y)),z=>a(z.map(i=>i/y|0)),z=>b(y).map((e,i)=>r=Math.min(r,z[i]/e),r=1/0)|r,z=>``+z==b(y)][o](b(x))

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.

[...] 0 [...] -> addition
[...] 1 [...] -> difference
[...] 2 <n> -> multiplication
[...] 3 <n> -> division
[...] 4 [...] -> counting
[...] 5 [...] -> equality

Sin golf:

function do_bag_op(lhs, op, rhs) {
    function bag2array(bag) {
        return bag.reduce(function (result, entry, index) {
            return result.concat(Array(entry).fill(index));
        }, []);
    }
    function array2bag(array, bag) {
        if (!bag) bag = [];
        array.forEach(function (entry) {
            if (bag[entry]) bag[entry]++;
            else bag[entry] = 1;
        }
        return bag;
    }
    var bag = array2bag(lhs);
    switch (o) {
    case 0: // addition
        return bag2array(array2bag(rhs, bag));
    case 1: // difference
        rhs.forEach(function(entry) {
            if (bag[entry]) bag[entry]--;
        });
        return bag2array(bag);
    case 2: // multiplication
        return bag2array(bag.map(function (entry) {
            return entry * rhs;
        }));
    case 3: // division
        return bag2array(bag.map(function (entry) {
            return Math.floor(entry / rhs);
        }));
    case 4: // counting
        return Math.floor(array2bag(rhs).reduce(function (count, entry, index) {
            return Math.min(count, bag[index] / entry);
        }, Infinity));
    case 5: // equality
        return String(bag) == String(array2bag(rhs));
    }
}
Neil
fuente
6

Octava, 253 244 226 bytes

function r=f(a,b,o)
u=union(a,b);p=hist(a,u);q=hist(b,u);m=d=0;if(numel(b)==1)m=p.*b;d=p/b;elseif(numel(a)==1)m=a.*q;end
r={p+q,p-q,m,d,min(fix(p./q)),isequal(p,q)}{o};if(o<5)r=[arrayfun(@(x,y)repmat(y,1,x),r,u,'un',0){:}];end

Esta función debe estar en un archivo. Para escribir la función en la ventana de comandos debe usar endfunctiono end.

Gracias a Luis Mendo por guardar 18 bytes.

Las operaciones son:

1 = addition
2 = difference
3 = multiplication
4 = division
5 = counting
6 = equality test

Ejemplo de uso:

>> f([1,2,2,3], [1,2,4], 1)
ans = 1   1   2   2   2   3   4

>> f([1,2,2,4], [1,2], 2)
ans = 2   4

>> f([1,2,3], [2,4], 2)
ans = 1   3

>> f([1,2,3,3,4], 3, 3)
ans = 1   1   1   2   2   2   3   3   3   3   3   3   4   4   4

>> f(2, [1,3], 3)
ans = 1   1   3   3

>> f([1,1,2,2,2], 2, 4)
ans = 1   2

>> f([1,2,2,3,3,3], 3, 4)
ans =  3

>> f([1,1,2,2,2,2,3,3,3], [1,2,3], 5)
ans =  2

>> f([3,2,1,2], [1,2,2,3], 6)
ans =  1

>> f([1,2,3], [1,2,2,3], 6)
ans = 0

Sin golf:

function r = f(a,b,o)
    u = union(a,b);
    p = hist(a,u);
    q = hist(b,u);
    m = d = 0;
    if (numel(b)==1)
        m = p.*b;
        d = p/b;
    elseif (numel(a)==1) 
        m = a.*q;
    end
    r = {p+q, p-q, m, d, min(fix(p./q)), isequal(p,q)}{o};
    if (o<5)
        r = [arrayfun(@(x,y) repmat(y, 1, x), r, u, 'un', 0){:}];
    end
end
Marco
fuente
5

Mathematica 387 347 300 284 bytes

k=KeyValueMap[Table,#]&;j=b@@Join@@#&;l=List;q=Counts
b~SetAttributes~Orderless
a_b+c_b^:=j@{a,c}
c_b-a_b^:=j@k@Merge[q/@(l@@@{a+c,2a}),-Min[0,+##2-#]&@@#&]
a_b*n_Integer/;n>0^:=a+a*(n-1)
a_Rational c_b^:=j@k[⌊a#⌋&/@q@*l@@c]
a_b==d_b^:=l@@a==l@@d
c_b/a_b^:=If[(c-a)+a==c,1+(c-a)/a,0]

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

SetAttributes[b,Orderless]
b/:-a_b:=d@@a
b/:a_b+c_b:=Join[a,c]
d/:a_b+c_d:=b@@Join@@KeyValueMap[Table,Merge[Counts/@(List@@@{a+b@@c,b@@c+b@@c}),Max[0,#-(+##2)]&@@#&]]
b/:Rational[1,a_]c_b:=b@@Join@@KeyValueMap[Table,Floor[#/a]&/@Counts@*List@@c]
b/:(a_b)^-1:=c@@a
c/:a_b d_c:=Min@Merge[Counts/@(List@@@{a,d}),If[+##2==0,\[Infinity],#/+##2]&@@#&]
b/:a_b*n_Integer:=a+a*(n-1)

Implementa el tipo de datos requerido con la cabeza b.

Primero bse define para ser Orderless. Cualquier objeto pasado al kernel con head bordenará automáticamente sus argumentos. Entonces, incluso si b[3,2,1]se escribe, el evaluador nunca verá otra cosa que no sea b[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 la n*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:

b[1,2,3,4,5] - b[2,3,6]
Element counts in sum of bags: <|1->1, 2->2, 3->2, 4->1, 5->1, 6->1|>
Element counts in 2x second bag:     <|2->2, 3->2, 6->2|>
Subtracting the corresponding values:
                               <|1->1, 2->0, 3->0, 4->1, 5->1, 6->-1|>

Arriba hay una lista de Keys->Values. KeyValueMapcon Tablecrea listas de cada Key Valuevez. (También Max[...,0]hay un allí para no intentar la creación de tablas de longitud negativa). Esto sale como:

{{1},{},{},{4},{5},{}}

que se aplana y Listse reemplaza la cabeza con b.

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 b1por b2(que en el código de golf son cy arespectivamente. 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 ==dan True. La última línea fuerza a Falsesi no lo hacen.

Casos de prueba:

Input:
b[1, 2, 2, 3] + b[1, 2, 4]
b[1, 2, 2, 4] - b[1, 2]
b[1, 2, 3] - b[2, 4]
b[1, 2, 3, 3, 4]*3
2*b[1, 3]
b[1, 1, 2, 2, 2]/2
b[1, 2, 2, 3, 3, 3]/3
b[1, 1, 2, 2, 2, 2, 3, 3, 3] /b[1, 2, 3]
b[3, 2, 1, 2] == b[1, 2, 2, 3]
b[1, 2, 3] == b[1, 2, 2, 3]

Output:
b[1, 1, 2, 2, 2, 3, 4]
b[2, 4]
b[1, 3]
b[1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4]
b[1, 1, 3, 3]
b[1, 2]
b[3]
2
True
False
LLlAMnYP
fuente
2

Q: 219 caracteres

a:(,)
s:{[x;y]x((!:)(#:)x)except(,/)({.[(#);x]}')flip(7h$(({(+/)x=y}[y]')(?:)y);(({where x=y}[x]')y))}
m:{(,/)$[0>(@:)x;(#[x]')y;(#[y]')x]}
d:{(?:)x(&:)({y<=(+/)x=z}[x;y]')x}
c:{min({(+/)x=y}[x]')y}
e:{(asc x)~asc y}

apara la suma, spara la diferencia (resta), mpara la multiplicación,d para 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 en y, donde nestá el número de copias de ese representante y. Manejo de posibles duplicados eny convierte un verdadero monstruo de una función.

La función de multiplicación toma xvalores de cada uno y, en el caso de quey sea ​​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.

C. Quilley
fuente
2

Ruby, respuesta de definición de clase, 323 291 bytes

La mayoría solo quería hacer Baguna clase real debido a la flexibilidad de Ruby con las clases. En este caso, hereda deArray porque 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 Number * Bagtrabajar correctamente . ELOGIA LA FUNCIÓN DE COBERTURA PARA HACERLO, ASÍ QUE NO NECESITO MENSAJAR LAS DEFINICIONES DE CLASE DE NÚMEROS

Pruébalo en línea! (El espacio en blanco no importa en Ruby, por lo que el código está un poco oculto allí).

class B<Array
def == o
sort==o.sort
end
def + o
B.new super
end
def - o
r=to_a
o.map{|i|r[r.index(i)||size]=p}
B.new r-[p]
end
def * i
B.new super
end
def / i
B.new uniq.map{|o|[o]*(count(o)/i)}.flatten
end
def c o
o.map{|i|count i}.min
end
def inspect
sort
end
def coerce o
[self,o]
end
end
Tinta de valor
fuente
1

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)

0: Addition
1: Difference
2: Multiplication
3: Division
4: Counting
5: Equality

El código:

->x,o,y{[->{(x+y).sort},->r=[*x]{y.map{|i|r[r.index(i)||x.size]=p};r-[p]},->{(x==[*x]?x*y :y*x).sort},->{x.uniq.map{|i|[i]*(x.count(i)/y)}.flatten},->{y.map{|i|x.count i}.min},->{x.sort==y.sort}][o][]}
Tinta de valor
fuente
1

C ++, 555 551 bytes

(saltos de línea agregados para facilitar la lectura; solo se requiere y se cuenta la primera línea nueva)

#include<map>
struct B:std::map<int,int>{
B(std::initializer_list<int>l){for(auto i:l)++(*this)[i];}};
B operator+(B a,B b){for(auto m:b)a[m.first]+=m.second;return a;}
B operator-(B a,B b){for(auto m:b){int&x=a[m.first];x-=x>m.second?m.second:x;if(!x)a.erase(m.first);};return a;}
B operator*(B b,int n){for(auto m:b)b[m.first]*=n;return b;}
B operator*(int n,B b){return b*n;}
B operator/(B b,int n){for(auto m:b)if(!(b[m.first]/=n))b.erase(m.first);return b;}
int operator/(B a,B b){auto r=~0u;for(auto m:b){int x=a[m.first]/m.second;r=r>x?x:r;}return r;}

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 questd::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 implementamos constoperaciones en términos de operadores de asignación en la forma idiomática de C ++. También usamos s()para hacer la multiplicación al 0devolver una bolsa verdaderamente vacía (probada agregando (B{1}*0 != B{})a main()); el original falla esta prueba, y no está claro si es un requisito.

template<class T>
struct Bag{
    std::map<T,int>b;
    Bag(const std::initializer_list<T>& l){for(auto i:l)++b[i];}
    Bag&s(){for(auto i=b.begin();i!=b.end();i=i->second?++i:b.erase(i));return*this;}
    Bag&operator+=(const Bag& o){for(auto m:o.b)b[m.first]+=m.second;return*this;}
    Bag&operator-=(const Bag& o){for(auto m:o.b){auto&x=b[m.first];x-=x>m.second?m.second:x;}return s();}
    Bag&operator*=(int n){for(auto m:b)b[m.first]*=n;return s();}
    Bag&operator/=(int n){for(auto m:b)b[m.first]/=n;return s();}
    auto operator/=(const Bag& o){auto r=~0u;for(auto m:o.b){int x=b[m.first]/m.second;r=r>x?x:r;}return r;}
    bool operator==(const Bag& o)const{return b==o.b;}

    Bag operator+(Bag o)const{return o+=*this;}
    Bag operator-(const Bag& o)const{Bag t=*this;return t-=o;}
    Bag operator*(int n)const{Bag t=*this;return t*=n;}
    friend Bag operator*(int n,const Bag& b){return b*n;}
    auto operator/(auto n)const{Bag t=*this;return t/=n;}
    bool operator!=(const Bag& o)const{return b!=o.b;}
};

using B = Bag<int>;

Pruebas

bool operator!=(B a,B b){return!(a==b);}
int main()
{
    return 0
        + (B{1,2,2,3}+B{1,2,4}  !=  B{1,1,2,2,2,3,4})
        + (B{1,2,2,4}-B{1,2}  !=  B{2,4})
        + (B{1,2,3}-B{2,4}  !=  B{1,3})
        + (B{1,2,3,3,4}*3  !=  B{1,1,1,2,2,2,3,3,3,3,3,3,4,4,4})
        + (2*B{1,3}  !=  B{1,1,3,3})
        + (B{1,1,2,2,2}/2  !=  B{1,2})
        + (B{1,2,2,3,3,3}/3  !=  B{3})
        + (B{1,1,2,2,2,2,3,3,3}/B{1,2,3} != 2)
        + (B{3,2,1,2}  !=  B{1,2,2,3})
        + (B{1,2,3}  ==  B{1,2,2,3})
        ;
}
Toby Speight
fuente
¡Buena respuesta! +1. Su código necesita un formato adecuado en la publicación.
Yytsi
Deliberadamente quería que el código se ajustara, para que pueda verlo todo. La alternativa era agregar saltos de línea.
Toby Speight
1
Se agregaron saltos de línea: creo que esto es mejor, porque prettify ahora funciona.
Toby Speight
1

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:

  • El argumento de las pitones en una clase puede ser reemplazado por cualquier cosa
  • la sangría solo tiene que ser un espacio único
  • el incorporado ordenado - funktion (lo sabía que lo había visto, pero pensé que era un método en las listas)
  • __ radd __ no es necesario (de todos modos, solo apoyo agregar objetos B (tipo bolsa))

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:

class B:
 def __init__(S,L=[]):S.L=sorted(list(L));S.p=lambda:[[i]*S.L.count(i)for k,i in enumerate(S.L)if i!=S.L[k-1]];S.__eq__=lambda o:S.L==o.L;S.__rmul__=S.__mul__=lambda o:B(S.L*o);S.__add__=lambda o:B(S.L+o.L);S.__sub__=lambda o:B([i for k in S.p()for i in k[:max(0,S.L.count(k[0])-o.L.count(k[0]))]]);S.__div__=lambda o:B([i for k in S.p()for i in k[::o][:[-1,None][len(k)%o==0]]]);S.c=lambda o:min([S.L.count(i)//o.L.count(i)for i in o.L])

controles:

print B([1,2,2,3]) + B([1,2,4]) == B([1,1,2,2,2,3,4]) # Add

print B([1,2,2,4]) - B([1,2]) == B([2,4]) #Substract
print B([1,2,3])   - B([2,4]) == B([1,3]) #Substract

print B([1,2,3,3,4]) * 3 == B([1,1,1,2,2,2,3,3,3,3,3,3,4,4,4])#Multiply
print 2 * B([1,3]) == B([1,1,3,3])                            #

print B([1,1,2,2,2])   /2 == B([1,2]) #Divide
print B([1,2,2,3,3,3]) /3 == B([3])   #

print B([1,1,2,2,2,2,3,3,3]).c(B([1,2,3]))==2 #Contained n times

print B([3,2,1,2]) == B([1,2,2,3]) # Equal
print B([1,2,3])   == B([1,2,2,3]) # Unequal

Salida:

True
True
True
True
True
True
True
True
True
False

Podría intentarlo en otro momento con establecer como base algún tiempo. Editar: Tal vez incluso lo intente solo con funciones.

Teck-freak
fuente
Bienvenido a PPCG! Una cosa a tener en cuenta sobre Python es que en realidad no necesita llamar a los primeros parámetros en las funciones de clase self, algo como Slo haría igual de bien. Otro truco es que la sortedfunción incorporada hace exactamente lo que desea de su nueva función s, 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
Value Ink el