# 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, 2022 at 19:25
• @cairdcoinheringaahing No, because the input is sorted. Jan 1, 2022 at 19:26
• What happens to [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 19, 19, 20, 20] Jan 3, 2022 at 7:52
• Related Jan 3, 2022 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, 2022 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, 2022 at 21:46
• Thank you for the explanation. Brilliant.
– user110034
Jan 1, 2022 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, 2022 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, 2022 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, 2022 at 19:13

# 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, 2022 at 19:55 • @Giuseppe Ah, the sequence function... Forgot about it. Thanks! Jan 1, 2022 at 20:01 • 31 bytes porting this, or at least its explanation. Jan 1, 2022 at 20:44 • @Giuseppe - i think it's distinct enough for a separate answer. Jan 1, 2022 at 21:12 # 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. # 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, 2022 at 20:34 • @pxeger I knew there was some kind of trick for that! Thanks. Jan 1, 2022 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, 2022 at 20:45 • Fails for the second test case and similar, btw you can omit parameter type in Clang. Jan 1, 2022 at 22:16 • Building on @AZTECCO 49 bytes Apr 16, 2022 at 19:36 # 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, 2022 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, 2022 at 20:09 • My bad! Thanks for the explanation ;) – Maël Jan 2, 2022 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, 2022 at 23:57 • upvote later - used all my votes on other answers :) – user110034 Jan 1, 2022 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, 2022 at 23:59 # 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. # 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! # 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.

# 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, 2022 at 22:51

$_+=$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, 2022 at 15:23 • @richardec Yup! Jan 4, 2022 at 4:52 # 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, 2022 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 + # Add to input  Port of caird coinheringaahing's answer. • Try it Online! for 5 bytes Jan 2, 2022 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, 2022 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, 2022 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!

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 ]


# Japt, 5 bytes

ü ®í+


Try it

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

• Not sure a 2D array is valid output but you can fix it by replacing the map with c_. Oct 3, 2022 at 20:46
• @Shaggy isn't std out enough? I mean the program prints a list Oct 4, 2022 at 1:05

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

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

• Now this is interesting. Will you please provide an explanation? Though I know next to nothing about Ruby, I can get along well enough with normal-looking code, but by submitting this, you golfed by brain right out of my head... :P
– user110034
Jan 4, 2022 at 23:37
• @richardec hehe, thanks. I added a quick explanation in the post. It's not much to it really, it might just look a bit messy/weird. The tally method is doing most of the heavy lifing here. Jan 5, 2022 at 0:34
• Thanks! It's really quite understandable now, even for a non-Ruby guy like me. Your explanation is concise and practical ;) The *_1.. was seriously stumping me... :P
– user110034
Jan 5, 2022 at 1:25
• btw ATO has an updated version of ruby where the polyfill can be omitted: Try It! Jan 5, 2022 at 17:46
• @Razetime cool, thanks Jan 5, 2022 at 18:24