17
4
Motivation: Sometimes certain items in a list don't count towards your totals. For example, counting plane passengers in rows, where babies sit on a parent's laps.
Challenge: write a program to split a list of items into chunks. Each chunk (except possibly the last) is the same size, where size is defined as the number of items passing a predicate function.
Rules:
- Your program must take
- a list of items
- a positive integer chunk size
- a predicate function (takes an item, and returns true or false)
- You must return the input list split into chunks
- Each chunk is a list of items
- Overall the items must remain in the same order, with none disgarded
- The number of items passing predicate in each chunk (except possibly the last) should match the input chunk size.
- items failing the predicate should not count toward this size
- Items failing the predicate are
- still included in the output chunks
- allocated to the earliest chunk, in the case that a chunk is "full" but the next items are ones failing the predicate
- thus the final chunk may not consist solely of items failing the predicate
- The final chunk may be of size less than the chunk size because all the items have been accounted for.
Non exhaustive examples:
The simplest example is to consider 1
s and 0
s, where the predicate function is x ==> x > 0
. In this case, the sum
of each chunk must match the chunk size.
- items:
[]
, size:2
, predicate:x > 0
--> either[]
or[[]]
- items:
[0, 0, 0, 0, 0, 0]
, size:2
, predicate:x > 0
-->[[0, 0, 0, 0, 0, 0]]
- items:
[0, 1, 1, 0]
, size:2
, predicate:x > 0
-->[[0, 1, 1, 0]]
- items:
[0, 1, 1, 0, 1, 0, 0]
, size:2
, predicate:x > 0
-->[[0, 1, 1, 0], [1, 0, 0]]
- items:
[0, 1, 0, 0, 1, 0, 1, 1, 0]
, size:2
, predicate:x > 0
-->[[0, 1, 0, 0, 1, 0], [1, 1, 0]]
And let's finish with the plane passengers where babies sit on a parent's lap example. A
for adult, b
for baby, plane row is 3
seats wide, adult always listed before their baby:
- items:
[A, b, A, b, A, A, A, b, A, b, A, A, b]
, size:3
, predicate:x => x == A
-->[[A, b, A, b, A], [A, A, b, A, b], [A, A, b]]
6This looks like a good question, but currently it's lacking a winning criterion. I suggest using [tag:code-golf]. – Laikoni – 2018-07-29T22:56:34.553
3Can we assume the list items are single characters? Or, say, numbers? – xnor – 2018-07-29T23:04:13.670
[tag:chunking] sounds interesting, though could maybe be replaced by [tag:set-partitions]. – Jonathan Frech – 2018-07-29T23:28:33.613
@Laikoni tagged [tag:code-golf] – Tom Viner – 2018-07-30T00:32:44.927
@xnor list items can be any basic data-type like strings or numbers – Tom Viner – 2018-07-30T00:34:08.853
@JonathanFrech [tag:set-partitions] are not appropriate as the order must be maintained – Tom Viner – 2018-07-30T00:34:54.307
@ChasBrown also hoping this can be opened! I don't think there's any point in empty chunks, but either
[]
or[[]]
would meet the criteria, I'll update the example. – Tom Viner – 2018-07-30T00:36:28.903"The final chunk may be of size less than the chunk size" -> What are the two sizes? We're given the chunk size, but the implication is that there's a different, other size. – Οurous – 2018-07-30T01:00:06.003
1@Ourous I've added "because all the items have been accounted for", i.e. the last chunk doesn't get a chance to get "full up", because that's just the end of the input items. – Tom Viner – 2018-07-30T01:09:05.557
When dealing with string items, can we assume that they are not empty? – Arnauld – 2018-07-30T07:04:53.550
@Arnauld, no I think the items aren't restricted like that. They can be
0
,0.0
,""
, or any other basic data type. – Tom Viner – 2018-07-30T08:16:43.203Can we give an empty/falsey output for when input is
[]
, instead of[]
or[[]]
? – sundar - Reinstate Monica – 2018-07-30T08:36:11.343General question, has there been a consensus on how to do these "blackbox predicate function" challenges in languages that don't have user-defined functions, for eg., MATL? I tried to search meta for this, but my search-fu seems weak today. – sundar - Reinstate Monica – 2018-07-30T16:07:51.043
@sundar: here's some meta.
– nimi – 2018-07-30T21:51:35.300@nimi That answer still assumes the language has user-defined functions, just not first-class ones. MATL has only builtin functions, no user-defined functions whether first class or not. There's a workaround to call out to the surrounding environment though, so I've posted an answer using that. Thanks for the link though! – sundar - Reinstate Monica – 2018-07-31T18:13:03.490