Erste Frage hier, schrei mich nicht an, wenn dies ein Duplikat oder eine schlechte Herausforderung ist.

Einführung

Ich habe mir diese Herausforderung selbst überlegt und es scheint ein gutes Grundrätsel für Anfänger im Code-Golfen zu sein. Es könnte mir auch bei der Entscheidung helfen, welche Code-Golf-Sprache ich lernen möchte.

Herausforderung

Bei einem Array von ganzen Zahlen, die kleiner oder gleich sind n, wird die minimale Anzahl von Zahlen aus dem Array ausgegeben oder zurückgegeben, die sich genau summieren n.

Sie können wählen, ob Sie eine Funktion oder ein vollständiges Programm schreiben möchten.

Eingang

Sie können davon ausgehen, sicher 0 <= n < 2^31.

Nehmen Sie ein Array oder eine Liste jeder Art ( vectorfür C ++ oder Java LinkedListsind zulässig) nsowie einen optionalen Parameter length, der die Länge des Arrays angibt.

Sie können die Eingabe auch als durch Leerzeichen getrennte Zeichenfolge verwenden, die ndurch ein Komma oder ein Leerzeichen voneinander getrennt ist:

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

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

wenn es einfacher ist.

Ausgabe

Ausgabe oder Rückgabe der Mindestanzahl von Zahlen aus dem Array, die sich genau summieren n. Mit dem obigen Beispiel:

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

Ihr Programm sollte drucken:

2

weil die minimale Anzahl von Zahlen , die Summe bis zu 10ist 2( 7und 3).

Für den Fall, dass es keine Lösung gibt, drucken oder geben Sie entweder ein Negativ, 0"Keine Lösung" (obwohl dies nicht sinnvoll wäre) ∞(wie vorgeschlagen) oder einen anderen falschen Wert mit Ausnahme einer leeren Zeichenfolge zurück.

Beispiel für Ein- und Ausgabe

Eingang:

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

Ausgabe:

2
3
-1

Wertung

Das ist Code-Golf, also gewinnt der kürzeste Code in Bytes.

Die Top-Antwort wird zu Weihnachten angenommen.

Pyth, 12 11 Bytes

lhafqsTQyEY

Dies nimmt nals erste Eingabezeile und die Liste in der zweiten Zeile.

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)

Probieren Sie es hier aus .

Japt , 30 21 18 Bytes

Es stellte sich heraus, dass es eine viel effizientere Methode gab. ;)

Uà f_x ¥V} ml n- g

Testen Sie es online! (Hinweis: n-wurde n@X-Y}aus Kompatibilitätsgründen in geändert )

Die Eingabe erfolgt als durch Leerzeichen oder Kommas getrenntes Array, gefolgt von einer Zahl. Ausgaben undefinedfür Testfälle ohne Lösungen.

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

Ich kann nicht glauben, dass ich nicht an diese Version gedacht habe, als ich das ursprünglich schrieb ...

Seitdem wurden einige Optimierungen vorgenommen, die sich hier als nützlich erweisen:

• Ein Uam Anfang des Programms kann in der Regel weggelassen werden.
• Ãist eine Abkürzung für } .
• n sortiert jetzt die Nummern standardmäßig richtig.

Jedes dieser Elemente entfernt ein Byte für insgesamt 15:

à f_x ¥VÃml n g

Online testen!

Mathematica, 73 65 Bytes

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

Reine Funktion, kehrt zurück, ∞wenn es keine Lösung gibt.

Python 3, 128 Bytes

Das ist nicht so gut, wie ich es gerne hätte, aber ich werde später daran arbeiten.

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

Mathematica, 45 Bytes

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

CJam, 34 Bytes

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

Probieren Sie es online aus . Das Eingabeformat ist die Summe, gefolgt von der Werteliste, zB:

18102 [143 1623 1646 16336 1624 983 122]

Beachten Sie, dass dies eine Ausnahme auslöst, wenn keine Lösung gefunden wird. Die Ausnahme geht an stderr, wenn CJam über die Befehlszeile ausgeführt wird und das richtige Ergebnis (0 ) weiterhin an stdout . Dies entspricht also dem Konsens, der unter Sollte es zulässig sein, dass Einreichungen mit einem Fehler beendet werden?

Der Code sieht möglicherweise länger aus als erwartet. Der Hauptgrund ist, dass CJam keine eingebauten Funktionen zum Erzeugen von Kombinationen hat. Zumindest ist das meine Entschuldigung und ich halte mich daran.

Erläuterung:

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.

JavaScript (ES6), 84 Byte

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

Erläuterung

Nimmt ein Arrayvon Numbers und ein Numberals Argumente. Gibt eine Anzahl von Infinitywenn kein Ergebnis zurück. Es ist eine rekursive Funktion, ndie jedes Element einzeln vom Array subtrahiert und daraus entfernt, bis 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

Prüfung

Dieser Test wird mauf Infinityspäter anstatt als Standardargument festgelegt, damit er in Chrome funktioniert (anstatt nur in Firefox).

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

Array (space-delimited) = <input type="text" id="array" value="143 1623 1646 16336 1624 983 122" /><br />
n = <input type="number" id="N" value="18102" /><br />
<button onclick="result.textContent=solution(array.value.split` `,N.value)">Go</button>
<pre id="result"></pre>

Haskell, 72 Bytes

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

Gibt zurück, 0wenn es keine Lösung gibt.

Anwendungsbeispiel: 10 # [1,5,7,3,7,3,6,3,2,6,3]-> 2.

Finden Sie alle Unterlisten der Eingabeliste l, die eine Summe von haben n. Nimm die Länge jeder dieser Unterlisten und sortiere sie. Hänge ein an 0und nimm das erste Element.

Wenn eine Singleton - Liste für die Ausgabe erlaubt ist, zum Beispiel [2], können wir 7 Bytes speichern: n#l=minimum[length x|x<-subsequences l,sum x==n]. Falls keine Lösung gefunden wird, wird die leere Liste []zurückgegeben.