Moja tablica powinna być równa, ale tak nie jest!

21

Biorąc pod uwagę tablicę liczb całkowitych, aktóra zawiera n liczb całkowitych i jedną liczbę całkowitą x; usuń jak najmniej elementów z, aaby suma była arówna x. Jeśli żadna kombinacja nie amoże się utworzyć x, zwróć wartość fałszowania.

Jak wskazano w komentarzu, jest to maksymalny zestaw z sumą x , przepraszam za mój mniejszy mózg matematyczny. Zapomniałem wielu warunków od czasu college'u.

Przykłady (Prawda):

f([1,2,3,4,5,6,7,8,9,10], 10) = [1,2,3,4]

f([2,2,2,2,2,2,2,2,2], 10) = [2,2,2,2,2]

f([2,2,2,2,-2,-2,-2,-4,-2], -8) = [2,2,-2,-2,-2,-4,-2]

f([-2,-4,-2], -6) = [-4,-2] OR [-2,-4]

f([2,2,2,4,2,-2,-2,-2,-4,-2], 0) = [2,2,2,4,2,-2,-2,-2,-4,-2] (Bez zmian)

f([], 0) = [] (Sprawa niezmienionej sumy zerowej)

Przykłady (Falsy, dowolna spójna wartość niebędąca tablicą):

Nie można zrobić sprawy: f([-2,4,6,-8], 3) = falsy (E.G. -1)

Przypadek zerowej sumy: f([], non-zero number) = falsy (E.G. -1)

  • Uwaga: jakakolwiek wartość [-1]nie może być poprawna w przypadku fałszowania, ponieważ jest to potencjalna prawda.

Zasady:

  • Dane wejściowe mogą być pobierane w formie tablic lub jako lista argumentów, przy czym ostatnia lub pierwsza istota x.
  • Wyjściem może być dowolna lista liczb całkowitych. EG 1\n2\n3\nlub [1,2,3].
  • Każda wartość może być używana jako wskaźnik fałszowania, inna niż tablica liczb całkowitych.
  • Twój kod musi maksymalizować rozmiar tablicy końcowej, kolejność nie ma znaczenia.
    • EG Dla f([3,2,3],5)obu [2,3]i [3,2]są jednakowo ważne.
    • EG Bo f([1,1,2],2)możesz wrócić tylko [1,1]tak, jak [2]jest krótszy.
  • Zarówno suma, jak ai wartość xbędą mniejsze 2^32-1i większe niż -2^32-1.
  • To jest golf golfowy , wygrana o najniższej liczbie bajtów.
  • Jeśli istnieje wiele subarrays tej samej wielkości, które są ważne, jest to nie do zaakceptowania wyjściu wszystkich z nich. Musisz wybrać jeden i wyprowadzić go.

Daj mi znać, jeśli został opublikowany, nie mogłem go znaleźć.

Znalazłem takie posty : Powiązane, ale zamknięte , ...

code-golf array-manipulation Urna Magicznej Ośmiornicy
źródło
1
Przypuszczam, że „Falsy, jakakolwiek spójna wartość inna niż tablica” obejmuje zgłaszanie błędu?
Jonathan Allan
„ Każda wartość może być używana jako wskaźnik fałszowania, inna niż tablica liczb całkowitych. ” Czy to obejmuje pustą tablicę?
Shaggy
@shaggy [] wskazuje na potencjalną wartość zgodną z prawdą, prawda? Czy dopuszczenie tej meta reguły jest ważniejsze niż wyraźna prawda i fałsz?
Magic Octopus Urn
@JohnathanAllan, jeśli ten błąd nie może zostać podniesiony w scenariuszu Prawdy - przypuszczam. Ale czuję, że celowo próbuje to rozszerzyć specyfikację. Jeśli zmienię sformułowanie ze wskaźnika na wartość zwracaną, czy będzie w porządku?
Magic Octopus Urn
Wierzę, że spójne wartości wyjściowe liczą się jako wartość zwracana na meta?
Magic Octopus Urn

Odpowiedzi:

7

Brachylog , 8 bajtów

h⊇.+~t?∧

Wypróbuj online!

Comiesięczna odpowiedź Brachylog. Zwraca, false.jeśli nie jest to możliwe.

Wyjaśnienie

h⊇.           The output is a subset of the head of the input
  .+~t?       The sum of the elements of the output must equal the tail of the input
       ∧      (Avoid implicit unification between the output and the input)
Fatalizować
źródło
6

Python 2 , 108 104 bajtów

lambda a,n:[x for l in range(len(a)+1)for x in combinations(a,l)if sum(x)==n][-1]
from itertools import*

Wypróbuj online!

-4 bajty, dzięki Jonathan Allan

Python 2 , 108 106 bajtów

def f(a,n):
 q=[a]
 while q:
  x=q.pop(0);q+=[x[:i]+x[i+1:]for i in range(len(x))]
  if sum(x)==n:return x

Wypróbuj online!

-2 bajty, dzięki Janathan Frech

TFeld
źródło
1
Możesz użyć range(-len(a),1)i, -laby uratować 2, ale lambda a,n:[x for l in range(len(a)+1)for x in combinations(a,l)if sum(x)==n][-1]oszczędzasz 4.
Jonathan Allan
@JonathanAllan Thanks :)
TFeld
1
Możliwe 106 bajtów .
Jonathan Frech,
@JonathanFrech Dzięki, wczoraj musiałem być zmęczony;)
TFeld
4

Pyth , 8 bajtów

  • 8-byter ( Spróbuj! ) - Wyprowadza tylko jedno możliwe rozwiązanie. W przypadku nierozwiązywalnych danych wejściowych nie wypisuje niczego do STDOUT, który jest pustym łańcuchem, co technicznie rzecz biorąc mówi falsey w Pyth, ale zapisuje do STDERR. Dziękujemy FryAmTheEggman za zasugerowanie tego (ignorowanie STDERR i skupianie się tylko na wyjściu STDOUT), oszczędzając w ten sposób 1 bajt.

    efqz`sTy

  • 9-byter ( Spróbuj! ) - Wyprowadza tylko jedno możliwe rozwiązanie, zawinięte w listę singletonów, jak domyślnie dozwolone (np ([1...10], 10) -> [[1,2,3,4]]; ([], 0) -> [[]].). Dla wejść nierozwiązywalnych, zwraca [], co jest falsey w Pyth.

    >1fqz`sTy

  • 10-byter ( Try it! ) - Aby uzyskać wyraźniejszy wynik, bez korzystania z reguły singleton-list i używania 0zamiast []wartości fałszowania.

    e+0fqz`sTy

Wyjaśnienie

Najpierw kod oblicza zestaw energetyczny listy danych wejściowych (wszystkie możliwe uporządkowane podkolekcje). Następnie zachowuje tylko te kolekcje, których suma jest równa liczbie wejściowej. Należy zauważyć, że kolekcje są generowane od najkrótszych do najdłuższych, dlatego skupiamy się na ostatniej. Aby to uzyskać:

  • 8-byter prostu wykorzystuje koniec wbudowaną, która generuje błąd, ale STDERR mogą być ignorowane, jak na naszych zasad witryny, wyjście na standardowe wyjście jest pusty ciąg znaków, który jest falsy.
  • 9-byter trwa ostatni element, ale stosując równoważną kodu Pythona lst[-1:]w miejsce lst[-1]aby uniknąć błędów z wyrzucane wejść nierozwiązywalnych.
  • 10 byter poprzedza 0 do listy filtrowanych podrzędnych zbiorów, po czym wykonuje się koniec tego zbioru (ostatni element). Jeśli danych wejściowych nie da się rozwiązać, wówczas zamiast tego naturalnie stosuje się 0 .
Pan Xcoder
źródło
[]jest falsy? Schludny. Dlaczego Pyth to robi []?
Magic Octopus Urn
@MagicOctopusUrn Pyth dziedziczy to po Pythonie : Wypróbuj online .
Pan Xcoder,
@FryAmTheEggman czy pusta lista nie byłaby prawdziwym wynikiem w przypadku testowym f([], 0) = []?
Sok
@FryAmTheEggman Dzięki za sugestię!
Dokonałem
3

Galaretka , 7 bajtów

ŒPS⁼¥ƇṪ

Wypróbuj online!

Wyjaśnienie wyników w zakresie TIO.

Erik the Outgolfer
źródło
3

Perl 6 , 38 37 bajtów

{*.combinations.grep(*.sum==$_).tail}

Wypróbuj online!

Funkcja curry.

nwellnhof
źródło
Zaraz, czy to w ;ogóle konieczne?
Jo King
@JoKing Wcześniejszej iteracji konieczne było uniknięcie błędu „źle sformułowanego podwójnego zamknięcia”. Ale z jakiegoś powodu można to teraz pominąć. (Myślę, że po tym jak otrzymuje $^xsię $_.)
nwellnhof
3

Brachylog , 4 bajty

⟨⊇+⟩

Wypróbuj online!

Prawie równoważne z Fatalize h⊇.+~t?∧, z wyjątkiem znacznie krótszego, dzięki funkcji predykatu składu, która zgodnie z historią edycji referencji była w toku do 8 stycznia, od opublikowania odpowiedzi o ponad dwa miesiące. ⟨⊇+⟩jest kanapką , rozwijającą się do {[I,J]∧I⊇.+J∧}, gdzie nawiasy klamrowe są w tym przypadku nieistotne, ponieważ kanapka i tak jest na swojej linii.

                The input
[I,J]           is a list of two elements I and J.
        .       The output,
         +J     which sums to J
           ∧    (which we don't unify with the output),
      I⊇        is a sublist of I
     ∧          (which we don't unify with [I,J]).

Znacznie mniej dramatyczna transformacja odpowiedzi Fatalize, która wykorzystuje te same predykaty z tymi samymi zmiennymi, ale wychodzi o bajt krótszy z różnej organizacji:

Brachylog , 7 bajtów

h⊇.&t~+

Wypróbuj online!

           The input
h          's first element
 ⊇         is a superlist of
  .        the output,
   &       and the input
    t      's last item
     ~+    is the sum of the elements of
           the output.

(Ponadto, jeśli ktoś chce zobaczyć coś dziwnego, zmień dowolny znak podkreślenia w testach na myślniki).

Niepowiązany ciąg
źródło
1
Kanapki zostały zaimplementowane przez @ ais523 w listopadzie 2018 r., Ale wprowadzono je w Brachylog na początku stycznia 2019 r.
Fatali
1
Oczywiście żadna z tych historii nie ma znaczenia, ponieważ języki, które datowały wyzwanie, były dozwolone od lat.
pppery
2

Czysty , 89 bajtów

import StdEnv,Data.List,Data.Func
$n=find((==)n o sum)o sortBy(on(>)length)o subsequences

Wypróbuj online!

Definiuje funkcję $ :: Int -> [Int] -> (Maybe [Int])zwracającą, Nothingjeśli nie ma odpowiedniej kombinacji elementów, i (Just [elements...])inaczej.

Obrzydliwe
źródło
2

JavaScript (ES6), 108 bajtów

Pobiera dane wejściowe jako (array)(n). Zwraca tablicę lub false.

a=>n=>a.reduce((a,x)=>[...a,...a.map(y=>1/r[(y=[...y]).push(x)]||eval(y.join`+`)-n?y:r=y)],[[]],r=!n&&[])&&r

Wypróbuj online!

Arnauld
źródło
2

Zaczęło się to fajnie i małe, ale przykuły mnie przypadki. Cokolwiek się stanie, jestem dumny z pracy, którą w to włożyłem.

Python 3 , 169 161 154 bajtów

from itertools import*
def f(a,x):
	if sum(a)==x:return a
	try:return[c for i in range(len(a))for c in combinations(a,i)if sum(c)==x][-1]
	except:return 0

Wypróbuj online!

Gigaflop
źródło
Pamiętaj, że jest to [code-golf], więc powinieneś postarać się, aby twój bajt był jak najmniejszy! Masz wiodącą nową linię i kilka innych trywialnych golfów białych , i założę się, że ktoś inny, kto zna Pythona, może pograć w golfa dalej.
Giuseppe
@Giuseppe Dziękujemy za przypomnienie mi o wiodących białych znakach. Spędziłem trochę czasu próbując skonsolidować niektóre części tego, ale w międzyczasie postanowiłem opublikować go na wypadek, gdyby ktoś inny mógł zasugerować zmiany.
Gigaflop,
Żaden problem! Minęło 5 lat, odkąd napisałem jakiś Python, ale nie range(x)generuje (0...x-1)? Więc range(len(a))nie dajesz możliwości pozostawienia tablicy bez zmian?
Giuseppe
@Giuseppe Eureka, to zrobiło. Być może zbytnio skupiałem się na nowym materiale, z którym pracowałem.
Gigaflop,
Zamiast if a==[] and x==0używać if sum(a)==x. Następnie możesz również usunąć +1z range.
Vedant Kandoi
2

R , 100 80 bajtów

function(a,x){i[sum(a|1):0,j[combn(a,i,,F),if(sum(j)==x)return(j)]]
F}
`[`=`for`

Wypróbuj online!

20 bajtów zapisanych dzięki digEmAll

Zwraca FALSEza niemożliwe kryteria.

Giuseppe
źródło
Oraz 80 nadużyć operatora „[” : D
digEmAll
@digEmAll Z pewnością się cieszę, że nie dostałem szansy na edycję w 98 bajtowej odpowiedzi :-)
Giuseppe
eheh zapomniałem go usunąć: D
digEmAll
1

Attache , 28 bajtów

${(y&`=@Sum\Radiations@x)@0}

Wypróbuj online!

Alternatywy

34 bajty :f[x,y]:=({y=Sum@_}\Radiations@x)@0

30 bajtów :First@${y&`=@Sum\Radiations@x}

29 bajtów :{(_&`=@Sum\_2)@0}#/Radiations

29 bajtów :${({y=Sum@_}\Radiations@x)@0}

29 bajtów :`@&0@${y&`=@Sum\Radiations@x}

29 bajtów :{_}@@${y&`=@Sum\Radiations@x}

Wyjaśnienie

${(y&`=@Sum\Radiations@x)@0}
${                         }    function receiving two arguments, x and y
            Radiations@x        calculate the radiations of x
                                (simulates removing all possible subslices of x)
           \                    keep those radiations
        Sum                     ...whose sum...
     `=@                        ...equals...
   y&                           ...y
  (                     )@0     select the first one (always the longest)
Conor O'Brien
źródło
0

APL (NARS), 65 znaków, 130 bajtów

{m←⍺=+/¨v←1↓{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}⍵⋄0=↑⍴b←m/v:⍬⋄b⊃⍨n⍳⌈/n←⍴¨b}

↓ jest używane, ponieważ pierwszym elementem zestawu zbiorów byłby jeden zbiór nieważności (tutaj ⍬ Zilde), który chce się wyeliminować, ponieważ wydaje się, że + / ⍬ wynosi zero ...

Za brak znalezienia lub błąd zwróci ⍬ lub drukowany tekst:

  o←⎕fmt
  o ⍬
┌0─┐
│ 0│
└~─┘

test:

  z←{m←⍺=+/¨v←1↓{0=⍴⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}⍵⋄0=↑⍴b←m/v:⍬⋄b⊃⍨n⍳⌈/n←⍴¨b}

  o 1 z ,1
┌1─┐
│ 1│
└~─┘
  o 2 z ,1
┌0─┐
│ 0│
└~─┘
  o 10 z 1 2 3 4 5 6 7 8 9 10
┌4───────┐
│ 1 2 3 4│
└~───────┘
  o 10 z 2,2,2,2,2,2,2,2,2
┌5─────────┐
│ 2 2 2 2 2│
└~─────────┘
  o ¯8 z 2,2,2,2,¯2,¯2,¯2,¯4,¯2
┌7──────────────────┐
│ 2 2 ¯2 ¯2 ¯2 ¯4 ¯2│
└~──────────────────┘
  o ¯6 z ¯2,¯4,¯2
┌2─────┐
│ ¯4 ¯2│
└~─────┘
  o 0 z 2,2,2,4,2,¯2,¯2,¯2,¯4,¯2
┌10───────────────────────┐
│ 2 2 2 4 2 ¯2 ¯2 ¯2 ¯4 ¯2│
└~────────────────────────┘
  o 10 z 1 2 3 4
┌4───────┐
│ 1 2 3 4│
└~───────┘
  o 10 z 1 2 3
┌0─┐
│ 0│
└~─┘
  o 0 z ⍬
┌0─┐
│ 0│
└~─┘
  o +/⍬  
0
~
RosLuP
źródło