Increment an Array

Question

Given a nonempty array of positive integers, "increment" it once as follows:

• If all the array elements are equal, append a 1 to the end of the array. For example:

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

• Else, increment the first element in the array that is the array's minimum value. For example:

  [1, 2] -> [2, 2]
  [2, 1] -> [2, 2]
  [3, 1, 1] -> [3, 2, 1] -> [3, 2, 2] -> [3, 3, 2] -> [3, 3, 3]
  [3, 4, 9, 3] -> [4, 4, 9, 3] -> [4, 4, 9, 4] -> [5, 4, 9, 4] -> [5, 5, 9, 4] -> ...
  

(Each -> represents one increment, which is all your program needs to do.)

Output the resulting incremented array.

The shortest code in bytes wins.

Answer 1

Jelly, 8 7 bytes

‘;ṀỤḢṬ+

Try it online! or verify all test cases.

How it works

‘;ṀỤḢṬ+  Main link. Argument: A

‘        Increment all elements of A.
  Ṁ      Yield the maximum of A.
 ;       Concatenate both results. Note that the appended maximum will be the 
         minimum of the resulting array if and only if all elements of A are equal.
   Ụ     Grade up; yield the indices of the resulting array, sorted by their
         corresponding values in that array.
    Ḣ    Head; extract the first index, which is the index of the first occurrence
         of the minimum. For an array of equal elements, this will be the index
         of the appended maximum.
     Ṭ   Untruth; for index i, yield an array of i-1 zeroes, followed by a 1.
      +  Add this array to A, incrementing the minimum or appending a 1.

Answer 2

Python 3, 62 53 51 50 bytes

Function which modifies the list passed to it (allowed by meta).

def F(a):a+=1//len({*a})*[0];a[a.index(min(a))]+=1

Try on repl.it!

-9 bytes thanks to Lynn for spotting that, because the array will be of positive integers, I can append '0' to the end of the array and have that incremented.

Special thanks to mbomb007 for golfing len(set(a)) to len({*a}), and Dennis for the floordiv trick!

Answer 3

JavaScript (ES6), 61 bytes

a=>new Set(a).size>1?++a[a.indexOf(Math.min(...a))]:a.push(1)

Outputs by modifying its argument. I can't find a way to determine whether an array has only one unique item in less that 17 bytes, but suggestions are welcome.

Test snippet

f=a=>new Set(a).size>1?++a[a.indexOf(Math.min(...a))]:a.push(1)
g=a=>0 in a?console.log("Input:",`[${a}]`,"Output:",`[${f(a),a}]`):console.log("Invalid input")

g([1])
g([2])
g([1,1])
g([1,2,2,3])
g([2,2,2,3])
g([3,2,2,3])
g([3,3,2,3])
g([3,3,3,3])
g([3,3,3,3,1])

<input id=I value="1,2,2,3"><button  onclick="g(I.value.match(/\d+/g)||[])">Run</button>

Other attempts

Here are a few alternate ways of deciding whether the array has more than one unique input:

a=>a.some(x=>x-a[0])?++a[a.indexOf(Math.min(...a))]:a.push(1)
a=>a.some(x=>x-m,m=Math.min(...a))?++a[a.indexOf(m)]:a.push(1)

Both of the somes can be replaced with find as well. .sort would be shorter for finding the minimum, if the default sort wasn't lexicographical (why, JS, why?):

a=>new Set(a).size>1?++a[a.indexOf(a.sort()[0])]:a.push(1)
// Instead we have to do:
a=>new Set(a).size>1?++a[a.indexOf(a.sort((x,y)=>x-y)[0])]:a.push(1)

I tried recursion to find the minimum, but it turned out way longer:

f=(a,n=1,q=a.indexOf(n))=>~q?a.some(x=>x-n)?++a[q]:a.push(1):f(a,n+1)

And here's a string-based solution which seemed like a good idea at first: (input is given in array format in a string, e.g. "[1,2,3]")

a=>a.replace(m=/(\d+),(?!\1)/.test(a)?Math.min(...eval(a)):']',+m+1||",1]")

Answer 4

Mathematica, 70 57 55 bytes

Virtually all of the improvement is due to Martin Ender, who kicks my ass at pattern matching approaches! Also JHM came up with essentially the same solution at essentially the same time. (byte count uses ASCII encoding)

±{p:x_ ..}:={p,1};±{x___,y_,z___}/;y≤x~Min~z:={x,y+1,z}

Defines a function ± taking one list argument. If that list argument contains some number of copies of the same element (detected by x_.. and named p), then output the list with a 1 appended. Otherwise, if that list argument has a special element y (with x being the zero or more elements before y, and z being the zero or more elements after y) which is at most the minimum of the other elements, then output the list with that y incremented. Any instance of the minimum element of the list will be matched by y, but fortunately Mathematica chooses the first one to act upon.

Answer 5

C++14, 178 176 174 155 142 135 bytes

submission

#include<list>
#include<algorithm>
[](auto&l){auto e=end(l),b=begin(l);l.size()^count(b,e,*b)?++*min_element(b,e):(l.push_back(1),0);};

invocation

std::list<int> s = {4, 4, 9, 4};

//invoke like this
auto i = [](auto&l){auto e=end(l),b=begin(l);l.size()^count(b,e,*b)?++*min_element(b,e):(l.push_back(1),0);};
i(s);

//or like that
[](auto&l){auto e=end(l),b=begin(l);l.size()^count(b,e,*b)?++*min_element(b,e):(l.push_back(1),0);}(s);

ungolfed

#include <list>
#include <algorithm>
#include <iostream>
using namespace std;

void i(list<int>& l) {
    auto e = l.end(), b = l.begin();

    if (l.size() == count(b, e, l.front())) {
        l.push_back(1);
    } else {
        ++*min_element(b, e);
    }
}

int main() {
    list<int> s = {4, 4, 9, 4};

    //invoke like this
    i(s);

    for (auto o:s)
        std::cout << o << ' ';
    std::cout << std::endl;
}

This is my first time playing golf, help is appreciated.

EDIT: forgot to mention you have to compile it with at least -std=c++11 -std=c++14

EDIT2: I realized i can leave out the space in the includes #include <list>

EDIT3: saved two more bytes by replacing l.begin() by begin(l)

EDIT4: saved another 19(!) bytes thanks to @Quentin (see his comment)

EDIT5: Quentin shaved off 13 more bytes, thanks!

EDIT6: as TuukkaX pointed out, unnamed lambdas/functions suffice so i removed the auto i= in the bytecount

Answer 6

05AB1E, 21 20 16 bytes

Saved 4 bytes thanks to Adnan.

DÙgi0¸«}ÐWksgÝQ+

Try it online!

Explanation

                      # input = [3,2,1] used as example
D                     # duplicate input
 Ùgi                  # if all elements are equal
    0¸«}              # append 0
        Ð             # triplicate list
                      # STACK: [3,2,1], [3,2,1], [3,2,1]
         Wk           # index of minimum element
                      # STACK: [3,2,1], [3,2,1], 2
           s          # swap top 2 elements of stack
                      # STACK: [3,2,1], 2, [3,2,1]
            g         # length of list
                      # STACK: [3,2,1], 2, 3
             Ý        # range [0 ... length]
                      # STACK: [3,2,1], 2, [0,1,2,3]
              Q       # equal
                      # STACK: [3,2,1], [0,0,1,0]
               +      # add
                      # OUTPUT: [3,2,2]

Answer 7

Scratch, 25 34 blocks + 7 6 bytes

Takes input as a predefined array of integers. Note that arrays are 1-indexed in Scratch.

In Python, this would look like: (Note that unlike Scratch, Python is 0-indexed)

lowval = 0
hival = 0
n = 1
for i in range(len(input)):
    if(input[i] < input[lowval]):
        lowval = i
    if(input[i] > input[hival]):
        hival = i
    # No increment statement needed because python.
if(lowval == hival):
    input.append(1)
else:
    input[lowval] += 1
print(input)

Answer 8

J, 25 22 bytes

(+~:*[=<./)@,0#~1=#@~.

Evaluates to an anonymous verb. Try It Online!

Explanation

(+~:*[=<./)@,0#~1=#@~.  Input is y.
                  #@    Is the length of
                    ~.   deduplicated y
                1=       equal to 1?
            ,0#~        Append that many 0s to y (one or none).
(         )@            Call the result z and apply this verb to it:
      =                  take the bit array of equality
     [                   between z
       <./               and its minimum element,
    *                    multiply that element-wise by
  ~:                     the bit array of first occurrences in z
 +                       and add the result to z.

Answer 9

MATL, 16 bytes

t&=?1h}t2#X<wQw(

Try it online! Or verify all test cases

How it works

t         % Take input implicitly. Duplicate
&=        % Matrix of all pairwise equality comparisons
?         % If all comparisons were true
  1h      %   Append 1 to the original copy ofthe array
}         % Else
  t       %   Duplicate array
  2#X<    %   Push minimum and index of its first occurrence
  wQw     %   Swap, increment, swap (adds 1 to the minimum)
  (       %   Assign the incremented minimum to that position
          % End if implicitly. Display implicitly

Answer 10

C#, 123 121 120 79 77 bytes

using System.Linq;l=>{if(l.All(o=>o==l[0]))l.Add(0);l[l.IndexOf(l.Min())]++;}

Modifies the argument passed to the function.

Thanks to Cyoce for saving 3 bytes! -> !Any to All, +=1 to ++.

Thanks to TheLethalCoder for saving a whopping 43 bytes! -> Removed method signature code. Removed parenthesis around the parameter list.

Answer 11

Mathematica, 56 bytes

±{b:a_ ..}:={b,1};±a_:=a/.{p___,b:Min@a,q___}:>{p,b+1,q}

Uses named function ±. Uses ISO8859-1 encoding

Alternative solutions (58 bytes)

±{b:a_ ..}:={b,1};±{p___,b_,q___}/;b<=p~Min~q:={p,b+1,q}
(* @GregMartin and I both independently came up with this above solution *)

±{b:a_ ..}:={b,1};±a:{p___,b_,q___}/;b==Min@a:={p,b+1,q}

Usage

±{1, 1}

{1, 1, 1}

±{3, 4, 5}

{4, 4, 5}

Answer 12

Haskell, 71 70 62 bytes

f(a:b)|(x,y:z)<-span=<<(<).minimum$a:b++[0|all(a==)b]=x++y+1‌​:z

@Zgarb saved 8 bytes, thanks!

When I started I hoped for some elegant tying-the-knot trickery, but @Zgarb's way is just as amazing.

Answer 13

Perl 6, 46 bytes

{.[[==]($_)??.elems!!.first(*==.min,:k)]++;$_}

(modifies the input Array, and returns it)

Expanded:

{     # bare block lambda with implicit parameter ｢$_｣

  .[      # use the following as an index into the array

      [==]( $_ )    # reduce the array with ｢&infix:<==>｣

    ??              # if they are equal

      .elems        # the value past the end ( ｢.end+1｣ would also work )

    !!              # else

      .first(       # find the first value
        * == .min,  # where the element is equal to the minimum
        :k          # return the key rather than the value
      )

  ]++;              # increment it ( auto vivifies if it doesn't exist )

  $_                # return the modified array
}

Answer 14

Jelly, 9 bytes

;1µ‘i¦E?Ṃ

Thanks to Dennis for the -2 bytes.

Body must be at least 30 characters; you entered ... .

Answer 15

Mathematica, 53 bytes 57 bytes 59 bytes

If[Equal@@#,#~Join~{1},x=#;x[[#~FirstPosition~Min@#]]++;x]&

Answer 16

R, 72 66 65 bytes

"if"(any((x=scan())-x[1]),"[<-"(x,u<-which.min(x),1+x[u]),c(x,1))

Try it online!

Increment is done using which.min which returns the first match. "[<-" allows to replace the value and returns the modified vector in one function call.

-7 bytes thanks to Giuseppe!

Answer 17

Octave, 69 67 64 bytes

It was actually shorter to make this a complete named function than using both input and disp.

Saved 3 bytes thanks to Luis.

function x=f(x)
[a,b]=min(x);if any(x-a),x(b)++;else x=[x,1];end

Old answer, not using a function:

[a,b]=min(x=input(''));if any(x-a),x(b)++;else x(end+1)=1;end;disp(x)

Answer 18

Ruby, 46 bytes

->a{a.uniq.size<2?a<<1:a[a.index(a.min)]+=1;a}

I feel like there's a better way to check if all elements are the same than a.uniq.size<2, but I'm too lazy to find it.

Answer 19

R, 97 bytes

if(all((a=scan())==a[1])){a=c(a,1)}else{while(!all(a==a[1])){a[which(a==min(a))][1]=min(a)+1}};a

Too bad that the synthax x=+1 doesn't exist in R !

Ungolfed :

if(all((a=scan())==a[1]))
{
    a=c(a,1)
}
else
{
    while(!all(a==a[1]))
    {
        a[which(a==min(a))][1]=min(a)+1
    }
a

Answer 20

Matlab, 83, 77, 71 Bytes

function a=x(a)
if~nnz(a-a(1));a=[a,1];else[~,I]=min(a);a(I)=a(I)+1;end

I'm relatively new to code golf so please be kind! I tried to use anonymous functions but googling says you can't use if/else statements and matlab doesn't have ternary operators, so this is the best i felt I could do.

Edit: Corrected and shortened (twice!) thanks to stewie-griffin.

Answer 21

TI-Basic, 53 bytes

If min(not(ΔList(Ans
Then
Ans->L1
cumSum(1 or Ans
min(Ans+ᴇ9(L1≠min(L1
L1(Ans)+1->L1(Ans
Else
augment(Ans,{1
End

Answer 22

Clojure, 112 100 bytes

Unfortunately min-key returns the last index of the smallest index, not the first one. This works for integer inputs and shorter arrays than 10^9 elements ;)

Edit: Defining an anonymous function, using (apply = a) instead of (= 1(count(set a))).

(fn[a](if(apply = a)(conj a 1)(update a(apply min-key #(+(nth a %)(* % 1e-9))(range(count a)))inc)))

Original:

(defn f[a](if(= 1(count(set a)))(conj a 1)(update a(apply min-key #(+(nth a %)(* % 1e-9))(range(count a)))inc)))

A less hacky 134-byte solution reverses the vector before updating it and then reverse it back again:

(defn f[a](if(= 1(count(set a)))(conj a 1)(let[r #(vec(reverse %))a(r a)](r(update a(apply min-key #(nth a %)(range(count a)))inc)))))

Answer 23

MATLAB, 66 53 bytes

if(range(a))[~,b]=min(a);a(b)=a(b)+1;else;a=[a 1];end

Output:

Initialize:

a = [3 2]

Successive runs:

[3 2] -> [3 3] -> [3 3 1] -> [3 3 2] -> [3 3 3] -> [3 3 3 1] ...

Answer 24

Java 8, 85 + 38 = 123 bytes

Void lambda taking a List<Integer> (output is mutated input). Byte count includes lambda and required import.

import static java.util.Collections.*;

l->{if(min(l)==max(l))l.add(0);int i=0,n;while((n=l.get(i))>min(l))i++;l.set(i,n+1);}

Try It Online

This almost looks like Python with those method imports...

Answer 25

SmileBASIC 3, 101 bytes

Defines a statement function I A where A is our integer array of numbers. Output is achieved by modifying the input (as arrays are references.)

DEF I A
M=MIN(A)IF M==MAX(A)THEN PUSH A,1RETURN
FOR C=0TO LEN(A)IF M==A[C]THEN INC A[C]BREAK
NEXT
END

Answer 26

SmileBASIC, 77 bytes

DEF I A
IF MIN(A)==MAX(A)THEN PUSH A,0
WHILE A[I]>MAX(A)I=I+1WEND
INC A[I]END

Answer 27

Pyth, 16 bytes

?tl{QXxQhSQQ1+Q1

A program that takes input of a list and prints the result.

Test suite

How it works

?tl{QXxQhSQQ1+Q1  Program. Input: Q
?                 If:
  l                The length
   {Q              of Q deduplicated
 t                 - 1
                   is non-zero:
     X     Q1       Increment in Q at index:
      xQ             Index in Q of
        h            the first element
         SQ          of Q sorted (minimum)
                  else:
             +     Append
               1   1
              Q    to Q
                   Implicitly print                    

Answer 28

Haskell, 93 bytes

f z|and$(==)<$>z<*>z=z++[1]|1>0=z#minimum z where(x:z)#m|x==m=x+1:z;(x:z)#m|1>0=x:z#m;[]#_=[]

Ungolfed:

incrementArray :: [Int] -> [Int]
incrementArray xs | and [x == y | x <- xs, y <- xs] = xs ++ [1]
                  | otherwise = g xs (minimum xs)
     where g (x:xs) m | x == m = (x + 1):xs
           g (x:xs) m | otherwise = x:g xs m
           g [] _ = []

Initial attempt, will try to come up with something more sophisticated later.

Answer 29

Wonder, 44 bytes

@[dp1unq#0?:=#[:0(iO f\min#0)#0+1f]#0?++#0 1

This is not what I had in mind when I made this language... It's literally worse than Perl in terms of readability!

Usage:

(@[dp1unq#0?:=#[:0(iO f\min#0)#0+1f]#0?++#0 1])[3 4 9 3]

Explanation

More readable:

@[
  dp 1 unq #0
    ? set #[
            get 0 (iO f\ min #0) #0
            + 1 f
           ] #0
    ? con #0 1
 ]

Basically checks if dropping 1 item from the unique subset of the argument makes the list empty. If not, then we increment the minimum of the array. Otherwise, we simply concatenate 1 to the argument.

Answer 30

Kotlin, 75 bytes

fun a(s:MutableList<Int>){if(s.toSet().size<2)s+=0;s[s.indexOf(s.min())]++}

Modifies the function argument.

Damn you strong typing! :MutableList<Int> accounts for 17 bytes alone. I don't think there is a solution where the type can be inferred, unfortunately.

Answer 31

jq, 44 characters

if unique[1]then.[index(min)]+=1else.+[1]end

Sample run (-c (--compact-output) option used only here for readability):

bash-4.3$ jq -c 'if unique[1]then.[index(min)]+=1else.+[1]end' <<< '[3,1,1]'
[3,2,1]

bash-4.3$ jq -c 'if unique[1]then.[index(min)]+=1else.+[1]end' <<< '[3,2,1]'
[3,2,2]

bash-4.3$ jq -c 'if unique[1]then.[index(min)]+=1else.+[1]end' <<< '[3,2,2]'
[3,3,2]

bash-4.3$ jq -c 'if unique[1]then.[index(min)]+=1else.+[1]end' <<< '[3,3,2]'
[3,3,3]

bash-4.3$ jq -c 'if unique[1]then.[index(min)]+=1else.+[1]end' <<< '[3,3,3]'
[3,3,3,1]

On-line test:

• [3,3,3,3,3]
• [3,4,9,3]

Answer 32

Groovy - 45 bytes

A groovy closure which accepts a list of Integer as input - please note this modifies the input List.

{o->(o-o[0])?o[o.indexOf(o.min())]+=1:o<<1;o}

Test cases can be seen here:

http://ideone.com/9vRd9e

Alternative of 56 bytes if the code needs to work with int[] or List<Integer>:

{o=it.toList();(o-o[0])?o[o.indexOf(o.min())]+=1:o<<1;o}

Answer 33

PHP, 79 bytes

function i($a){max($a)>($n=min($a))?$a[array_search($n,$a)]++:$a[]=1;return$a;}

I think this needs no explanation.

Answer 34

MATLAB, 69 67 bytes

function a=f(a);if~range(a)a=[a 1];else[~,j]=min(a);a(j)=a(j)+1;end

range(a) is non-zero if not all elements are equal, and [~,j]=min(a) assigns the index of the minimum value in a to j, defaulting to the first value it finds. Input is a row vector. Saved 2 bytes by reversing the if/else logic to get rid of some semicolons (else[~,j] is legal, but elsea=[a 1] is not).

Answer 35

Actually, 18 bytes

The algorithm used in this answer is largely based on Dennis' Jelly answer. Golfing suggestions welcome! Try it online!

;;M@u#q;m@í0@α1@q¥

Ungolfing

      Implicit input a.
;;    Duplicate a twice.
M     Get the maximum of a.
@u#   Increment all of a and convert back to a list.
q;    Append max(a) to the end of a_plus_one, and duplicate. Call it b.
m@í   Get index of the minimum of b. Call it min_index.
        If all elements of a were equal, this is the maximum at the end.
        Else, it's somewhere else in the array.
0@α   Push a list of min_index zeroes.
1@q   Append a 1 to the end. Call this array c.
        This will increment at the desired index or otherwise append a 1.
¥     Pairwise add a and c to get our incremented array.
      Implicit return.

Answer 36

Tcl, 114 bytes

proc I a {if [llength [set S [lsort -u $a]]]<2 {lappend a 1} {lset a [lsearch $a [set m [lindex $S 0]]] [incr m]}}

Try it online!

Answer 37

Java, 155 bytes

a->{List b=a;Collections.sort(b);if(new Set(a).size()==1)a.add(1);else for(int i=0;i<b.size();)if(a.get(i)==b.get(0)){a.set(i,a.get(i)+1);break;}return a;}