Un centavo ahorrado es un centavo

21

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

anónimo2
fuente
1
s / contado / ganado
mbomb007
44
@ mbomb007 Durante cuatro bytes: s/count/earn.
wizzwizz4
55
Para mí y supongo que para otras personas que no pagan con dólares no es obvio qué es un centavo y un centavo. No fue difícil resolverlo, pero ¿tal vez podrías escribirlo un poco más internacional?
Kritzefitz
2
@Kritzefitz. He agregado eso a la pregunta.
TRiG
2
@jpaugh: Si bien coin-o-philes podría estar de acuerdo, tendría que estar en desacuerdo. Un centavo es la moneda estándar que tiene un valor de un centavo. Cincuenta y cuatro centavos es una cantidad de dinero. Cincuenta y cuatro centavos son explícitamente cincuenta y cuatro monedas. También se llama una "moneda de un centavo" o (oficialmente) una "pieza de un centavo". No puedo pensar en ningún entorno formal donde la palabra "centavo" sería inaceptable. Estas personas , que se dedican específicamente a recolectar monedas, no tienen problema en llamarlo un "centavo".
MichaelS

Respuestas:

12

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
millas
fuente
10
... eso ni siquiera es justo.
ETHproductions
... y apuesto a que es mucho más rápido!
Jonathan Allan
18

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

nimi
fuente
s # l @ (c: d) | s> = c = (sc) # l + s # d; s # _ = 0 ^ s
Damien
y cuál sería el resultado de 1209 [1,5,10,33,48] y 6000 [1,5,10,33] para poder calibrar mi código
RosLuP
@RosLuP: 1209 # [1,5,10,33,48]-> 1314050.
nimi
@nimi ok para 1314050 Tengo el mismo resultado aquí ... Gracias ...
RosLuP
@RosLuP: ... 537min después: 6000 # [1,5,10,33]-> 22086484.
nimi
15

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

Martin Ender
fuente
@RosLuP Necesitará acceso a Mathematica para ejecutar esto. Además, esta es una función anónima, por lo que llamarlo, encapsularlo entre paréntesis o almacenarlo en una variable. Por ejemplo,(Length@*FrobeniusSolve)[{1, 7, 9}, 18]
millas
y cuál sería el resultado de 1209 [1,5,10,33,48] y 6000 [1,5,10,33] para que pueda calibrar mi código
RosLuP
@RosLuP 1314050 y 22086484, respectivamente.
Martin Ender
Ok, aquí resulta lo mismo, gracias ...
RosLuP
16 votos para esto se justifican solo si el programador que escribió Length @ * FrobeniusSolve eres tú ...
RosLuP
12

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
PurkkaKoodari
fuente
9

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.

xnor
fuente
Es sorprendente cómo golpeas exactamente el mismo número de bytes que @nimi usando un enfoque diferente.
Kritzefitz
9

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
Neil
fuente
... Dangit. Muy buena idea.
ETHproductions
y cuál sería el resultado de 1209 [1,5,10,33,48] y 6000 [1,5,10,33] para que pueda calibrar mi código
RosLuP
@RosLuP El código dado finalmente devuelve 1314050 para su primer ejemplo. Mi intérprete no puede manejar la recursividad necesaria para evaluar el segundo ejemplo.
Neil
@RosLuP Modifiqué la función para asumir que existe una moneda de centavo adicional y que devolvió 22086484 por 6000 [5,10,33].
Neil
@Neil ok 22086484 para 6000 [1,5,10,33] ... En cambio, sería 11239 aquí para 6000 [5,10,33] (la matriz que escribiste)
RosLuP
7

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)
Dada
fuente
6

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
Jonathan Allan
fuente
2
+1 por usar tantos símbolos de euro en una pregunta relacionada con el dinero.
steenbergh
6

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])],[]):[[]]
ETHproducciones
fuente
y cuál sería el resultado de 1209 [1,5,10,33,48] y 6000 [1,5,10,33] para que pueda calibrar mi código
RosLuP
@RosLuP Obtengo 1314050 (después de 5 minutos) y un desbordamiento de pila (después de una hora), respectivamente. Con la versión más rápida que acabo de agregar, obtengo 1314050 y 22086484 en pocos segundos.
ETHproductions
Con mi vieja computadora Pentium 2.8Gh 6 segundos para el primer resultado, para los segundos 5 minutos + o -
RosLuP
5

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

Jörg Hülsermann
fuente
5

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.

Christian Sievers
fuente
1
No sé Axiom, ¿es posible eliminar el espacio antes for?
Jonathan Allan
1
@JonathanAllan ¡Sí, lo es! Buen instinto de golf, gracias!
Christian Sievers
5

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.

JDL
fuente
1
Buen uso de expand.grid! Y me encanta el t(t())truco. Como su función solo involucra una sola línea de código, puede eliminar las llaves, ahorrándole 2 bytes. Además, puede cambiar do.call(expand.grid,lapply(u/v,seq,from=0))por solo expand.grid(lapply(u/v,seq,f=0)), ahorrando 11 bytes.
rturnbull
Gracias por eso! Nunca me di cuenta de expand.gridque tomaría una lista como entrada. Es una pena que ":"no funcione bien con los no enteros, de lo contrario lapply(u/v,":",0)habría ahorrado un par más.
JDL
do.call(x,y)es igual que x(y), por lo que no se trata de qué tipos de entrada se aceptan. Si realmente quiere usar :, supongo que podría usar lapply(u%/%v,`:`,0), pero es el mismo conteo de bytes.
rturnbull
1
" do.call(x,y)es lo mismo que x(y)" --- solo si yno es una lista, que es en este caso. Sin embargo, acepta tu segundo punto.
JDL
3

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
millas
fuente
J es tan increíble, pero también tan loco
CommaToast
2

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

t-clausen.dk
fuente
2

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?!
DLosc
fuente
1

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
usuario59178
fuente
Si se llama con más de 97 tipos diferentes de monedas, morirá una muerte por recursión sin devolver nada, pero como son muchos más tipos diferentes de monedas, entonces tenemos que respaldar que está bien.
user59178
1

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.

rnso
fuente
No estoy familiarizado con la raqueta, pero lo hice escribir una solución en Clojure para un problema similar a esto hace unos años que hizo uso dereduce
milla
'reducir' no es parte del lenguaje base de Racket, aunque 'fold' está disponible. He agregado una solución modificada anteriormente ya que la solución anterior tiene algún error.
rnso
Parece que un grupo de entusiastas de Lisp se reunieron ... e hicieron un escándalo
Joe
1
¡Algunos de los entusiastas de Lisp primero hicieron un Scheme( groups.csail.mit.edu/mac/projects/scheme ) que finalmente condujo a un verdaderoRacket ( racket-lang.org , stackoverflow.com/questions/3345397/… )!
rnso
1

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
millas
fuente
1

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.
Sherlock9
fuente
0

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

Karl Napf
fuente