Herausforderung

Bei einer positiven Ganzzahl von N28 oder mehr wird eine Liste von Zahlen ausgegeben N, in der jede Ziffer genau einmal 1durchlaufen wird 7. Sie können als Programm oder Funktion geben.

Die Ziffern können einzeln oder verkettet angezeigt werden, sofern Sie sie ohne Wiederholungen jeweils einmal verwenden. Beispielsweise [12, 34, 56, 7]ist gültig, wie [1, 27, 6, 4, 35]und [1234, 567], aber nicht [123, 34567]oder [3, 2, 1476]. Die Reihenfolge, in der die Nummern aufgelistet sind, spielt keine Rolle.

Wenn Ndies mit 1-7 nicht möglich ist, geben Sie nichts zurück oder geben Sie nichts aus.

Andere Informationen

• Dies ist Codegolf, daher gewinnt der kürzeste Code in Bytes bis Donnerstag, den 15. Oktober.

• Stellen Sie Fragen in den Kommentaren.

• Alles, was ich in der Herausforderung nicht spezifiziere, liegt bei Ihnen.

• Standardlücken sind nicht zulässig.

Beispiele

Dies kann Verwirrung stiften:

Eingang

28

Ausgabe

[1, 2, 3, 4, 5, 6, 7]

Eingang

100

Ausgabe

[56, 7, 4, 31, 2]

Eingang

1234567

Ausgabe

[1234567]

Eingang

29

Ausgabe

Nichts, 29 ist ungültig.

Eingang

1891

Ausgabe

[1234, 657]

Eingang

370

Ausgabe

[15, 342, 7, 6]

Ich werde mehr machen, wenn nötig.

Hier ist ein Pastebin aller möglichen Zahlen, die mit diesen sieben Zahlen erstellt wurden, mit freundlicher Genehmigung von FryAmTheEggman.

Pyth, 18 14 Bytes

hfqSjkTjkS7./Q

Vielen Dank an @isaacg für das Abschlagen von 2 Bytes und den Weg für 2 weitere.

Der Code stürzt ab, wenn keine Ausgabe erzeugt wird, wodurch keine Ausgabe erzeugt wird.

Dies funktioniert für kleine Eingaben, wenn Sie geduldig genug sind, und für größere, wenn Sie genügend Zeit und Speicher haben.

Um zu überprüfen, ob der Code wie beabsichtigt funktioniert, können Sie den Code 7durch ein 3für die Ziffern 1 bis 3 ersetzen . Klicken Sie hier für eine Testsuite.

Beispiel läuft

$ time pyth/pyth.py -c 'hfqSjkTjkS7./Q' <<< 28
(1, 2, 3, 4, 5, 6, 7)

real    4m34.634s
user    4m34.751s
sys     0m0.101s
$ time pyth/pyth.py -c 'hfqSjkTjkS7./Q' <<< 29 2>/dev/null

real    9m5.819s
user    9m6.069s
sys     0m0.093s

Wie es funktioniert

           ./Q    Compute all integer partitions of the input.
 f                Filter the integer partitions:
    jkT             Join the integers with empty separator.
   S                Sort the characters of the resulting string.
      jkS7          Join [1, ..., 7] with empty separator.
  q                 Check both results for equality.
                  Keep the partition of `q' returned True.
h                 Retrieve the first element of the filtered list.
                  For a non-empty list, this retrieves the solution.
                  For the empty list, it causes an error and produces no output.

Python 3, 109

def f(n,s=set('1234567'),l='0,'):[f(n,s-{x},l+x+c)for c in(',','')for x in s]or n-sum(eval(l))or~print(l[2:])

Eine Funktion, die eine Zahl annimmt und ein Tupel wie dieses ausgibt 123,4567,. Ja, das ist ein gültiges Tupel.

Die Idee ist, alle möglichen Zeichenfolgen so zu generieren 43,126,7,5,, dass die Ziffern 1durch 7Kommas getrennt sind, ohne dass zwei Kommas aufeinander folgen. Werten Sie diesen Ausdruck als Tupel aus und seine Summe ist gleich n, drucken Sie ihn aus und schließen Sie ihn mit einem Fehler ab.

Um alle diese Zeichenfolgen zu erstellen, verfolgen wir die szu verwendenden Zeichen und versuchen, sie entweder mit einem Komma zu versehen, wodurch die Ziffer am Ende der Eingabe endet, oder ohne, in welchem ​​Fall sich zukünftige Ziffern darauf verketten.

Kurzschluss wird verwendet, um zu überprüfen, dass sdas Feld leer ist, weil das Listenfeld leer ist n==sum(eval(l)). In diesem Fall wird gedruckt lund mit einem Fehler beendet, indem ~das Nonezurückgegebene Feld gedruckt wird (danke an Sp3000 dafür.).

Ich glaube, dass in Python 3.5 zwei Zeichen durch Schreiben gespeichert werden können s={*'1234567'}(danke Sp3000).

Es gibt einige kleine Ärgernisse, die Zeichen auffressen. Einer ist , dass in dem Fall , dass lwie die Suche 1234567ohne Komma, es als eine einzelne Zahl analysiert wird und Aufruf sumgibt einen Fehler. Dies geschieht mit dem Hack, bei dem man lmit dem Element beginnt 0und es beim Drucken entfernt. Dies kostet 6 Zeichen.

Das Durchlaufen cdes Kommas und der leeren Zeichenfolge ist ärgerlich wortreich for c in(',',''), da Python 3 nicht zulässt, dass dieses Tupel nackt ist. Ich möchte, ?dass es ein ',?'Zeichen gibt, das in Zahlen ignoriert wird, um 4 Zeichen weniger zu tun , aber es scheint kein solches Zeichen zu geben.

Alte Methode:

Python 2, 117

def f(n,s={1,2,3,4,5,6,7},l=[],p=0):
 if{n,p}|s=={0}:print l;1/0
 if p:f(n-p,s,l+[p])
 for x in s:f(n,s-{x},l,p*10+x)

Definiert eine Funktion, die eine Nummer annimmt und eine Liste druckt.

Die Idee ist, mit der Rekursion jeden Zweig auszuprobieren. Die Variablen verfolgen sind

• Die verbleibende Summe nbenötigt
• Der Satz der snoch zu verwendenden Ziffern
• Die Liste lder bisher gemachten Nummern
• Die aktuell teilweise gebildete Nummer p

Wenn n==0und sleer ist, drucken Sie lund beenden Sie durch Fehler.

Wenn die aktuelle teilweise gebildete Zahl pnicht Null ist, versuchen Sie, sie zur Liste hinzuzufügen und von der verbleibenden Summe zu entfernen.

Versuchen Sie für jede Ziffer, die xwir von verwenden können s, sie anzuhängen pund zu entfernen s.

Pyth, 23

#iRThfqQsiR10Ts./M.pS7q

Naive Brute Force, online zu langsam, dauert auf meinem Computer ungefähr eine Minute. Verwendet das übliche Muster "Schleife für immer bis zur Ausnahme" von Pyth-Golf, bei dem der Zugriff auf die resultierende gefilterte Liste von Kombinationen einen Fehler für unmögliche Zahlen verursacht, wie z 29.

Ausgänge wie eine Python-Liste, z

1891
[1234, 657]
100
[1, 2, 34, 56, 7]
370
[12, 345, 6, 7]

Hier ist eine Paste aller 10136-Nummern, die auf diese Weise erstellt werden können.

Python 2.7, 178 172 169 Bytes

n=input()
for i in range(8**7):
 for j in len(set('%o0'%i))/8*range(128):
    s=''
    for c in'%o'%i:s+='+'[:j%2*len(s)]+c;j/=2
    if eval(s)==n:print map(int,s.split('+'));1/0

Beachten Sie, dass die letzten drei Zeilen mit Tabulatoren eingerückt werden sollen, aber ich kann in diesem Editor nicht herausfinden, wie das geht.

Bearbeiten: Eine Ebene der Verschachtelung mit Hilfe von Sp3000 abgeflacht

JavaScript (ES6), 165 196

Edit etwas gekürzt. Könnte kürzer sein eval, aber ich mag es, schnell zu sein

Brute Force, schändlicherweise länger als die Pith-Version, aber schneller. Testen Sie das folgende Snippet in einem EcmaScript 6-kompatiblen Browser.

f=z=>{for(r=i=1e6;r&&++i<8e6;)for(m=/(.).*\1|[089]/.test(w=i+'')?0:64;r&&m--;t.split`+`.map(v=>r-=v,r=z))for(t=w[j=0],l=1;d=w[++j];l+=l)t+=l&m?'+'+d:d;return r?'':t}

function test() { O.innerHTML=f(+I.value) }

test()

// Less golfed

f=z=>{
  for(r=i=1e6; r&&++i<8e6;)
    for(m=/(.).*\1|[089]/.test(w=i+'')?0:64; r&&m--; t.split`+`.map(v=>r-=v,r=z))
      for(t=w[j=0],l=1;d=w[++j];l+=l)
        t+=l&m?'+'+d:d;
  return r?'':t
}

<input id=I value=28><button onclick=test()>-></button><span id=O></span>

Python 2, 270 268 Bytes

from itertools import*;P=permutations
x,d,f=range(1,8),[],input()
r=sum([[int(''.join(str(n)for n in i))for i in list(P(x,j))]for j in x],[])
z=1
while z:
 t=sum([[list(j)for j in P(r,z)]for i in x],[])
 v=filter(lambda i:sum(i)==f,t)
 if v:print v[0];break
 else:z+=1

Ich arbeite immer noch am Golfen.

Dies wiederholt sich, bis eine Übereinstimmung gefunden wird.

Haskell (145 Bytes)

main=getLine>>=print.head.f[1..7].read
f[]0=[[]]
f b s=[n:j|(n,g)<-m b,j<-f g$s-n]
m b=[(d+10*z,g)|d<-b,(z,g)<-(0,filter(/=d)b):m(filter(/=d)b)]

Verwendet die Rekursion.

Ungolfed (337 Bytes):

delete d = filter (/= d)
main = getLine >>= print . (`form` [1..7]) . read

form s [] | s == 0    = [[]]
form s ds | s <= 0    = []
form s ds | otherwise = [n:ns | (n, ds') <- makeNumbers ds, ns <- form (s-n) ds']

makeNumbers [] = []
makeNumbers ds  = [(d + 10 * n',ds') | d <- ds, (n',ds') <- (0,delete d ds):makeNumbers (delete d ds)]

Scala, 195 Bytes

Dies ist nicht die effizienteste und es dauerte über 15 Minuten, um die Ausgabe für 29 zu erhalten, aber es funktioniert

def g(s: Seq[Int]): Iterator[Seq[Int]]=s.combinations(2).map(c=>g(c.mkString.toInt +: s.filterNot(c.contains))).flatten ++ Seq(s)
def f(i: Int)=(1 to 7).permutations.map(g).flatten.find(_.sum==i)

Hier ist eine Ausgabe

scala> f(100)
res2: Option[Seq[Int]] = Some(Vector(46, 35, 12, 7))

scala> f(1891)
res3: Option[Seq[Int]] = Some(Vector(567, 1324))

scala> f(370)
res4: Option[Seq[Int]] = Some(Vector(345, 12, 6, 7))

scala> f(29)
res5: Option[Seq[Int]] = None

Ruby, 105 Bytes

Rohe Gewalt! Überprüft jede Teilmenge der Längen zwischen 0 und 7 der Ganzzahlen zwischen 1 und 7654321 und stellt fest, ob eine davon unseren Kriterien entspricht. Sie möchten wahrscheinlich nicht warten, bis dies beendet ist.

->n{8.times{|i|[*1..7654321].permutation(i){|x|return x if
x.join.chars.sort==[*?1..?7]&&eval(x*?+)==n}}}

Um den Algorithmus auszuführen und zu verifizieren, können Sie den Suchbereich einschränken, indem Sie 7654321die größte Zahl eingeben, von der Sie wissen, dass sie in der Antwort enthalten ist. Zum Beispiel 56 für n = 100 oder 1234 für n = 1891. Hier ist ein Probelauf des letzteren:

$ ruby -e "p ->n{8.times{|i|[*1..1234].permutation(i){|x|return x if x.join.chars.sort==[*?1..?7]&&eval(x*?+)==n}}}[gets.to_i]" <<< 1891
[657, 1234]