Incrementally Increment Identical Integers

Question

_{Inspired by this Stack Overflow post.}

Given an ascending-sorted array of possibly duplicated integers, your goal is to increment each number by a counter, starting at 0, that resets for each group.

Spec:

• Any numbers may be negative (but if so, they'll be at the beginning, because the array is sorted),
• The array will have at least one element,
• There may be any number of integers in one group
• The groups of numbers have nothing to do with one another

To demonstrate:

[1, 1, 1, 1, 10, 10, 20, 20, 20, 30, 40, 40, 40, 40]

should become this

[1, 2, 3, 4, 10, 11, 20, 21, 22, 30, 40, 41, 42, 43]

because

  1 1 1 1   10 10   20 20 20   30   40 40 40 40
+ 0 1 2 3    0  1    0  1  2    0    0  1  2  3
  -------   -----   --------   --   -----------
  1 2 3 4   10 11   20 21 22   30   40 41 42 43   

Test cases

input -> output
[1, 2, 3] -> [1, 2, 3]
[1, 1, 2, 2, 3, 3] -> [1, 2, 2, 3, 3, 4]
[0, 0, 0, 0, 0] -> [0, 1, 2, 3, 4]
[1, 1, 10, 10, 100, 100, 100, 100] -> [1, 2, 10, 11, 100, 101, 102, 103]
[-5, -5, -5, -5, -4, 4, 4, 4, 4, 9, 9] -> [-5, -4, -3, -2, -4, 4, 5, 6, 7, 9, 10]
[1, 1, 1, 1, 2, 2] -> [1, 2, 3, 4, 2, 3]

Answer 1

BQN, 3 bytes^SBCS

Perfect challenge for BQN's occurence count builtin.

+⟜⊒

Run online!

The modifier ⟜ composes two functions. If there is a single argument (as is the case here), the right function is called on that argument, and then the left function is called with that result and the original argument:

(f⟜g x) ≡ (x f g x)

The builtin ⊒ takes a vector and returns for each element how many times the same value appeared before:

(⊒ 1‿1‿1‿10‿10‿100) ≡ 0‿1‿2‿0‿1‿0

The result of ⊒ is then added element-wise to original input by +:

(1‿1‿1‿10‿10‿100 + 0‿1‿2‿0‿1‿0) ≡ 1‿2‿3‿10‿11‿100

---

Ports of other more interesting answers:

• ⊢+⊒˜-⊐˜, DLosc in Python
• (⊢+˝=⌜×⊒<⌜⊒)˜, Luis Mendo in MATL

Answer 2

Python 3.8, 48 46 bytes

2-byte savings jointly contributed by Jonathan Allan and dingledooper

lambda L,j=1:[n-(j:=j-1)-L.index(n)for n in L]

Try it online!

Explanation

The original 48-byte solution is easier to explain:

lambda L:[n+i-L.index(n)for i,n in enumerate(L)]

Consider each number \$n\$ in the list together with its index \$i\$. Suppose that we are looking at the \$k^{th}\$ occurrence (0-indexed) of the number \$n\$. We want to add \$k\$ to the number. Since identical numbers are adjacent, the index of the \$0^{th}\$ occurrence of \$n\$ will be at index \$i-k\$. This is the result of L.index(n), meaning \$k\$ is i-L.index(n). Add that value to \$n\$ for each element of the list, and we're done.

To get the 46-byte solution, we track the index using a variable instead of enumerate, updating it in the list comprehension using Python 3.8's "walrus operator" :=. We could track the actual index \$i\$:

lambda L,i=-1:[n+(i:=i+1)-L.index(n)for n in L]

but it saves a byte to track \$j \equiv -i\$ instead, because we can initialize it to 1 instead of -1.

Answer 3

J, 9 bytes

+i.@#-i.~

Try it online!

Basically a port of DLosc's python answer, which fits naturally in the array paradigm.

how

Consider 1, 1, 1, 1, 10, 10, 20, 20, 20, 30, 40, 40, 40, 40

• i.~ Index of each element's first appearance:

  0 0 0 0 4 4 6 6 6 9 10 10 10 10
  

• i.@#- Subtract that from 0 1 2 ... n:

  0 1 2 3 0 1 0 1 2 0 0 1 2 3
  

• + Add that to the original input:

  1 2 3 4 10 11 20 21 22 30 40 41 42 43
  

Answer 4

MATL, 7 bytes

t&=XRs+

Try it online! Or verify all test cases

How it works

Consider input [1, 1, 10, 10, 100, 100, 100, 100] as an example.

t    % Implicit input. Duplicate
     % STACK: [1 1 10 10 100 100 100 100], [1 1 10 10 100 100 100 100]
&=   % Matrix of equality comparisons 
     % STACK: [1 1 10 10 100 100 100 100], [1 1 0 0 0 0 0 0
                                            1 1 0 0 0 0 0 0
                                            0 0 1 1 0 0 0 0
                                            0 0 1 1 0 0 0 0
                                            0 0 0 0 1 1 1 1
                                            0 0 0 0 1 1 1 1
                                            0 0 0 0 1 1 1 1
                                            0 0 0 0 1 1 1 1]
XR   % Upper triangular part, without the diagonal
     % STACK: [1 1 10 10 100 100 100 100], [0 1 0 0 0 0 0 0
                                            0 0 0 0 0 0 0 0
                                            0 0 0 1 0 0 0 0
                                            0 0 0 0 0 0 0 0
                                            0 0 0 0 0 1 1 1
                                            0 0 0 0 0 0 1 1
                                            0 0 0 0 0 0 0 1
                                            0 0 0 0 0 0 0 1]
s    % Sum of each column
     % STACK: [1 1 10 10 100 100 100 100], [0 1 0 1 0 1 2 3]
+    % Add, element-wise. Implicit display
     % STACK: [1 2 10 11 100 101 102 103]

Answer 5

Jelly, 5 bytes

ŒɠḶF+

Try it online!

How it works

ŒɠḶF+ - Main link. Takes a list L on the left
Œɠ    - Group run lengths
  Ḷ   - Zero based range
   F  - Flatten
    + - Add elementwise to L

For example, take L = [1, 1, 2, 2, 3, 3]:

• Œɠ: [2, 2, 2]
• Ḷ: [[0, 1], [0, 1], [0, 1]]
• F: [0, 1, 0, 1, 0, 1]
• +: [0, 1, 0, 1, 0, 1] + [1, 1, 2, 2, 3, 3] = [1, 2, 2, 3, 3, 4]

Answer 6

R, 40 33 bytes

Edit: -7 bytes thanks to @Giuseppe.

function(a)a+sequence(rle(a)$l)-1

Try it online!

Answer 7

Haskell + hgl, 11 bytes

gr+>zW(+)nn

Explanation

Most of this is pretty simple

• gr is "group"; it groups a list into a list of equal segments.
• zW is "zip with"; it takes a function and uses it to combine two lists pairwise.
• (+) is "plus"; it adds things.
• nn is "the natural numbers"; an infinite list of all non-negative numbers in order.
• zW(+)nn combines the last 3 into a single thing which takes a list and adds every element with its index.

The last thing here that links gr with zW(+)nn. The +> operator. This operator has a name it's called "Kleisli composition". Regular composition takes functions a -> b and b -> c and produces a third function a -> c, Kleisli composition does very similar. It takes Kleisli morphisms, which are just a particular kind of function, that maps into a monad. So a -> m b where m is a monad would be an example of a function from a to m b, but is a Kleisli morphism from a to b.

So Kleisli composition takes a function a -> m b and a function b -> m c and produces a function a -> m c where m is some monad.

This is in fact sort of the fundamental essence of a monad, that Kleisli composition forms a category. So how are we using it here?

Well we have gr :: List a -> List (List a) and zW(+)nn :: List a -> List a and the thing we want is List a -> List a. A naive way to do it would be to group the whole thing map across each element and the concat everything back up:

jn<m(zW(+)nn)<gr

However an experienced Haskell golfer will notice that map and then concat is exactly the monad behavior of the List. So we could potentially get a bind to do the concat and the map in one go.

And now if we look at the types we can see they fit the shape of Kleisli morphisms. So we can actually, compose, map and concat all at once using Kleisli composition.

Answer 8

Scala, 43 bytes

s=>s.indices.map(i=>s(i)+i-s.indexOf(s(i)))

Try it online!

A port of DLosc's great answer. Go upvote that!

My original answer, 48 bytes

s=>s.distinct.flatMap(x=>x to x-1+s.count(x.==))

Try it online!

This one gets distinct elements, then for every element x, it makes a range from x to x + n, where n is the number of occurrences of x.

Answer 9

C (tcc), 56 54 bytes

c;f(int*p,int*q){for(c=0;p-q;*p+=++c)c*=!(*p-*++p-c);}

Try it online!

• -2 bytes thanks to pxeger

This is a rather straightforward port of my suboptimal Python answer. Takes a pointer to the beginning and end of the array.

Explanation

c;  /* int c; (thanks pxeger) */
f(
    int *p,  /* pointer to the first integer */
    int *q   /* pointer to the last integer */
) {
    for (
        c=0;  /* initialise the increment */
        p-q;  /* reached the end? (if so, stop) */

        /* note: these run out of order */
                         *p+=++c)
        c*=!(*p-*++p-c);
        /*
            equivalent to:
                int original_p0 = p[0] - c;  // undo increment
                if (original_p0 != p[1]) {
                    c = 0;  // different, so reset counter
                }
                p[1] += c;
                c += 1;
                p += 1; // move to next p
        */
}

Answer 10

R, 31 bytes

function(a)a+seq(!a)-match(a,a)

Try it online!

Port of Jonah's J answer. Uses 1-based indices but it makes no difference.

Test harness taken from pajonk's answer.

Answer 11

Husk, 6 bytes

ṁGo→Kg

Try it online!

     g  # group equal elements
ṁ       # then map the following onto each group
        # (concatenating the results):
 G      #   scan from left
        #   (arg1=result so far, arg2=next element)
  o     #   combination of 2 functions:
    K   #     constant function (= arg1)
   →    #     incremented

Answer 12

Add++, 26 23 bytes

L,dBG€bL€RbFz£+dbL1Xz£_

Try it online!

Explained

L,dBG€bL€RbFz£+dbL1Xz£_
L,                       # create a lambda that:
  d                      # pushes two copies of the input
   BG                    # ... groups the second on consecutive items
     €bL                 # ... gets the length of each of those groups
        €R               # ... creates the range [1...n] for each of those lengths (add++ doesn't have a range [0...n) built-in for some reason dang it caird.)
          bF             # ... flattens that list
            z            # and zips it with the original input. This creates a list of items and how much to increment by
             £+          # now, reduce each item by addition
               dbL       # and push the length of the list, keeping a copy on the stack of the original list
                  1X     # push a list of length(^) 1s
                    z£_  # and subtract that from each item in the other list (this is just to account for the fact that there's no [0...n) built-in)

Answer 13

Prolog (SWI), 75 66 bytes

B+A,[C]-->[A],{C is A+B},B+1+A;[X],{C=X},1+X.
_+_-->[].
a-->0+x,!.

Try it online!

This program can be run by calling the grammar a//0 to parse the input list. The remainder after parsing will be unified with the output list.

Answer 14

Jelly, 5 bytes

+ċṪ$Ƥ

A monadic Link accepting a sorted list of integers that yields a list of integers.

Try it online!

How?

+ċṪ$Ƥ - Link: list of integers, A
    Ƥ - for prefixes of A:
   $  -   last two links as a monad, f(prefix):
  Ṫ   -     pop off the tail from the prefix
 ċ    -     count occurrences of that in the remaining prefix
+     - A add that (vectorises)

Answer 15

Python 3, 61 60 bytes

I wrote this answer to make sure my algorithm was sound, before I implemented it in C.

def f(a,b=.5,c=0):
 for d in a:c*=not d-b;yield d+c;c+=1;b=d

Try it online!

Explanation

def f(
    a,     # input list
    b=.5,  # previous value
    c=0    # consecutive counter
):
    for d in a:
        c *= not d-b;  # if d and b are different, c = 0
        yield d + c;
        c += 1;
        b = d          # next loop, this'll be the previous value

Answer 16

Perl 5, 37 bytes

s/-?\d+/$&-$f?$i=0:$i++;$i+($f=$&)/ge

Try it online!

Answer 17

Zsh, 38 bytes

p=.5
for x;echo $[(c=p-x?0:c+1)+(p=x)]

Attempt This Online!

I think there might a solution abusing mv's backup functionality like this answer, but I can't work out how.

Answer 18

APL (Dyalog Unicode), 22 17 10 bytes

Saved 7 bytes thanks to ovs!

∊{⊂⍺+⍳≢⍵}⌸

Try it online!

Answer 19

Perl 5 + -p, 12 bytes

$_+=$h{$_}++

Try it online!

Answer 20

Python + Pandas, 40 bytes

lambda L:S(L)+S(L).groupby(L).cumcount()

The code doesn't run on TIO, since it's pandas...

But anyway, here is the code.

Answer 21

x86-64 machine code, 15 bytes

3b 06 74 02 31 c9 ad 29 4e fc ff cf e0 f2 c3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the length of the array in RDI and the address of the array of 32-bit integers in RSI. The starting point is after the first 4 bytes.

Assembly:

.global f
repeat:
    cmp eax, [rsi]      # Compare last value and current value
    je skip             # Jump if they are equal
f:
    xor ecx, ecx        # (If not equal, or at the start) ECX = 0
skip:
    lodsd               # Put the current value in EAX, and advance the pointer
    sub [rsi-4], ecx    # Subtract ECX from the (same) value
    dec edi             # Count down from the length
    loopnz repeat       # Jump back if not finished, also reducing ECX by 1
    ret                 # Return

Here is another solution I found, at 16 bytes, taking the arguments in the opposite order:

.global f
f:
    mov eax, edx
repeat:
    cmpxchg [rdi], edx
    cmovne edx, eax
    inc edx
    scasd
    dec esi
    jnz repeat
    ret

Answer 22

Vyxal, 5 bytes

Ġvẏf+

Try it Online!

-1 thanks to lyxal

Ġ     # Group runs of identical chars
 vẏf  # 0...n each and flatten
    + # Add to input

Port of caird coinheringaahing's answer.

Answer 23

JavaScript (ES6), 51 bytes

x=>x.map((y,i)=>y+x.reduce((r,z,k)=>r+=z==y&k<i,0))

Answer 24

APL+WIN, 22 bytes

Prompts for input vector

v+¯1++⌿p×+\p←<⍀v∘.=v←⎕

Try it online! Thanks to Dyalog Classic

Answer 25

Charcoal, 10 bytes

ＩＥθ⁺ι№…θκι

Try it online! Link is to verbose version of code. Does not require the array to be sorted or grouped. Explanation:

  θ         Input array
 Ｅ          Map over elements
    ι       Current element
   ⁺        Plus
     №      Count of
         ι  Current element in
      …θκ   Prefix of input
Ｉ           Cast to string
            Implicitly print

Alternative approach, also 10 bytes, but requires the array to be grouped:

ＩＥθ⁺ι⁻κ⌕θι

Try it online! Link is to verbose version of code. Explanation:

  θ         Input array
 Ｅ          Map over elements
    ι       Current element
   ⁺        Plus
      κ     Current index
     ⁻      Minus
       ⌕    First index of
         ι  Current element in
        θ   Input array
Ｉ           Cast to string
            Implicitly print

Answer 26

Retina 0.8.2, 68 bytes

r(`(?<=(^|,)(\3,)*)((-)?\d+)
#$#2$*1$4$3$*
+`1-1
-
#(-)?(1*)-?
$1$.2

Try it online! Link includes test cases. Explanation:

r(`

Use right-to-left matching for the whole script, as that allows the matches to be specified slightly more golfily.

(?<=(^|,)(\3,)*)((-)?\d+)

Match each integer, and count how many times it's been repeated.

#$#2$*1$4$3$*

Replace each integer with a marker #, the repetition count in unary, and the integer in unary. Note that if the integer is positive this already adds the count to the integer.

+`1-1
-

If the integer was negative then find the difference between it and the count.

#(-)?(1*)-?
$1$.2

Convert the integer back to decimal, ignoring a trailing - sign, which indicates that the count was at least as large as the absolute value of the integer and therefore the result is no longer negative.

28 bytes in Retina 1 if only non-negative integers need to be supported:

r`(?<=(\2,)*)(\d+)
$.(*_$#1*

Try it online! Link includes test cases. Explanation:

r`(?<=(\2,)*)(\d+)

From right to left, match each integer, and count how many times it's been repeated.

$.(*_$#1*

Add the number of repetitions to the integer.

Answer 27

Factor, 44 bytes

[ dup '[ over + swap _ index - ] map-index ]

Try it online!

Port of @Dlosc's Python answer.

dup '[ ... _ ... ] slots a copy of the input into the quotation at the _. map-index is like map except it also places the index on the stack in addition to the element.

There were a lot of other approaches and attempts; the last three are just longer versions of the above.

[ histogram >alist [ first2 over + 1 <range> ] map-concat ]
[ [ ] group-by values [ dup length iota v+ ] map-flat ]
[ histogram [ over + 1 <range> ] f assoc>map concat ]
[ dup '[ _ overd index -rot + - abs ] map-index ]
[| l | l [ | n i | n i + l index - ] map-index ]
[| l | l [ over + swap l index - ] map-index ]

Answer 28

Japt, 5 bytes

ü ®í+

Try it

ü      - group
  ®    - for each
   í+  - zip with index then sum

Answer 29

J-uby, 66 61 bytes

:group_by+:next|:values|:*&(:zip%(:size|:*)|:*&:sum)|:flatten

Try it online!

Surely there is a way to improve this. Yep, + is very useful.

Answer 30

Ruby, 37 bytes

Requires Ruby version 2.7 or newer.

->a{a.tally.flat_map{[*_1.._1+_2-1]}}

Attempt This Online!

A quick rundown:

->a{X} is an anonymous lambda function taking a parameter a and returning X.

tally returns a hash with each unique number in the input list and the number of times that number appeared in the list.

[*1..4] returns [1,2,3,4]. flat_map returns a flattened list from the result of the given {code block} being run on each number/count pair returned by tally, where _1 is a placeholder for the number and _2 is the count. So for example with an array with 5 2s, [*_1.._1+_2-1] returns [2,3,4,5,6].