Wyzwanie

Biorąc dodatnią liczbę całkowitą N, która jest 28 lub powyżej, wyjście lista numerów podsumowujących na Nktóry wykorzystuje każdą cyfrę 1przez 7dokładnie jeden raz. Możesz podać jako program lub funkcję.

Cyfry mogą pojawiać się same lub być połączone, o ile użyjesz każdego z nich bez powtórzeń. Na przykład [12, 34, 56, 7]jest poprawny, jak jest [1, 27, 6, 4, 35]i [1234, 567], ale nie [123, 34567]lub [3, 2, 1476]. Kolejność wyświetlania liczb nie ma znaczenia.

Jeśli Nnie można tego zrobić za pomocą 1-7, zwróć lub wyślij nic.

Inne informacje

• To jest kod golfowy, więc wygrywa najkrótszy kod w bajtach do czwartku 15 października.

• Zadawaj pytania w komentarzach.

• Wszystko, czego nie wymienię w wyzwaniu, zależy od ciebie.

• Standardowe luki są niedozwolone.

Przykłady

Mogą one usunąć wszelkie nieporozumienia:

Wkład

28

Wydajność

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

Wkład

100

Wydajność

[56, 7, 4, 31, 2]

Wkład

1234567

Wydajność

[1234567]

Wkład

29

Wydajność

Nic, 29 jest nieważne.

Wkład

1891

Wydajność

[1234, 657]

Wkład

370

Wydajność

[15, 342, 7, 6]

W razie potrzeby zrobię więcej.

Oto tablica wszystkich możliwych liczb utworzonych za pomocą tych siedmiu liczb, dzięki uprzejmości FryAmTheEggman.

Pyth, 18 14 bajtów

hfqSjkTjkS7./Q

Dzięki @isaacg za grę w golfa na 2 bajtach i torowanie drogi dla 2 kolejnych.

Kod ulegnie awarii, jeśli nie wygeneruje żadnego wyniku, co nie spowoduje wygenerowania żadnego wyniku.

Będzie to działać dla małych wejść, jeśli jesteś wystarczająco cierpliwy, a dla większych, jeśli masz wystarczająco dużo czasu i pamięci.

Aby sprawdzić, czy kod działa zgodnie z przeznaczeniem, można zastąpić 7z 3do sumy cyfr od 1 do 3 . Kliknij tutaj, aby uzyskać zestaw testowy.

Przykład działa

$ 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

Jak to działa

           ./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:])

Funkcja, która pobiera liczbę i generuje krotkę w podobny sposób 123,4567,. Tak, to jest prawidłowa krotka.

Chodzi o to, aby wygenerować wszystkie możliwe ciągi jak 43,126,7,5,które mają cyfry 1poprzez 7oddzielone przecinkami, bez dwóch kolejnych przecinkami. Oceń to wyrażenie jako krotkę, a jego suma będzie równa n, wydrukuj je i zakończ z błędem.

Aby zbudować wszystkie takie ciągi, śledzimy zestaw sznaków, które mają być użyte, i próbujemy dodać każdy z nich przecinkiem, co powoduje, że cyfra kończy wpis, lub bez, w którym to przypadku przyszłe cyfry zostaną połączone.

Zwarcie służy do sprawdzenia, czy sjest pusta, ponieważ lista-comp jest pusta, i że n==sum(eval(l))w takim przypadku możemy wydrukować li zakończyć się błędem biorąc ~z Nonezwrócony przez drukowanie (dzięki SP3000 do tego.).

Wierzę, że w Pythonie 3.5 dwa znaki można zapisać, pisząc s={*'1234567'}(dzięki Sp3000).

Jest kilka drobnych niedogodności, które pochłaniają znaki. Jednym z nich jest to, że w przypadku lwyglądu 1234567bez przecinków jest on analizowany jako pojedynczy numer, a wywołanie sumpowoduje błąd. Jest to obsługiwane przez hack rozpoczynania lod elementu 0i usuwania go podczas drukowania. To kosztuje 6 znaków.

Iterowanie cpo przecinku i pustym łańcuchu jest denerwująco trudne for c in(',',''), ponieważ Python 3 nie pozwala na to, aby ta krotka była naga. Chciałbym, aby istniał jakiś znak, ?który jest ignorowany w liczbach, aby zrobić ',?'o 4 znaki mniej, ale wydaje się, że nie ma takiego znaku.

Stara metoda:

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)

Definiuje funkcję, która pobiera liczbę i drukuje listę.

Chodzi o to, aby użyć rekurencji do wypróbowania każdej gałęzi. Ścieżki zmiennych są

• Pozostała npotrzebna kwota
• Zestaw cyfr spozostałych do użycia
• Lista lwykonanych do tej pory liczb
• Obecna częściowo uformowana liczba p

Kiedy n==0i sjest pusty, wydrukuj li zakończ przez pomyłkę.

Jeśli bieżąca częściowo uformowana liczba pjest różna od zera, spróbuj dodać ją do listy i usunąć z pozostałej sumy.

Dla każdej cyfry, z xktórej możemy korzystać s, spróbuj dodać ją pi usunąć s.

Pyth, 23

#iRThfqQsiR10Ts./M.pS7q

Naiwna brutalna siła, zbyt wolna w sieci, zajmuje około minuty na moim komputerze. Używa wspólnego wzorca „pytaj na zawsze aż do wyjątku” golfów pyth, gdzie dostęp do wynikowej filtrowanej listy kombinacji powoduje błąd dla liczb niemożliwych, takich jak 29.

Dane wyjściowe takie jak lista pythonowa, np

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

Oto pasta wszystkich 10136 liczb, które można wykonać w ten sposób.

Python 2.7, 178 172 169 bajtów

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

Zauważ, że ostatnie trzy wiersze powinny być wcięte tabulatorami, ale nie mogę wymyślić, jak to zrobić w tym edytorze.

Edycja: Spłaszczono jedną warstwę zagnieżdżenia za pomocą Sp3000

JavaScript (ES6), 165 196

Edytuj Skrócono trochę. Może być krótszy eval, ale podoba mi się to, że jest szybki

Brutalna siła, wstydliwie dłuższa niż wersja Pith, ale szybsza. Przetestuj poniższy fragment kodu w przeglądarce zgodnej z EcmaScript 6.

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 bajtów

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

Nadal pracuję nad golfem.

Zapętla się, dopóki nie zostanie znalezione dopasowanie.

Haskell (145 bajtów)

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

Wykorzystuje rekurencję.

Niegolfowane (337 bajtów):

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 bajtów

To nie jest najbardziej wydajne i zajęło ponad 15 minut, aby uzyskać wynik dla 29, ale działa

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)

Oto niektóre dane wyjściowe

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

Rubinowy, 105 bajtów

Brutalna siła! Sprawdza każdy podzbiór długości od 0 do 7 liczb całkowitych od 1 do 7654321 i sprawdza, czy którykolwiek z nich spełnia nasze kryteria. Prawdopodobnie nie chcesz czekać, aż to się skończy.

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

Aby uruchomić i zweryfikować algorytm, możesz zawęzić obszar wyszukiwania, zastępując 7654321największą liczbą, o której wiesz, że będzie w odpowiedzi. Na przykład 56 dla n = 100 lub 1234 dla n = 1891. Oto okres próbny tego drugiego:

$ 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]