Мой массив должен равняться этому, но это не так!

21

Дан массив целых чисел, aкоторый содержит n целых чисел и одно целое число x; удалить наименьшее количество элементов, aчтобы сделать сумму aравной x. Если никакие комбинации не aмогут сформироваться x, вернуть ложное значение.

Как указано в комментарии, это максимальный набор с суммой х , извините мой меньший математический мозг. Я забыл много терминов с колледжа.

Примеры (правда):

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] (Без изменений)

f([], 0) = [] (Неизменный случай с нулевой суммой)

Примеры (Falsy, любое непротиворечивое значение не из массива):

Невозможно сделать дело: f([-2,4,6,-8], 3) = falsy (E.G. -1)

Случай с нулевой суммой: f([], non-zero number) = falsy (E.G. -1)

  • Примечание. Любое значение, например, [-1]не может быть допустимым для ложных значений, поскольку это потенциальный достоверный вывод.

Правила:

  • Входные данные могут быть приняты в виде массива или в виде списка аргументов, последний или первый x.
  • Выходными данными может быть любой список целых чисел с разделителями. НАПРИМЕР1\n2\n3\n или [1,2,3].
  • Любое значение может быть использовано в качестве ложного индикатора, кроме массива целых чисел.
  • Ваш код должен максимизировать размер конечного массива, порядок не имеет значения.
    • Например, для f([3,2,3],5)обоих [2,3]и[3,2] одинаково действительны.
    • Например, для f([1,1,2],2)вас можно вернуть только [1,1]как [2]короче.
  • И сумма, aи значение xбудут меньше 2^32-1и больше чем-2^32-1 .
  • Это код-гольф , выигрывает наименьшее количество байт.
  • Если существует несколько допустимых подмассивов одинакового размера, вывести их все будет недопустимо. Вы должны выбрать один и вывести его.

Дайте мне знать, если это было опубликовано, я не смог его найти.

Сообщения, которые я нашел, как это : Связанные, но закрытые , ...

code-golf array-manipulation Урна волшебного осьминога
источник
1
Я полагаю, что «Falsy, любое непротиворечивое значение, не являющееся массивом» включает в себя возникновение ошибки
Джонатан Аллан
« Любое значение может использоваться как индикатор ложного, кроме массива целых чисел. » Включает ли это пустой массив?
Лохматый
@shaggy [] указывает на потенциальную истинную ценность, верно? Позволяет ли это мета-правило важнее, чем отдельная правда и ложь?
Волшебная Урна Осьминога
@JohnathanAllan, если эта ошибка не может возникнуть в сценарии «Истина», я бы предположил. Но я чувствую, что это намеренно пытается расширить спецификацию. Если я поменяю формулировку с индикатора на возвращаемое значение, это нормально?
Волшебная Осьминог Урна
Я верю, что последовательные значения выхода учитываются как возвращаемое значение, хотя для мета?
Волшебная Урна Осьминога

Ответы:

7

Брахилог , 8 байт

h⊇.+~t?∧

Попробуйте онлайн!

Ежемесячный брахилог ответ. Возвращаетfalse. если это невозможно.

объяснение

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)
Fatalize
источник
6

Python 2 , 108 104 байта

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*

Попробуйте онлайн!

-4 байта, благодаря Джонатану Аллану

Python 2 , 108 106 байт

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

Попробуйте онлайн!

-2 байта, благодаря Джанатану Фреху

TFeld
источник
1
Вы можете использовать range(-len(a),1)и -lсохранить 2, но lambda a,n:[x for l in range(len(a)+1)for x in combinations(a,l)if sum(x)==n][-1]сохраняет 4
Джонатан Аллан
@JonathanAllan Спасибо :)
TFeld
1
Возможные 106 байтов .
Джонатан Фрех
@JonathanFrech Спасибо, я, должно быть, вчера устал;)
TFeld
4

Pyth , 8 байт

  • 8 байт ( попробуйте! ) - выводит только одно возможное решение. Для неразрешимых входных данных он ничего не печатает в STDOUT, которая является пустой строкой, которая технически говорит фальшиво в Pyth, но записывает в STDERR. Спасибо FryAmTheEggman за предложение об этом (игнорируя STDERR и фокусируясь только на выводе STDOUT), тем самым экономя 1 байт.

    efqz`sTy

  • 9-байт ( попробуйте! ) - выводит только одно возможное решение, включенное в одноэлементный список, как разрешено по умолчанию (например, ([1...10], 10) -> [[1,2,3,4]]; ([], 0) -> [[]]). Для неразрешимых входных данных возвращается [], что в Pyth неверно .

    >1fqz`sTy

  • 10 байт ( попробуйте! ) - для более четкого вывода, без использования правила синглтон-списка и использования, 0а не []в качестве ложного значения.

    e+0fqz`sTy

объяснение

Во-первых, код вычисляет powerset входного списка (все возможные упорядоченные его подгруппы). Затем он сохраняет только те коллекции, сумма которых равна входному номеру. Следует отметить, что коллекции создаются от самых коротких до самых длинных, поэтому мы сосредоточимся на последнем. Чтобы получить это:

  • 8-byter просто использует конец встроенный, который бросает ошибку, но STDERR могут быть проигнорированы в соответствии с нашими правилами сайта, выход на STDOUT быть пустой строкой, которая является falsy.
  • 9-byter берет последнего элемента, но используя эквивалентный код Python lst[-1:]вместо lst[-1]ошибок избежать от броска для неразрешимых входов.
  • 10-byter присоединяет 0 в список отфильтрованных суб-коллекции, а затем берет конец этой коллекции (последний элемент). Если входные данные не разрешимы, то вместо этого естественно используется 0 .
Мистер Xcoder
источник
[]это ложь? Ухоженная. Почему Пиф делает это []?
Волшебная Осьминог Урна
@MagicOctopusUrn Pyth наследует это от Python : попробуйте онлайн .
Г-н Xcoder
@FryAmTheEggman не будет ли пустой список правдивым выводом в тестовом случае f([], 0) = []?
Сок
@FryAmTheEggman Спасибо за ваше предложение! Я внес необходимые изменения :)
Mr. Xcoder
3

Perl 6 , 38 37 байт

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

Попробуйте онлайн!

Функция карри.

nwellnhof
источник
Подождите, это ;даже необходимо?
Джо Кинг,
@JoKing На более ранней итерации необходимо было избежать ошибки «неправильное двойное замыкание». Но по какой-то причине это можно опустить сейчас. (Я думаю , что после того, как я заменил $^xс $_.)
nwellnhof
3

Брахилог , 4 байта

⟨⊇+⟩

Попробуйте онлайн!

Примерно эквивалентно Fatalize h⊇.+~t?∧, за исключением намного короче, благодаря функции составления предиката, которая, согласно истории редактирования ссылки, находилась в процессе разработки до 8 января, после чего ответ был отложен более чем на два месяца. ⟨⊇+⟩это бутерброд , расширяющийся до {[I,J]∧I⊇.+J∧}, где скобки в этом случае не имеют значения, так как бутерброд в любом случае находится на своей собственной линии.

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

Гораздо менее драматичное преобразование ответа Фатализ, который использует те же самые предикаты с теми же переменными, но получается на байт короче из-за того, что они организованы иначе:

Брахилог , 7 байт

h⊇.&t~+

Попробуйте онлайн!

           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.

(Также, если кто-то хочет увидеть что-то странное, измените любое подчеркивание в тестовых случаях на дефис.)

Несвязанная строка
источник
1
Бутерброды были реализованы @ ais523 в ноябре 2018 года, но были извлечены только в Brachylog в начале января 2019 года.
Fatalize
1
Конечно, ни одно из этого поиска истории не имеет значения, так как языки, которые устарели, были разрешены в течение многих лет.
pppery
2

Чисто , 89 байт

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

Попробуйте онлайн!

Определяет функцию, $ :: Int -> [Int] -> (Maybe [Int])возвращающуюся, Nothingесли нет подходящей комбинации элементов, и (Just [elements...])иначе.

Οurous
источник
2

JavaScript (ES6), 108 байт

Принимает вход как (array)(n). Возвращает либо массив, либо 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

Попробуйте онлайн!

Arnauld
источник
2

Это началось круто и мало, но крайние случаи меня достали. Что бы ни случилось, я горжусь работой, которую я вложил в это.

Python 3 , 169 161 154 байта

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

Попробуйте онлайн!

гигафлоп
источник
Помните, что это [код-гольф], поэтому вы должны постараться, чтобы ваш байт был как можно меньше! У вас есть ведущий новичок и некоторые другие тривиальные гольф-поля, и я держу пари, что кто-то еще, кто знает, что Python, может сыграть в эту игру дальше.
Джузеппе
@Giuseppe Спасибо, что напомнили мне о ведущих пробелах. Я потратил некоторое время, пытаясь объединить некоторые части этого, но решил опубликовать его в то же время на случай, если другие могут предложить изменения.
Gigaflop
Не проблема! Прошло уже 5 лет с тех пор, как я написал Python, но не range(x)генерирует (0...x-1)? То range(len(a))есть вы не оставляете возможность оставить массив без изменений?
Джузеппе
@ Джузеппе Эврика, это было сделано. Возможно, я слишком сосредоточился на новом материале, с которым работал.
Gigaflop
Вместо if a==[] and x==0использования if sum(a)==x. Тогда вы также можете удалить +1из range.
Ведант Кандой
2

R , 100 80 байт

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

Попробуйте онлайн!

20 байтов сохранено благодаря digEmAll

Возвращает FALSEпо невозможным критериям.

Giuseppe
источник
И 80 злоупотребляют оператором '[' : D
digEmAll
@digEmAll Я, конечно, рад, что у меня не было возможности отредактировать ваш 98-байтовый ответ :-)
Джузеппе
эхех забыл его удалить: D
digEmAll
1

Атташе , 28 байт

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

Попробуйте онлайн!

альтернативы

34 байта :f[x,y]:=({y=Sum@_}\Radiations@x)@0

30 байтов :First@${y&`=@Sum\Radiations@x}

29 байт :{(_&`=@Sum\_2)@0}#/Radiations

29 байт :${({y=Sum@_}\Radiations@x)@0}

29 байт :`@&0@${y&`=@Sum\Radiations@x}

29 байт :{_}@@${y&`=@Sum\Radiations@x}

объяснение

${(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)
Конор О'Брайен
источник
0

APL (NARS), 65 символов, 130 байтов

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

↓ используется потому, что первым элементом набора множеств будет одно пустое множество (здесь ⍬ Зильда), которое нужно исключить, потому что кажется, что + / ⍬ равно нулю ...

Если не найти или ошибка, он вернет ⍬ или в печатном тексте:

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

тест:

  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
источник