Nuggets of Code

Jest ^{to hipotetyczna sytuacja, w której jest} piątek wieczorem, a zaprosiłeś zwykłych kumpli golfowych do udziału w swoim ulubionym hobby: golfie kodowym. Ponieważ jednak jest to tak wyczerpujące zadanie, musisz zebrać trochę pokarmu dla grupy, abyś mógł grać w golfa jak najwięcej z kodu.

Teraz ulubioną przekąską wszystkich są nuggetsy z kurczaka, ale jest problem: nie ma jednej paczki, która zaspokoi potrzeby wszystkich. Ponieważ jesteś już w golfowym nastroju, postanowiłeś stworzyć program, który dokładnie określi, jakie pakiety musisz kupić, aby móc zaspokoić potrzeby każdego z samorodków.

Rozmiary opakowań samorodków z kurczaka są wszędzie, aw zależności od miejsca zamieszkania na świecie zmieniają się również standardowe rozmiary. Jednak najbliższe [miejsce, które obsługuje samorodki] zawiera następujące rozmiary pakietów samorodków:

4, 6, 9, 10, 20, 40

Teraz możesz zauważyć, że nie możesz zamówić pewnych kombinacji bryłek. Na przykład 11samorodki nie są możliwe, ponieważ nie ma 11dokładnie takiej kombinacji . Możesz jednak zrobić 43, zdobywając 1 paczkę 20, 1 paczkę 10, 1 paczkę 9i 1 paczkę 4,

20 + 10 + 9 + 4 = 43 (597)

gdzie 597każdy termin jest podniesiony do kwadratu i zsumowany (wskazówka: optymalne rozwiązanie ma to jako najwyższą wartość) . Istnieją oczywiście inne sposoby tworzenia 43, ale jak wiadomo, im więcej samorodków na opakowanie, tym taniej robi na samorodek. Tak więc chcesz idealnie kupić najmniejszą liczbę paczek i jak najwięcej, aby zminimalizować koszty.

Zadanie

Powinieneś stworzyć program lub funkcję, która pobiera listę liczb całkowitych odpowiadających wymaganiom każdej osoby. Następnie należy obliczyć i wydrukować najbardziej opłacalne zamówienie ^α , aby kupić samorodki kurczaka. Najbardziej opłacalnym zamówieniem ^α jest kombinacja, w której suma kwadratów każdej ilości jest najwyższa. Jeśli nie ma absolutnie żadnego sposobu, aby kupić bryłki doskonale, trzeba wydrukować wartość falsy takie jak 0, False, Impossible!, lub, co jest dostępne w języku polskim.

Przykład I / O:

[2 7 12 4 15 3] => [20 10 9 4]
     1, 1, 2, 1 => False
  6 5 5 5 5 5 9 => 40
      [6, 4, 9] => 9 10
              1 => 0
            199 => 40, 40, 40, 40, 20, 10, 9
              2 => Impossible!

Oto lista idealnych rozwiązań dla pierwszych 400. Pamiętaj, że nie są one sformatowane w sposób, w jaki oczekiwałbym twojego, każde tuplema formę (N lots of M).

Zasady

1. Brak standardowych luk.
2. Bez użycia wbudowanych funkcji, które wykonują wszystkie lub większość zadań, takich jak FrobeniusSolveMathematica.

^{α - Aby wyjaśnić to na przykładzie, możesz również zrobić 43, robiąc to 4 + 6 + 6 + 9 + 9 + 9 = 43 (319), ale nie byłoby to optymalne, a zatem niepoprawne wyjście, ponieważ suma kwadratów jest mniejsza niż kombinacja, którą zauważyłem we wstępie. Zasadniczo wyższa suma kwadratów = niższy koszt = najbardziej opłacalny.}

Pyth, 26 25 bajtów

e+Zo.aNf!-TCM"  
("./sQ

Zauważ, że istnieją pewne niedrukowalne znaki. Wypróbuj online: demonstracja . Jest dość wolny (ale nie tak wolny jak moje 26-bajtowe rozwiązanie).

Wyjaśnienie:

                          implicit: Q = input list
                     sQ   sum(Q)
                   ./     generate all integer partitions
       f                  filter for partitions T, which satisfy:
             "   ("          string containing chars with the ASCII-values of 4,6,9,10,20,40
           CM                convert each char to the ASCII-value
         -T                  remove this numbers from T
        !                    and check, if the resulting list is empty
    o                      order the remaining subsets N by:
     .aN                      the vector length of N (sqrt of sum of squares)
  +Z                       insert 0 at the beginning
 e                         print the last element

Pyth, 32 bajty

e+Zo.aNfqsTsQysm*]d/sQdCM"  
(

Zauważ, że istnieją pewne niedrukowalne znaki. Wypróbuj online: Demonstracja Ta wersja jest znacznie szybsza. Znajduje rozwiązanie dla danych wejściowych [6,7,8]w ciągu około jednej sekundy, a rozwiązanie dla danych wejściowych [30]w około 90 sekund.

Wyjaśnienie:

                                 implicit: Q = input list
                          "...(  the string containing chars with the ASCII-values of 4,6,9,10,20,40
                        CM       convert each char to the ASCII-value
                m                map each number d to:
                  ]d                create the list [d]
                 *  /sQd            and repeat it sum(Q)/d times
               s                 unfold
              y                  generate all subsets
        f                        filter for subsets T, which satisfy:
         qsTsQ                      sum(Q) == sum(T)
    o                            order the remaining subsets N by:
     .aN                            the vector length of N (sqrt of sum of squares)
  +Z                             insert 0 at the beginning
 e                               print the last element

Perl, 175 153

sub f{my$n=$_[0];if(!$n){return 1;}foreach$o(40,20,9,10,6,4){if($n>=$o&&f($n-$o)){print"$o ";return 1;}}return 0;}$n+=$_ for@ARGV;if(!f($n)){print":(";}

Pobiera dane wejściowe z argumentów programu. Wyświetla a :(, jeśli nie może znaleźć idealnego rozwiązania.

Nieskluczony kod:

sub f
{
    my $n = $_[0];
    if(!$n)
    {
        return 1;
    }
    foreach $o(40,20,9,10,6,4)
    {
        if($n>=$o&&f($n-$o))
        {
            print "$o ";
            return 1;
        }
    }
    return 0;
}

$n += $_ for @ARGV;
if(!f($n))
{
    print ":(";
}

PS: To chyba pierwszy wpis, który nie zajmuje 10 minut 1 2;)

Sprawdź to tutaj.

CJam, 45 29 28 bajtów

q~:+_[40K9A6Z)U]m*_::+@#=0-p

Zauważ, że to podejście jest bardzo wolne i wymaga dużej ilości pamięci.

Wypróbuj online w interpretatorze CJam .

Można go znacznie przyspieszyć kosztem 5 bajtów:

q~:+_40/4+[40K9A6Z)U]m*_::+@#=0-p

Złożoność jest wciąż wykładnicza w sumie danych wejściowych, ale powinno to obsłużyć przypadki testowe do 159 z interpreterem online i do 199 z interpreter Java w ciągu kilku sekund.

Wypróbuj online w interpretatorze CJam .

Pomysł

Zakup optymalna (maksymalna suma kwadratów) to ważny zakup (poprawna ilość bryłek), który ma aż 40 „s, jak to możliwe, to jak wielu 20 ” s, jak to możliwe, a następnie aż 9 „s jak to możliwe (na przykład, 9 9jest preferowane powyżej 10 4 4) i tak dalej przez 10 , 6 i 4 .

W tym podejściu generujemy iloczyn kartezjański N kopii N tablicy [40 20 9 10 6 4 0] , gdzie N jest pożądaną liczbą bryłek. N to (zła) górna granica liczby zakupów, które musimy zrobić. W przyspieszonej wersji kodu zamiast tego używamy N / 40 + 4 .

Ze względu na sposób uporządkowania tablicy produkt kartezjański rozpocznie się od wektora [40 ... 40] i zakończy na wektorze [0 ... 0] . Obliczamy indeks pierwszego wektora, który ma poprawną sumę (która będzie miała również optymalną sumę kwadratów), wyszukujemy odpowiedni element tablicy, usuwamy zera, które służyły za symbole zastępcze i wypisujemy wynik.

Jeśli nie można znaleźć wektora, indeks będzie wynosił -1 , więc pobieramy [0 ... 0] , które zamiast tego wypisuje pustą tablicę.

Kod

q~                            e# Read from STDIN and evaluate the input.
  :+                          e# Push N, the sum of all elements of the resulting array.
     [40K9A6Z)U]              e# Push B := [40 20 9 10 6 4 0].
    _           m*            e# Push B**N, the array of all vectors of dimension N
                              e# and coordinates in B.
                  _::+        e# Copy and replace each vector by its sum.
                      @#      e# Get the first index of N.
                        =     e# Retrieve the corresponding element.
                         0-p  e# Remove 0's and print.

Julia, 126 bajtów

r->(t=filter(i->all(j->j∈[4,6,9,10,20,40],i),partitions(sum(r)));show(!isempty(t)&&collect(t)[indmax(map(k->sum(k.^2),t))]))

Tworzy to nienazwaną funkcję, która przyjmuje tablicę jako dane wejściowe i drukuje tablicę lub wartość logiczną do STDOUT, w zależności od tego, czy istnieje rozwiązanie. Aby to nazwać, nadaj mu nazwę, np f=n->....

Niegolfowane + wyjaśnienie:

function f(r)
    # Nugget pack sizes
    packs = [4, 6, 9, 10, 20, 40]

    # Filter the set of arrays which sum to the required number of nuggets
    # to those for which each element is a nugget pack
    t = filter(i -> all(j -> j ∈ packs, i), partitions(sum(r)))

    # Print the boolean false if t is empty, otherwise print the array of
    # necessary nugget packs for which the sum of squares is maximal
    show(!isempty(t) && collect(t)[indmax(map(k -> sum(k.^2), t))])
end

Przykłady:

julia> f([1])
false

julia> f([2,7,12,4,15,3])
[20,10,9,4]

Python 3 - 265 znaków

import itertools as i
n=list(map(int,input().split(',')));m=[]
for f in range(1,9):
 for j in range(6*f):
  for x in i.combinations((4,6,9,10,20,40,)*f,j+1):
   if sum(n)==sum(x):m.append(x)
if m!=[]:v=[sum(l**2for l in q)for q in m];print(m[v.index(max(v))])
else:print(0)

Pokazuje odstępy:

import itertools as i
n=list(map(int,input().split(',')));m=[]
for f in range(1,5):
 for j in range(6*f):
\tfor x in i.combinations((4,6,9,10,20,40,)*f,j+1):
\t if sum(n)==sum(x):m.append(x)
\t\tif m!=[]:v=[sum(l**2for l in q)for q in m];print(m[v.index(max(v))])
else:print(0)

Przechodzi wszystkie przypadki testowe

Uwaga: nie wiem, czy to przejdzie wszystkie przypadki, ponieważ jest tak wolny ... Ale powinien ...

JavaScript, 261 256 261

d="length";function g(a){for(z=y=0;y<a[d];z+=+a[y++]);return z}x=[40,20,10,9,6,4];l=prompt().split(",");o=g(l);p=[];for(i=0;i<x[d];i++)r=g(p),s=r+x[i],(s<o-3||s==o)&&p.push(x[i]),(i==x[d]-1||40<o-r)&&r+x[i]<o-3&&(i=-1,0==i||o-r<p[p[d]-1]&&p.pop());g(p)==o&&p||0

Nie jestem pewien, czy to w porządku, wydaje się, że działa, ale na pewno brakuje mi rzeczy.

Nie wydaje się jednak być powolny, aż do 123456wyjścia[40 x 3086, 10, 6] prawie natychmiastowego .

Wyjaśnienie:

Iteracja po rozmiarach modelu użytkowego (najpierw największy)

• Jeśli suma stosu plus rozmiar samorodka jest mniejsza niż cel - 3 -> wciśnij go na stos
• Jeśli pozostało więcej niż 40 -> zresetuj licznik pętli
• Jeśli suma stosu jest większa niż cel, gdy osiągnięto ostatni rozmiar samorodka -> pop ostatni element, zresetuj licznik pętli
• Jeśli suma stosu sumuje się, zwróć go, w przeciwnym razie zwróć 0

Dla 199 | 1 zbudowany stos wygląda tak

i | stack
0   [40]
0   [40, 40]
0   [40, 40, 40]
0   [40, 40, 40, 40]
0   [40, 40, 40, 40]
1   [40, 40, 40, 40, 20]
2   [40, 40, 40, 40, 20, 10]
3   [40, 40, 40, 40, 20, 10, 9]
4   [40, 40, 40, 40, 20, 10, 9]
5   [40, 40, 40, 40, 20, 10, 9]
==> [40, 40, 40, 40, 20, 10, 9]

Za 1

i | stack
0   []
1   []
2   []
3   []
4   []
5   []
==> 0