# Incrementally Increment Identical Integers

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]

• Can there be elements repeated "outside" their group, such as [1, 1, 2, 2, 1, 1]? What would the output for that be, [1, 2, 2, 3, 1, 2] or [1, 2, 2, 3, 3, 4]? Jan 1 at 19:25
• @cairdcoinheringaahing No, because the input is sorted. Jan 1 at 19:26
• What happens to [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 19, 19, 20, 20] Jan 3 at 7:52
• Related Jan 3 at 14:14
• @Stilez you'd add [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0, 1] to it, to get [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 19, 20, 20, 21]
– user110034
Jan 3 at 15:11

# BQN, 3 bytesSBCS

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:

• Very concise, I don't understand it but it looks cool. If possible, will you please provide a small explanation? :)
– user110034
Jan 1 at 21:46
• Thank you for the explanation. Brilliant.
– user110034
Jan 1 at 23:28

# 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.

• Save a couple of bytes by moving to 3.8+ and using the walrus operator with lambda L,i=1:[n-(i:=i-1)-L.index(n)for n in L] (dingledooper also posted this a few seconds after me, so dual credit is fine!) Jan 1 at 20:13
• I figured there might be something with := that was shorter than enumerate, but counting backward to save a byte in the initialization is really clever! Jan 1 at 20:49

# 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


# MATL, 7 bytes

t&=XRs+


### 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]


# 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]
• Wow, this is awesome. I can't believe it can be done with so little code! :D
– user110034
Jan 1 at 19:13

# 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.

# R, 40 33 bytes

Edit: -7 bytes thanks to @Giuseppe.

function(a)a+sequence(rle(a)$l)-1  Try it online! • 33 bytes Jan 1 at 19:55 • @Giuseppe Ah, the sequence function... Forgot about it. Thanks! Jan 1 at 20:01 • 31 bytes porting this, or at least its explanation. Jan 1 at 20:44 • @Giuseppe - i think it's distinct enough for a separate answer. Jan 1 at 21:12 # 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. # 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! 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 */ }  • You can declare c outside the function so you don't need the int: Try it online! Jan 1 at 20:34 • @pxeger I knew there was some kind of trick for that! Thanks. Jan 1 at 20:37 • I was also going to suggest removing the ints from the function parameters, but I don't really understand why you need it. Jan 1 at 20:45 • @pxeger I couldn't get it to compile with them gone. I shouldn't need them. Jan 1 at 20:45 • Fails for the second test case and similar, btw you can omit parameter type in Clang. Jan 1 at 22:16 # 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. • -1 byte – Maël Jan 2 at 19:45 • That won't work; try it with iiii(5). R functions sometimes have different behavior with length-one input (sample is another), to the chagrin of R golfers. Jan 2 at 20:09 • My bad! Thanks for the explanation ;) – Maël Jan 2 at 20: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  # 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)  • Wow, I see a lot of money in that code :P - Will you please provide a small explanation? They're very interesting. – user110034 Jan 1 at 23:57 • upvote later - used all my votes on other answers :) – user110034 Jan 1 at 23:58 • @richardec of course, I'll write up an explanation - I was actually in the process of doing so and found a way to shave 3 bytes off lol Jan 1 at 23:59 # 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)


# 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


s/-?\d+/$&-$f?$i=0:$i++;$i+($f=$&)/ge  Try it online! # APL (Dyalog Unicode), 22 17 10 bytes Saved 7 bytes thanks to ovs! ∊{⊂⍺+⍳≢⍵}⌸  Try it online! • Your first approach can be simplified with the Key operator ⌸ to ∊{⊂⍺+⍳≢⍵}⌸ – ovs Jan 1 at 22:51 • @ovs Nice, thanks! – user Jan 1 at 23:05 # Perl 5 + -p, 12 bytes $_+=$h{$_}++


Try it online!

# 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.

• Haha, this is nice ;)
– user110034
Jan 2 at 15:23
• @richardec Yup! Jan 4 at 4:52

# Prolog (SWI), 75 bytes

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


Try it online!

This program can be run by calling the predicate */2 with the first argument being the input list. The second argument will be unified with the output list.

# 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

• Wow, this is a language-ish I haven't head of. Cool, thank you! :D
– user110034
Jan 2 at 15:24

# Vyxal, 5 bytes

Ġvẏf+


Try it Online!

-1 thanks to lyxal

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


• Try it Online! for 5 bytes Jan 2 at 3:08

# JavaScript (ES6), 51 bytes

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

• x=>x.map((y,i)=>x.reduce((r,z,k)=>r+=z==y&k<i,y))
– tsh
Jan 2 at 3:29

# APL+WIN, 22 bytes

Prompts for input vector

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


Try it online! Thanks to Dyalog Classic

# 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

• "Does not require the array to be sorted" - That's a cool bonus!
– user110034
Jan 1 at 21:55

# 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.

# Factor, 44 bytes

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


Try it online!

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 ]


# 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. # Japt, 5 bytes ü ®í+  Try it ü - group ® - for each í+ - zip with index then sum  # Wolfram Language (Mathematica), 28 bytes (Clear@g;g@a_=a;g[#]++&/@#)&  Try it online! Clear@g; clear rules for g g@a_=a; initialize g[a]=a for all a g[#]++&/@# post-increment g[x] for each x in input  ## Nibbles, 5 bytes !$,~~+-@?_


That's 10 nibbles which are encoded in 0.5 bytes each. Nibbles isn't on TIO yet.

Translation:

!       zip
\$      the input list
,~     1..
~      (by a function, as opposed to 1 op zip) \x y->
+
-
@  y
?  index
_ the input list
implicit x
implicit y


Usage: pass the input in via the command line i.e.

nibbles filename.nbl "[1,1,1,1,10,10]"


Command line args used instead of stdin because input int list would still be 1 nibble in its second use (DeBruijn indicies incremented by 2 from the zip).

This is basically the same as DLosc's solution in Python (adding the difference of the index from its position)

• Interesting! I hadn't heard of Nibbles. What do you mean by "That's 10 nibbles which are encoded in 0.5 bytes each", though? If you were to store this Nibbles program to a file (assuming that's possible), wouldn't the file be 10 bytes in size?
– user110034
Jan 5 at 21:23
• You can compress it using nibbles -c and it really would be stored as 5 bytes since each instruction will only require 4 bits. The main idea is that you codegolf like normal using ascii but essentially get to divide by 2 at the end (with a few exceptions). Check out the webpage tutorial which explains this better. Jan 6 at 1:14