Número mínimo de números para somar exatamente n

15

Primeira pergunta aqui, não grite comigo se isso for uma duplicata ou um mau desafio.

Introdução

Eu mesmo pensei nesse desafio e parece ser um bom quebra-cabeça básico para jogadores iniciantes de código. Também pode me ajudar a decidir qual idioma do código de golfe aprender.

Desafio

Dada uma matriz de números inteiros menores ou iguais a n, produza ou retorna o número mínimo de números da matriz que somam exatamente n.

Você pode optar por escrever uma função ou um programa completo.

Entrada

Você pode assumir com segurança 0 <= n < 2^31.

Pegue uma matriz ou lista de qualquer tipo ( vectorpara C ++ ou Java é LinkedListpermitido), junto com ne um parâmetro opcional length, que especifica o comprimento da matriz.

Você também pode considerar a entrada como uma sequência separada npor espaço, separada por vírgula ou espaço:

1 5 7 3 7 3 6 3 2 6 3,10

1 5 7 3 7 3 6 3 2 6 3 10

se for mais fácil.

Resultado

Saída ou retorne o número mínimo de números da matriz que somam exatamente n. Usando o exemplo acima:

1 5 7 3 7 3 6 3 2 6 3,10

Seu programa deve imprimir:

2

porque o número mínimo de números que soma 10é 2( 7e 3).

No caso de não haver solução, imprima ou retorne um negativo, 0"Nenhuma solução" (embora isso não seja inteligente), (como sugerido) ou qualquer outro valor falso, com exceção de uma sequência vazia.

Exemplo de entrada e saída

Entrada:

1 5 7 3 7 3 6 3 2 6 3,10
143 1623 1646 16336 1624 983 122,18102
5 6 9,12

Resultado:

2
3
-1

Pontuação

Isso é código-golfe, então o código mais curto em bytes vence.

A resposta principal será aceita no Natal.

TheCoffeeCup
fonte
Editei suas especificações, porque geralmente permitimos os mesmos métodos de E / S para funções e programas; veja o consenso aqui . Sinta-se à vontade para reverter se não concorda.
lirtosiast
Podemos produzir falsepara casos sem soluções?
ETHproductions
@ETHproductions Claro, acrescentará isso.
TheCoffeeCup
Você considera a saída vazia falsey, já que a string vazia é falsey em Pyth?
lirtosiast
@ThomasKwa Eu não gosto de saídas de string vazias, mas você pode incluí-lo como "se x foi permitido ..." em sua resposta ...
TheCoffeeCup 10/15 /

Respostas:

7

Pitão, 12 11 bytes

lhafqsTQyEY

Isso leva ncomo a primeira linha de entrada e a lista na segunda linha.

lhafqsTQyEY     (Implicit: Q = 1st line of input; E = 2nd line)
         E      The list
        yE      Powerset (sorted by increasing length; empty set first)
   f            Filter by lambda T:
     sT         sum(T)
    q                  ==
       Q                  Q
   fqSTQyE      Sublists that sum to Q, sorted by increasing length
  a       Y     append an empty array (in case none match)
lh              take the length of the first element (0 for empty array)

Experimente aqui .

lirtosiast
fonte
1
Seu código e sua explicação não coincidem.
Isaacg
@isaacg Agora corrigido.
lirtosiast
5

Japonês , 30 21 18 bytes

Acontece que havia um método muito mais eficiente. ;)

Uà f_x ¥V} ml n- g

Teste online! (Nota: n-foi alterado para n@X-Y}por motivos de compatibilidade)

Isso recebe a entrada como uma matriz separada por espaço ou vírgula, seguida por um número. Saídas undefinedpara casos de teste sem soluções.

Uà f_  x ¥ V} ®   l} n- g
UàfmZ{Zx ==V} mZ{Zl} n- g

            // Implicit: U = input array, V = input integer
Uà fZ{   }  // Generate all possible combinations of U, then filter to only items Z where
Zx ==V      //   the sum of Z is equal to V.
mZ{Zl}      // Map each remaining combination to its length.
n-          // Sort by subtraction; smaller items end up in the front.
g           // Take the first item.
            // Implicit: output last expression

Não acredito que não pensei nessa versão quando escrevi originalmente ...

Várias otimizações foram feitas desde então, que são úteis aqui:

  • A Uno início do programa geralmente pode ser deixada de fora.
  • Ãé um atalho para .
  • n agora classifica os números corretamente por padrão.

Cada um deles retira um byte, totalizando 15:

à f_x ¥VÃml n g

Teste online!

ETHproductions
fonte
Isso é 25 bytes, não 21. #
558 Albert Renshaw
1
O @AlbertRenshaw Japt suporta a codificação IEC_8859-1 , na qual cada um desses caracteres tem 1 byte. Você pode salvar este programa como um arquivo de texto codificado em IEC_8859-1 e carregá-lo no intérprete online .
ETHproductions
Ah legal! Obrigado por me informar
Albert Renshaw
1

Mathematica, 73 65 bytes

Min[Length/@Select[IntegerPartitions[#2,#2,#],Sort@#==Union@#&]]&

Função pura, retorna se não houver solução.

LegionMammal978
fonte
1

Python 3, 128 bytes

Isso não é tão divertido quanto eu gostaria, mas vou trabalhar nisso mais tarde.

from itertools import*
def s(a,n):
 for i in range(len(a)):
  for j in permutations(a,i+1):
   if sum(j)==n:return i+1
 return 0
Sherlock9
fonte
1

Mathematica, 45 bytes

Min@Cases[Subsets@#,i_/;Tr@i==12:>Length@#2]&
alefalpha
fonte
1

CJam, 34 bytes

0q~_,2,m*\f.*{:+1$=},\;0f-{,}$0=,+

Experimente online . O formato de entrada é a soma seguida pela lista de valores, por exemplo:

18102 [143 1623 1646 16336 1624 983 122]

Observe que isso gerará uma exceção se nenhuma solução for encontrada. A exceção vai para stderr quando o CJam é executado na linha de comando e o resultado correto (0 ) ainda é impresso no stdout. Portanto, isso atende ao consenso estabelecido em Deve-se permitir que os envios saiam com erro?

O código pode parecer mais longo do que o esperado. O principal motivo é que o CJam não possui built-in para gerar combinações. Ou pelo menos essa é a minha desculpa, e eu estou cumprindo.

Explicação:

0       Push 0 result for exception case.
q~      Get and interpret input.
_,      Copy and get length of input value list.
2,      Push [0 1].
m*      Cartesian power. This generates all possible lists of 0/1 values with the
        same length as the input value list.
\       Swap input value list to top.
f.*     Apply element-wise product of input value list with all 0/1 lists.
        We now have all combinations of values, with 0 in place of unused values.
{       Start filter block.
  :+      Sum values.
  1$      Copy target sum to top.
  =       Compare.
},      Filter.
\;      Swap target sum to top and discard.
0f-     Remove 0 values. We now have all solution lists.
{,}$    Sort by length.
0=      Get first solution, which after sorting is the shortest.
        This will raise an exception if the list of solutions is empty, bailing
        out with the initial 0 on the stack.
,       Get length of solution.
+       Add the 0 we initially pushed for the exception case.
Reto Koradi
fonte
1

JavaScript (ES6), 84 bytes

f=(a,n,m=1e999,x)=>n&&a.map((v,i)=>(x=[...a],x.splice(i,1),x=f(x,n-v)+1)<m?m=x:0)&&m

Explicação

Toma um Arrayde se Numberum Numbercomo argumentos. Retorna um número de Infinityse nenhum resultado. É uma função recursiva que subtrai ne remove cada elemento da matriz, um por um, até n == 0.

f=(a,n,m=1e999,x)=> // m and x are not passed, they are here to declare them in the local
                    //     scope instead of globally, initialise m to Infinity
  n&&               // if n == 0, return 0
  a.map((v,i)=>     // iterate over each number in a
    (x=[...a],      // x = copy of a
    x.splice(i,1),  // remove the added number from the array
    x=f(x,n-v)+1)   // x = result for the numbers in this array
      <m?m=x:0      // set m to minimum result
  )
  &&m               // return m

Teste

Esse teste é definido mcomo Infinitymais tarde, em vez de como um argumento padrão, para fazê-lo funcionar no Chrome (em vez de apenas no Firefox).

user81655
fonte
1

Haskell, 72 bytes

import Data.List
n#l=head$sort[length x|x<-subsequences l,sum x==n]++[0]

Retorna 0se não houver solução.

Exemplo de uso: 10 # [1,5,7,3,7,3,6,3,2,6,3]-> 2.

Encontre todas as sub-listas da lista de entrada lcom uma soma de n. Pegue o comprimento de cada sub-lista e classifique. Anexar um0 e pegue o primeiro elemento.

Se uma lista de singleton é permitido para a saída, por exemplo [2], podemos salvar 7 bytes: n#l=minimum[length x|x<-subsequences l,sum x==n]. No caso de não haver solução, a lista vazia []é retornada.

nimi
fonte