17
\$\begingroup\$

Grouping takes a list and splits it into new lists of equal adjacent elements. For example

[1,1,2,1,1] -> [[1,1],[2],[1,1]]

If you then take the length of these groups you get a new list of integers

[1,1,2,1,1] -> [2,1,2]

Your task is to write a program that takes a list of positive integers and find the number of times you can group and length it before the resulting list has a single element. For example the list [1,2,3,3,2,1] can be regrouped 4 times

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

This is so answers will be scored in bytes with fewer bytes being better.

Test cases

[1,2,3,3,2,1] -> 4
[1,2,3,4,5,6,7] -> 2
[1,1,1,1,1,1] -> 1
[2] -> 0
[1,2,4] -> 2
[1,2,2,1,1,2] -> 4
[1,2,2,1,1,2,1,2,2] -> 5
[1] -> 0
\$\endgroup\$
  • 3
    \$\begingroup\$ This is basically run-length encoding without storing the values. \$\endgroup\$ – 12Me21 Feb 23 '18 at 23:09
  • \$\begingroup\$ [1] is a valid input and should give 0, correct? \$\endgroup\$ – ETHproductions Feb 24 '18 at 1:43
  • \$\begingroup\$ @ETHproductions Yes, I'll add that because it is a bit of a tricky case. \$\endgroup\$ – Sriotchilism O'Zaic Feb 24 '18 at 2:11

27 Answers 27

7
\$\begingroup\$

Haskell, 49 bytes

import Data.List
f[_]=0
f c=1+f(length<$>group c)

Try it online!

\$\endgroup\$
5
\$\begingroup\$

CJam, 18 bytes

q~_,{_e`0f=}*]:,1#

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Japt, 12 bytes

ÊÉ©1+ßUò¦ ml

Test it online!

Explanation

 Ê É © 1+ßUò¦  ml
Ul -1&&1+ßUò!= ml    Ungolfed
                     Implicit: U = input array
Ul -1                Take U.length - 1.
     &&              If this is non-zero:
          Uò!=         Split U between non-equal elements.
               ml      Take the length of each run of equal elements.
         ß             Run the entire program again on the resulting array.
       1+              Add one to the return value.

Recursion is a really non-conventional approach for Japt, but it seems to be 4 bytes shorter than the next alternative...

\$\endgroup\$
  • \$\begingroup\$ @Shaggy My 16-byte version with F.a() is still accessible through the revision history. I'd love to see your 14-byter though! \$\endgroup\$ – ETHproductions Feb 24 '18 at 2:31
3
\$\begingroup\$

Brachylog, 12 bytes

;.{ḅlᵐ}ⁱ⁾l1∧

Try it online!

Explanation

;.{   }ⁱ⁾        Iterate Output times the following predicate on the input:
   ḅ               Group consecutive equal elements together
    lᵐ             Map length
         l1∧     The result of this iteration must have length 1
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 108 bytes

j,k,n;f(A,l)int*A;{for(j=k=n=0;j<l;j++)if(n++,A[j]-A[k])A[k++]=--n,A[k]=A[j],n=1;A=l>1?-~f(A,k,A[k++]=n):0;}

Try it online!

Explanation

j,k,n;                // array pos, group pos, group val
f(A,l)int*A;{         // function takes array and length
 for(j=k=n=0;j<l;j++) // initialize, loop through array
  if(n++,             // increase n (*), check if group ended
  A[j]-A[k])          // group ended
   A[k++]=--n,        // advance group pos, decrease n, counteracting (*)
   A[k]=A[j],         // store new group type
   n=1;               // group is at least one long
 A=l>1?               // check if array length is larger than one
  -~f(A,k,A[k++]=n)   // fix last group length, enter recursion
  :0;}                // array length is less than two, return zero

Try it online!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 67 65 63 bytes

f=a=>a[1]?1+f(q=j=i=[],a.map(x=>x^a[++i]?j=!q.push(++j):++j)):0

Oddly enough, JavaScript and Japt seem to have the same shortest algorithm for once...

\$\endgroup\$
2
\$\begingroup\$

K (oK), 20 19 bytes

Solution:

#2_{#:'(&~~':x)_x}\

Try it online!

Examples:

#2_{#:'(&~~':x)_x}\1 2 3 3 2 1
4
#2_{#:'(&~~':x)_x}\1 2 3 4 5 6 7
2
#2_{#:'(&~~':x)_x}\1 1 1 1 1 1
1
#2_{#:'(&~~':x)_x}\1#2
0
#2_{#:'(&~~':x)_x}\1 2 4
2

Explanation:

This one is pretty simple, am wondering if there is an even better approach though... Find the indices where the input differs, split at those indices and then count the length of each sub-list. Iterate until results converge to 1.

#2_{#:'(&~~':x)_x}\ / the solution
   {             }\ / scan over lambda until results converge
                x   / implicit input
               _    / cut at indices
       (      )     / do this together
         ~~':x      / differ... not (~) match (~) each-previous (':) x)
        &           / indices where true
    #:'             / count (#:) each (')
 2_                 / drop first two results
#                   / count result

Notes:

The following 14 byte solution works for all except a single-item list:

#1_(-':&~~':)\

Try it online!

\$\endgroup\$
2
\$\begingroup\$

J, 25 23 bytes

1 byte saved thanks to streetster

1 byte saved thanks to FrownyFrog

2#@}.#;.1@(0,2=/\])^:a:

Try it online!

Initial solution:

_2+[:#(#;.1~1,2~:/\])^:a:

Try it online!

Explanation

      (               )^:a: - repeat until result stops changing, store each iteration
        ;.1~                - cut the input (args swapped)              
            1,2~:/\]      - where the items are no longer the same
       #                    - and take the length of the sublists
 2+[:#                      - finally subtract 2 from the number of steps
\$\endgroup\$
  • 1
    \$\begingroup\$ Can you do 'drop two' then 'count' rather than _2+ to save a byte? \$\endgroup\$ – streetster Feb 24 '18 at 10:08
  • 1
    \$\begingroup\$ I think #;.1@(0,2=/\]) saves 1 byte. \$\endgroup\$ – FrownyFrog Feb 24 '18 at 10:33
  • \$\begingroup\$ @ FrownyFrog Yes, it does. Thank you! \$\endgroup\$ – Galen Ivanov Feb 24 '18 at 12:09
  • \$\begingroup\$ @streetster Yes, It helps to save a byte. Thank you! \$\endgroup\$ – Galen Ivanov Feb 24 '18 at 12:14
2
\$\begingroup\$

Stax, 9 bytes

ÆÑfá╒]`*Ä

Run and debug it online

The ascii representation of the same program is this.

{D}{|RMHgf%

This uses a stax feature called a generator that produces value according to transformation and filter blocks.

{ }            the filter for the generator
 D             tail of array; this is truthy for length >= 2
   {    gf     generator block - termination condition is when the filter fails
    |R         run-length encode into pairs [element, count]
      M        transpose matrix
       H       last element
          %    length of final generated array
\$\endgroup\$
2
\$\begingroup\$

Python 2, 84 bytes

f=lambda a:len(a)>1and-~f(eval(''.join('1'+',+'[x==y]for x,y in zip(a,a[1:]))+'1,'))

Try it online!

How?

f is a recursive function which, if its input, a, has length 2 or more (len(a)>1) returns 1+f(x)* where x is the group lengths of a; while if its input is length 1 or 0 returns False (equal to 0 in Python) - this is because the right hand side of the and does not get evaluated when the left is falsey.

* -~f(x) is -(-1 - f(x)) but can abut the and unlike 1+f(x) or f(x)+1)

The group lengths are calculated by creating code which is then evaluated with eval(...). The code created is something like 1,1,1+1+1,1,1+1,1, which evaluates to a tuple like (1,1,3,1,2,1).

The code is created by zipping through a and a without its head (...for x, y in zip(a,a[1:]) making x and y each of the adjacent pairs in a. If the pair are equal x==y evaluates to True (1) otherwise False (0) - this result is used to index into the string ,+ yielding + and , respectively and each resulting character is preceded by a 1 ('1'+...) - the whole thing then has a final, trailing 1, appended. For example if a were [5,5,2,9,9,9] then the x,y pairs would be (5,5)(5,2)(2,9)(9,9)(9,9) making the equalities 10011 then the characters would be +,,++, which with the preceding 1s becomes 1+1,1,1+1+ and the final trailing 1, making 1+1,1,1+1+1, which evaluates to (2,1,3) as required.

Note that the trailing , ensures that an input with a single group is evaluated as a tuple rather than an integer (i.e. [3,3] -> 1+1, -> (2) rather than [3,3] -> 1+1 -> 2)

\$\endgroup\$
1
\$\begingroup\$

CJam, 19 bytes

q~{_);}{_e`0f=}w],(

Try it online!

\$\endgroup\$
1
\$\begingroup\$

CJam, 20 bytes

l~{__,(}{e`z0=}w;;],

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 53 50 49 45 bytes

Includes +3 for -p

Give the list of numbers as one line on STDIN

#!/usr/bin/perl -p
s%%$\+=1<s:\d+:$.++x($'-$&and$.=1):eg%eg}{

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Husk, 8 bytes

-1 byte thanks to @Zgarb!

←Vε¡(mLg

Try it online!

Explanation

←Vε¡(mLg)  -- example input: [1,2,3,3,2,1]
   ¡(   )  -- repeatedly apply the function & collect results
    (  g)  -- | group: [[1],[2],[3,3],[2],[1]]
    (mL )  -- | map length: [1,1,2,1,1]
           -- : [[1,2,3,3,2,1],[1,1,2,1,1],[2,1,2],[1,1,1],[3],[1],[1],...
 V         -- index where
  ε        -- | length is <= 1: [0,0,0,0,1,1...
           -- : 5
←          -- decrement: 4
\$\endgroup\$
  • 1
    \$\begingroup\$ ←Vε is a shorter check for finding the singleton list's index. \$\endgroup\$ – Zgarb Feb 24 '18 at 6:46
1
\$\begingroup\$

Jelly, 10 bytes

ŒgL€$ḊпL’

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This fails for [1]. You should be able to fix it using two dequeues / pops instead of _2 \$\endgroup\$ – Mr. Xcoder Feb 24 '18 at 14:48
  • \$\begingroup\$ ÐĿ wasn't a good choice in the first place... Replaced it with a while loop. \$\endgroup\$ – Dennis Feb 24 '18 at 14:55
1
\$\begingroup\$

05AB1E, 9 bytes

[Dg#γ€g]N

Try it online!

Explanation

[Dg#   ]     # loop until the length of the current value is 1
    γ        # split into groups of consecutive equal elements
     €g      # get length of each
        N    # push the iteration variable N
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 32 bytes

Saved 2 bytes thanks to Martin Ender. Using CP-1252 encoding, where ± is one byte.

±{_}=0;±x_:=1+±(Length/@Split@x)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Defining an operator saves two bytes: ±{_}=0;±x_:=1+±(Length/@Split@x) (assuming WindowsANSI encoding) \$\endgroup\$ – Martin Ender Feb 24 '18 at 19:03
1
\$\begingroup\$

Ruby, 54 56 55 54 bytes

g=->l,d=0{l[1]?g[l.chunk(&:i).map{|i,j|j.size},d+1]:d}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

SmileBASIC, 110 108 bytes

DEF R L,J
K=LEN(L)FOR I=1TO K
N=POP(L)IF O-N THEN UNSHIFT L,0
INC L[0]O=N
NEXT
IF I<3THEN?J ELSE R L,J+1
END

Call function as R list,0; output is printed to the console.

\$\endgroup\$
0
\$\begingroup\$

Python 2, 85 bytes

from itertools import*
f=lambda a:~-len(a)and-~f([len(list(v))for k,v in groupby(a)])

Try it online!

\$\endgroup\$
0
\$\begingroup\$

R, 51 45 bytes

f=function(a)"if"(sum(a|1)>1,f(rle(a)$l)+1,0)

Try it online!

Recursively take the length of the run length encoding and increment the counter.

\$\endgroup\$
0
\$\begingroup\$

Retina 0.8.2, 31 bytes

,.*
$&_
}`(\b\d+)(,\1)*\b
$#2
_

Try it online! Link includes test cases. Explanation:

,.*
$&_

If there is a comma, we're going to make another iteration, so append a count character.

}`(\b\d+)(,\1)*\b
$#2

Replace each run with its decremented length. The above stages repeat until there are no commas left.

_

Count the number of iterations.

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 52 bytes

{+($_,*.comb(/(\d+)[" "$0»]*/).map(+*.words)...^1)}

Test it

Expanded:

{  # bare block lambda with implicit parameter 「$_」

  + (              # turn the following into a Numeric (get the count)


      $_,          # seed the sequence with the input

      *.comb(      # turn into a string, and grab things that match:

        /          # regex
          ( \d+ )  # a run of digits (number)
          [
            " "    # a space
                   # (gets inserted between elements of list when stringified)

            $0     # another instance of that number
            »      # make sure it isn't in the middle of a number

          ]*       # get as many as possible
        /
      ).map(
        +*.words  # turn each into a count of numbers
      )

      ...^        # keep doing that until (and throw away last value)

      1           # it gives a value that smart-matches with 1
                  # (single element list)
  )
}
\$\endgroup\$
0
\$\begingroup\$

Brain-Flak, 78 bytes

({}<>)<>({()<(<>{}<(())><>){({}[({})]<>){((<{}>))}{}((){})<>}<>{}({}<>)<>>}{})

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pyth, 9 bytes

ltt.uhMr8

Test suite!

\$\endgroup\$
0
\$\begingroup\$

Kotlin, 123 bytes

Accepts List<Int>.

{var a=it;var b=0;while(a.size>1){var c=a[0];var d=0;with(a){a=listOf();forEach{if(it!=c){a+=d;d=0};d++;c=it};a+=d};b++};b}

More readable:

{ l ->
    var input = l
    var result = 0
    while (input.size > 1) {
        var last = input[0]
        var runSize = 0
        with(input) {
            input = listOf()
            forEach { current ->
                if (current != last) {
                    input += runSize
                    runSize = 0
                }
                runSize++
                last = current
            }
            input += runSize
        }
        result++
    }
    result
}

Try it online!


131 bytes, TIO

{l->var a=l;var b=0;while(a.size>1){var c=a[0];var d=0;a.let{a=arrayListOf();for(e in it){if(e!=c){a+=d;d=0};d++;c=e};a+=d};b++};b}

181 bytes, TIO

Includes 39 for import kotlin.coroutines.experimental.*.

{l->var a=l;var b=0;while(a.size>1){var c=a[0];var d=0;a=buildSequence{for(e in a){if(e!=c){yield(d);d=0;};d++;c=e};yield(d)}.toList();b++};b}
\$\endgroup\$
0
\$\begingroup\$

Red, 140 bytes

func[b][n: 0 while[(length? b)> 1][l: copy[]parse split form b" "[any[copy s[set t string! thru any t](append l length? s)]]b: l n: n + 1]n]

Try it online!

I just wanted to give Red's Parse dialect another try.

Ungolfed

f: func [b] [
    n: 0
    while [(length? b) > 1][
        l: copy []
        parse split form b " " [
            any [copy s [set t string! thru any t]
                (append l length? s)]
        ]
        b: l
        n: n + 1
    ]
    n
]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.