Положить массив в контейнеры

12

В этом простом задании вы получаете входной массив Lнеотрицательных целых чисел и количество бинов bбольше 0, но не больше длины L. Ваш код должен возвращать новый массив M, длина которого равна bи которая содержит массив L. Это проще всего объяснить на примерах.

L = [1,0,5,1]и b = 2возвращается M = [1,6].

L = [0,3,7,2,5,1]и b = 3возвращается M = [3,9,6].

Пока все просто. Однако в этом вопросе bне обязательно делить len(L). В этом случае последний бин будет иметь меньше чисел, чтобы составить его.

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

L = [0,3,7,2,5,1]и b = 4возвращается M = [3,9,6,0]. M = [10,8,0,0]не является приемлемым выводом, так как третий бин не имеет имени числа чисел, вносящих в него свой вклад в качестве бинов 1и 2.

L = [0,3,7,2,5]и b = 2возвращается M = [10,7]. M = [3, 14]не является приемлемым выводом, так как последний бин будет иметь 3элементы, способствующие этому, но первый имеет только 2.

L = [1,1,1,1,1,1,1]и b = 3возвращается M = [3,3,1].

Как последнее правило, ваш код должен работать за линейное время.

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


Оказывается, есть некоторые входные данные, которые не могут быть решены. Например [1,1,1,1,1]и b=4. Ваш код может выводить все что угодно для этих входных данных.


источник
6
Я думаю, что было бы неплохо еще несколько тестов.
Джонатан Фрех
5
your code must run in linear time- Я нашел бы любой алгоритм, который не следует этому, естественно, довольно странно
Уриэль
2
@ Uriel Нет предела тому, насколько странными могут быть ответы от code-golf :)
4
@Lembik Хотя каким образом отказ от таких потенциальных странных подходов полезен для игры в гольф?
Джонатан Фрех
@JonathanFrech, это просто до настроек ОП :)

Ответы:

5

APL (Дьялог) , 19 байт

{+/⍺(⌈⍺÷⍨≢⍵)⍴⍵,⍺⍴0}

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

Мы добавляем b нулей к массиву перед преобразованием его в равные части ⌈⍺÷⍨≢⍵( ⌈ длина L ÷ b ⌉ ) и суммируем их, как показано на рисунке,⍺⍴0 , так как любое количество пустых пятен (которые не являются частью исходного массива) больше, чем b - 1 будет заполнен как минимум b - 1 элементами из других блоков, что делает точку балансировки последней группы на максимальном значении b - 1 отличным от остальных. Мы используем b> b - 1, потому что это код гольф.

Например, L с 15 элементами и b = 3 не будут сгруппированы как

x x x x x x
x x x x x x
x x x 0 0 0

а скорее как (обратите внимание, как самые правые 2 xс «заполняют» самые левые нули)

x x x x x
x x x x x
x x x x x

в то время как массив из 16 элементов будет заполнен 2 ( 3 - 1 ) пустыми пятнами, как

x x x x x x
x x x x x x
x x x x 0 0
Уриэль
источник
3

R , 75 71 70 63 байт

function(L,b)colSums(matrix(L[1:(ceiling(sum(L|1)/b)*b)],,b),T)

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

Эти подушечки Lс NAдо тех пор , пока длина кратна b, затем принимает сумму столбцов Lв виде матрицы с bколоннами, извлекая NAзначения.

Объясняя как основанный на стеке язык:

function(L,b){
      (ceiling(sum(L|1)/b*b)  # push the next multiple of b >= length(L), call it X
    1:..                      # push the range 1:X
  L[..]                       # use this as an index into L. This forces L
                              # to be padded to length X with NA for missing values
        matrix(..,,b)         # create a matrix with b columns, using L for values
                              # and proceeding down each column, so
                              # matrix(1:4,,2) would yield [[1,3],[2,4]]
colSums(.., na.rm = T)        # sum each column, removing NAs

Giuseppe
источник
Очень красиво и быстро! Подъем R-кодера ...
2
@Lembik Мне посчастливилось попасть прямо в TNB между вами, говоря: «Я собираюсь опубликовать это как вызов», а вы фактически отправляете это.
Джузеппе
1
О, смотрите "длина [<-" тоже вернется, как наш любимый приятель "[<-". Нет байтов, сохраненных для меньшей читаемости:function(L,b)colSums(matrix("length<-"(L,ceiling(length(L)/b)*b),,b),T)
Vlo
1
@Vlo no bytes saved for less readability, вероятно, девиз игры в гольф R ... хотя я полагаю, что sum(L|1)это байт, сохраненный от length(L)!
Джузеппе
3

MATL , 6 байтов

vi3$es

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

Рассмотрим ввод 4, [0,3,7,2,5,1]как пример.

v       % Vertically concatenate stack contents. Gives the empty array, []
        % STACK: []
i       % Input b
        % STACK: [], 4
        % Implicitly input L at the bottom of the stack
        % STACK: [0,3,7,2,5,1], [], 4
3$e     % 3-input reshape. This reshapes L with [] rows and b columns, in
        % column-major order (down, then across). [] here means that the
        % number of rows is chosen as needed to give b columns. Padding
        % with trailing zeros is applied if needed
        % STACK: [0 7 5 0;
                  3 2 1 0]
s       % Sum of each column
        % STACK: [3 9 6 0]
        % Implicitly display
Луис Мендо
источник
1
Это самый впечатляющий ответ на мой взгляд.
3

Рубин , 54 53 байта

Сохраненный байт благодаря @Kirill L.

->l,b{s=1.0*l.size/b;(1..b).map{l.shift(s.ceil).sum}}

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

Восстановить Монику - нотайнард
источник
Хорошо, вы также можете сохранить байт, заменив [0]*bна1..b
Кирилл Л.
@KirillL. Благодарю. Мне даже не пришло в голову.
Восстановить Монику - Нотмайнард
2

Java 10, 96 89 86 байт

a->b->{int r[]=new int[b],i=0,n=a.length;for(;i<n;)r[i/((n+b-1)/b)]+=a[i++];return r;}

Попробуйте это онлайн здесь .

Нашел более короткий способ написать i/(n/b+(n%b==0?0:1) здесь: i/((n+b-1)/b)

Спасибо Оливье Грегуару за игру в гольф 3 байта.

Безголовая версия:

input -> bins -> { // input is int[] (original array), bins is int (number of bins)
    int result[] = new int[bins], // resulting array, initialized with all 0
    i = 0, // for iterating over the original array
    n = a.length; // length of the original array
    for(; i < n ;) // iterate over the original array
        result[i / ((n + bins - 1) / bins)] += input[i++]; // add the element to the right bin; that's bin n/bins if bins divides n, floor(n/bins)+1 otherwise
    return result;
}
OOBalance
источник
86 байт
Оливье Грегуар,
@ OlivierGrégoire Спасибо!
OOBalance
1

Эликсир , 98 байт

fn l,b->Enum.map Enum.chunk(l++List.duplicate(0,b-1),round Float.ceil length(l)/b),&Enum.sum/1 end

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

Лучший эликсир имеет расщепление на части длиной n . И оно не может хорошо разделить деление на целое число, поэтому мы делим деление на округление. К сожалению, единственный способ сделать это приводит к плавающей запятой, поэтому мы снова округляем его до целого числа.

Okx
источник
Некоторые из ваших выходов имеют неправильную длину.
@Lembik исправил это.
Okx
1

Perl 6 ,  52 51  50 байт

52 байта: проверить это

->\L,\b{L.rotor(:partial,ceiling L/b)[^b].map: &sum}

51 байт: проверить это

{@^a.rotor(:partial,ceiling @a/$^b)[^$b].map: &sum}

50 байт: попробуйте

{map &sum,@^a.rotor(:partial,ceiling @a/$^b)[^$b]}

47 байт , не конкурируя Попробуй

{@^a.rotor(:partial,ceiling @a/$^b)[^$b]».sum}

Он неконкурентный, так как ».sumему разрешено выполнять вычисления параллельно. Так может быть или не быть в линейном времени.


Expanded:

{  # bare block with two placeholder parameters 「@a」 and 「$b」

  map                   # for each sublist

    &sum,               # find the sum


    @^a                 # declare and use first parameter

    .rotor(             # break it into chunks

      :partial,         # include trailing values that would be too few otherwise

      ceiling @a / $^b # the number of elements per chunk

    )[ ^$b ]           # get the correct number of chunks if it would be too few

}
Брэд Гилберт b2gills
источник
1

Древесный уголь , 22 байта

NθAηW﹪Lηθ⊞η⁰E⪪η÷LηθIΣι

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

Nθ

Вход b.

Aη

Вход L.

W﹪Lηθ⊞η⁰

Нажмите до, 0чтобы длина делится на .LLb

E⪪η÷LηθIΣι

Разделите Lдлину на bи разделите Lна секции этой длины, затем сложите каждую секцию и приведите к строке для неявного вывода в отдельных строках.

Нил
источник
1

C (лязг) , 58 байт

i;f(*L,l,b,*m){b=l/b+!!(l%b);for(i=0;i<l;m[i++/b]+=L[i]);}

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

f()принимает параметры следующим образом:
Lуказатель на входной массив
l: длина входного массива
b: количество бинов
m: указатель на буфер, который получает новый массив

Ниже приведена повторная входная версия @ 60 байт:

f(*L,l,b,*m){b=l/b+!!(l%b);for(int i=0;i<l;m[i++/b]+=L[i]);}
GPS
источник
1

PHP, 88 байт

function($a,$b){return array_map(array_sum,array_chunk($a,~-count($a)/$b+1))+[$b-1=>0];}

анонимная функция, принимает массив и целое число, возвращает массив

Только игра в гольф потенциал этого было заменял ceil(count($a)/$b))с (count($a)-1)/$b+1и сокращенным (count($a)-1)с ~-count($a). Результирующий float неявно приводится к целому числу в array_chunkвызове.

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

Titus
источник