Smallest groups in an array

Question

Introduction

Let's observe the following array:

[1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1]

A group consists of the same digits next to each other. In the above array, there are 5 different groups:

[1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1]
 1, 1, 1 
 2, 2
 1, 1, 1, 1
 2, 2, 2
 1, 1, 1

The smallest group of these is [2, 2], so we output [2, 2].

Let's take another example:

[3, 3, 3, 4, 4, 4, 4, 5, 5, 4, 4, 3, 3, 4, 4]
 3, 3, 3
 4, 4, 4, 4
 5, 5
 4, 4
 3, 3
 4, 4

You can see that there are multiple groups with the same length. The smallest groups are:

[3, 3], [4, 4], [4, 4] and [5, 5].

So we just output [3, 3], [4, 4], [4, 4], [5, 5] in any reasonable format. You may output these in any order.

The Task

Given an array consisting of only positive integers, output the smallest group(s) from the array. You can assume that the array will contain at least 1 integer.

Test cases

Input: [1, 1, 2, 2, 3, 3, 4]
Output: [4]
Input: [1]
Output: [1]
Input: [1, 1, 10, 10, 10, 100, 100]
Output: [1, 1], [100, 100]

This is code-golf, so the submission with the least amount of bytes wins!

• Leaky Nun: Related.
• downrep_nation: can the input be a string?
• Adnan: @downrep_nation Hmm, how would you want to do that then? If you can do it with multidigit integers, than it's fine.
• downrep_nation: ints are very limited by size and strings are not. thats why im asking
• Adnan: @downrep_nation Okay, so how do you want to provide the input then for the last test case? 11101010100100 doesn't seem correct for input :p.

Answer 1

Mathematica, 24 bytes

MinimalBy[Length]@*Split

This is a composition of two functions that can be applied to a list. Split takes all groups of consecutive numbers, and MinimalBy[Length] selects those with minimal length.

• Martin Ender: Damn, just fired up Mathematica to test this... +1 :)
• Adnan: Now I'm wondering if I haven't made this too trivial :/.

Answer 2

Pyth, (削除) 14 (削除ここまで) (削除) 12 (削除ここまで) 11

mM_MmhbrQ8

Test Suite

2 bytes thanks to Jakube! And 1 byte thanks to isaacg!

Unfortunately, run length decoding doesn't quite do what we want it to do, but it will work with a minor workaround, but that makes it slightly longer than the manual implementation:

mr]d9.mhbrQ8

Credit to Jakube for finding this out.

• Jakube: Btw, rld works, but you have to provide a list of pairs: mr]d9.mhbrQ8
• izzyg: More about run length decoding: Run length decoding expects a list of pairs, such as what run length encoding returns, not an individual pair.
• izzyg: .bmYN == mM_M
• FryAmTheEggman: @isaacg Ah, right that makes sense, I guess I wasn't thinking through that enough. Also that map trick is neat, thanks!

Answer 3

Haskell, 38 bytes

import Data.Lists
argmins length.group

Usage example: argmins length.group $ [3,3,3,4,4,4,4,5,5,4,4,3,3,4,4] -> [[4,4],[3,3],[4,4],[5,5]].

Build groups of equal elements and find those with minimal length.

• lynn: Where’s the documentation for Data.Lists?
• nimi: @Lynn: Data.Lists. See also the links to the re-exported modules on this page. argmins for example is from Data.List.Extras.Agrmax.

Answer 4

Python 2, 120 bytes

import re
r=[x.group().split()for x in re.finditer(r'(\d+ )1円*',input())]
print[x for x in r if len(x)==min(map(len,r))]

Takes input as a string of space-separated integers with a trailing space, and outputs a list of lists of strings. The strategy is to find groups using the regex (\d+ )1円* (which matches one or more space-separated integers, with a trailing space), then split them on spaces into lists of integers, and print those groups whose length is equal to the minimum group length.

Try it online

Answer 5

Python 2.x, 303 bytes

x=input()
r=[q[2]for q in filter(lambda l:(len(l[2])>0)&((l[0]<1)or(x[l[0]-1]!=x[l[0]]))&((l[1]>len(x)-1)or(x[l[1]]!=x[l[1]-1]))&(len(filter(lambda k:k==l[2][0],l[2]))==len(l[2])),[(a,b,x[a:b])for a in range(0,len(x))for b in range(0,len(x)+1)])]
print filter(lambda k:len(k)==min([len(s)for s in r]),r)

Ugliest. Code. Ever.

Input: An array in the format r'\[(\d,)*(\d,?)?\]'
In other words, a python array of numbers

Output: An array of arrays (the smallest groups), in the order that they appear in the input array

Additional Coincidental Features (Features that I did not intend to make):

• The input can be an empty array; the output will be an empty array.
• By changing min to max, it will return an array of the largest groups.
• If you just do print r, it will print all of the groups in order.

Answer 6

Retina, (削除) 91 (削除ここまで) (削除) 85 (削除ここまで) (削除) 80 (削除ここまで) (削除) 79 (削除ここまで) (削除) 77 (削除ここまで) (削除) 76 (削除ここまで) (削除) 75 (削除ここまで) 74 bytes

M!`\b(\d+)(,1円\b)*
(,()|.)+
$#2:$&
O#`.+
s`^(.*\b(.+:).*)¶(?!2円).+
1ドル
.+:
<empty-line>

Try it online!

Explanation

The input is 1,1,10,10,10,100,100.

The first line matches groups with same terms:

M!`\b(\d+)(,1円\b)*

The input becomes:

1,1
10,10,10
100,100

The following two lines prepend the number of commas to the line:

(,()|.)+
$#2:$&

The input becomes:

1:1,1
2:10,10,10
1:100,100

Then they are sorted by this line, which looks for the first number as index:

O#`.+

The input becomes:

1:1,1
1:100,100
2:10,10,10

Then these two lines find the place where the length is different, and remove everything onwards:

s`^(.*\b(.+:).*)¶(?!2円).+
1ドル

The input becomes:

1:1,1
1:100,100

Then the numbers are removed by these two lines:

.+:
<empty-line>

Where the input becomes:

1,1
100,100

Answer 7

C#, 204 bytes

void f(string o){var r=Regex.Matches(o,@"([0-9])1円{0,}").Cast<Match>().OrderBy(x=>x.Groups[0].Value.Length);foreach(var s in r){foreach(var z in r)if(s.Length>z.Length)return;Console.WriteLine(s.Value);}}

I don't know if using a string is fair considering all the golfing esolangs get their input in the same way but he requested array input.

thats how it looks

ungolfed:

 public static void f(string inp)
 {
 var r = Regex.Matches(inp, @"([0-9])1円{0,}").Cast<Match>().OrderBy(x => x.Groups[0].Value.Length);
 foreach (Match s in r)
 {
 foreach (Match z in r)
 if (s.Length > z.Length)
 return;
 Console.WriteLine(s.Value);
 }
 }

I need a way to get the smallest matches for the match array, most of my bytes are wasted there, help appreciated. I'm trying to get into LINQ and lambda stuff.

• Leaky Nun: Technically a string is an array.

Answer 8

R, (削除) 70 (削除ここまで) 65 bytes

Edit: -5 bytes thanks to Giuseppe

function(x)(y=split(x,diffinv(!!diff(x))))[min(l<-lengths(y))==l]

Try it online!

This feels rather clunky, so I won't be surprised if there's a much slicker R way to do this... Edit: there is...

function(x) # x is vector of values;
(y= # define y as
 split(x, # groups of values of x that share the same
 cumsum( # cumulative sum of
 x!=c(0,x)))) # 1 if different to the next element;
[ # now, get element(s) of y
 (l=lengths(y)) # whose length(s)
 ==min(l[l>0])] # equal the smallest non-zero lengths of y

• Giuseppe: Would rle be handy here?
• Giuseppe: this is 58
• Dominic van Essen: @Giuseppe - Nice! And 56 bytes by including the variable defs into the function def. Post it. I thought about rle, but didn't try it because it seemed to me that it would be too verbose to 'rebuild' the groups. Obviously I was wrong...
• Giuseppe: Done! And as a bonus 65 bytes tweaking your approach.

Answer 9

MATL, 15 bytes

Y'tX<tb=bw)wTX"

Try it online

Input is a vector, like [1 2 3 4], and output is a matrix where each column is one of the smallest groups, e.g.:

1 100
1 100

for the third test case.

Explanation:

Y' %// Run length encoding, gives 2 vectors of group-lengths and values
t %// Duplicate group lengths
X< %// Minimum group length
tb %// Duplicate and get vector of group lengths to the top
= %// Find which group lengths are equal to the minimum
bw) %// And get the values of those groups
wTX" %// Repeats the matrix of minimum-length-group values by the minimum group length

Answer 10

Jelly, (削除) 22 (削除ここまで) (削除) 17 (削除ここまで) 16 bytes

I0;œṗ1L=\ÐfL€Ṃ$$

Try it online!

I0;œṗ1L=\ÐfL€Ṃ$$ Main link. List: z = [a,b,c,...]
I Compute [b-a, c-b, d-c, ...]
 0; Concatenate 0 in front: [0, b-a, c-b, d-c, ...]
 œṗ Split z where the corresponding item in the above array is not zero.
 L=\Ðf Filter sublists whose length equal:
 L€Ṃ$ the minimum length throughout the list.
 1 $ (grammar stuffs)

Answer 11

JavaScript (ES6), 106

a=>(a.map((v,i)=>v==a[i-1]?g.push(v):h.push(g=[v]),h=[]),h.filter(x=>!x[Math.min(...h.map(x=>x.length))]))

Test

f=a=>(a.map((v,i)=>v==a[i-1]?g.push(v):h.push(g=[v]),h=[]),h.filter(x=>!x[Math.min(...h.map(x=>x.length))]))
console.log=x=>O.textContent+=x+'\n'
;[[1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1]
, [3, 3, 3, 4, 4, 4, 4, 5, 5, 4, 4, 3, 3, 4, 4]
, [1, 1, 2, 2, 3, 3, 4]
, [1]
, [1, 1, 10, 10, 10, 100, 100]]
.forEach(t=>console.log(t+' -> '+f(t).join` `))

<pre id=O></pre>

• Leaky Nun: Does h.map(length) not work?
• edc65: @KennyLau no, for it to work length should be a function with the string as argument, not a method of string
• Not that Charles: @edc65 Actually, a property of String. Not a method.

Answer 12

JavaScript (ES6), 113 bytes

a=>a.map(n=>n==c[0]?c.push(n):b.push(c=[n]),c=b=[])&&b.sort((a,b)=>a[l]-b[l],l='length').filter(e=>e[l]==b[0][l])

Answer 13

APL, 25 chars

{z/⍨(⊢=⌊/)≢ ̈z←(1,2≠/⍵)⊂⍵}

In English:

• put in z the argument split where a number is different than the one preceding;
• compute the length of each subarray
• compare the minimum with each of the lengths producing a boolean...
• ... that is used to reduce z

• Adalynn: Commute. Commute. Commute! ⍵⊂⍨1,2≠/⍵

Answer 14

J, 31 bytes

[:(#~[:(=<./)#@>)]<;.1~1,2~:/\]

Input is an array of values. Output is an array of boxed arrays.

Usage

 f =: [:(#~[:(=<./)#@>)]<;.1~1,2~:/\]
 f 1 1 2 2 3 3 4
┌─┐
│4│
└─┘
 f 3 3 3 4 4 4 4 5 5 4 4 3 3 4 4
┌───┬───┬───┬───┐
│5 5│4 4│3 3│4 4│
└───┴───┴───┴───┘

Explanation

[:(#~[:(=<./)#@>)]<;.1~1,2~:/\] Input: s
 ] Identity function, get s
 2 The constant 2
 \ Operate on each overlapping sublist of size 2
 ~:/ Check if each pair is unequal, 1 if true else 0
 1, Prepend a 1 to that list
 ] Identity function, get s
 <;.1~ Using the list above, chop s at each true index
[:( ) Operate on the sublists
 #@> Get the length of each sublist
 [:( ) Operate on the length of each sublist
 <./ Get the minimum length
 = Mark each index as 1 if equal to the min length else 0
 #~ Copy only the sublists with min length and return

Answer 15

Clojure, 65 bytes

#(let[G(group-by count(partition-by + %))](G(apply min(keys G))))

Uses + as identity function as (+ 5) is 5 :) The rest should be obvious, G is a hash-map used as a function and given a key it returns the corresponding value.

Answer 16

Brachylog, 6 bytes

ḅlolgh

Try it online!

Input through the input variable and output through the output variable.

ḅ The list of runs of consecutive equal elements of
 the input
 lo sorted by length
 lg and grouped by length
 has the output variable
 h as its first element.

Although, unlike ḅ, g groups non-consecutive equal elements, the lo is still necessary to find the group with the shortest lengths, and it works because the order of groups in the output from g is determined by the position of the first element of each group, so that ghm could function as sort of a deduplicate by pseudo-metapredicate.

Answer 17

Perl 5 -MList::Util=pairkeys,min -a, 69 bytes

map$r{y/ //}.="[ $_]",pairkeys"@F "=~/((\d+ )2円*)/g;say$r{min keys%r}

Try it online!

Answer 18

Husk, 4 bytes

←kLg

Try it online!

Answer 19

Jelly, 5 bytes

ŒgLÐṂ

Try it online!

Answer 20

05AB1E, 5 bytes

γé¬gù

Try it online!

Commented:

γ # split into chunks of equal adjacent elements
 é # sort the chunks by length
 ¬ # get the shortest (first) chunk without popping the list
 g # take the length of that chunk
 ù # keep all chunks with this length

Try it with step-by-step output!

Answer 21

Japt -g, 4 bytes

Outputs a 2D-array.

òÎüÊ

Try it

òÎüÊ :Implicit input of array
ò :Partition between elements where
 Î : The sign of their difference is truthy (not 0)
 ü :Group and sort by
 Ê : Length
 :Implicit output of first element

Answer 22

R, 56 bytes

function(x,r=rle(x),l=min(r$l))lapply(r$v[r$l==l],rep,l)

Try it online!

-2 bytes thanks to Dominic van Essen. Uses rle and rep to collapse and reconstruct the array.

Answer 23

K (ngn/k), 24 bytes

{{x=&/x:#'x}#(&~=':x)_x}

Try it online!

• (&~=':x)_x split the input on indices where the values change
• {x=&/x:#'x}# filter down to items of the minimum length

Answer 24

Factor + grouping.extras, 36 bytes

[ [ ] group-by values all-shortest ]

Try it online!

• [ ] group-by values Split a sequence into groups of contiguous equal elements.
• all-shortest Take all the shortest groups.

[ stable-slices all-shortest ] would work except it doesn't have the right behavior for 1-element inputs.

Answer 25

Nekomata, 2 bytes

ĉş

Attempt This Online!

ĉ Split the input into chunks of equal elements
 ş Find the shortest chunk

Answer 26

JavaScript (Node.js), 97 bytes

x=>eval(`[[${x}]]`.replace(/\b(\d+),(?!1円\b)/g,'1ドル],[')).filter((t,_,x)=>!x.some(y=>t[y.length]))

Try it online!

• l4m2: Not sure if this works

Answer 27

Ruby, 47 bytes

->a{a.slice_when(&:!=).group_by(&:size).min[1]}

Attempt This Online!

Answer 28

PowerShell for Windows, 88 bytes

$h=@{}
$args|%{$i+=$p-ne$_;$h.+$i+=,$p=$_}
($g=@($h|% v*|sort c*))|? c*t -eq $g[0].count

Try it online!

The script uses the Powershell alias sort that should be sort-object with Linux.

Less golfed:

$hashTable=@{}
$args|foreach-object{
 $i += ($prev -ne $_)
 $prev = $_
 $hashTable.+$i += ,$prev
}
$groups=@($hashTable|foreach-object Values|sort-object Count)
$groups|where-object count -eq $groups[0].count

Answer 29

Arturo, 46 bytes

$=>[c:chunk&=>[&]select c=>[=size&size min c]]

Try it