Biorąc pod uwagę niepustą listę dodatnich liczb całkowitych , Twoim zadaniem jest określenie liczby unikalnych wartości± x ± y ± z ± …
Na przykład rozważ listę . Istnieje osiem możliwych sposobów tworzenia sum:
Istnieje sześć unikalnych sum , więc odpowiedź to 6 .
Przypadki testowe
[1, 2] => 4
[1, 2, 2] => 6
[s]*n => n+1
[1, 2, 27] => 8
[1, 2, 3, 4, 5, 6, 7] => 29
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] => 45
[1, 7, 2, 8, 3, 1, 6, 8, 10, 9] => 56
[93, 28, 92, 100, 43, 66, 2, 98, 2, 52, 57, 75, 39, 77, 45, 15, 13, 82, 81, 20, 68, 14, 5, 3, 72, 56, 57, 1, 23, 25, 76, 59, 60, 71, 71, 24, 1, 3, 72, 84, 72, 28, 83, 62, 66, 45, 21, 28, 49, 57, 70, 3, 44, 47, 1, 54, 53, 56, 36, 20, 99, 9, 89, 74, 1, 14, 68, 47, 99, 61, 46, 26, 69, 21, 20, 82, 23, 39, 50, 58, 24, 22, 48, 32, 30, 11, 11, 48, 90, 44, 47, 90, 61, 86, 72, 20, 56, 6, 55, 59] => 4728
Rozwiązanie referencyjne (optymalizuje szybkość, a nie rozmiar).
Jeśli nie możesz poradzić sobie z ostatnim przypadkiem, ponieważ używasz metody brutalnej siły lub podobnej, nie ma sprawy.
Punktacja
To jest golf golfowy , więc wygrywa najkrótsze prawidłowe rozwiązanie (mierzone w bajtach).
code-golf
math
combinatorics
Esolanging Fruit
źródło
źródło
[2,2,2,2,...]
) Odpowiedzią powinna być długość tablicy + 1. Jest tak, ponieważ w tym przypadku pozycja znaków jest nieistotna i tylko liczba każdej sprawyOdpowiedzi:
Wolfram Language (Mathematica) , 27 bajtów
Wypróbuj online!
Znalezienie liczby unikalnych sum wymiany znaków jest równoważne znalezieniu liczby unikalnych sum podzbioru.
Dowód wymagałby dodania sumy danych wejściowych do każdej sumy zamiany znaków i podzielenia przez dwa. Potem jest oczywisty bijection.
Wyjaśnienie
Iteruj przez dane wejściowe, przy czym początkowa wartość to
{0}
: weź związek między<current value>
i<current value> + input element
(mapy na listy).Golfowa wersja
Length
funkcji.źródło
Galaretka , 6 bajtów
Wypróbuj online!
tło
Niech L będzie listą wejściową, a {P, N} podział na algebraiczne zbiory ze znakami dodatnimi i ujemnymi. Specyfikacja wyzwania wymaga obliczenia s {P, N} = suma (P) - suma (N) .
Ponieważ jednak suma (P) + suma (N) = suma (L) i suma (L) nie zależy od podziału, mamy s {P, N} = suma (P) - suma (N) = suma ( P) - (suma (L) - suma (P)) = 2 suma (P) - suma (L) .
Zatem każda unikalna wartość sumy (P) odpowiada jednej unikalnej wartości s {P, N} .
Jak to działa
źródło
MATL ,
1110 bajtówWypróbuj online! To jest port odpowiedzi Luisa Mendo na Octave / MATLAB . Wciąż próbuję nauczyć się MATL i pomyślałem, że opublikuję go wraz z wyjaśnieniem, ponieważ MATL jest językiem miesiąca.
Wyjaśnienie:
Oto lektura dla każdego, kto nie jest zaznajomiony z programowaniem stosowym w ogóle, a zwłaszcza z MATL-em.
Wektor wejściowy jest domyślnie umieszczony na stosie. Zauważ, że kiedy operacja jest wykonywana na elemencie na stosie, wówczas ten element jest usuwany ze stosu.
A następnie domyślnie wyprowadza ostatni element na stosie.
źródło
Python 2 , 55 bajtów
Wypróbuj online!
źródło
Python 2 , 52 bajty
Wypróbuj online!
Wykorzystuje binarną reprezentację liczby do przechowywania osiągalnych sum podzbiorów.
źródło
k<<n
dodaje n do każdej sumy. Zamawianie zek
sklepami tych nowych kwot przyk
jednoczesnym zachowaniu wszystkich poprzednich, a zduplikowani Simowie nie są rejestrowani05AB1E , 4 bajty
Wykorzystuje to samo podejście, które zastosowano w odpowiedzi Jelly'ego na żelki .
Wypróbuj online!
źródło
Haskell, 46 bajtów
Wypróbuj online!
Zamiast sumowania podzbiorów listy danych wejściowych, wykonujemy wszystkie kombinacje zachowania liczby lub zastąpienia jej
0
npTo dwa bajty krótsze niż
subsequences
.źródło
f x=sum[1|i<-[0..sum x],elem i$sum<$>mapM(:[0])x]
będzie krótsze niż import, ale najwyraźniej tak nie jest.import Data.List;length.foldr((<*>)union.map.(+))[0]
R,
8375 bajtów-8 bajtów dzięki JayCe i Giuseppe
Tworzy macierz wszystkich możliwych kombinacji (1, -1) dla rozmiaru wektora wejściowego, mnoży to przez oryginalny wektor, aby uzyskać sumy. Następnie unikatowy i znajdź długość wyniku.
function(v)nrow(unique(t(t(expand.grid(rep(list(c(1,-1)),sum(v|1)))))%*%v))
Poprzednia wersja:
f=function(v)nrow(unique(as.matrix(expand.grid(rep(list(c(1,-1)),length(v))))%*%v))
Niegolfowany z komentarzami:
źródło
t
: TIOsum(v|1)
jest bajt krótszy niżlength(v)
Octave / MATLAB,
454140 bajtówDane wejściowe to wektor kolumny (używany
;
jako separator).Błędy kodu dla ostatniego przypadku testowego z powodu ograniczeń pamięci.
Wykorzystuje pomysł z odpowiedzi JungHwan Min (podzbiory zamiast znaków naprzemiennych), aby zaoszczędzić kilka bajtów.
Wypróbuj online!
źródło
Pari / GP , 39 bajtów
Wypróbuj online!
źródło
Python 3 , 61 bajtów
Wypróbuj online!
Podejście rekurencyjne, śledzenie unikalnych sum podzbiorów.
Prawdziwa zabawa polega na tym, że bije
itertools
to z dużym marginesem:76 bajtów
Wypróbuj online!
źródło
Pyth , 5 bajtów
Wykorzystuje to samo podejście, które zastosowano w odpowiedzi Jelly'ego na żelki .
Wypróbuj tutaj.
źródło
Attache , 29 bajtów
Wypróbuj online!
Działa to poprzez złożenie
±
operatora nad listą wejściową, następnie pobranie±
tej listy, a następnie zliczenie unikalnych atomów tablicy.Oto kilka przykładów działania składania:
Następnie generujemy wszystkie permutacje znaku końcowego, stosując ponownie PlusMinus.
Bardziej wydajna wersja, 31 bajtów
Wypróbuj online! To nie kończy się na końcowym przypadku testowym, ponieważ nie generuje niepotrzebnych kombinacji.
źródło
R , 62 bajty
Wypróbuj online!
Algorytm Porty Dennisa. Jest najbliżej odpowiedzi Octave / MATL, ponieważ używa podobnego produktu bitmapowego i macierzowego do włączania / wyłączania terminów.
źródło
APL (Dyalog Classic) ,
1211 bajtów-1 dzięki H.PWiz
Wypróbuj online!
źródło
-⍨
może być⊢
Perl 5
-p
, 39 bajtówWypróbuj online!
źródło
JavaScript (ES6), 63 bajty
Wypróbuj online!
źródło
Łuska , 5 bajtów
Wypróbuj online!
Portowa odpowiedź Dennisa na galaretkę.
Wyjaśnienie
źródło
Perl 6 , 33 bajtów
Wypróbuj online!
źródło
Narzędzia Bash + GNU, 49 bajtów
Wypróbuj online!
Dane wejściowe podane jako lista oddzielona przecinkami w wierszu polecenia.
Wyjaśnienie
źródło
język maszynowy x86_64 dla systemu Linux,
3129 bajtówWypróbuj online!
Zainspirowany odpowiedzią @ xnor. Wymaga maszyny z
POPCNT
instrukcją.źródło
C (gcc) ,
7469 bajtówWypróbuj online!
Port C odpowiedzi @ xnor
źródło
APL (Dyalog Classic) ,
343332 bajtyWypróbuj online!
Dzięki @ngn za -1 bajt!
źródło
1-⍨≢⍵
->≢1↓⍵
+.×⍨
->+.×
Czysty , 82 bajty
Wypróbuj online!
Definiuje funkcję
? :: [Int] -> Int
używającf :: [Int] -> ([Int] -> Int)
jako pomocnik w celu zmniejszenia nad każdą możliwą sumę po dodawanie lub odejmowanie.źródło
APL (Dyalog Classic) , 21 bajtów
Wypróbuj online!
Wyjaśnienie
Ciąg funkcji równoważny
{((⍴⍵)⍴2)⊤⍳(⍴⍵)}
, który generuje macierz, która ma reprezentacje binarne od 0 do długości danych wejściowych jako kolumnMapy
1
s do-1
s i0
s do1
sMnożenie macierzy przez dane wejściowe, co daje tablicę wszystkich możliwych sum
Usuń duplikaty, a następnie policz
źródło
Java 8,
2078344 bajtyPort odpowiedzi @ xnor na Python 2 .
-39 bajtów dzięki @Jakob .
Wypróbuj online .
źródło
Long
:s->Long.bitCount(s.reduce(1l,(a,e)->a|a<<e))
..reduce
(i.bitCount
równie dobrze mogę dodać ..>.>) -39 bajtów tutaj! :)Java 8, 85 bajtów
Inny port Java XNOR „s odpowiedź . Podobnie jak oryginalna odpowiedź, wykorzystuje bitmapę o dowolnej precyzji, dzięki czemu nie ma górnej granicy wielkości sumy podzbioru.
To lambda od sekwencyjnego
java.util.stream.Stream<Integer>
doint
.Wypróbuj online
Zauważ, że sumator (trzeci argument
reduce
) nie jest używany, ponieważ strumień jest sekwencyjny. Wybrana funkcja jest dowolna.źródło
Julia 0.6 ,
5452 bajtyWypróbuj online!
( -2 bajtów zastępując
¬
przy~
dzięki Jo Króla )Działa dla wszystkich przypadków testowych. Wykorzystuje transmisję do zebrania wszystkich możliwych kwot, a następnie je zlicza.
Wyjaśnienie:
Starsze rozwiązanie:
Julia 0.6 , 64 bajty
Wypróbuj online!
Działa dla tablic wejściowych o długości do 63 (więc nie działa dla ostatniego przypadku testowego, co jest zgodne z OP).
Wyjaśnienie:
źródło
JavaScript (węzeł Babel) , 64 bajty
Wypróbuj online!
To nie zadziała w przypadku ostatniego testu.
Bardziej skuteczne rozwiązanie (działa na ostatniej walizce testowej):
JavaScript (węzeł Babel) , 71 bajtów
Wypróbuj online!
To nie zadziała w prawdziwej przeglądarce z powodu
Array#smoosh
.Dzięki Bubblerowi
[x+f,x-f]
->[x+f,x]
oszczędza 2 bajty.źródło
[x+f,x]
zamiast[x+f,x-f]
( dowód JungHwan Min ).F=([f,...r],s=[0])=>f?F(r,[...s,...s.map(x=>x+f)]):new Set(s).size
[...s,...s.map(x=>x+f)]
,s.concat(s.map(x=>x+f))
i,s,s.map(x=>s.push(x+f))
dzielą tę samą długość ...Czerwony , 73 bajty
Odpowiedź Portu Dennisa na Python 2. Nie obsługuje ostatniego przypadku testowego.
Wypróbuj online!
źródło