Teilen Sie eine Liste in große Teile, aber ohne Elemente zu zählen, die das Vergleichselement nicht erfüllen

17

Motivation : Manchmal zählen bestimmte Elemente in einer Liste nicht zu Ihren Gesamtsummen. Zählen Sie beispielsweise Fluggäste in Reihen, in denen Babys auf dem Schoß eines Elternteils sitzen.

Herausforderung : Schreiben Sie ein Programm, um eine Liste von Elementen in Blöcke aufzuteilen. Jeder Block (außer möglicherweise der letzte) hat dieselbe Größe , wobei die Größe als die Anzahl der Elemente definiert ist, die eine Prädikatfunktion bestehen.

Regeln :

  1. Ihr Programm muss dauern
    • eine Liste von Elementen
    • eine positive Ganzzahlblockgröße
    • eine Prädikatfunktion (nimmt ein Element und gibt true oder false zurück)
  2. Sie müssen die in Blöcke aufgeteilte Eingabeliste zurückgeben
  3. Jeder Chunk ist eine Liste von Elementen
  4. Insgesamt müssen die Artikel in der gleichen Reihenfolge bleiben, ohne dass sie verworfen werden
  5. Die Anzahl der Elemente, die das Prädikat in jedem Block (außer möglicherweise dem letzten) übergeben, sollte mit der Größe des Eingabeblocks übereinstimmen.
  6. Elemente, die das Prädikat nicht erfüllen, sollten bei dieser Größe nicht berücksichtigt werden
  7. Elemente, die das Prädikat nicht erfüllen, sind
    1. weiterhin in den Ausgabestücken enthalten
    2. Wird dem frühesten Chunk zugewiesen, wenn ein Chunk "voll" ist, aber die nächsten Elemente das Prädikat nicht erfüllen
      • Daher besteht der letzte Block möglicherweise nicht nur aus Elementen, die das Prädikat nicht erfüllen
  8. Der endgültige Block hat möglicherweise eine kleinere Größe als der Block, da alle Elemente berücksichtigt wurden.

Nicht erschöpfende Beispiele:

Das einfachste Beispiel ist, 1s und 0s zu betrachten, in denen die Prädikatfunktion ist x ==> x > 0. In diesem Fall summuss der Wert jedes Blocks mit der Blockgröße übereinstimmen.

  • Elemente:, []Größe 2:, Prädikat: x > 0-> entweder []oder[[]]
  • Elemente:, [0, 0, 0, 0, 0, 0]Größe 2:, Prädikat: x > 0->[[0, 0, 0, 0, 0, 0]]
  • Elemente:, [0, 1, 1, 0]Größe 2:, Prädikat: x > 0->[[0, 1, 1, 0]]
  • Elemente:, [0, 1, 1, 0, 1, 0, 0]Größe 2:, Prädikat: x > 0->[[0, 1, 1, 0], [1, 0, 0]]
  • Elemente:, [0, 1, 0, 0, 1, 0, 1, 1, 0]Größe 2:, Prädikat: x > 0->[[0, 1, 0, 0, 1, 0], [1, 1, 0]]

Und lassen Sie uns mit den Flugzeugpassagieren enden, bei denen Babys auf dem Schoß eines Elternteils sitzen . AFür Erwachsene, bfür Babys ist die 3Sitzreihe in der Ebene breit, Erwachsene stehen immer vor ihrem Baby:

  • Elemente:, [A, b, A, b, A, A, A, b, A, b, A, A, b]Größe 3:, Prädikat: x => x == A->[[A, b, A, b, A], [A, A, b, A, b], [A, A, b]]
Tom Viner
quelle
6
Das sieht nach einer guten Frage aus, aber derzeit fehlt ein Gewinnkriterium. Ich schlage vor, Code-Golf zu verwenden .
Laikoni
3
Können wir annehmen, dass die Listenelemente einzelne Zeichen sind? Oder sagen wir Zahlen?
xnor
chunking klingt interessant, könnte aber vielleicht durch set-partitionen ersetzt werden .
Jonathan Frech
@Laikoni getaggt Code-Golf
Tom Viner
1
@Ourous Ich habe hinzugefügt, "weil alle Elemente berücksichtigt wurden", dh der letzte Block hat keine Chance, "voll" zu werden, da dies nur das Ende der eingegebenen Elemente ist.
Tom Viner

Antworten:

2

Gelee , 10 Bytes

vⱮTm⁵ḊœṖŒṘ

Ein vollständiges Programm, das die monadische Black-Box-Funktion als erstes optionales Argument, die Liste als zweites optionales Argument und die Blockgröße als drittes optionales Argument verwendet und eine Python-Darstellung der resultierenden Liste von Listen ausgibt (um Jellys implizites Zerschlagen von zu vermeiden) Listen mit Zeichen).

Probieren Sie es online! (Beachten Sie, dass eine Liste von Zeichen an ein Jelly-Programm übergeben wird, indem es als Zeichenfolge in Python-Anführungszeichen formatiert wird.)

Wie?

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
Jonathan Allan
quelle
8

Brachylog , 37 Bytes

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

Probieren Sie es online!

Ich war angenehm überrascht, dass dies - so ziemlich eine Wiederholung der Frage - erfolgreich beendet wurde und eine korrekte Ausgabe hervorbringt.

Angenommen, das Prädikat ist als Prädikat 2 unterhalb dieses Codes vorhanden. Gibt eine Liste von Listen ("Chunks") oder falseeine leere Eingabe aus.

Erläuterung:

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 - Setzen Sie Monica wieder ein
quelle
7

Apl (Dyalog Unicode) 17 16 Bytes (SBCS)

Vielen Dank an Adám, der mir 1 Byte gespart hat.

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

Probieren Sie es online! zur Erklärung werde ich die 17-Byte-Lösung weglassen.

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

⍺⍺¨⍵Wendet das Prädikat auf die Liste an, wobei ein boolescher Vektor zurückgegeben wird.
+\Generiert eine laufende Summe. Ersetzt das
1⌈führende 0s durch 1s.
⌈⍺÷⍨Dividiert jedes Element durch die Blockgröße und rundet die
⍵⊆⍨Partitionen des ursprünglichen Vektors auf

jslip
quelle
2
Das ist beeindruckend! Und ich mag die Ausgabe-Anzeige, passend zu dem Problem.
Sundar - Reinstate Monica
Speichern Sie ein Byte, indem Sie in ein Programm konvertieren (tradfn body):w⊆⍨⌈⎕÷⍨1⌈+\⎕¨w←⎕
Adám
5

Sauber , 96 92 Bytes

Verwendet eine benannte Funktion, f :: a -> Booldie gemäß Metakonsens zulässig ist.

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

Probieren Sie es online!

Erweitert (mit Standardmarkierung, damit Kommentare angezeigt werden):

$ 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
quelle
4

Java 10, 207 186 159 148 Bytes

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 ist definitiv nicht die richtige Sprache für diese Herausforderung (oder natürlich jede Codegolf-Herausforderung ..)

-21 Bytes dank @OOBalance

Probieren Sie es online aus.

Erläuterung:

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

Blackbox-Eingabeformat:

Nimmt an, dass eine benannte Funktion boolean f(Object i)vorhanden ist, die gemäß dieser Meta-Antwort zulässig ist .

Ich habe eine abstrakte Klasse, Testdie die Standardfunktion f(i)sowie das obige Lambda enthält:

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ür die Testfälle überschreibe ich diese Funktion f. Der letzte Testfall heißt zum Beispiel so:

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));
Kevin Cruijssen
quelle
1
" (or any codegolf-challenge of course..)ehh ich weiß nicht, du hast meine sauberen Antworten in mindestens einigen Fällen herausgeschlagen." Wie auch immer, ich freue mich immer auf Ihre Antworten.
Οurous
2
@ Οurous Es ist eher ein Meme, dass Java in keiner Weise für Codegolf geeignet ist, was meiner Meinung nach auch für Clean gilt, wenn wir es mit tatsächlichen Golfsprachen wie Jelly, 05AB1E usw. vergleichen. Ich mag es immer noch, all diese Codegolf-Herausforderungen zu lösen in Java (und Sie auch in Clean, nehme ich an). Und ab und zu ist Java in der Lage, Python zu schlagen . ;) Und ich war einmal eine führende Antwort mit Java , bis Bash es ruinierte (und R weiter Golf spielte). xD
Kevin Cruijssen
1
186 Bytes, wenn Sie eine Liste von Arrays zurückgeben: bit.ly/2mSjCIc
OOBalance
@OOBalance Danke! Intelligente Verwendung von Arrays.copyOfRange!
Kevin Cruijssen
@OOBalance konnte ein bisschen mehr Golf spielen, indem die Eingabe als Liste verwendet und verwendet wurde .sublist. Ihre Funktionalität bleibt ansonsten gleich, spart jedoch viele Bytes und entfernt den Import. (Und jetzt funktioniert es auch für den Testfall mit Zeichen anstelle von ganzen Zahlen.)
Kevin Cruijssen
4

R , 58 Bytes

function(v,g,n,a=(cumsum(Map(g,v))-1)%/%n)split(v,a*(a>0))

Probieren Sie es online!

  • -5 Bytes dank @ Giuseppe
digEmAll
quelle
1
58 Bytes
Giuseppe
3

C (gcc) , 70 66 Bytes

Ich benutze eine Struktur, um den Anfang einer Unterliste zu notieren, da C über solche Dinge nichts weiß.

Danke an ceilingcat für die Vorschläge.

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

Probieren Sie es online!

ErikF
quelle
3

Haskell, 72 Bytes

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

Probieren Sie es online!

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' 
nimi
quelle
3

MATL, 19 Bytes

HyX$Ysi/Xk1y>+!w7XQ

Basierend auf der ausgezeichneten APL-Antwort von jslip .

MATL hat eigentlich keine benutzerdefinierten Funktionen als solche, aber es gibt eine Möglichkeit, die Umgebung, in der es ausgeführt wird (MATLAB / Octave), aufzurufen. Daher wird diese Funktion für die Prädikatfunktion verwendet. Die Verwendung wäre ungefähr so , aber diese Funktionalität ist aus Sicherheitsgründen online deaktiviert. Hier ist eine Version, die isoddstattdessen eine fest codierte Prädikatfunktion verwendet: Probieren Sie es in MATL Online aus .

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 - Setzen Sie Monica wieder ein
quelle
2

Ruby , 57 Bytes

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

Probieren Sie es online!

Anonymer Lambda, der Eingabearray a, Blockgröße nund Prädikat akzeptiert g. Verwaltet einen Zähler cfür Elemente, die mit dem Prädikat übereinstimmen, und gruppiert Elemente nach der Anzahl der bereits verbrauchten Blöcke. Leider wird der anfängliche Wert -1 / n nicht auf 0 gerundet, daher müssen wir ein paar Bytes aufwenden, um ihn zu beheben.

Kirill L.
quelle
2

R , 100 Bytes

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],"
")

Probieren Sie es online!

von digEmAll handlich überfordert

Giuseppe
quelle
Ich weiß nicht, ob benannte Listen als Ausgabe in
Ordnung
Hmm nun, ich würde das als separate Antwort posten!
Giuseppe
1

JavaScript (Node.js) , 90 Byte

(s,p,r=[l=[]],n=s+1)=>g=a=>0 in a?g(a,(n=(n||s)-p(v=a.shift()))||r.push(l=[]),l.push(v)):r

Probieren Sie es online!

Aufrufen als F(2, x => x > 0)([0, 1, 1, 0])

tsh
quelle
1

Mathematica, 82 Bytes

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

list die Eingabeliste; sist Stückgröße; pist eine unbenannte / anonyme / reine / Lambda-Funktion, die true / false zurückgibt, wenn Elemente der Liste bearbeitet werden.

Last@Reap[...]Gibt eine Liste mit Listen aller Elemente zurück, in denen Sow-n enthalten war .... Sie werden in Unterlisten gruppiert, deren zweites Argument e~Sow~teine Abkürzung ist Sow[e, t].

Ich musste Zähler auf -1 initialisieren, um eine Blockgröße von 1 zu verarbeiten, sonst müsste ich check Mod[i, s]( i~Mod~s) gleich 1 setzen, was niemals passieren könnte.

Der Rest des Codes wird im ungolfed Block erklärt.

LLlAMnYP
quelle