Jest to „odpowiednik” innej łamigłówki, Osiem monet dla uczciwego króla na Puzzling.SE.

Możesz przeczytać powyższą układankę jako tło. Szczegóły dotyczące tej układanki są następujące.

Tworzony jest zestaw 8 rodzajów monet o różnych wartościach, król chce, abyś znalazł maksymalną N, tak aby dowolną liczbę cen od 0 do N można było zapłacić kombinacją nie więcej niż 8 monet i bez opłat.

Na przykład (wzięty z odpowiedzi Glorfindela). Jeśli podano zestaw monet o wartościach 1, 2, 5, 13, 34, 89, 233, 610, twój program powinien wypisać 1596, ponieważ każda liczba od 0 do 1596 (włącznie) może być reprezentowana przez sumę nie więcej niż 8 liczb z podanej listy (liczby mogą się powtarzać), a 1597 nie może być reprezentowane w ten sposób.

W matematyczny sposób, jeśli wejście jest zestawem S składającym się z 8 dodatnich liczb całkowitych, pożądane wyjście N spełnia to, że dla dowolnej liczby n między 0 a N istnieje x1, x2, x3, ..., x8, tak że

Twoim celem jest napisanie programu, funkcji lub fragmentu, który pobiera 8 liczb jako dane wejściowe i wyprowadza maksymalną N, jak opisano powyżej.

Zasady:

• Dozwolone elastyczne we / wy, dzięki czemu Twój program może przyjmować dane wejściowe w dowolnej formie, która jest najbardziej odpowiednia. Możesz założyć, że liczby wejściowe są posortowane w sposób, który najlepiej odpowiada Twojemu programowi.
  • Proszę podać to w swojej odpowiedzi, jeśli twój program zależy od kolejności wprowadzania danych
• Dane wejściowe to zestaw 8 różnych dodatnich liczb całkowitych (bez zer). Dane wyjściowe to jedna nieujemna liczba całkowita.
  • Jeśli w zestawie wejściowym nie ma 1, twój program powinien wypisać 0, ponieważ dowolna liczba od 0 do 0 spełnia wymagania.
  • W przypadku nieprawidłowego wprowadzenia (zestaw zawiera liczby zerowe, ujemne lub zduplikowane), twój program może zrobić wszystko.
• Standardowe luki są zabronione.
• Twój program powinien uruchomić się w ciągu kilku minut na nowoczesnym komputerze.

Przypadki testowe (przejęte głównie z odpowiedzi pod połączonym pytaniem dotyczącym zagadek):

[1, 2, 3, 4, 5, 6, 7, 8] => 64
[2, 3, 4, 5, 6, 7, 8, 9] => 0
[1, 3, 4, 5, 6, 7, 8, 9] => 72
[1, 2, 5, 13, 34, 89, 233, 610] => 1596
[1, 5, 16, 51, 130, 332, 471, 1082] => 2721
[1, 6, 20, 75, 175, 474, 756, 785] => 3356

To jest golf golfowy , więc wygrywa najkrótszy program lub fragment w każdym języku!

Python 3 , 113 62 bajty

for i in[1]*3:x|={a+b for a in x for b in x}
while{i+1}&x:i+=1

Oto xdane wejściowe jako zestaw liczb całkowitych i idane wyjściowe.

Wypróbuj online!

(Dzięki: Erik the Outgolfer, Mr. Xcoder, Lynn)

Galaretka , 12 bajtów

œċⱮ8Ẏ§ṢQJƑƤS

Wypróbuj online!

Uruchomienie wszystkich testów na TIO na moim telefonie zajmuje średnio ~ 3,7 sekundy, więc zaskakująco szybko działa.

Wyjaśnienie

œċⱮ8Ẏ§ṢQJƑƤS     Monadic link / Full program.
  Ɱ8             Promote 8 to [1 ... 8] and for each value k:
œċ                    Generate all combinations of k elements from the list.
    Ẏ§           Tighten, then sum. Flatten to a 2D list then sum each.
      ṢQ         Sort the result and remove equal entries.
        JƑƤ      For each prefix of this list, return 1 if it is equal to its length range, 0 otherwise.
           S     Finally, sum the result (counts the 1's which is equivalent to what is being asked).

Haskell, 56 50 bajtów

g c=[x|x<-[1..],all((/=x).sum)$mapM(0:)$c<$c]!!0-1

Wypróbuj online!

Podejście brutalnej siły. Dodaj 0do listy monet i wypróbuj wszystkie kombinacje 8 typów. Znajdź pierwszą liczbę, nktóra nie jest równa sumie żadnego z typów i wróć n-1.

Zajmuje około 5 minut [1, 2, 5, 13, 34, 89, 233, 610]na mój 7-letni laptop.

Edycja: -6 bajtów dzięki @ Ørjan Johansen

Jeszcze krótsza wersja (-2 bajty, znowu dzięki @ Ørjan Johansen) to

Haskell, 48 bajtów

g c=[x|x<-[1..],all((/=x).sum)$mapM(:0:c)c]!!0-1

ale zużywa znacznie więcej pamięci i przechodzi w intensywne stronicowanie na moim komputerze i nie kończy się „w ciągu kilku minut”.

Galaretka , 9 bajtów

Żœċ8§ḟ’$Ṃ

Wypróbuj online!

Jak to działa

Żœċ8§ḟ’$Ṃ  Main link. Argument: A (array)

Ż          Prepend a 0 to A.
 œċ8       Take all combinations of length 8, with repetitions.
    §      Take the sum of each combination.
       $   Combine the two links to the left into a monadic chain.
      ’      Decrement all sums.
     ḟ       Filterfalse; keep only sums that do not appear in the decremented sums.
        Ṃ  Take the minimum.

Wolfram Language (Mathematica) , 53 bajty

LengthWhile[CoefficientList[(1+Tr[x^#])^8,x],#>0&]-1&

Wypróbuj online!

JavaScript (ES6),  100 88 80  76 bajtów

Zasadniczo jest to poszukiwanie siły brutalnej, ale wzbogacone o przycinanie w celu przyspieszenia. Średni czas wykonania dla przypadków testowych w TIO jest zbliżony do 1 sekundy.

Zakłada, że ​​tablica wejściowa jest sortowana od najwyższej do najniższej.

a=>[...Array(a[0]*9)].findIndex(g=(i=8,s)=>s*i>0?a.every(x=>g(i-1,s-x)):s)-1

Wypróbuj online!

Skomentował

a =>                      // a[] = input array
  [...Array(a[0] * 9)]    // create an array of 9 * max(a) entries
  .findIndex(             // find the position of the first truthy result
    g = (i = 8, s) =>     // g = recursive function taking a counter i, initialized to 8
                          //     and a sum s, initialized to the position in the above array
      s * i > 0 ?         //   if s is positive and i is not equal to 0:
        a.every(x =>      //     for each value x in a[]:
          g(i - 1, s - x) //       do a recursive call with i - 1 and s - x
        )                 //     end of every()
      :                   //   else:
        s                 //     yield s (s = 0 means success and makes findIndex go on)
  ) - 1                   // end of findIndex(); decrement the result

Python 2 , 145 bajtów

from itertools import*
x=set(map(sum,reduce(chain,map(combinations_with_replacement,[input()]*9,range(9)))))
print~-min(set(range(1,max(x)+2))-x)

Wypróbuj online!

Pari / GP , 57 bajtów

a->n=-1;while(polcoeff((1+sum(i=1,8,x^a[i]))^8,n++),);n-1

Wypróbuj online!

Python 2 , 125 115 111 bajtów

lambda c:sum(i==j for i,j in enumerate(sorted(set(map(sum,product([0]+c,repeat=8))))))-1
from itertools import*

Wypróbuj online!

Oczekuje listy liczb całkowitych jako danych wejściowych.

Wyjaśnienie:

# an anonymous function
lambda c:
                                                          # get all length-8 combinations of values, from (0,0,0,0,0,0,0,0) to (8,8,8,8,8,8,8,8)
                                                          # zero is added to ensure that combinations of fewer than 8 coins are represented Ex:(1,0,0,0,0,0,0,0)
                                                          product([0]+c,repeat=8)
                                                  # for each combination, sum the values
                                                  map(sum,.......................)
                                       # get unique values, then sort them smallest to largest
                                       sorted(set(................................))
             # for each index, value pair, return if the index is equal to the value
             i==j for i,j in enumerate(.............................................)
         # in Python arithmetic, False is 0 and True is 1. So, count how many items match their index.
         # Since zero was added to the list, there will always be one extra match (0==0). So offset by one.
         sum(........................................................................)-1
from itertools import*

Perl6, 65 63 41 bajtów ( 39 37 znaków)

{@_=(0,|@_)X+(0,|@_)for ^3;($_ if $_==$++for @_.sort.unique)-1}

Wypróbuj online!

Jest to anonimowy blok, który przekazuje swoje dane jako tablicę. (0,|@_)To szybki sposób dodać 0do @_, a mimo to zrobić dwa razy, to wciąż nieco krótsza niż @_.push: 0;które następnie trzeba po spacji _. To podejście oparte na brutalnej sile, które nieco podważa fakt, że to 8 kombinacji. Po dodaniu krzyżowym tworzona jest anonimowa lista wartości sekwencyjnych. W przypadku operatorów matematycznych listy oceniają ich długość, więc -1 pociąga za sobą podwójne obciążenie: uwzględnia 0 i wymusza na Int.

To może zająć jego słodki czas, ale przez zmianę jednego lub obu (0,|@_)do (0,|@_.unique)przed pierwszym formoże być znacznie przyspieszone. Dodaje to +7 (czas działania <60s) lub +14 (czas działania <10s) do wyniku, jeśli uważasz, że pierwszy jest zbyt wolny (zrobiłem to dla kodu połączonego, aby uniknąć przekroczenia limitu czasu po 60 sekundach).

Edycja: JoKing w komentarzach poprawił to (ten sam pomysł, dodaj krzyż, a następnie zwróć ostatni kolejny wynik) do zadziwiającego 39 znaków (41 bajtów):

{(@_=@_ X+0,|@_)xx 3;first *+1∉@_,^∞}

Wypróbuj online!

Końcowe zestawienie nie potrzebuje 0, co pozwala zaoszczędzić kilka bajtów, wystarczy dodać 0 tylko raz. Te xx 3mimetyki pętli for (jeszcze sery na monety będącego potęgą liczby 2). Znak firstpodrzędny zwraca pierwszą liczbę na nieskończonej liście 0..*( ^Infjest to również możliwe, ale nie oszczędza miejsca), który +1nie jest członkiem listy dodanej krzyżowo. Podobnie jak mój, jest wolny, więc dodaj +7 za uniquepierwszy równy, jeśli uważasz, że jest zbyt wolny dla wskazówek.

JavaScript (Node.js) , 171 145 115 bajtów

f=(s,n=3)=>n?f(s=new Set(a=[0,...s]),n-1,a.map(m=>a.map(n=>s.add(m+n)))):Math.min(...[...s].filter(m=>!s.has(m+1)))

Wypróbuj online! Port odpowiedzi @ Mark's Python 3. 108 bajtów w przeglądarce Firefox 30-57:

f=(s,n=3)=>n?f(new Set((for(n of s=[0,...s])for(m of s)n+m)),n-1):Math.min(...[...s].filter(m=>!s.has(m+1)))

Wolfram Language (Mathematica) , 46 bajtów

0//.x_/;Min[Tr/@FrobeniusSolve[#,x+1]]<9:>x+1&

Wypróbuj online!

Podejście brutalnej siły: sprawdza liczby całkowite licząc w górę, aż osiągnie wartość, której nie można zapłacić za 8 monet. Bardzo, bardzo wolno (limit czasu tio), ale jestem całkiem pewien, że warunek jest poprawny.

Czysty , 161 bajtów

import StdEnv,Data.List
$l=:[1:_]#k=sort(nub(map sum(iter 8(concatMap(\[h:t]=[[e,h:t]\\e<-[0:l]|e>=h]))[[0]])))
=length(takeWhile((>=)1)(zipWith(-)(tl k)k))
$_=0

Wypróbuj online!