Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
Does 0 count as positive integer – Downgoat 2 hours ago
4  
@Downgoat 0 is not ever positive on PPCG. If 0 was allowed, the term would be "non-negative" – ETHproductions 2 hours ago

17 Answers 17

Python 3, 62 53 51 bytes

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

def F(a):a+=[0]*(len({*a})<2);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})!

share|improve this answer
    
@Lynn that's clever, thank you! – Flp.Tkc 5 hours ago
    
Hmm. "Output the resulting incremented array". Does this qualify? – TuukkaX 5 hours ago
    
I can't quite remember where, but I remember seeing a meta post that modifying a given list in place is allowed by default. I'll have a look for it @TuukkaX – Flp.Tkc 5 hours ago
    
@TuukkaX I'm not entirely sure. It seems ok but I'll defer to the meta concensus about modifying arrays in place, if there is one. – Calvin's Hobbies 5 hours ago
1  
In Python 3, you can use len({*L})<2 to find if all elements of a list are equal. – mbomb007 4 hours ago

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

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]")
share|improve this answer
    
Is using a.find(n=>n==Math.min(...a)) shorter? – Downgoat 2 hours ago
    
@Downgoat I'm not sure how I'd use that, as it returns the item rather than the index – ETHproductions 2 hours ago
    
yeah >_> whoops, I missed your ++ and didn't realize you needed a reference – Downgoat 2 hours ago

C#, 123 121 bytes

using System.Linq;void I(System.Collections.Generic.List<int>l){if(l.All(o=>o!=l[0]))l.Add(0);l[l.IndexOf(l.Min())]+=1;}

Modifies the argument passed to the function.

Thanks to Cyoce for saving 2 bytes! -> !Any to All.

share|improve this answer
    
could you replace !l.Any(o=>o!=l[0])) with l.All(o=>o==l[0])? – Cyoce 4 hours ago
    
@Cyoce It indeed does. I thought of the same thing, but wrote Any instead of All and was in the thought, that it doesn't work :D Thanks! – TuukkaX 4 hours ago
    
Does C# not have ++? – Cyoce 2 hours ago

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.
share|improve this answer
    
Congrats on beating me by one byte. – Zachary T 1 hour ago

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
share|improve this answer

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
}

share|improve this answer

Octave, 69 67 bytes

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

function x=f(x)
[a,b]=min(x);if any(x-a),x(b)++;else x(end+1)=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)
share|improve this answer
    
x=[x 1] instead of x(end+1)=1 – Luis Mendo 3 hours ago

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]
share|improve this answer
    
I think that DÙgi0¸«}ÐWksgÝQ+ also works. – Adnan 4 hours ago
    
@Adnan: Aah, nice idea using ÝQ with k. Thanks! – Emigna 4 hours ago

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.

share|improve this answer
2  
a.uniq[1] will be truthy iff there are distinct values. – histocrat 2 hours ago

Jelly, 9 bytes

;1µ‘i¦E?Ṃ

Thanks to Dennis for the -2 bytes.

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

share|improve this answer

Mathematica, 70 57 bytes

Virtually all of the improvement is due to Martin Ender, who kicks my ass at pattern matching approaches!

±{p:x_..}:={p,1};±{x___,y_,z___}/;y<=Min@{x,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.

share|improve this answer
    
You can use prefix notation for Min. But overall it's shorter to distinguish between the two cases with some pattern matching: ±{p:x_ ..}:={p,1};±n_:=(a=n;a[[a~FirstPosition~Min@a]]++;a) (Still trying to come up with a shorter solution for the increment case.) – Martin Ender 5 hours ago
1  
Best I've come up with is a byte longer, but maybe it inspires you to something shorter: ±{p:x_ ..}:={p,1};±{x___,y_,z___}/;Min@x>y<=Min@z:={x,y+1,z} – Martin Ender 5 hours ago
    
a~MatchQ~{b_ ..} is a byte shorter than Length@Union@a==1 – JHM 1 hour ago
    
Because ± is a 2-byte character, your code is 59 bytes long. Also, there must be a space between x_ and .. because Mathematica interprets x_.. as x_. . (which throws errors). Plus, the infix form of Min (x~Min~z) would make this 2 bytes shorter (which makes this solution identical to one of mine :p ...) Welp you can take the credit because my edit was later than yours.... – JHM 23 mins ago

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                    
share|improve this answer

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.

share|improve this answer

Mathematica, 58 bytes

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

Uses named function ±.

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}

share|improve this answer

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.

share|improve this answer

Haskell, 71 bytes

m%(a:b)|m/=a=a:m%b|n<-m+1=n:b
f c@(a:b)|l<-c++[0|all(a==)b]=minimum l%l

x%y increases the first value of x that appears in y, f performs the task by calling it with the minimum of the list that may have been appended with a 0. When I started I hoped for some elegant tying-the-knot trickery, but this simple solution seems shorter.

share

Mathematica, 53 bytes

If[Equal@@#,{##,1},x=#;x〚#~FirstPosition~Min@#〛++;x]&
share|improve this answer
    
That's 57 bytes. and are a 3-byte characters. Also, your code does not work because {##,1} part implies that the input is separate integers (i.e. f[1, 2, 3]) but the x=# part implies that the input is a List (i.e. f[{1, 2, 3}]). A quick fix would be to change x=# to x={#} and accept raw integers as input, making your code 59 bytes long. – JHM 56 mins ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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