Разделить список на куски по размеру, но не считая элементы, не имеющие предикат

17

Мотивация : иногда определенные элементы в списке не учитываются при подсчете итогов. Например, подсчет пассажиров самолета в рядах, где дети сидят на коленях у родителей.

Задача : написать программу для разбиения списка элементов на куски. Каждый блок (кроме, возможно, последнего) имеет одинаковый размер , где размер определяется как число элементов, передающих функцию предиката.

Правила :

  1. Ваша программа должна занять
    • список предметов
    • положительный целочисленный размер куска
    • функция предиката (принимает элемент и возвращает истину или ложь)
  2. Вы должны вернуть входной список, разбитый на куски
  3. Каждый кусок представляет собой список элементов
  4. В целом, предметы должны оставаться в том же порядке, ни один из которых не игнорируется.
  5. Количество элементов, передаваемых предикатом в каждом чанке (кроме, возможно, последнего), должно соответствовать размеру входного чанка.
  6. элементы, не соответствующие предикату, не должны учитываться в этом размере
  7. Элементы, не соответствующие предикату:
    1. все еще включены в выходные чанки
    2. выделяется для самого раннего чанка, в случае, если чанк «полон», но следующие элементы не соответствуют предикату
      • таким образом, последний кусок может не состоять исключительно из элементов, не соответствующих предикату
  8. Конечный кусок может иметь размер меньше размера фрагмента, потому что все элементы были учтены.

Неисчерпывающие примеры:

Простейший пример - рассмотреть 1s и 0s, где есть функция предиката x ==> x > 0. В этом случае sumкаждый блок должен соответствовать размеру блока.

  • элементы:, []размер:, 2предикат: x > 0-> []или[[]]
  • элементы:, [0, 0, 0, 0, 0, 0]размер:, 2предикат: x > 0->[[0, 0, 0, 0, 0, 0]]
  • элементы:, [0, 1, 1, 0]размер:, 2предикат: x > 0->[[0, 1, 1, 0]]
  • элементы:, [0, 1, 1, 0, 1, 0, 0]размер:, 2предикат: x > 0->[[0, 1, 1, 0], [1, 0, 0]]
  • элементы:, [0, 1, 0, 0, 1, 0, 1, 1, 0]размер:, 2предикат: x > 0->[[0, 1, 0, 0, 1, 0], [1, 1, 0]]

И давайте закончим с пассажирами самолета, где дети сидят на коленях у родителей . Aдля взрослого, bдля ребенка, плоскость ряда 3широкая, взрослый всегда указан перед своим ребенком:

  • элементы:, [A, b, A, b, A, A, A, b, A, b, A, A, b]размер:, 3предикат: x => x == A->[[A, b, A, b, A], [A, A, b, A, b], [A, A, b]]
Том Винер
источник
6
Это выглядит как хороший вопрос, но в настоящее время ему не хватает критерия выигрыша. Я предлагаю использовать код-гольф .
Лайкони
3
Можем ли мы предположить, что элементы списка представляют собой отдельные символы? Или, скажем, цифры?
xnor
куски звучат интересно, хотя могут быть заменены сет-разделами .
Джонатан Фрех
@Laikoni помечен code-golf
Том Винер
1
@Ourous Я добавил «потому что все элементы были учтены», то есть последний блок не получает возможности «заполниться», потому что это только конец элементов ввода.
Том Винер

Ответы:

2

Желе , 10 байт

vⱮTm⁵ḊœṖŒṘ

Полная программа, принимающая монадическую функцию черного ящика в качестве первого необязательного аргумента, список в качестве второго необязательного аргумента и размер фрагмента в качестве третьего необязательного аргумента, который печатает представление Python результирующего списка списков (чтобы избежать неявного разрушения Jelly списки, содержащие символы).

Попробуйте онлайн! (обратите внимание, что список символов передается в программу Jelly путем форматирования его как строки в кавычках Python)

Как?

vⱮTm⁵ḊœṖŒṘ - Main Link: B, L, S
 Ɱ         - map across second argument with (i.e. for X in L):
v          -   evaluate as a monad with input (i.e. B(X))
  T        - truthy indices (e.g. [0,0,1,0,1,1,1,0,0,0,1,0,0]T -> [3,5,6,7,10])
    ⁵      - 3rd optional argument = S
   m       - modulo slice   (e.g. [3,4,7,9,12,15,16,18,19,20]m3 -> [[3,4,7],[9,12,15],[16,18,19],[20]]
     Ḋ     - dequeue        (e.g. [[3,4,7],[9,12,15],[16,18,19],[20]]Ḋ -> [[9,12,15],[16,18,19],[20]]
      œṖ   - partition right (L) at the indices in that
        ŒṘ - print Python representaion
Джонатан Аллан
источник
8

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

hW&t~c.k{↰₂ˢl}ᵐ;WxĖ∧.bhᵐ↰₂ᵐ∧.t↰₂ˢl≤W∧

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

Я был приятно удивлен, обнаружив, что это - в значительной степени переформулировка вопроса - успешно завершается и дает правильный результат.

Предполагается, что предикат присутствует как предикат 2 под этим кодом. Выводит список списков («чанков») или falseдля пустого ввода.

Объяснение:

hW&               % First input is W, the expected "weight" of each chunk
                  %  (i.e. the number of items passing predicate in each chunk)

t                 % Take the second input, the list of items
 ~c.              % Output is a partition of this list
    k{    }ᵐ      % For each partition (chunk) except the last, 
      ↰₂ˢ         %   Select the items in the chunk that pass the predicate
         l        %   Get the length of that
                  % (So now we have the list of the "weights" of each chunk)
            ;Wx   % Remove the input expected weight from this list, and 
               Ė  %  the result of this should be empty.
                  %  This verifies that the list of weights is either 
                  %  composed of all W-values, or is empty (when input is [0 0 0] for eg.)

    ∧.bhᵐ↰₂ᵐ      % And, the first element of each chunk (except the first) should
                  %  pass the predicate. This is another way of saying:
                  %  "Items failing the predicate are allocated to the earliest chunk"

    ∧.t↰₂ˢl≤W     % And, the final chunk (which we haven't constrained so far)
                  %  should have weight ≤ the input expected weight
                  %  This disallows putting everything in the final chunk and calling it a day!

    ∧             % (no further constraints on output)
sundar - Восстановить Монику
источник
7

Apl (Dyalog Unicode) 17 16 байт (SBCS)

Спасибо Адаму за то, что он спас мне 1 байт.

w⊆⍨⌈⎕÷⍨1⌈+\⎕¨w←⎕

Попробуйте онлайн! В целях объяснения я оставлю 17-байтовое решение.

{⍵⊆⍨⌈⍺÷⍨1⌈+\⍺⍺¨⍵}

⍺⍺¨⍵применяет предикат к списку, возвращая логический вектор,
+\генерирует промежуточный итог,
1⌈заменяет начальные 0s на 1s,
⌈⍺÷⍨делит каждый элемент на размер фрагмента и округляет до
⍵⊆⍨исходного вектора этот вектор

jslip
источник
2
Это поразительно! И мне нравится выходной дисплей, соответствующий визуальному решению проблемы.
sundar - Восстановить Монику
Сохраните байт, преобразовав в программу (tradfn body):w⊆⍨⌈⎕÷⍨1⌈+\⎕¨w←⎕
Adám
5

Чисто , 96 92 байта

Использует именованную функцию, f :: a -> Boolразрешенную в соответствии с мета-консенсусом.

import StdEnv,StdLib
$l n|l>[]=last[[i: $t n]\\i<-inits l&t<-tails l|n>=sum[1\\e<-i|f e]]=[]

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

Расширен (с подсветкой по умолчанию для отображения комментариев):

$ l n // define function $ on `l` and `n`
 | l > [] // if `l` is not the empty list
  = last [ // the last element of ...
                   \\ i <- inits l // prefixes of `l`
                    & t <- tails l // matching suffixes of `l`
                    | n >= // where n is greater than or equal to
                           sum [1 \\ e <- i | f e] // the number of matching elements in the prefix
          [i: $t n] // prepend that prefix to the application of $ to the rest of the list
         ]
 = [] // if `l` is empty, return empty
Οurous
источник
4

Java 10, 207 186 159 148 байт

a->n->{var r=new java.util.Stack();int l=a.size(),i=0,c=0,j=0;for(;i<=l;i++)if(i==l||f(a.get(i))&&++c>n&i>0){r.add(a.subList(j,j=i));c=1;}return r;}

Java определенно не является подходящим языком для этой задачи (или любой проблемы с Codegolf, конечно ..)

-21 байт благодаря @OOBalance

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

Объяснение:

a->n->{                    // Method with List & int parameters & List of Lists return-type
  var r=new java.util.Stack();
                           //  Result-list, starting empty
  int l=a.size(),          //  Size of the input-List
      c=0,                 //  Count-integer, starting at 0
      j=0,                 //  Range-integer, starting at 0
  i=0;for(;i<=l;i++){      //  Loop `i` in the range [0, `l`]
    if(i==l||              //   If this is the last iteration
       f(a.get(i))         //   Or if the black-box function is true for the current item
       &&++c               //    Increase the counter by 1
        >n&                //    If the counter is now larger than the size
        &i>0){             //    and it's not the first item of the List
      a.subList(j,j=i);    //     Add a sub-List to the result from range [`j`, `i`)
                           //     And set `j` to `i` at the same time
      c=1;}                //     And reset `c` to 1
  return r;}               //  Return the List of Lists as result

Формат ввода черного ящика:

Предполагается, что именованная функция boolean f(Object i)присутствует, что разрешено в соответствии с этим мета-ответом .

У меня есть абстрактный класс, Testсодержащий функцию по умолчанию f(i), а также лямбду выше:

abstract class Test{
  boolean f(Object i){
    return true;
  }

  public java.util.function.Function<java.util.List, java.util.function.Function<Integer, java.util.List<java.util.List>>> c =
    a->n->{var r=new java.util.Stack();int l=a.size(),i=0,c=0,j=0;for(;i<=l;i++)if(i==l||f(a.get(i))&&++c>n&i>0){r.add(a.subList(j,j=i));c=1;}return r;}
  ;
}

Для тестовых случаев я перезаписываю эту функцию f. Например, последний тестовый пример называется так:

System.out.println(new Test(){
  @Override
  boolean f(Object i){
    return (char)i == 'A';
  }
}.c.apply(new java.util.ArrayList(java.util.Arrays.asList('A', 'b', 'A', 'b', 'A', 'A', 'A', 'b', 'A', 'b', 'A', 'A', 'b'))).apply(3));
Кевин Круйссен
источник
1
« (or any codegolf-challenge of course..)Да, я не знаю, вы избили мои Чистые ответы, по крайней мере, в нескольких случаях. Во всяком случае, я всегда с нетерпением жду ваших ответов.
18:30
2
@ Οurous Это скорее мем, что Java никак не подходит для Codegolf, что, я думаю, применимо и к Clean, если мы сравним его с реальными языками гольфа, такими как Jelly, 05AB1E и т. Д. Мне все еще нравится решать все эти проблемы Codegolf. в Java, хотя (и вы в чистоте, как я полагаю). И однажды (долго), Java способен побить Python . ;) И я когда-то был ведущим ответом с Java , пока bash не испортил его (и R продолжил игру в гольф). xD
Кевин Круйссен
1
186 байт, если вы вернете
OOBalance
@OOBalance Спасибо! Умное использование Arrays.copyOfRange!
Кевин Круйссен
@OOBalance смог немного больше играть в гольф, используя входные данные в качестве Списка и используя .sublist. Ваша функциональность остается такой же, кроме этого, но она экономит много байтов и удаляет импорт. (И теперь это также работает для тестового случая с символами вместо целых чисел.)
Кевин Круйссен
3

С (ССЗ) , 70 66 байт

Я использую структуру, чтобы отметить начало подсписка, поскольку C не знает о таких вещах.

Спасибо потолку за предложения.

t;f(a,s,c)l*a;int(*c)();{for(;a->v;a++)(t+=c(a->v))>s?t=++a->s:0;}

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

ErikF
источник
3

Haskell, 72 байта

p#s|let l@(h:t)!a|sum[1|e<-h:a,p e]>s=a:l![]|n<-a++[h]=t!n;_!a=[a]=(![])

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

p#s     = (![])         -- main function that takes a predicate function 'p',
                        -- a size 's' and a input list without a name that is
                        -- directly passed as the first argument to function '!'
  let  l@(h:t)!a        -- function '!' is a local function (so that 'p' and 's'
                        -- are in scope). Takes a list 'l' of at least one element
                        -- 'h' (and 't' being the rest of the list) and an
                        -- accumulator 'a'
   |sum[1|e<-h:a,p e]>s -- if 'p' holds for more than 's' elements in 'h' and 'a'
     =a:l![]            --   put 'a' in front of a recursive call with the same list
                        --   'l' and an empty accumulator
   |n<-a++[h]           -- else bind 'n' to 'h' appended to 'a' and
     =t!n               --   call '!' again with 't' and 'n'
  _!a=[a]               -- base case for '!'. If the input list is empty, return
                        --   a singleton list with 'a' 
Ними
источник
3

MATL, 19 байт

HyX$Ysi/Xk1y>+!w7XQ

Основанный на превосходном ответе jslip APL .

MATL на самом деле не имеет пользовательских функций как таковых, но у него есть способ вызвать среду, в которой он работает (MATLAB / Octave), поэтому он использует это для функции предиката. Использование будет примерно таким , но эта функциональность отключена в сети из соображений безопасности, поэтому вот версия, в которой isoddвместо этого используется жестко закодированная функция предиката: попробуйте ее в MATL Online .

H    % Push the function name to be called, assumed to be 
     %  stored in the H clipboard
y    % Take the first input, push copies of it both below and above the 
     %  function name
X$   % Call the function (say 'isupper') with the input as argument
     %  returns a boolean vector
Ys   % Cumulative sum
i/   % Take the chunk size and divide each element by it
Xk   % ceil
1y>+ % Turn the (initial) 0s to 1s
!    % Transpose. Now we have a column vector specifying which chunk 
     %  each input element should go into
w    % Bring the other copy of the input on top 
7    % Code for this function: '@(x){x.'}'
     %  i.e. place each chunk in a row vector and enclose it in a cell
XQ   % 'accumarray' - split the input into chunks based on
     %   the given column vector, apply the given function to each chunk
     %   (which here just wraps it up as a cell), and accumulate the results
     %   in an array.
     % implicit output
sundar - Восстановить Монику
источник
2

Рубин , 57 байт

->a,n,g{c=-1;a.group_by{|x|[0,c+=g[x]?1:0].max/n}.values}

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

Анонимная лямбда принимает входной массив a, размер чанка nи предикат g. Поддерживает счетчик cэлементов, соответствующих предикату, и группирует элементы по количеству уже использованных фрагментов. К сожалению, начальное значение -1 / n не округляется до 0, поэтому нам нужно потратить несколько байтов, чтобы исправить это.

Кирилл Л.
источник
2

R , 100 байт

function(L,K,P,s=sapply(L,P),y=cut(cumsum(s),seq(0,sum(s),K),,T))for(l in levels(y))cat(L[y==l],"
")

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

перехитрила ловко от DigEmAll

Giuseppe
источник
Я не знаю, в порядке ли именованные списки в качестве выходных данных (и если я пропустил некоторые крайние случаи ...): 65 байт
digEmAll
Хм, хорошо, я бы опубликовал это как отдельный ответ!
Джузеппе
1

Mathematica, 82 байта

f[l_,s_,p_]:=Last@Reap[i=t=-1;Do[If[p@e,If[++i~Mod~s==0&&i>0,t++]];e~Sow~t,{e,l}]]

Ungolfed:

f[l_,s_,p_] :=                (* define a function that takes three    *)
                              (* arguments                             *)

  Last@Reap[                  (* collect and return results which were *)
                              (* gathered by the procedural loop below *)

    i=t=-1;                   (* initialize two counters               *)

    Do[                       (* start iterating over the list         *)

      If[p@e,                 (* if element passes predicate           *)
        If[                   (* then if preincremented i is 0 modulo  *)
          ++i~Mod~s==0&&i>0,  (* chunk size and i > 0                  *)
          t++                 (* increment t                           *)
        ]
      ];e~Sow~t,              (* finally sow the element tagged with   *)
                              (* the current value of t                *)

    {e,l}]                    (* e references current element of list  *)
                              (* l is the list itself                  *)
  ]

lсписок ввода; sразмер куска; pявляется неназванной / анонимной / чистой / лямбда-функцией, которая возвращает истину / ложь, работая с элементами списка.

Last@Reap[...]возвращает список списков каждого элемента, который был Sow-n внутри .... Они сгруппированы в подсписки, вторым аргументом e~Sow~tкоторых является сокращение Sow[e, t].

Мне пришлось инициализировать счетчики -1, чтобы обработать размер куска 1, в противном случае мне нужно будет проверить Mod[i, s](i~Mod~s ) равным 1, чего никогда не произойдет.

Остальная часть кода объясняется в блоке ungolfed.

LLlAMnYP
источник