... contou!
Você passará ao seu programa uma variável que representa uma quantidade de dinheiro em dólares e / ou centavos e uma matriz de valores de moedas. Seu desafio é gerar o número de combinações possíveis da matriz especificada de valores de moedas que somariam a quantia passada para o código. Se não for possível com as moedas nomeadas, o programa deve retornar 0
.
Nota sobre a terminologia numismática americana:
- Moeda de 1 centavo: centavo
- Moeda de 5 cêntimos: níquel
- Moeda de 10 cêntimos: moeda de dez centavos
- Moeda de 25 cêntimos: quarto de dólar
Exemplo 1:
Programa é passado:
12, [1, 5, 10]
(12 centavos)
Saída:
4
Existem 4 maneiras possíveis de combinar as moedas nomeadas para produzir 12 centavos:
- 12 centavos
- 1 níquel e 7 centavos
- 2 níquel e 2 centavos
- 1 centavo e 2 centavos
Exemplo 2:
Programa é passado:
26, [1, 5, 10, 25]
(26 centavos)
Saída:
13
Existem 13 maneiras possíveis de combinar as moedas nomeadas para produzir 26 centavos:
- 26 centavos
- 21 centavos e 1 níquel
- 16 centavos e 2 níquel
- 11 centavos e 3 níquel
- 6 tostões e 4 níquel
- 1 centavo e 5 níquel
- 16 centavos e 1 centavo
- 6 centavos e 2 centavos
- 11 centavos, 1 centavo e 1 níquel
- 6 centavos, 1 centavo e 2 níquel
- 1 centavo, 1 centavo e 3 níquel
- 1 centavo, 2 centavos e 1 níquel
- 1 quarto e 1 centavo
Exemplo 3:
Programa é passado:
19, [2, 7, 12]
Saída:
2
Existem 2 maneiras possíveis de combinar as moedas nomeadas para produzir 19 centavos:
- 1 moeda de 12 centavos e 1 moeda de 7 centavos
- 1 moeda de 7 centavos e 6 moedas de 2 centavos
Exemplo 4:
Programa é passado:
13, [2, 8, 25]
Saída:
0
Não há maneiras possíveis de combinar as moedas nomeadas para produzir 13 centavos.
Isso já passou pela Sandbox. Aplicam-se brechas padrão. Isso é código de golfe, então a resposta com o menor número de bytes vence.
fonte
s/count/earn
.Respostas:
Geléia ( garfo ), 2 bytes
Isso se baseia em um ramo do Jelly, onde eu estava trabalhando na implementação de átomos de solução Frobenius. Infelizmente, você não pode experimentá-lo online.
Uso
Explicação
fonte
Haskell,
3734 bytesExemplo de uso:
26 # [1,5,10,25]
->13
.Abordagem recursiva simples: tente o próximo número da lista (contanto que seja menor ou igual à quantidade) e pule-o. Se subtrair o número levar a um valor zero, use
1
outro (ou se a lista ficar sem elementos) use a0
. Soma aqueles1
s e0
s.Edit: @Damien: salvou 3 bytes apontando para um caso base mais curto para a recursão (que também pode ser encontrada na resposta @xnors ).
fonte
1209 # [1,5,10,33,48]
->1314050
.6000 # [1,5,10,33]
->22086484
.Mathematica,
3522 bytesGraças a milhas por sugerir
FrobeniusSolve
e salvar 13 bytes.Avalia como uma função sem nome, que leva a lista de moedas como o primeiro argumento e o valor alvo como o segundo.
FrobeniusSolve
é uma abreviação para resolver equações diofantinas da formapara os números inteiros não negativos e fornece todas as soluções.
xi
fonte
(Length@*FrobeniusSolve)[{1, 7, 9}, 18]
Pitão, 8 bytes
Força bruta bruta, muita memória para testes reais. Este é O (2 mn ), onde n é o número de moedas e m é a soma alvo. Toma entrada como
target\n[c,o,i,n,s]
.fonte
Haskell, 37 bytes
O uso de alguns múltiplos da primeira moeda
h
diminui a soma necessárias
para um valor não negativo na progressão decrescente[s,s-h..0]
, que deve ser feita com as moedas restantes. Quando não sobrar moedas, verifique se a soma é zero aritmeticamente como0^s
.fonte
JavaScript (ES6),
5148 bytesAceita moedas em qualquer ordem. Tenta usar e não usar a primeira moeda, calculando recursivamente o número de combinações de qualquer maneira.
n==0
significa uma combinação correspondente,n<0
significa que as moedas excedem a quantidade, enquantoc==undefined
significa que não restam moedas. Observe que a função é muito lenta e, se você tiver uma moeda de um centavo, a função a seguir será mais rápida (não passe a moeda de um centavo no conjunto de moedas):fonte
Perl, 45 bytes
A contagem de bytes inclui 44 bytes de código e
-p
sinalizador.Toma os valores das moedas na primeira linha e o valor alvo na segunda linha:
Breves explicações:
fonte
Geléia ,
109 bytesExperimente online!
Quão?
fonte
JavaScript (ES6), 59 bytes
As moedas são inseridas do mais alto para o mais baixo, por exemplo
f(26,[100,25,10,5,1])
. Se você tiver um centavo, remova-o e use esta versão muito mais rápida:Isso usa uma fórmula recursiva muito parecida com a do @ nimi. Eu escrevi isso originalmente alguns dias atrás, quando o desafio ainda estava na caixa de areia; ficou assim:
As únicas diferenças eram o valor padrão de
c
(tinha um valor definido no desafio original) e a alteração0
da.reduce
função para1
(isso era dois bytes mais curto e um bazilhão de vezes mais rápido quec=[100,25,10,5,1]
).Aqui está uma versão modificada que gera todas as combinações, em vez do número de combinações:
fonte
PHP, 327 bytes
Tente
fonte
Axioma,
6362 bytes1 byte salvo por @JonathanAllan
Essa abordagem usa funções de geração. Provavelmente isso não ajudou a diminuir o tamanho do código. Penso que esta é a primeira vez que, ao jogar com o Axiom, fui até definir minha própria função.
A primeira vez que a função é chamada, ela dá um aviso horrendo, mas ainda produz o resultado correto. Depois disso, tudo ficará bem, desde que a lista não esteja vazia.
fonte
for
?R,
817663 bytesGraças a @rturnbull por jogar fora 13 bytes!
Exemplo (note que
c(...)
é assim que você passa vetores de valores para R):Explicação:
u
é o valor desejado,v
é o vetor dos valores das moedas.cria um quadro de dados com todas as combinações possíveis de 0 a k moedas (k depende da denominação), onde k é o menor, de modo que k vezes o valor dessa moeda seja pelo menos u (o valor a ser alcançado).
Normalmente, usamos isso
as.matrix
para transformar isso em uma matriz, mas são muitos caracteres. Em vez disso, assumimos a transposição da transposição (!) Que a força automaticamente, mas leva menos caracteres.%*% v
depois calcula o valor monetário de cada linha. O último passo é contar quantos desses valores são iguais ao valor desejadou
.Observe que a complexidade computacional e os requisitos de memória disso são horríveis, mas ei, é código de golfe.
fonte
expand.grid
! E eu amo ot(t())
truque. Como sua função envolve apenas uma única linha de código, você pode remover os chavetas, economizando 2 bytes. Além disso, você pode alternardo.call(expand.grid,lapply(u/v,seq,from=0))
por apenasexpand.grid(lapply(u/v,seq,f=0))
, economizando 11 bytes.expand.grid
que levaria uma lista como entrada. É uma pena que":"
não funcione bem com não-números inteiros, caso contráriolapply(u/v,":",0)
, teria economizado mais alguns.do.call(x,y)
é o mesmo quex(y)
, portanto, não se trata de que tipos de entrada são aceitos. Se você realmente deseja usar:
, suponho que possa usá-lapply(u%/%v,`:`,0)
lo, mas é a mesma contagem de bytes.do.call(x,y)
é o mesmo quex(y)
" --- somente sey
não houver uma lista, nesse caso. No entanto, concorde com o seu segundo ponto.J, 27 bytes
Uso
Explicação
fonte
TSQL, 105 bytes
Isso pode suportar até um dólar com esses 4 tipos de moedas. A versão não-gasta pode suportar até cerca de 4 dólares, mas muito lenta - na minha caixa, isso leva 27 segundos. O resultado é 10045 combinações entre
Golfe:
Ungolfed:
Violino
fonte
repl do tinylisp , 66 bytes
Solução recursiva: tenta usar a primeira moeda e não a primeira, depois adiciona os resultados de cada uma. Complexidade de tempo exponencial e sem recursão de cauda, mas calcula bem os casos de teste.
Ungolfed (chave para builtins:
d
= definir,q
= citar,i
= se,l
= menor que,s
= subtrair,h
= cabeça,t
= cauda):Exemplo de uso:
fonte
PHP, 130 bytes
Função recursiva de 99 bytes (e 31 bytes de chamá-lo) que remove repetidamente o valor da moeda atual do destino e se chama com o novo valor e as outras moedas. Conta o número de vezes que o alvo atinge 0 exatamente. Executar como:
fonte
Raquete 275 bytes
Ungolfed:
Teste:
Saída:
A seguinte solução recursiva apresenta algum erro:
Não funciona corretamente para:
Saída:
(1 1 3 3) é possível, mas não aparece na lista de soluções.
fonte
reduce
Scheme
( groups.csail.mit.edu/mac/projects/scheme ) que finalmente levou à expansãoRacket
( racket-lang.org , stackoverflow.com/questions/3345397/… )!Gelatina , 15 bytes
Experimente online! ou Verifique todos os casos de teste.
Este foi mais um exercício para escrever uma versão eficiente no Jelly sem usar os recursos internos. Isso se baseia na abordagem típica de programação dinâmica usada para calcular o número de maneiras de fazer alterações
Explicação
fonte
Na verdade , 15 bytes
Sugestões de golfe são bem-vindas. Experimente online!
Ungolfing
fonte
Python, 120 bytes
Força bruta através de todas as combinações de moedas até o valor alvo (mesmo que o menor não seja 1).
fonte