... contado!

Le pasará a su programa una variable que representa una cantidad de dinero en dólares y / o centavos y una variedad de valores de monedas. Su desafío es generar el número de combinaciones posibles de la matriz dada de valores de monedas que se sumarían a la cantidad pasada al código. Si no es posible con las monedas nombradas, el programa debería regresar 0.

Nota sobre la terminología numismática estadounidense:

• Moneda de 1 centavo: centavo
• Moneda de 5 centavos: níquel
• Moneda de 10 centavos: dime
• Moneda de 25 centavos: cuarto (cuarto de dólar)

Ejemplo 1:

Programa aprobado:

12, [1, 5, 10]

(12 centavos)

Salida:

4

Hay 4 formas posibles de combinar las monedas nombradas para producir 12 centavos:

1. 12 centavos
2. 1 níquel y 7 centavos
3. 2 monedas de 5 centavos y 2 centavos
4. 1 centavo y 2 centavos

Ejemplo 2

Programa aprobado:

26, [1, 5, 10, 25]

(26 centavos)

Salida:

13

Hay 13 formas posibles de combinar las monedas nombradas para producir 26 centavos:

1. 26 centavos
2. 21 centavos y 1 níquel
3. 16 centavos y 2 centavos
4. 11 centavos y 3 monedas de cinco centavos
5. 6 centavos y 4 monedas de cinco centavos
6. 1 centavo y 5 centavos
7. 16 centavos y 1 centavo
8. 6 centavos y 2 monedas de diez centavos
9. 11 centavos, 1 centavo y 1 níquel
10. 6 centavos, 1 centavo y 2 monedas de cinco centavos
11. 1 centavo, 1 centavo y 3 monedas de cinco centavos
12. 1 centavo, 2 monedas de diez centavos y 1 níquel
13. 1 cuarto y 1 centavo

Ejemplo 3

Programa aprobado:

19, [2, 7, 12]

Salida:

2

Hay 2 formas posibles de combinar las monedas nombradas para producir 19 centavos:

1. 1 moneda de 12 centavos y 1 moneda de 7 centavos
2. 1 moneda de 7 centavos y 6 monedas de 2 centavos

Ejemplo 4

Programa aprobado:

13, [2, 8, 25]

Salida:

0

No hay formas posibles de combinar las monedas nombradas para producir 13 centavos.

Esto ha sido a través del Sandbox. Se aplican lagunas estándar. Este es el código de golf, por lo que gana la respuesta con la menor cantidad de bytes.

Gelatina ( tenedor ), 2 bytes

æf

Esto se basa en una rama de Jelly donde estaba trabajando en la implementación de Frobenius para resolver átomos, por lo que desafortunadamente no puedes probarlo en línea.

Uso

$ ./jelly eun 'æf' '12' '[1,5,10]'
4
$ ./jelly eun 'æf' '26' '[1,5,10,25]'
13
$ ./jelly eun 'æf' '19' '[2,7,12]'
2
$ ./jelly eun 'æf' '13' '[2,8,25]'
0

Explicación

æf  Input: total T, denominations D
æf  Frobenius count, determines the number of solutions
    of nonnegative X such that X dot-product D = T

Haskell, 37 34 bytes

s#l@(c:d)|s>=c=(s-c)#l+s#d
s#_=0^s

Ejemplo de uso: 26 # [1,5,10,25]-> 13.

Enfoque recursivo simple: intente con el siguiente número de la lista (siempre que sea menor o igual a la cantidad) y omítalo. Si restar el número lleva a una cantidad de cero, tome un 1else (o si la lista se queda sin elementos) tome un 0. Suma esos 1s y 0s.

Editar: @Damien: guardó 3 bytes señalando un caso base más corto para la recursión (que también se puede encontrar en @xnors answer ).

Mathematica, 35 22 bytes

Gracias a las millas por sugerir FrobeniusSolvey guardar 13 bytes.

Length@*FrobeniusSolve

Evalúa una función sin nombre, que toma la lista de monedas como primer argumento y el valor objetivo como segundo. FrobeniusSolvees una abreviatura para resolver ecuaciones diofantinas de la forma

a1x1 + a2x2 + ... + anxn = b

para los enteros no negativos y nos da todas las soluciones.xi

Pyth, 8 bytes

/sM{yS*E

Fuerza bruta bruta, demasiado intensiva en memoria para pruebas reales. Esto es O (2 ^mn ), donde n es el número de monedas ym es la suma objetivo. Toma entrada como target\n[c,o,i,n,s].

/sM{yS*EQQ      (implicit Q's)
      *EQ       multiply coin list by target
     S          sort
    y           powerset (all subsequences)
   {            remove duplicates
 sM             sum all results
/        Q      count correct sums

Haskell, 37 bytes

s%(h:t)=sum$map(%t)[s,s-h..0]
s%_=0^s

El uso de algunos múltiplos de la primera moneda hdisminuye la suma requerida sa un valor no negativo en la progresión decreciente [s,s-h..0], que luego debe hacerse con las monedas restantes. Una vez que no queden monedas, verifique que la suma sea cero aritméticamente como 0^s.

JavaScript (ES6), 51 48 bytes

f=(n,a,[c,...b]=a)=>n?n>0&&c?f(n-c,a)+f(n,b):0:1

Acepta monedas en cualquier orden. Intenta usar y no usar la primera moneda, calculando recursivamente el número de combinaciones de cualquier manera. n==0significa una combinación coincidente, n<0significa que las monedas exceden la cantidad mientras c==undefinedque significa que no quedan monedas. Tenga en cuenta que la función es muy lenta y si tiene una moneda de un centavo, la siguiente función es más rápida (no pase la moneda de un centavo en el conjunto de monedas):

f=(n,a,[c,...b]=a)=>c?(c<=n&&f(n-c,a))+f(n,b):1

Perl, 45 bytes

El recuento de bytes incluye 44 bytes de código y -pbandera.

s%\S+%(1{$&})*%g,(1x<>)=~/^$_$(?{$\++})^/x}{

Toma los valores de las monedas en la primera línea y la cantidad objetivo en la segunda línea:

$ perl -pE 's%\S+%(1{$&})*%g,(1x<>)=~/^$_$(?{$\++})^/x}{' <<< "1 5 10 25
26"
13

Explicaciones cortas:

-p                        # Set $_ to the value of the input, 
                          # and adds a print at the end of the code.
s%\S+%(1{$&})*%g,         # Converts each number n to (1{$&})* (to prepare the regex)
                          # This pattern does half the job.
(1x<>)                    # Converts the target to unary representation.
  =~                      # Match against.. (regex)
    /^ $_ $               # $_ contains the pattern we prepared with the first line.
     (?{$\++})            # Count the number of successful matches
     ^                    # Forces a fail in the regex since the begining can't be matched here.
    /x                    # Ignore white-spaces in the regex 
                          # (needed since the available coins are space-separated)
 }{                       # End the code block to avoid the input being printed (because of -p flag) 
                          # The print will still be executed, but $_ will be empty, 
                          # and only $\ will be printed (this variable is added after every print)

Jalea , 10 9 bytes

œċЀS€€Fċ

Pruébalo en línea!

¿Cómo?

œċЀS€€Fċ - Main link: coins, target
  Ѐ      - map over right argument, or for each n in [1,2,...,target]
œċ        - combinations with replacement, possible choices of each of n coins
    S€€   - sum for each for each (values of those selections)
       F  - flatten into one list
        ċ - count occurrences of right argument

JavaScript (ES6), 59 bytes

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),0):1

Las monedas se ingresan de mayor a menor, por ejemplo f(26,[100,25,10,5,1]). Si tiene un centavo, quítelo y use esta versión mucho más rápida en su lugar:

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),1):1

Esto usa una fórmula recursiva muy parecida a @ nimi. Originalmente escribí esto hace unos días cuando el desafío todavía estaba en la caja de arena; se veía así:

f=(n,c=[100,25,10,5])=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),1):1

Las únicas diferencias son el valor predeterminado de c(tenía un valor establecido en el desafío original) y el cambio 0de la .reducefunción a 1(esto era dos bytes más corto y un billón de veces más rápido que c=[100,25,10,5,1]).

Aquí hay una versión modificada que genera todas las combinaciones, en lugar del número de combinaciones:

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:[...x,...f(n-y,c.slice(i)).map(c=>[...c,y])],[]):[[]]

PHP, 327 bytes

function c($f,$z=0){global$p,$d;if($z){foreach($p as$m){for($j=0;$j<=$f/$d[$z];){$n=$m;$n[$d[$z]]=$j++;$p[]=$n;}}}else for($p=[],$j=0;$j<=$f/$d[$z];$j++)$p[]=[$d[$z]=>$j];if($d[++$z])c($f,$z);}$d=$_GET[a];c($e=$_GET[b]);foreach($p as$u){$s=0;foreach($u as$k=>$v)$s+=$v*$k;if($s==$e&count($u)==count($d))$t[]=$u;}echo count($t);

Intentalo

Axioma, 63 62 bytes

1 byte guardado por @JonathanAllan

f(n,l)==coefficient(series(reduce(*,[1/(1-x^i)for i in l])),n)

Este enfoque utiliza funciones generadoras. Probablemente eso no ayudó a reducir el tamaño del código. Creo que esta es la primera vez que en mi juego con Axiom fui tan lejos como para definir mi propia función.

La primera vez que se llama a la función, da una advertencia horrenda, pero aún produce el resultado correcto. Después de eso, todo está bien siempre que la lista no esté vacía.

R, 81 76 63 bytes

¡Gracias a @rturnbull por jugar al golf 13 bytes!

function(u,v)sum(t(t(expand.grid(lapply(u/v,seq,f=0))))%*%v==u)

Ejemplo (tenga en cuenta que así c(...)es como pasa vectores de valores a R):

f(12,c(1,5,10))
[1] 4

Explicación:

ues el valor deseado, ves el vector de valores de monedas.

expand.grid(lapply(u/v,seq,from=0))

crea un marco de datos con cada combinación posible de 0 a k monedas (k depende de la denominación), donde k es el más bajo, de modo que k multiplicado por el valor de esa moneda es al menos u (el valor a alcanzar).

Normalmente lo usaríamos as.matrixpara convertir eso en una matriz, pero eso es muchos caracteres. En su lugar, tomamos la transposición de la transposición (!) Que la coacciona automáticamente, pero toma menos caracteres.

%*% vluego calcula el valor monetario de cada fila. El último paso es contar cuántos de esos valores son iguales al valor deseado u.

Tenga en cuenta que la complejidad computacional y los requisitos de memoria de esto son horribles, pero bueno, es el código golf.

J, 27 bytes

1#.[=](+/ .*~]#:,@i.)1+<.@%

Uso

   f =: 1#.[=](+/ .*~]#:,@i.)1+<.@%
   12 f 1 5 10
4
   26 f 1 5 10 25
13
   19 f 2 7 12
2
   13 f 2 8 25
0

Explicación

1#.[=](+/ .*~]#:,@i.)1+<.@%  Input: target T (LHS), denominations D (RHS)
                          %  Divide T by each in D
                       <.@   Floor each
                             These are the maximum number of each denomination
                     1+      Add 1 to each, call these B
                ,@i.         Forms the range 0 the the product of B
             ]               Get B
              #:             Convert each in the range to mixed radix B
     ]                       Get D
       +/ .*~                Dot product between D and each mixed radix number
                             These are all combinations of denominations up to T
   [                         Get T
    =                        Test if each sum is equal to T
1#.                          Convert as base 1 digits to decimal (takes the sum)
                             This is the number of times each sum was true

TSQL, 105 bytes

Esto solo puede manejar hasta un dólar con estos 4 tipos de monedas. La versión sin golf puede manejar hasta alrededor de 4 dólares, pero muy lenta: en mi caja, esto toma 27 segundos. El resultado es 10045 combinaciones por cierto

Golfizado:

DECLARE @ INT = 100
DECLARE @t table(z int)
INSERT @t values(1),(5),(10),(25)
;WITH c as(SELECT 0l,0s UNION ALL SELECT z,s+z FROM c,@t WHERE l<=z and s<@)SELECT SUM(1)FROM c WHERE s=@

Sin golf:

-- input variables
DECLARE @ INT = 100
DECLARE @t table(z int)
INSERT @t values(1),(5),(10),(25)

-- query
;WITH c as
(
  SELECT 0l,0s
  UNION ALL
  SELECT z,s+z
  FROM c,@t
  WHERE l<=z and s<@
)
SELECT SUM(1)
FROM c
WHERE s=@
-- to allow more than 100 recursions(amounts higher than 1 dollar in this example)
OPTION(MAXRECURSION 0)

Violín

tinylisp repl, 66 bytes

(d C(q((Q V)(i Q(i(l Q 0)0(i V(s(C(s Q(h V))V)(s 0(C Q(t V))))0))1

Solución recursiva: intenta usar la primera moneda y no usar la primera moneda, luego agrega los resultados de cada una. Complejidad de tiempo exponencial y sin recursividad de cola, pero calcula bien los casos de prueba.

Sin golf (clave para construir: d= definir, q= citar, i= si, l= menor que, s= restar, h= cabeza, t= cola):

(d combos
 (q
  ((amount coin-values)
   (i amount
    (i (l amount 0)
     0
     (i coin-values
      (s
       (combos
        (s amount (h coin-values))
        coin-values)
       (s
        0
        (combos
         amount
         (t coin-values))))
      0))
    1))))

Ejemplo de uso:

tl> (d C(q((Q V)(i Q(i(l Q 0)0(i V(s(C(s Q(h V))V)(s 0(C Q(t V))))0))1
C
tl> (C 12 (q (1 5 10)))
4
tl> (C 26 (q (1 5 10 25)))
13
tl> (C 19 (q (2 7 12)))
2
tl> (C 13 (q (2 8 25)))
0
tl> (C 400 (q (1 5 10 25)))
Error: recursion depth exceeded. How could you forget to use tail calls?!

PHP, 130 bytes

function r($n,$a){if($c=$a[0])for(;0<$n;$n-=$c)$o+=r($n,array_slice($a,1));return$o?:$n==0;}echo r($argv[1],array_slice($argv,2));

Función recursiva de 99 bytes (y 31 bytes de llamada) que elimina repetidamente el valor de la moneda actual del objetivo y se llama a sí mismo con el nuevo valor y las otras monedas. Cuenta el número de veces que el objetivo alcanza exactamente 0. Corre como:

 php -r "function r($n,$a){if($c=$a[0])for(;0<$n;$n-=$c)$o+=r($n,array_slice($a,1));return$o?:$n==0;}echo r($argv[1],array_slice($argv,2));" 12 1 5 10

Raqueta 275 bytes

(set! l(flatten(for/list((i l))(for/list((j(floor(/ s i))))i))))(define oll'())(for((i(range 1(add1(floor(/ s(apply min l)))))))
(define ol(combinations l i))(for((j ol))(set! j(sort j >))(when(and(= s(apply + j))(not(ormap(λ(x)(equal? x j))oll)))(set! oll(cons j oll)))))oll

Sin golf:

(define(f s l)
  (set! l              ; have list contain all possible coins that can be used
        (flatten
         (for/list ((i l))
           (for/list ((j              
                       (floor
                        (/ s i))))
             i))))
  (define oll '())                    ; final list of all solutions initialized
  (for ((i (range 1  
                  (add1
                   (floor             ; for different sizes of coin-set
                    (/ s
                       (apply min l)))))))
    (define ol (combinations l i))          ; get a list of all combinations
    (for ((j ol))                           ; test each combination
      (set! j (sort j >))
      (when (and
             (= s (apply + j))              ; sum is correct
             (not(ormap                     ; solution is not already in list
                  (lambda(x)
                    (equal? x j))
                  oll)))
        (set! oll (cons j oll))             ; add found solution to final list
        )))
  (reverse oll))

Pruebas:

(f 4 '[1 2])
(println "-------------")
(f 12 '[1 5 10])
(println "-------------")
(f 19 '[2 7 12])
(println "-------------")
(f 8 '(1 2 3))

Salida:

'((2 2) (2 1 1) (1 1 1 1))
"-------------"
'((10 1 1) (5 5 1 1) (5 1 1 1 1 1 1 1) (1 1 1 1 1 1 1 1 1 1 1 1))
"-------------"
'((12 7) (7 2 2 2 2 2 2))
"-------------"
'((3 3 2) (2 2 2 2) (3 2 2 1) (3 3 1 1) (2 2 2 1 1) (3 2 1 1 1) (2 2 1 1 1 1) (3 1 1 1 1 1) (2 1 1 1 1 1 1) (1 1 1 1 1 1 1 1))

La siguiente solución recursiva tiene algún error:

(define (f s l)                      ; s is sum needed; l is list of coin-types
  (set! l (sort l >))
  (define oll '())                   ; list of all solution lists
  (let loop ((l l)   
             (ol '()))               ; a solution list initialized
    (when (not (null? l))
        (set! ol (cons (first l) ol)))
    (define ols (apply + ol))        ; current sum in solution list
    (cond
      [(null? l) (remove-duplicates oll)]
      [(= ols s) (set! oll (cons ol oll))
                 (loop (rest l) '()) 
                 ]
      [(> ols s) (loop (rest l) (rest ol))
                 (loop (rest l) '())   
                 ]
      [(< ols s) (loop l ol) 
                 (loop (rest l) ol)
                 ])))

No funciona correctamente para:

(f 8 '[1 2 3])

Salida:

'((1 1 1 2 3) (1 2 2 3) (1 1 1 1 1 1 1 1) (2 3 3) (1 1 1 1 1 1 2) (1 1 1 1 2 2) (1 1 2 2 2) (2 2 2 2))

(1 1 3 3) es posible pero no aparece en la lista de soluciones.

Jalea , 15 bytes

s+\Fṁḷ
2*BW;ç/Ṫ

Pruébalo en línea! o Verificar todos los casos de prueba.

Esto fue más un ejercicio de escribir una versión eficiente en Jelly sin usar builtins. Esto se basa en el enfoque típico de programación dinámica utilizado para calcular la cantidad de formas de realizar cambios

Explicación

s+\Fṁḷ  Helper link. Input: solutions S, coin C
s       Slice the solutions into non-overlapping sublists of length C
 +\     Cumulative sum
   F    Flatten
     ḷ  Left, get S
    ṁ   Mold the sums to the shape of S

2*BW;ç/Ṫ  Main link. Input: target T, denominations D
2*        Compute 2^T
  B       Convert to binary, creates a list with 1 followed by T-1 0's
          These are the number of solutions for each value from 0 to T
          starting with no coins used
   W      Wrap it inside another array
    ;     Concatenate with D
     ç/   Reduce using the helper link
       Ṫ  Tail, return the last value which is the solution

En realidad , 15 bytes

Sugerencias de golf bienvenidas. Pruébalo en línea!

╗;R`╜∙♂S╔♂Σi`Mc

Ungolfing

         Implicit input n, then the list of coins a.
╗        Save a to register 0.
;R       Duplicate n and create a range [1..n] from that duplicate.
`...`M   Map the following function over that range. Variable i.
  ╜        Push a from register 0.
  ∙        Push the i-th Cartesian power of a.
  ♂S       Sort each member of car_pow.
  ╔        Uniquify car_pow so we don't count too any duplicate coin arrangements.
  ♂Σ       Take the sum of each coin arrangement.
  i        Flatten the list.
c        Using the result of the map and the remaining n, push map.count(n).
         Implicit return.

Python, 120 bytes

from itertools import*
lambda t,L:[sum(map(lambda x,y:x*y,C,L))-t for C in product(range(t+1),repeat=len(L))].count(0)

Fuerza bruta a través de todas las combinaciones de monedas hasta el valor objetivo (incluso si la más pequeña no es 1).