title: Adversarial Iterated Prisoner's Dilemma

text:
# Question
Title: Adversarial Iterated Prisoner's Dilemma
In this challenge, you will play the iterated Prisoner's Dilemma, but with a twist: There's also an adversary trying to mess you up!

The Prisoner's dilemma is a scenario in game theory where there are two players, who we'll call the "prisoners", each with two options: cooperate, or defect. Each prisoner does better for themself if they defect than if they cooperate, but both prisoners would prefer the outcome where both prisoners cooperate to the one where both prisoners defect.

The *iterated* prisoner's dilemma is the same game, except you play against the same opponent repeatedly, and you know what your opponent has played in the past. Your objective is to accumulate the highest score for yourself, regardless of your opponent's score.

The *adversarial* iterated prisoner's dilemma introduces a third player: The *flipper*. The flipper can choose to interfere with the prisoners' communication. After the prisoners make their plays, the flipper can choose to flip one or both of the prisoners' moves, making it look like they played the opposite move. The flipper can only perform this flip a limited number of times over the course of the round. The flipper's goal is to maximize the number of times the prisoners defect.

## Challenge

In this challenge, you will write Python 3 programs to play as the prisoner and as the flipper. You may submit programs for either or both.

Prisoner programs will receive the following inputs:

* Your past moves, *without* the flipper's flips added.
* The other prisoner's past moves, *with* the flipper's flips added.
* A state variable, which is initialized as an empty list, which you can modify over the course of the round.

Your program should output `'c'` for cooperate and `'d'` for defect. The lists of past moves will be represented in the same fashion.

For instance, here's a program that cooperates unless the opponent's last play was a defection:

```
def basic_tit_for_tat(my_plays, their_plays, state):
    if len(their_plays) == 0:
        return 'c'
    return their_plays[-1]

```

Flipper programs will receive the following inputs:

* The past moves for both players, both true and post-flip. The true moves list will include the move played this round, while the post-flip list will not.
* The number of flips remaining, which starts at 40 flips, covering 100 turns.
* A state variable, which is initialized as an empty list, which you can modify over the course of the round.

Your program should output `0` to flip neither move, `1` to flip prisoner 1's move, `2` to flip prisoner 2's move, and `3` to flip both moves. If you have no flips remaining, your program will not be called. If you have one flip remaining and you output `3`, it will be treated as if you had output `1`, to simplify error handling.

For example, here's a program which flips each prisoner's move every fifth turn, if the true move is cooperate:

```
def basic_steady_flipper(p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state):
    turn = len(p1_flipped_moves)
    if turn % 5 == 0 and p1_moves[-1] == "c":
        return 1
    if turn % 5 == 2 and p2_moves[-1] == "c":
        return 2
    return 0

```

If you don't know Python, write your submission in pseudocode, and someone (me or another member of the site) can make the corresponding Python program.

If you want to use randomness, please hand-roll it rather than using the `random` package, as I don't want programs to modify global state. See basic\_random\_flipper for an example.

## Tournament

The tournament runner can be found in this repository: adversarial-ipd. Run adversarial-game.py to run the tournament. I'll keep that repository updated with new submissions. To get things started, I'll put a few basic example programs in basic.py.

A round consists of 100 turns, involving the same two prisoners and the same flipper. The flipper's budget over that round is 40 flips, which can be distributed however the flipper likes between the two prisoners. The flipper also doesn't have to use all of their flips.

I will simulate a round between every triplet of `(prisoner1, prisoner2, flipper)`, including having prisoners play against themselves.

A prisoner receives one point whenever they defect (output `'d'`), and receives two points whenever the other prisoner cooperates (outputs `'c'`). Note that the prisoner's score is not directly affected by the flipper's action - the flipper only affects communication, not score.

A flipper receives one point whenever either of the prisoners defects.

A program's overall score is its average score over all of its matchups. The players will be all valid submissions to the question, plus the basic programs to get us started.

## Restrictions

Do not modify the input, other than the state variable. Do not interact with the environment. Do not make a sacrificial submission that attempts to benefit other submissions. Submissions may not duplicate the basic programs or other earlier submissions. Standard loopholes are not allowed.

Update: Please make your submissions deterministic, so I don't need to run the tournament many times to get an average.

If you have any questions, feel free to ask!

## Current results

```
Prisoners:
string_prisoner:                166.995
prisoner_nn:                    154.392
masquerade:                     153.781
slightly_vindictive:            153.498
basic_defect:                   152.942
basic_tit_for_tat:              150.245
holding_a_grudge:               147.132
use_their_response_unless_t...: 146.144
basic_threshold:                145.113
blind_rage:                     144.418
basic_tit_for_two_tats:         143.861
stuck_buttons:                  141.798
less_deterministic_prisoner:    134.457
tit_forty_tat:                  134.228
detect_evil:                    134.036
basic_cooperate:                118.952

Flippers:
string_flipper:                 149.43
flipper_nn:                     145.695
basic_immediate_flipper:        144.539
advanced_evil_p1_flipper:       143.246
basic_evil_p1_flipper:          131.336
basic_mod_4_flipper:            103.918
paranoia_pattern:               102.055
basic_steady_flipper:           100.168
basic_biased_flipper:           99.125
less_deterministic_flipper:     90.7891
basic_random_flipper:           86.5469
tempting_trickster:             66.1172
basic_non_flipper:              63.7969

```

---

I will declare a pair of winners (one prisoner, one flipper) one month after this challenge is posted.

See for comparison my Noisy Iterated Prisoner's Dilemma challenge, where there is randomness instead of an adversary, as well as evolutionary scoring.

# Answer
# String (prisoner + flipper)

```
def string_prisoner(my_plays, their_plays, state):
    s = "zbemvqjmwqozghuxgymklypogluxxnfvdzcmcusncnsqnuktdhxesvaipgyphcpfgmirmmqlahnkofttkcshrbpvslqngmkjmspkrdzujs"
    if state:
        i = 'cd'.index(my_plays[-1])
        j = 'cd'.index(their_plays[-1])
    else:
        state.append(18)
        i, j = 1, 0
    h = state[-1]
    h = ord(s[4 * h + 2 * i + j]) - 97
    state[0] = h
    return 'cd'[h % 2]

def string_flipper(p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state):
    s = "wvwyhbwyjplcvuowuuwyobcyunxypirmhisyxmsenxqypkcyomgqwnuaomrypzkyxnwblegqdssijkbhnjywnnmrpzwygxsepbwypfsysn"
    if state:
        i = 'cd'.index(p1_moves[-1])
        j = 'cd'.index(p2_moves[-1])
    else:
        state.append(13)
        i, j = 0, 1
    h = state[-1]
    h = ord(s[4 * h + 2 * i + j]) - 97
    state[0] = h
    return h % 4

```
> 3 votes

# Answer
# Neural Networks (Prisoner + Flipper)

```
import math

def sigmoid(z):
    z = max(-60.0, min(60.0, 5.0 * z))
    return 1.0 / (1.0 + math.exp(-z))

def eval_nn(nn, inputs, output_size):
    values = {}
    for i, x in enumerate(inputs):
        values[~i] = x
    for v, bias, links in nn:
        val = bias
        for v2, w in links:
            val += values[v2] * w
        values[v] = sigmoid(val)
    return [values[i] for i in range(output_size)]

def flipper_nn(p1_plays, p1_flipped, p2_plays, p2_flipped, flips_remaining, f_state):
    flipper = [(2,1.1181821042173234,[(-4,1.7400885547178728),(-5,-0.06813411778649736),(-1,0.36820555967416463)]),(1413,0.5463770972701019,[(-7,1.2906662332985084)]),(1006,-0.7872435180237973,[(-1,0.15812448989961483)]),(400,0.8765368123690065,[(-1,-0.5507089170354788),(-4,-2.6155008235530275),(-6,-0.13973123898832307),(1413,0.611948590243875)]),(4,-0.7227321303517735,[(-5,1.5683558624231078),(-6,-1.2370613914091573),(-4,0.5237132563743849),(1006,-0.32865555879156394)]),(0,-0.8037738878771841,[(400,-1.539896544478685),(-6,-1.2406408935562372),(-2,1.4008065675860095),(-5,1.3368457316858942)]),(1241,2.8053793783985843,[(400,-1.1720600247508444)]),(3,-0.6671763505247656,[(-7,1.3637083521769713),(-2,0.23978597611290645),(400,0.07355299289323734),(-5,1.4847572012033936)]),(5,1.3240920945810233,[(-3,0.09279702179768222),(-4,-0.42695177997561584),(400,0.01877521376790067)]),(1,1.4532564361954763,[(-4,-3.3511395309047542),(-6,3.4483449908621946),(400,-0.30914255807222707),(-1,4.416629240437298),(1241,-3.2869409990358784)])]
    if not f_state:
        f_state.append([0, 0, 0, 0])
    p1_play = 1 if p1_plays[-1] == 'c' else -1
    p2_play = 1 if p2_plays[-1] == 'c' else -1
    d1, d2, *f_state[0] = eval_nn(flipper, [p1_play, p2_play, flips_remaining, *f_state[0]], 6)
    return 2 * (d1 > .5) + (d2 > .5)

def prisoner_nn(p1_plays, p2_flipped, p1_state):
    prisoner = [(0,-2.2128141878495886,[(-2,0.647135699564962),(-1,-3.819879756972317),(-6,-1.5898309666275279),(-5,-1.3569920659927621)]),(2,-0.026842109156755112,[(-6,1.9088324301092459),(-1,-1.498237595085962),(-2,-1.3979942638308056)]),(3,-1.4642587337125894,[(-5,0.027435320810760975),(-3,0.8940799124862344)]),(5,-1.5627901857506785,[(-7,-0.3885493442923349),(-4,-0.6468723685254656),(-6,0.4827740033482678),(-1,1.0907376062753547)]),(3655,-0.6335740926081981,[(-3,-1.131136914882346)]),(4,0.030539518044983505,[(-4,0.6436349726871196),(-6,-0.7427970484374815),(3655,-0.23969124478552287)]),(1,0,[])]
    if not p1_state:
        p1_state.append([0, 0, 0, 0, 0])
    lastact = (1 if p2_flipped[-1] == 'c' else -1) if p2_flipped else 0
    lastsact = (1 if p1_plays[-1] == 'c' else -1) if p1_plays else 0
    act, *p1_state[0] = eval_nn(prisoner, [lastsact, lastact, *p1_state[0]], 6)
    return ['d', 'c'][act > 0.5]

```

Created using neat-python, but I added a simple neural network implementation so it isn't a dependency.
> 9 votes

# Answer
# Paranoia Pattern (flipper)

```
def paranoia_pattern(
    p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state
):
    turn = len(p1_moves)
    match turn:
        case 1:
            # Don't let them get off on the right foot
            return 3

        case 2:
            # And don't let them get used to it
            return 0

        case _ if flips_left > 4:
            # Then alternate aggressively...
            return 1 << (turn % 2)

        case 65 | 66:
            # and finally throw them back off if they've gotten used to the break.
            return 3

        case _:
            return 0

```

I noticed that the "smarter" pre-packaged flippers never "waste" a flip on a defect. This means prisoners are more able to trust that cooperates are in fact real, which also reduces their incentive to defect for real, if they can tell the flipper isn't just constant or random.

However, prisoners can and should live in constant fear of betrayal instead, and this flipper will aggressively beat it into them, without even bothering to look at what they're actually doing.
> 5 votes

# Answer
# Masquerade (prisoner)

```
def masquerade(my_plays, their_flipped_plays, state):
    turn = len(my_plays)
    if turn == 0:
        return "c"
    elif turn == 2:
        return "d"
    elif turn < 7:
        return "c"

    always_cooperate_patterns = [
        ['c', 'd', 'c', 'd', 'd', 'c', 'd', 'c'], ['c', 'c', 'c', 'd', 'd', 'd', 'c', 'c'],
        ['d', 'c', 'c', 'd', 'd', 'd', 'c', 'c'], ['c', 'c', 'c', 'c', 'd', 'c', 'd', 'c'],
        ['c', 'c', 'd', 'd', 'd', 'd', 'd', 'd'], ['d', 'c', 'd', 'c', 'c', 'c', 'd', 'c'],
        ['c', 'c', 'd', 'c', 'd', 'c', 'd', 'd'], ['d', 'd', 'd', 'd', 'c', 'c', 'c', 'c'],
        ['d', 'd', 'c', 'd', 'c', 'c', 'c', 'c'], ['d', 'c', 'd', 'd', 'c', 'c', 'd', 'c'],
        ['c', 'd', 'c', 'd', 'd', 'd', 'c', 'c'], ['c', 'c', 'c', 'c', 'd', 'c', 'c', 'd'],
        ['c', 'd', 'c', 'd', 'd', 'c', 'c', 'c'], ['c', 'c', 'c', 'c', 'd', 'd', 'c', 'c'],
        ['c', 'c', 'c', 'd', 'd', 'c', 'c', 'd'], ['d', 'c', 'd', 'c', 'c', 'd', 'c', 'c'],
        ['c', 'd', 'd', 'd', 'c', 'c', 'd', 'd'], ['c', 'c', 'c', 'd', 'd', 'd', 'd', 'd'],
        ['d', 'd', 'd', 'c', 'c', 'd', 'd', 'd'], ['d', 'd', 'd', 'c', 'd', 'd', 'd', 'd'],
        ['c', 'c', 'd', 'c', 'c', 'c', 'd', 'c'], ['d', 'c', 'd', 'd', 'c', 'd', 'c', 'c'],
        ['d', 'c', 'c', 'c', 'd', 'c', 'd', 'd'], ['c', 'd', 'd', 'd', 'c', 'd', 'c', 'c'],
        ['c', 'c', 'c', 'd', 'c', 'c', 'd', 'c'], ['d', 'd', 'c', 'd', 'd', 'd', 'd', 'd'],
        ['c', 'c', 'd', 'd', 'c', 'c', 'c', 'c'], ['c', 'c', 'd', 'c', 'c', 'd', 'c', 'c'],
        ['c', 'c', 'c', 'd', 'c', 'c', 'c', 'c'], ['c', 'c', 'd', 'c', 'c', 'c', 'c', 'c'],
        ['c', 'c', 'c', 'd', 'd', 'c', 'c', 'c'], ['c', 'c', 'd', 'c', 'c', 'c', 'c', 'd']
    ]

    # "self"-detection
    if their_flipped_plays[:8] in always_cooperate_patterns:
        return "c"

    # defect for the last few turns
    if turn > 30:
        return "d"

    # if they often defect, defect as well
    if their_flipped_plays.count("d") > 0.3 * len(their_flipped_plays):
        return "d"

    # tit-tit for tat
    # inspired by slightly vindictive
    if "d" in their_flipped_plays[-2:]:
        return "d"

    return "c"

```

Plays nice for the first 7 rounds, then switches to tit-tit for tat, and finally switches to only defecting after turn 30. Also detects initial patterns where it is optimal to always cooperate.
> 5 votes

# Answer
# Prisoner

```
def use_their_response_unless_they_are_foolish(my_plays, their_flipped_plays, state):
    # play "c" at beginning
    if not len(my_plays): return 'c'
    # play "d" at last few turns
    if len(my_plays) > 96: return 'd'
    # if op always answer "c", we can cheat on it
    if 60 < len(my_plays) < 1.8 * their_flipped_plays.count('c'): return 'd'
    # otherwise, play 'c' they play 'c'
    if their_flipped_plays[-4:].count('c') >= 2: return 'c'
    # or randomly select a response from their past behavior
    rand = their_flipped_plays * 5 + ['c', 'd']
    return rand[(int('0x' + ''.join(their_flipped_plays), 16) ^ 17 ** len(my_plays)) % len(rand)]

```
> 4 votes

# Answer
# Holding A Grudge (prisoner)

```
def holding_a_grudge(
    my_plays, their_flipped_plays, state
):
    # First cooperate for 7 plays:
    if len(my_plays) < 7: return 'c'

    # If 3 or more of their first 7 plays were defects,
    # hold a grudge for the entire round and keep defecting as well:
    amountOfDefects = their_flipped_plays[:7].count('d')
    if amountOfDefects >= 3: return 'd'

    # If none of their first 7 plays were defects, always cooperate yourself:
    if amountOfDefects == 0: return 'c'

    # Otherwise, cooperate 3/4th of the times:
    rand = (int('0x' + ''.join(their_flipped_plays), 16) ^ 17 ** len(my_plays)) % 100
    if rand >= 25: return 'c'
    return 'd'

```

(`rand` taken from *@tsh*' answer.)
> 4 votes

# Answer
# Tit Forty Tat (Prisoner)

```
def tit_forty_tat(my_plays, their_plays, state):
    defects = their_plays.count('d')
    if(defects > 40):
        return their_plays[-1]
    else:
        return 'c'

```

*Fool me 40 times, shame on you. Fool me 41 times...*

Assumes any defect is the result of flipping, and an honest mistake. After 40 defects however, the other player **must** have defected intentionally, so we just play Tit for Tat for the rest of the round.
> 3 votes

# Answer
# Slightly Vindictive (prisoner)

```
def slightly_vindictive(my_plays, their_flipped_plays, state):
    # play nice(-ish) if they've ever cooperated
    if 'c' in their_flipped_plays:
        # defect twice when they defect once
        if 'd' in their_flipped_plays[-2:]:
            return 'd'
        return 'c'
    # wait up to 10 turns for opponent to cooperate
    if len(my_plays) <= 10: return 'c'
    return 'd'

```
> 2 votes

# Answer
# Tempting Trickster (flipper)

```
def tempting_trickster(
    p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state
):
    # Tease them a bit
    target = 'dc'[len(p1_moves) <= 3]

    move = p1_moves[-1] == target
    move |= (p2_moves[-1] == target) << 1
    return move

```

Inspired by a more ambitious prisoner I'm working on...

What if the best way to get prisoners to defect is not to actually make them look *bad* to each other, but rather to convince them that

1. the other prisoner is very patient and won't retaliate too quickly if offended
2. if you defect for real, the flipper will actually cover for you?

The answer is a pretty hard "no" in a test run--this barely does better than not flipping at all--but maybe it'll have its time to shine later.
> 2 votes

# Answer
## Detect Evil

The goal here is to detect if the opponent is evil. We use our knowledge of the 40 max count of flips to hedge our bets.

```
def detect_evil(my_plays, their_plays, state):
  turn = len(their_plays)
  # Batter through the flipper by sending more than 20 "c"s to start:
  if (turn < 22):
    return "c"

  # Defect last few turns, just because
  if (turn > 96):
    return "d"

  # See if it is plausible that they are always cooperating.  If so, cooperate:
  their_coop = their_plays.count("c")
  if (their_coop + 20 >= turn):
    return "c"

  # seed possible returns to cooperation around the half-way point:
  if (turn > 49 and ((turn % 7) == 0)):
    return "c"

  # Try to return to cooperation state if they "c"'d last turn in response
  # or in coordination with my "c":
  if (their_plays[-1:] == ["c"]) and (my_plays[-2:].count("c") > 0):
    return "c"

  # Assume flipper flips 20 "c" to "d" on their side:
  their_defect = their_plays.count("d")
  their_defect_min = their_defect-20
  their_defect_chance = their_defect_min / turn if (turn > 0) else 0

  # Assume flipper flips 20 "c" to "d" on my side:
  my_defect = my_plays.count("d")
  my_defect_max_count = my_defect + 20
  my_defect_chance = my_defect_max_count / turn if (turn > 0) else 0

  # Tit-tit-tit for tat, but only if they are probably defecting more than
  # they see me defecting:
  if their_plays[-3:].count("d") > 0:
    if my_defect_chance < their_defect_chance:
      return "d"

  # Otherwise, assume the best:
  return "c"

```

we don't try to detect stupidity in our counterparty ("c" always, regardless of our "d"), just evil (sends "d"s at us).

The enemy "d"ing as many times as they see us "d" is considered "fair", and we assume the flipper is making both of us look more evil than we are.

If the enemy is detected as evil, we defect whenever we see a "d" in the last 3 turns. Otherwise, we cooperate always.

Finally, throw in some unilateral "c"s in the last half of the game, to prevent the hostile "tit tit tit for tat" from leading to a needless chain of "d". A bit of forgiveness.

(I'll be back to fix typos.)
> 2 votes

# Answer
# Modulo 4 (flipper)

```
def basic_mod_4_flipper(
    p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state
):
    return len(p1_flipped_moves) % 4

```

Very simple submission, but still effective
> 2 votes

# Answer
## Make P1 Look Evil Flipper

```
def basic_evil_p1_flipper(
  p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state
):
  out = 0
  if p1_moves[-1] == "c":
    out += 1
  return out

```

but the problem is, P1 could see a friendly P2. And if P2 isn't vindictive enough, P1 could work out that P2 is nice, and stubbornly refuse to defect.

So we allocate up to 10 flips to shutting down P2's overtures of niceness, and the remainder make P1 look like they always-defect.

## Fool P1 as well

```
def advanced_evil_p1_flipper(
  p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state
):
  out = 0
  if p1_moves[-1] == "c":
    out += 1
  turn = len(p1_flipped_moves)
  turns_left = 100-turn
  p1_coop = p1_moves.count("c")
  p1_visible = p1_flipped_moves.count("c")
  p1_flips_used = p1_coop - p1_visible
  p1_coop_percent = p1_coop / turn if turn > 0 else p1_coop

  p2_coop = p2_moves.count("c")
  p2_visible = p2_flipped_moves.count("c")
  p2_flips_used = p2_coop - p2_visible

  flips_left = 40 - p1_flips_used - p2_flips_used

  if (p2_coop <= 10 or (flips_left > (p1_coop_percent*turns_left))):
    if (p2_moves[-1] == "c"):
      out += 2

  return out

```

Here, we always flip P1 if we can.

We expend flips to make P2 always defect if it is before turn 10, *or* if we project that we have enough flips to keep P1 always defecting while also flipping this move for P2.

So players looking for cooperation won't see it at the start of the game. If they decide to attempt to regain trust mid-way through the game, they still won't see cooperation. And if P2 assumes up to 20 fake defects on the other party will conclude P1 is evil, and hopefully give up on them.
> 1 votes

# Answer
# Stuck Buttons (Prisoner)

```
def stuck_buttons(my_plays, their_plays, state):
    if not state:
        state.append(4)
        state.append(-1)
        return 'c'

    if state[0]:
        state[0] -= 1
        return my_plays[-1]
    else:
        state[0] = 4
        state[1] += 1
        return their_plays[state[1]]

```

I want to use the tit for tat strategy, but the buttons for "cooperate" and "defect" have been used so much they're getting stuck. I can't seem to change my choice until after 4 turns!
> 1 votes

# Answer
# Blind Rage (Prisoner)

```
def blind_rage(my_plays, their_plays, state):
    if not state:
        # Start in a good mood
        state.append(0)
        return 'c'

    if state[0] >= 5:
        # Calming down...
        state[0] = 0
        return 'c'

    if state[0]:
        # Rage mode
        state[0] += 1
        return 'd'

    if their_plays[-1] == 'd':
        # "You dare defect against me? I'll show you!"
        state[0] += 1
        return 'd'

    # Normal course of operation.
    return 'c'

```

Usually a cooperative prisoner, this one will fly into a blind rage when the opponent defects. Only calms down after 5 moves.
> 1 votes

# Answer
# Less-Deterministic

## Prisoner

```
def less_deterministic_prisoner(my_plays, their_plays, state):
    if not state:
        state.append(0xe1)  # Initial state
        state.append(8)  # Whether to collect more info for seed
        state.append(False)  # PRNG has been initialized?

        return 'c'

    if state[1]:
        # Seed the PRNG with the data we get
        state[0] <<= 1
        state[0] |= (their_plays[-1] == 'd')
        state[1] -= 1

        return 'c'

    if not state[2]:
        # XOR with some data for some good old security through obscurity.
        state[0] ^= 0x03
        state[2] = True

    # PRNG is properly seeded now!
    my_choice = (state[0] & 0x8000) >> 15

    tap16 = (state[0] & 0x8000) >> 15
    tap15 = (state[0] & 0x4000) >> 14
    tap13 = (state[0] & 0x1000) >> 12
    tap4 = (state[0] & 0x0008) >> 3

    feedback = tap16 ^ tap15 ^ tap13 ^ tap4

    state[0] <<= 1
    state[0] &= 0xffff
    state[0] |= feedback

    return 'cd'[my_choice]

```

## Flipper

```
def less_deterministic_flipper(p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state):
    if not state:
        state.append(0x21)  # Initial state
        state.append(4)  # Whether to collect more info for seed
        state.append(False)  # PRNG has been initialized?

        return 0

    if state[1]:
        # Seed the PRNG with the data we get
        state[0] <<= 1
        state[0] |= (p1_moves[-1] == 'd')
        state[0] <<= 1
        state[0] |= (p2_moves[-1] == 'd')
        state[1] -= 1

        return 0

    if not state[2]:
        # XOR with some data for some good old security through obscurity.
        state[0] ^= 0x44
        state[2] = True

    # PRNG is properly seeded now!
    first_bit = (state[0] & 0x8000) >> 15

    tap16 = (state[0] & 0x8000) >> 15
    tap15 = (state[0] & 0x4000) >> 14
    tap13 = (state[0] & 0x1000) >> 12
    tap4 = (state[0] & 0x0008) >> 3

    feedback = tap16 ^ tap15 ^ tap13 ^ tap4

    state[0] <<= 1
    state[0] &= 0xffff
    state[0] |= feedback

    second_bit = (state[0] & 0x8000) >> 15

    tap16 = (state[0] & 0x8000) >> 15
    tap15 = (state[0] & 0x4000) >> 14
    tap13 = (state[0] & 0x1000) >> 12
    tap4 = (state[0] & 0x0008) >> 3

    feedback = tap16 ^ tap15 ^ tap13 ^ tap4

    state[0] <<= 1
    state[0] &= 0xffff
    state[0] |= feedback

    # Use the two bits to make a choice
    choice = first_bit << 1
    choice |= second_bit

    return choice

```

Implements a simple PRNG that is seeded with the input we get from the opponent. With three total players in the mix, surely there's no way the others will be able to reliably influence our PRNG for their gain, right?

This bot is different from `basic_random_flipper` as it attempts to output a different sequence for each interaction.
> 1 votes

# Answer
# Non-deterministic

*EDIT: This bot is non-competing - see @isaacg's comment below.*

## Prisoner

```
def non_deterministic_prisoner(my_plays, their_plays, state):
    state.append(object())
    return 'cd'[hash(str(state)) % 128 < 65]

```

## Flipper

```
def non_deterministic_flipper(p1_moves, p1_flipped_moves, p2_moves, p2_flipped_moves, flips_left, state):
    state.append(object())
    return hash(str(state)) % 4

```

`basic_random_flipper` is in fact deterministic (in that it will flip the same way given the same state). This flipper relies on where it is placed in memory, which means it will output different results even if given the same state.

I suppose it's not *technically* non-deterministic as you could in theory predict where the objects will be created in memory.
> 0 votes

---
Tags: game, king-of-the-hill, python
---


title: Base consecutive k-frequency counter

text:
# Question
Title: Base consecutive k-frequency counter
Given a base \\$k\\$ as well as two indices (also passed in base \\$k\\$, call them \\$s\\$ and \\$e\\$) return a list containing a frequency count of all base-\\$k\\$ digits occurring between \\$s\\$ and \\$e\\$ inclusive. For example, upon input \\$k = 10, s = 1, e = 10\\$, we would return the list \\$\[0: 1, 1: 2, 2: 1, 3: 1, 4:1, 5:1, 6:1 , 7:1, 8:1, 9:1\]\\$. Note that the values in the list should be base \\$k\\$ as well.

# Answer
# Vyxal, 75 bitsv2, 9.375 bytes

```
vβ÷ṡ⁰τfĊ⁰τ

```

Accepts input as \\$\[s, e\], k\\$. Takes in indices as a list of digits (to be able to take numbers of bases greater than 10).

Try it Online! | Another example

Bitstring:

```
100011000100010100000110110111110010011010110100010011110011110110000110010

```

```
vβ÷ṡ⁰τfĊ⁰τ
vβ          Convert each index to base 10
  ÷ṡ        Split to stack and push range
    ⁰τ      Convert range to base k
      fĊ    Flatten list and push counts
        ⁰τ  Convert counts list to base k

```
> 4 votes

# Answer
# Python, 163 bytes

```
def f(k,s,e):b=lambda n:n and b(n//k).lstrip("0")+[str(n%k),chr(n%k+55)][n%k>9]or"0";a="".join(map(b,range(int(s,k),int(e,k)+1)));return{c:b(a.count(c))for c in a}

```

Attempt This Online!

Basic solution; a majority of the code is taken up by the helper function converting from base 10 to base \\$k\\$. I'm sure you could do something clever with a function which directly counts from \\$s\\$ to \\$e\\$ in base \\$k\\$. Only works for bases between 2 and 36.
> 2 votes

# Answer
# Ruby, 80 bytes

```
->k,s,e{(s.to_i(k)..e.to_i(k)).flat_map{_1.digits k}.tally.map{[_1,_2.to_s(k)]}}

```

Attempt This Online!

Takes `k` as integer, `s` and `e` as strings in base `k`. Test cases taken from math scat's Vyxal answer.
> 2 votes

# Answer
# Haskell, 148 bytes

```
import Data.List
k#n|n<k=[n]
k#n|(d,m)<-divMod n k=m:k#d
f k s e=[(last(show x:[[toEnum$x+55]|x>9]),1+length y)|x:y<-group$sort$concatMap(k#)[s..e]]

```

Attempt This Online!
> 1 votes

# Answer
# Google Sheets, 228 bytes

`=let(_,lambda(v,base(v,A1)),r,query(tocol(sort(to_text(split(regexreplace(join(,map(sequence(A3-A2+1,1,A2),_)),"(.)","$1 ")," ")))),"select count(Col1),Col1 group by Col1 label count(Col1)''",0),{map(index(r,,1),_),index(r,,2)})`

Put the base in cell `A1`, start in `A2` and end in `A3`, and the formula in `C1`.

The same ungolfed:

```
=let(
  _, lambda(v, base(v, A1)),
  values, sequence(A3 - A2 + 1, 1, A2),
  string, join(, map(values, _)),
  digits, tocol(sort(to_text(split(regexreplace(string, "(.)", "$1 "), " ")))),
  result, query(
    digits,
    "select count(Col1), Col1 group by Col1 label count(Col1)''",
    0
  ),
  hstack(
    map(index(result, , 1), _),
    index(result, , 2)
  )
)

```

| parameters |  | results |  |
| --- | --- | --- | --- |
| 16 | base | C | 0 |
| 1 | start | 1D | 1 |
| 200 | end | 1D | 2 |
|  |  | 1D | 3 |
|  |  | 1D | 4 |
|  |  | 1D | 5 |
|  |  | 1D | 6 |
|  |  | 1D | 7 |
|  |  | 1D | 8 |
|  |  | 1C | 9 |
|  |  | 1C | A |
|  |  | 1C | B |
|  |  | 15 | C |
|  |  | C | D |
|  |  | C | E |
|  |  | C | F |
> 1 votes

---
Tags: base-conversion
---


title: Increment an Array

text:
# Question
Title: Increment an Array
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
> 18 votes
# 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
> 13 votes
# 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
> 9 votes
# 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
> 9 votes
# 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 `some`s 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
> 7 votes
# 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 votes
# 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
> 5 votes
## 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
> 4 votes
# 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
> 4 votes
## 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
> 4 votes
# , ~~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
> 4 votes
# APL (Dyalog Unicode), 48 bytes

```
f←{1≥≢∪⍵:⍵,1⋄1+@(⊃⍋⍵)⊢⍵}

```

Try it online!

Alternate versions of `1+@(⊃⍋⍵)⊢⍵`: `⍵+(⍳≢⍵)=⊃⍋⍵`, `⊢+⍳∘≢=⊃∘⍋`. -2 thanks to @Adam and @Razetime.

Explanation:

```
{1≥≢∪⍵:⍵,1⋄1+@(⊃⍋⍵)⊢⍵}
 1≥≢∪⍵                   ⍝ if all elements are identical
       ⍵,1               ⍝ then yield ⍵ with 1 appended to the end.
          ⋄              ⍝ ... else,
              (⊃⍋⍵)      ⍝ index of the smallest value
           1+@     ⊢⍵    ⍝ increment the value from ⍵

```

# Answer
> 3 votes
# 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
> 3 votes
# 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
> 3 votes
# 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
> 3 votes
## 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
> 3 votes
# AWK, 63 bytes

```
a=b=1{for(;$++a;d=$b==$a&&c==$a?a+1:b)b=(c=$b)>$a?a:b;$d++}++NF

```

Try it online!

The code scans all the numbers presented on the input line and sets variable, `d`, to the position of the smallest number, or to the number of fields plus one if all values are equal. Then it increments the number at that position and prints everything. As a result it either adds a new field with a value of 1 or increments the smallest number in the given set of numbers.

The first condition/test is always true, and just does some initialization.

```
a=b=1

```

The code block is a `for` loop, which applies one statement to each number from the input line.

```
for(;$++a;d=$b==$a&&c==$a?a+1:b)b=(c=$b)>$a?a:b

```

The check to continue iterating just increments the `a` "current field" variable and stops when it's gets a 0 (by running off the end of the list).

```
    $++a

```

The body of the loop updates `b` such that it's always pointing to the position of the smallest number in the input. The code also has to save the previous position of the smallest number, stored in `c`, to deal with cases where the minimum is the last number on the line.

```
    b=(c=$b)>$a?a:b

```

The "end of loop" statement sets variable `d` to the current field "plus one" if the current value matches the current minimum as well as the previous minimum, or to the position of the current minimum otherwise.

```
    d=$b==$a&&c==$a?a+1:b

```

One the loop completes, the code increments whichever field `d` points to. If all the fields are the same, it will increment an uninitialized field, which in AWK will default to 0. Otherwise it will increment the first field with the smallest value.

```
$d++

```

The second condition/test just increments the number of fields in the input line, which will always evaluate to true. If all the fields were the same numeric value, that change in `NF` will cause a `1` to be appended to the list. And if it changed one of the presented fields the additional field printed as a result of incrementing `NF` will be an empty string.

```
++NF

```

# Answer
> 2 votes
# Jelly, 9 bytes

```
;1µ‘i¦E?Ṃ

```

Thanks to Dennis for the -2 bytes.

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

# Answer
> 2 votes
**Mathematica, 53 bytes 57 bytes 59 bytes**

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

```

# Answer
> 2 votes
# 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
> 2 votes
# , 63 bytes

```
`if`(any((v=scan())-v[1]),{v[m]=v[m<-which.min(v)]+1;v},c(v,1))

```

Try it online!

Had a shot at this without peeking at the previous R answer first.

Although the overall approaches are pretty similar, this pleasingly comes-out 2 bytes shorter.

Here we use a code block (enclosed in curly brackets `{}`) as an expression, which allows us to adjust a chosen element of the input vector `v`, and let the expression evaluate to the new value of `v`.
Shorter, but less fancy than the previous approach of abusing the indexing operator `[<-` as a function (which definitely deserves an upvote anyway).

# Answer
> 2 votes
# Vyxal `aW`, ~~21~~ 18 bytes

*-3 bytes by using the register instead of variables.*

```
:≈[1J|:g£(nn¥=[›0£

```

Try it Online With Equal Elements!

Try it Online With Unequal Elements!

Explanation:

```
                    # Implicit input; a flag takes input as list
:                   # Duplicate input
 ≈[1J               # If all elements are equal: append 1
     |:g£           # Else: save minimum value to the register
         (          # For every element in the input:
          n         # Duplicate current element n
           n¥=[     # If current element n == register value:
               ›0£  # Increment current element and clear the register
                    # Implicit output; W flag outputs full stack

```

# Answer
> 2 votes
# Brachylog, ~~20~~ 17 bytes

```
=,1|iᶠo{+₁ʰ}ʰtᵒhᵐ

```

Try it online!

### Explanation

The first case is easy. The second is less so.

```
=,1|iᶠo{+₁ʰ}ʰtᵒhᵐ
=                  Assert that all elements are equal
 ,1                Append 1
   |               If that failed, try the following instead:
    iᶠ             Get a list of [value, index] pairs for every item in the array
      o            Sort: put smallest value first, and smallest index for equal values
       {   }ʰ      Apply this predicate to the first element of the resulting list:
        +₁ʰ          Add 1 to its first element (first occurrence of min value)
             tᵒ    Sort by the second element of each sublist (index)
               hᵐ  Head of each sublist (value)

```

Here's a worked example of the second branch:

```
               Input: [2,3,1,5,1]
iᶠ             [[2,0], [3,1], [1,2], [5,3], [1,4]]
  o            [[1,2], [1,4], [2,0], [3,1], [5,3]]
   {+₁ʰ}ʰ      [[2,2], [1,4], [2,0], [3,1], [5,3]]
         tᵒ    [[2,0], [3,1], [2,2], [5,3], [1,4]]
           hᵐ  [2,3,2,5,1]

```

# Answer
> 2 votes
# APL (Dyalog Unicode), 20 bytes

```
{⍵+<\⍵=⌊/⍵}⊢,0~⍬≡⊢~⊃

```

Try it online!

First we append a zero if the input is unique, then increment the first minimum (which will be the trailing zero in the unique case, as the numbers in the input are positive)

`⊢~⊃` Input without all occurences of the first element.
`⍬≡` Is this the empty vector? (are values in the input the same)
`0~` 0 without the result of that (a single 0 if all values are the same, empty vector otherwise)
`⊢,` Append this to the input

`{⍵+<\⍵=⌊/⍵}` Increment the first minimum.
`⌊/⍵` Minimum value
`⍵=` Boolean vector with 1's at all minima
`<\` Less-than scan; only leaves the first 1
`⍵+` Add this boolean vector to the previous vector

# Answer
> 2 votes
# Thunno 2, 11 bytes

```
ạ?1a:MçȮ⁺Ẹȧ

```

Attempt This Online!

#### Explanation

```
ạ?1a:MçȮ⁺Ẹȧ  # Implicit input
ạ            # Is it all equal?
 ?           # If it is:
  1a         #  Append a 1
    :        # Otherwise:
     M       #  Take the minimum
      ç  Ẹ   #  Parallely apply:
       Ȯ     #   Index of the minimum
        ⁺    #   Increment the minimum
          ȧ  #  Assign the new value
             # Implicit output

```

# Answer
> 2 votes
# , 45 bytes

```
\(x)`if`(sd(c(x,x)),x+!rank(x,,"f")-1,c(x,1))

```

Attempt This Online!

This would be 4 bytes longer as a full program, which is a fairer comparison to earlier answers that had been posted when backslash functions were not yet a thing, and full program was a golfier approach:

## , 49 bytes

```
`if`(sd(c(x<-scan(),x)),x+!rank(x,,"f")-1,c(x,1))

```

Attempt This Online!

# Answer
> 1 votes
# 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
> 1 votes
# 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
> 1 votes
## 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
> 1 votes
# 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
> 1 votes
# 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
> 1 votes
# **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
> 1 votes
**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
> 1 votes
# 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
> 1 votes
# 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
> 1 votes
# 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
> 1 votes
# K (oK), 24 bytes

**Solution:**

```
{(x[x?&/x]+:1;x,1)1=#?x}

```

Try it online!

**Explanation:**

Nothing too fancy, potentially golfable further:

```
{(x[x?&/x]+:1;x,1)1=#?x} / the solution
{                      } / anonymous lambda taking implicit x argument
                     ?x  / get distinct values in x
                    #    / count length
                  1=     / is it 1?
 (           ;   )       / two item list which is index into
              x,1        / append 1 to input
  x[     ]+:1            / modify x in-place (add 1) at index given in []
      &/x                / minimum of x
    x?                   / lookup index (returns first one)

```

# Answer
> 1 votes
# Vyxal, 10 bytes

```
≈[1J|g₌ḟ›Ȧ  # main program

```

```
≈           # all elements in input are equal
 [1J|g₌ḟ›Ȧ  # main if statement
  1J        # if true, append 1 to input
     g₌ḟ›Ȧ  # if false...
     g      # get the minimum
      ₌ḟ›   # push the index of the min and the increment of the min
         Ȧ  # set that index to the increment
            # implicit output

```

I came up with this independently but surprisingly it was pretty similar in structure to @AaronMiller's answer. Try it Online!

# Answer
> 1 votes
# JavaScript, 55 bytes

```
a=>a.every(e=>e==a[0])?a.push(1):a.fill(Math.max(...a))

```

Modifies the array passed to it, otherwise, it's 3 bytes longer:

```
a=>a.every(e=>e==a[0])?a.push(1)&&a:a.fill(Math.max(...a))

```

Try it Online!

## Explanation

```
a=>a.every          // Check that every element "e"...
  (e=>e==a[0])      // ...is equal to the first element.
    ?a.push(1)      // If it's the case push 1 at the end.
      :a.fill       // Else fill the entire array...
        (Math.max   // ...with the biggest...
          (...a))   // ...entry of the array.

```

### Some notable parts

* Checking the first element of the array is valid because all of the elements needs to be the same anyways
* If the array have different elements, it will end up being an array filled with the largest number anyways, so let's do directly that

# Answer
> 1 votes
# PowerShell, ~~76~~ 60 bytes

```
$x,$y=($a=$args)|sort -u
$a[$a.IndexOf(+$x)]+=!!$y
$a+,1*!$y

```

Try it online!

# Answer
> 1 votes
# Uiua, 19 bytes

```
(⍜⊡'+1⊢⍏.|⊂∶1)≍↻1..

```

Try it!

```
(⍜⊡'+1⊢⍏.|⊂∶1)≍↻1..
                  .  # duplicate
              ≍↻1.   # are all elements equal?
(        |   )       # run the left part if not, or right part if so
          ⊂∶1        # append 1 to end
        .            # duplicate
      ⊢⍏             # index of minimum element
 ⍜⊡'+1               # increment value at that index

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), 50 bytes

```
If[Equal@@#,Append@1,1+#&~MapAt~#&@@Ordering@#]@#&

```

Try it online!

# Answer
> 1 votes
# Uiua, 14 bytes

```
⬚0+⍘⊚?⧻⊢≍,⊃⍖⍏.

```

Try it online!

Finds the 0-based index to increment (or the length if the elements are all equal), and adds 1 at that index. The  (rise; the indices in the array that would put the values in sorted order) is reused three times:

* "all equal" test can be done with "rise matches fall"
* "the first index of minimum element" is "first of rise"
* "the length of the array" is the same as "the length of rise"

```
⬚0+⍘⊚?⧻⊢≍,⊃⍖⍏.    input: an array of positive integers A
            ⊃⍖⍏.   push fall(A), rise(A), A
          ≍,         keep rise(A) and evaluate "rise(A) == fall(A)"
      ?⧻⊢            if so, call length; otherwise call first on rise(A)
    ⍘⊚              inverse where; create an array B so that B[i] == count of i
                     (3 -> [0, 0, 0, 1])
⬚0+                  elementwise add the result to A, padding with zeros if needed

```

# Answer
> 0 votes
# 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
> 0 votes
# 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
> 0 votes
# 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
> 0 votes
## 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
> 0 votes
# 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:

# Answer
> 0 votes
## 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
> 0 votes
# 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
> 0 votes
# 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
> 0 votes
# 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
> 0 votes
# Perl 5 `-MList::Util=,reduce -pa`, ~~75~~ 68 bytes

```
$F[(grep$_-$F[0],@F)?reduce{$F[$a]>$F[$b]?$b:$a}0..$#F:@F]++;$_="@F"

```

Try it online!

# Answer
> 0 votes
# Julia 1.8, 44 bytes

```
!x=allequal(x) ? [x;1] : (x[argmin(x)]+=1;x)

```

Attempt This Online!

`allequal` requires julia 1.8 or later

# Answer
> 0 votes
# Vim, 49 bytes

```
y$i,<esc>:s/^\(,\d*\)\1*$/&,0
/\<<C-r>=min([<C-r>"])
\>
f0<C-a>|x

```

Takes the array as comma-separated integers in the buffer. Try it online!

### Explanation

```
y$i,<esc>

```

Yank the original list of integers; then insert an extra comma at the beginning.

```
:s/^\(,\d*\)\1*$/&,0<cr>

```

Using regex, determine if the entire line consists of the same number. If so, append `,0`.

```
/\<...\><cr>

```

Find the first match of `...` as a full word (`\<` and `\>` represent word boundaries, corresponding to `\b` in PCRE), where `...` is:

```
<C-r>=min([<C-r>"])<cr>

```

Using the expression register, calculate the minimum of the original list.

If the original list was heterogeneous, the cursor is now on the number we want to increment. If the original list was all equal, however, we want to increment the 0 at the end, so:

```
f0

```

Move to the next occurrence of `0` on the line. If there is no `0`, this does nothing.

```
<C-a>|x

```

Increment the number under the cursor. Go to the beginning of the line and delete the extra comma.

# Answer
> 0 votes
# Factor, 77 bytes

```
[ dup all-eq? [ 1 suffix ] [ dup [ ] infimum-by* 1 + swap pick set-nth ] if ]

```

Try it online!

Went through a bunch of different iterations of this. `tri` was shorter than stack shufflers, amazingly, when using `change-nth`, but locals were king. However, we can attain even fewer bytes by using `infimum-by*`, which places both the index and value of the smallest element on the stack.

# Answer
> 0 votes
# Arturo, ~~60~~ 56 bytes

```
$->a->([]=a--a\0)?->a++1[i:index a min a a\[i]:a\[i]+1a]

```

Try it

# Answer
> 0 votes
# Scala, 159 bytes

Golfed version. Try it online!

```
a=>{def g(l:List[Int]):List[Int]=l match{case x::q if x==a.min=>(x+1)::q;case x::q=>x::g(q);case _=>Nil};if(a.distinct.length==1)a:+1 else g(a.toList).toArray}

```

Ungolfed version. Try it online!

```
object Main extends App {

  def incrementArray(arr: Array[Int]): Array[Int] = {
    val minVal = arr.min
    def g(list: List[Int], m: Int): List[Int] = list match {
      case x :: xs if x == m => (x + 1) :: xs
      case x :: xs           => x :: g(xs, m)
      case Nil               => Nil
    }
    if (arr.distinct.length == 1) arr :+ 1
    else g(arr.toList, minVal).toArray
  }

  var r = Array(3, 1, 1);
  for (i <- 1 to 10) {
    r = incrementArray(r)
    println(r.mkString(", "))
  }

}

```

---
Tags: code-golf, number, arithmetic, array, integer
---