text:
Honest Rock, Paper, Scissors
Many people consider RPS to be a game of chance. If both players play unpredictably, the best strategy is to play randomly. However, let's introduce a bit of predictability to it.
Each bot will have a chance to tell the other bot what it's going to play simultaneously. Then there is a pause in which each bot will know what the other player announced. If it plays that weapon it announced it will score one point in addition to its points for a win loss or draw.
A win is worth two points, a draw, one point, and a loss 0 points.
     Honest Bot       Dishonest
Win     3                  2
Draw    2                  1
Loss    1                  0

It is in your best interest to be honest (but also to make sure your opponent does not believe you).
The matches will be played in a round robin format, and the objective will be to maximise your own total score across the matches you play.
I/O Format:

Your bot will be a Python 2.7 function that takes 4 arguments, and must have a unique name (which will be used to represent your submission).
The first two arguments will always be, in order: the opponent's past moves, followed by your past moves.  These will be a list in order from first to most recent round, with each index containing a list with the move the opponent claimed they would make, followed by the move they actually made.
The next two arguments will allow your bot to determine if this is an "honest" round or a "real" round.  If it is an "honest" round, they will both be None.  If it is a "real" round, they will be, in order, the move your opponent declared they would make, followed by the move you declared you would make.
All arguments or portions of arguments that represent moves will use "R", "P", and "S" to represent rock, paper, and scissors, respectively.
Your function should return either an "R" for rock, a "P" for paper, or an "S" for scissors.  Bots that have the ability to return other values will be disqualified.
Each bot will be run against every other bot 200 times, and itself 100 times.  The goal is to be the bot with the most points at the end of the competition.
In regards to discussion in the comments, submissions may not read from or write to any file, or in any way sabotage or read opponent's code.

Examples:
These are four example bots I put together quickly.  They will be joining the competition as additional bots.  If you lose to the last one, you have some work to do.
def honestpaper(I,dont,care,about_these):
    return "P"

def honestrock(I,dont,care,about_these):
    return "R"

def honestscissors(I,dont,care,about_these):
    return "S"

import random
def randombot(I,dont,care,about_these):
    return random.choice(["R","P","S"])

Controller:
And here's the controller I'll be using.  New submissions will be imported at the beginning and added to the bot_map dictionary.
from honestrock import honestrock
from honestpaper import honestpaper
from honestscissors import honestscissors
from randombot import randombot

bot_map = {
  0:honestrock, 1:honestpaper, 2:honestscissors, 3:randombot
}

player_num=len(bot_map)

def real(history1,history2,number,honest1,honest2):
    return bot_map[number](history1,history2,honest1,honest2)

def honest(history1,history2,number):
    return bot_map[number](history1,history2,None,None)

def play_match(num1,num2):
    history1=[]
    history2=[]
    score1=0
    score2=0
    for x in range(250):
        h1=honest(history2,history1,num1)
        h2=honest(history1,history2,num2)
        r1=real(history2,history1,num1,h2,h1)
        r2=real(history1,history2,num2,h1,h2)

        if h1==r1: score1+=1
        if h2==r2: score2+=1

        if r1==r2: score1+=1; score2+=1
        elif r1=="R":
            if r2=="P": score2+=2
            else: score1+=2
        elif r1=="P":
            if r2=="S": score2+=2
            else: score1+=2
        else:
            if r2=="R": score2+=2
            else: score1+=2

        history1.append([h1,r1])
        history2.append([h2,r2])
    return score1,score2

scores = []
for x in range(player_num):
    scores.append(0)

for _ in range(100):

    for x in range(player_num):
        for y in range(player_num):
            scorex,scorey=play_match(x,y)
            scores[x]+=scorex
            scores[y]+=scorey

for score in scores:
    print score

Final Scores:
csbot                    3430397
thompson                 3410414
rlbot                    3340373
have_we_been_here_before 3270133
mason                    3227817
deepthought              3019363
adaptive_bot             2957506
THEbot                   2810535
dontlietome              2752984
irememberhowyoulie       2683508
learningbot4             2678388
betrayal                 2635901
averager                 2593368
honestrandom             2580764
twothirds                2568620
mirrorbot                2539016
tit4tat                  2537981
honestscissors           2486401
trusting_bot             2466662
rotate_scissors          2456069
rotate_paper             2455038
rotate_rock              2454999
honestpaper              2412600
honestrock               2361196
rockBot                  2283604
trustingRandom           2266456
user5957401bot           2250887
randombot                2065943
Dx                       1622238
liarliar                 1532558
everybodylies            1452785

What's the status?

Mason
Tries to pick up information about other bots such as how honest they are and how they're effected by my first move. I then try and find other obvious bots that follow a pattern and exploit those into giving me more points. Finally, the Mason has a secret weapon: knowledge of a secret society where both bots participating mutually go for a full draw, gaining 500 points each. Unfortunately the secret is rather... Well secret and changes every time the Mason does.
def mason(op_hist, my_hist, op_move, my_move):
    win_map = {"R": "P", "P": "S", "S": "R"}
    lose_map = {"R": "S", "P": "R", "S": "P"}
    if not len(op_hist):
        return "S"
    if op_hist[0] == ['S', 'S']:
        code = "S" + "".join("RPS"[ord(i) % 3] if isinstance(i, str) else "RPS"[i % 3] for i in __import__("sys")._getframe().f_code.co_code)[1::2]
        honest, guess = zip(*op_hist)
        if honest == guess == tuple(code[:len(op_hist)]):
            return code[len(op_hist)]
    op_honesty = sum(len(set(round))-1 for round in op_hist) / float(len(op_hist))
    if not my_move:
        moves = "".join(i[1] for i in op_hist)
        # Identify rotators
        if "PSRPSR" in moves:
            return moves[-2]
        # Identify consecutive moves
        if "RRRRR" in moves[:-10] or "SSSSS" in moves[:-10] or "PPPPP" in moves[:-10]:
            return win_map[moves[-1]]
        # Try just what wins against whatever they choose most
        return win_map[max("RPS", key=moves.count)]
    op_beats_my_honest = sum(win_map[me[0]] == op[1] for op, me in zip(op_hist, my_hist)) / float(len(op_hist))
    op_draws_my_honest = sum(me[0] == op[1] for op, me in zip(op_hist, my_hist)) / float(len(op_hist))
    op_loses_my_honest = sum(lose_map[me[0]] == op[1] for op, me in zip(op_hist, my_hist)) / float(len(op_hist))
    if op_honesty <= 0.4:
        return win_map[op_move]
    max_prob = max((op_loses_my_honest, op_draws_my_honest, op_beats_my_honest))
    if max_prob >= 0.6:
        if op_beats_my_honest == max_prob:
            return lose_map[my_move]
        if op_draws_my_honest == max_prob:
            return win_map[my_move]
        if op_loses_my_honest == max_prob:
            return my_move
        assert False
    return my_move

Rlbot: reinforcement learning
Uses a reinforcement learning approach, tackling this game in a way similar to the n-armed bandit problem. It does so in two ways: tries to learn which declaration is better against each opponent and sticks to that one (useful against constant bots), and tries to learn the outcome of various moves in previous similar situations (similar in regard to the relative plays, e.g. rock vs paper is similar to a previous paper vs scissor). The initial assumptions are optimistic, so this player will assume that being honest will give it 3 points and lying will give 2, and will therefore always be honest until proven otherwise.
Update: The first tournament results highlighted a problem with this bot, which was its inability to detect patterns in its opponents' declarations (which made it play suboptimally against rotators). I've then added a pattern-matching component to the code for the honest rounds, which uses a regex to look for the longest suffix in the history of opponent declarations that is present somewhere previously in that history, and what move was played after that. We assume that the opponent will play the same move again, and use reinforcement learning as before to decide what the best answer to that should be.
import re
def rlbot(hismoves,mymoves,hismove,mymove):
 def score(d,m1,m2):
  s=0
  if m1==m2:
   s=1
  elif (m1+m2) in "RPSR":
   s=2
  return s+(d==m2)

 alpha=0.2
 if mymove:
  history=[([d1,m1],[d2,m2]) for ((d1,m1),(d2,m2)) in zip(hismoves,mymoves) if score(None,hismove,mymove)==score(None,d1,d2)]
  bestscore=-1
  bestmove=""
  for move in "RPS":
   ev=2+(move==mymove)
   for ((d1,m1),(d2,m2)) in history:
    if score(None,move,mymove)==score(None,m2,d2):
     ev=(1-alpha)*ev+alpha*score(d2,m1,m2)
   if ev>bestscore:
    bestscore=ev
    bestmove=move
  return bestmove

 else:
  if len(hismoves)==0:
   return "R"
  bestscore=-1
  bestmove=""
  hisdeclarations="".join(d for [d,m] in hismoves)
  predicted_move=re.search(r'(.*)\n.*\1(.)',hisdeclarations+'\n'+hisdeclarations).group(2)
  history=[([d1,m1],[d2,m2]) for ((d1,m1),(d2,m2)) in zip(hismoves,mymoves) if d1==predicted_move]
  for move in "RPS":
   ev=3
   for (his,my) in history:
    (d1,m1)=his
    (d2,m2)=my
    if d2==move:
     ev=(1-alpha)*ev+alpha*score(d2,m1,m2)
   if ev>bestscore:
    bestscore=ev
    bestmove=move
  return bestmove

Try it online!

I've never really used python much so I'm sure I've made a mistake somewhere.
import random
def learningbot3(opponentlist,a,opponent,me):
 #tell the other bot a random thing
 if opponent==None:
  return random.choice(["R","P","S"])
 #check whether the other bot has mostly told the truth in the last 10 rounds
 truth=0
 for game in opponentlist[-10:]:
  truth-=1
  if game[0]==game[1]:
   truth+=2
 #assume the other bot will tell the truth
 if truth>=3:
  if me==opponent:
    return me
  elif opponent=="R":
   return "P"
  elif opponent=="P":
   return "S"
  elif opponent=="S":
   return "R"
 #assume the other bot is lying
 elif truth<=-3:
  return random.choice([me,opponent])
  #return opponent
 #pick whatever we said we would
 else:
  return me

It should check the last 10 rounds to see how often the opponent lied, then chose a different response depending on that.

Here is my adaptive bot. It analyses the last 2 moves of the opponent to determine if it is an honest bot or not and plays accordingly:
Edit 1: If the other bot is a constant bot (ie. always plays the same weapon) this bot crushes it by playing the winning weapon and being honest at the same time.
Edit 2: Improved constant bot detector to work with rotator bots too.
import random
def adaptive_bot(other_past, my_past, other_next, my_next):
    winners = {"R": "P", "P": "S", "S": "R"}
    if my_next is None:
        return winners[other_past[-6:][0][1]] if other_past else random.choice(list(winners.keys()))
    else:
        is_other_honest = all([other_claim == other_move for other_claim, other_move in other_past[-2:]])
        return winners[other_next] if is_other_honest else my_next

csbot
def csbot(ophist,myhist,opdecl,mydecl):

  import random

  RPS = "RPS"

  def value(opd,myd,opmove,mymove):
    if opmove==mymove:
      val = 9
    elif opmove+mymove in RPS+RPS:
      val = 20
    else:
      val = -2
    return val+10*(myd==mymove)-(opd==opmove)

  def best(od,md):
    l = float(len(ophist))
    weights = dict([ (m, random.random()/8) for m in RPS ])
    for n in range(len(ophist)):
      if ophist[n][0]==od and myhist[n][0]==md:
        weights[ophist[n][1]] += 1+4*((n+1)/l)**2
    sw = sum([ weights[m] for m in RPS ])
    bestexpect = 0
    for m in RPS:
      expect = sum([ weights[om]/sw*value(od,md,om,m) for om in RPS ])
      if expect > bestexpect:
        bestexpect = expect
        bestmove = m
    return bestmove, bestexpect

  honest = all ([ decl==mv for decl, mv in ophist ])

  if honest:
    if mydecl<>None:
      return mydecl
    expnxt = set();
    for i in range(len(ophist)-1):
      if ophist[i][0]==ophist[-1][0]:
        expnxt.add(ophist[i+1][0])
    if len(expnxt)==1:
      return RPS[ (RPS.index(expnxt.pop())+1) % 3 ]

  if mydecl==None:
    l = float(len(ophist))
    weights = dict([ (m, random.random()) for m in RPS ])
    for n in range(len(ophist)):
      weights[ophist[n][0]] += 1+((n+1)/l)**2
    sw = sum([ weights[m] for m in RPS ])
    bestexpect = 0
    worstexpect = 99
    for m in RPS:
      expect = sum([ best(od,m)[1]/sw*weights[od] for od in RPS ])
      if expect > bestexpect:
        bestexpect = expect
        bestmove = m
      if expect < worstexpect:
        worstexpect = expect
    if bestexpect-worstexpect < 3:
      bestmove = random.choice(RPS)
    return bestmove

  return best(opdecl,mydecl)[0]

Be honest as long as the other player is, and detect simple deterministic bots. Play the move that maximizes the expected value, where we mostly go for our points, but also like to not give points to the other player. But own points are better by a factor of ten, hence the unusual numbers in the value function. Opponent moves are expected according to how often we have seen them before in this situation (declared moves), but recently seen moves are weighted more than moves seen earlier. For random initial moves (situations never seen before) and some extra fuzzyness, the weights include small extra random numbers.
Update: Use expected results also in the honest round. To be able to do this, normalize and take the additional point the opponent may get for honesty into account - it couldn't influence our decission in the real round but is needed now. I considered doing this from the beginning, but wrongfully thought it wouldn't be worthwhile. I saw that it would be possible to give trusting_bot less points (but that bot isn't a strong opponent anyway), but missed that extra points could be gained from rockbot by good play in the honest round even though its play in this round is random.

This does not always seem to return a result.

I think your if mydecl == None: is erroneous.

@user1502040 Why do you think so? I've never observed any problem.

@ChristianSievers https://stackoverflow.com/questions/3257919/what-is-the-difference-between-is-none-and-none

Betrayal
def betrayal(yours, mine, you ,me):
    import random
    if you is None:
        pick = random.choice(['R','P','S'])
    else:
        you = you[0]
        me = me[0]
        if len(yours) < 50: #Build myself a reputation of honesty
            pick = me
        else:
            if len(yours) >= 50 and len(yours) < 100:
                honesty = sum([1 if y[0]==y[1] else 0 for y in yours])/float(len(yours))
                if honesty <= 0.5: #If dishonest try to outwit
                    pick = 'S' if me=='R' else 'R' if me == 'P' else 'P'
                else: #Else just plain cheat
                    pick = 'P' if you=='R' else 'R' if you=='S' else 'S'
            elif len(yours) >= 100: #When dishonest moves outweight honest moves, change tactics...
                honesty = sum([1 if y[0]==y[1] else 0 for y in yours[50:]])/float(len(yours[50:]))
                if honesty <= 0.5: #... and just play according to most likely pick
                    what_did_you_do = [k[1] for k in yours if k[1]!=k[0]]
                    index = [i for i,k in enumerate(yours) if k[1]!=k[0]]
                    what_i_said_i_ll_do = [k[0] for i,k in enumerate(mine) if i in index]
                    matches = zip(what_i_said_i_ll_do, what_did_you_do)
                    what_you_might_answer = [k[1] for k in matches if k[0]==me]
                    table = [len([k for k in what_you_might_answer if k=='R']),len([k for k in what_you_might_answer if k=='P']),len([k for k in what_you_might_answer if k=='S'])]
                    maybe_your_pick = ['R','P','S'][table.index(max(table))]
                    pick = 'P' if maybe_your_pick=='R' else 'R' if maybe_your_pick=='S' else 'S'
                else:
                    pick = 'P' if you=='R' else 'R' if you=='S' else 'S'
    return pick

The idea is that for the first 50 moves I play honestly, and then once I have lured the opponent into thinking i am honest, play dishonestly, trying to play what would counter what the opponent will play (based on whether he was honest or dishonest in the past). When I reach the point at which i played as often honestly than dishonestly I change tactics and pick the most likely move of the opponent based on previous known configurations.

import random
def honestrandom(a, b, c, move):
    if move == None:
        return random.choice(["R","P","S"])
    return move

Two Thirds
Uses the strategy Peter Taylor mentioned in the Sandbox and in this comment.
It uses the Nash equilibrium.
import random

def two_thirds(h_opp, h_me, opp, me):

    def result(opp, me):
        if opp==me: return 0
        if opp=="R" and me=="S" or opp=="S" and me=="P" or opp=="P" and me=="R": return -1
        return 1

    moves = {"R", "P", "S"}
    honest = (opp == None)
    if honest:
        return random.choice(list(moves))
    else:
        res = result(opp, me)
        if res==-1:
            counter = list(moves - {opp, me})[0]
            return random.choice([me,counter,counter])
        if res==1:
            return random.choice([me,me,opp])
        return me

This errors for me.  On line 13, return random.choice(moves).  I think it's probably because you're using .choice on a dictionary.  Until that's fixed, I'm afraid this submission is invalid.

@Gryphon It's not a dictionary, it's a set.

Ah, sorry.  I just saw squiggly-brackets and thought "dictionary".  My bad.  Any idea why the random.choice is erroring on that line then?

@Gryphon It would seem that random.choice relies on picking a random index number and then returning the object in the list at that index. Since sets don't have an order, they also don't support indexing and thus don't work with random.choice. A simple fix for this would be to cast the set to a list before calling random.choice.

Ah.  I don't have python on this computer, so I can't fix this right now, but I'll fix it in my code when I get home.  If @mbomb007 would fix it here, that'd be great.

turn "return random.choice(moves)" into "random.choice(list(moves))" and "counter = (moves - {opp, me})[0]" into "list(moves - {opp, me})[0]". That should fix it.

@mbomb007, note that in my version of the code, I have implemented the fixes suggested by Magenta in the comment above.  I would suggest you edit to do the same.

Ah, thanks. I didn't know that choice didn't work on sets.

could you link to the strategy or include a brief description?

@FlipTack Added.

Bot Name: I Remember How You Lie
import random

#Bot Name: I Remember How You Lie
def irememberhowyoulie(opponentlist, mylist, opponentmove, mymove):
    random.seed()

    wintable = {
                "R": {"R": 1, "P": 0, "S": 2},
                "P": {"R": 2, "P": 1, "S": 0},
                "S": {"R": 0, "P": 2, "S": 1}
               }

    winprob = {
               "R": {"R": 0.0, "P": 0.0, "S": 0.0},
               "P": {"R": 0.0, "P": 0.0, "S": 0.0},
               "S": {"R": 0.0, "P": 0.0, "S": 0.0}
              }

    totalprob = {"R": 0, "P": 0, "S": 0}

    # Calculate the probability that the opponent will lie base on the probability that it lied in the last 15 ~ 25 rounds
    # And calculate the probability that what the bot will show next
    picklength = min(random.randint(15, 25), len(opponentlist))
    lying, tempsum = 0, 0.0
    pickedup = {"R": 0, "P": 0, "S": 0}
    if picklength == 0:
        lying = 0.5
    else:
        for eachround in opponentlist[-picklength:]:
            pickedup[eachround[1]] += 1
            if eachround[0] != eachround[1]:
                lying += 1
        lying = lying * 1.0 / picklength
    for s in pickedup:
        pickedup[s] = 1.0 / (1 + pickedup[s])
        tempsum += pickedup[s]

    #Honest Round
    if opponentmove is None and mymove is None:
        a = random.random() * tempsum
        if a < pickedup["R"]:
            return "R"
        elif a < pickedup["R"] + pickedup["P"]:
            return "P"
        else:
            return "S"

    #Real Round
    else:
        for me in winprob:
            ishonest = 0
            if me == mymove:
                ishonest = 1
            for op in winprob[me]:
                if op == opponentmove:
                    winprob[me][op] = (wintable[me][op] + ishonest) * (1 - lying)
                else:
                    winprob[me][op] = (wintable[me][op] + ishonest) * lying * pickedup[op] / (tempsum - pickedup[opponentmove])
                totalprob[me] += winprob[me][op]

        optimalmove, optimalvalue = "R", -9999999.0
        for me in totalprob:
            if totalprob[me] > optimalvalue:
                optimalmove, optimalvalue = me, totalprob[me]
        return optimalmove

Tested for several 100-round runs, and turned out that the winner scores about 220 in average. Rather honest I think;)
First time for me to participate in KOTH challenges, so I think there is still room for improvement

Tit for Tat
The classic Axelrodian contestant: hopeful, yet petty; simple, yet robust. This isn't Prisoner's Dilemma and I made no attempt to predict the opponent's move, so I highly doubt it'll be truly competitive. But "cooperating" still produces the most overall points for contestants, so I think it'll at least do middlingly.
import random
def tit4tat(opphist, myhist, oppfut, myfut):
    if (not myfut): return random.choice(['R','P','S'])
    if (not opphist) or opphist[-1][0]==opphist[-1][1]: return myfut
    return random.choice(['R','P','S'])

DeepThought
def check_not_loose_bot(opHist, myHist):
    not_loose_points = 0
    for i in range(0, len(opHist)):
        if opHist[i][1] == opHist[i][0] or myHist[i][0] == win_map[opHist[i][0]] and opHist[i][1] == win_map[myHist[i][0]]:
            not_loose_points += 1
    not_loose_percent = float(not_loose_points) / len(opHist)
    if not_loose_percent > 0.9:
    #    print("is not willing to loose")
        return True
    return False

def check_trick_bot(opHist, myHist):
    trick_points = 0
    for i in range(0, len(opHist)):
        if opHist[i][1] == win_map[myHist[i][0]]:
            trick_points += 1
    trick_percent = float(trick_points) / len(opHist)
    if trick_percent > 0.9:
  #      print("is tricking me")
        return True
    return False

def check_honest_bot(opHist):
  #  print("check honest")
    honest_points = 0
    for i in range(0, len(opHist)):
        if opHist[i][0] == opHist[i][1] :
            honest_points += 1
    honest_percent = float(honest_points) / len(opHist)
    if honest_percent > 0.9:
    #    print("is honest")
        return True
    return False

def check_self_match(opHist, myHist):
    for i in range(0, len(myHist)):
        if opHist[i][0] != myHist[i][0]:
            # im not playing against myself, because the other one was claiming a different value than i did
#            print("differ: "+str(opHist)+", "+str(myHist))
            return False
        if opHist[i][1] != opHist[i][0]:
#            print("lie")
            # im not playing against myself, because the other bot wasn't honest (and i'm always honest as long as i think i play against myself)
            return False
    return True

def check_equal(move1, move2, fullCheck): # WARNING: FOR COMPABILITY THIS IS RETURNING NEQ INSTEAD OF EQ
    if fullCheck:
        return move1 != move2
    else:
        return move1[0] != move2[0] #only check claims

def is_pattern(opHist, pattern_start, prob_pattern_start, pattern_length, full_check):
    for i in range(0, pattern_length-1):
        if check_equal(opHist[pattern_start + i] , opHist[prob_pattern_start + i], full_check):
            return False
    return True

win_map = {"R": "P", "P": "S", "S": "R"}
def deterministic_best_guess(opHist, full_check = True):
    size = 0
    random_result = random.choice(["R", "P", "S"])
    for pattern_length in range(2, (len(opHist)+1)/2): #a pattern has to occur at least twice
        for pattern_start in range(0, len(opHist) - 2 * pattern_length):
            if not is_pattern(opHist, pattern_start, len(opHist) - pattern_length + 1, pattern_length, full_check):
                 continue
            is_repeated = False
            is_fooled = False
            for repeated_pattern_start in range(pattern_start + pattern_length, len(opHist) - pattern_length):
                if not is_pattern(opHist, pattern_start, repeated_pattern_start, pattern_length, full_check):
                     continue
                is_repeated = True
                if check_equal(opHist[pattern_start + pattern_length - 1], opHist[repeated_pattern_start + pattern_length - 1], full_check):
                    is_fooled = True
                    break
    #            print("pattern found: " + str(opHist[pattern_start : pattern_start + pattern_length]) +" at "+str(pattern_start)+" and "+str(repeated_pattern_start))
   #             print("check: "+str(opHist))
            if is_fooled or not is_repeated:
                break
            #we have found a deterministic best guess
  #          print("most likely next step: "+ str(opHist[pattern_start + pattern_length - 1]))
            if full_check:
                return win_map[opHist[pattern_start + pattern_length - 1][1]], True
            return win_map[opHist[pattern_start + pattern_length - 1][0]], True # if we don't have a full check, the pattern only applies to claims. So pretend to win against the claimed result.

    #fallback
 #   print("fallback")
    return random_result, False

def DeepThought(opHist, myHist, opMove, myMove):
    if opMove == None:
    #claiming phase
        if len(myHist) == 0:
        #seed random to be able to be deterministic when chosing randomly
            #The seed is secret (kind of)
            random.seed(133427)
        else:
            #seed random according to my previous claims
            seed = 133427
            for i in range(0, len(myHist)):
                if myHist[i][0] == "R":
                    seed = seed*3+1
                elif myHist[i][0] == "S":
                    seed = seed*7+1
                elif myHist[i][0] == "P":
                    seed = seed*11+1
                while seed%2 == 0:
                    seed /= 2
            random.seed(seed)
        if check_self_match(opHist, myHist):
            #claim a random value, will happen in the first round or in a self-match
            result = random.choice(["R", "P", "S"])
            return result
      #  print("differ detected")
        if check_trick_bot(opHist, myHist) and len(myHist) > 10:
            # i play against a trick bot. I can reduce its points by trieing to guess its claim, and force him to lie
            result, sure = deterministic_best_guess(opHist, False)
        else:
            result, sure = deterministic_best_guess(opHist)
        random.seed(0)
        return result
    if check_self_match(opHist, myHist):
        #i play against myself, i can only hope for a honest draw, so do that
        return myMove
#    print("no self-math")
    #dbg needs a valid seed, so provide it
    random.seed(133427)
    result, sure = deterministic_best_guess(opHist)
    if sure:
        #i'm sure i play against a deterministic bot. I'll be honestly winning. YEY.
        return myMove
    if check_honest_bot(opHist) and len(opHist) > 10:
        #i play against an honest bot. I'll accept a draw, but i will not accept a loss
        if win_map[myMove] == opMove:
            return win_map[opMove]
        return myMove
    if check_trick_bot(opHist, myHist) and len(opHist) > 10:
        #i play against a tricking bot. He'll make me either loose honestly (1 Pnt) or i have to be dishonest (2 Pnt). So let's lie.
        return win_map[win_map[myMove]]
    if check_not_loose_bot(opHist, myHist) and len(opHist) > 10:
        #i play against a bot thats not willing to loose. If it looks like i won, i can loose honestly (1Pnt, 2Pnt for him),
        #or i have to be dishonest (2 Pnt, 0 Pnt for him). So let's lie in that case.
        #If it looks like its a draw, i'll be honest (conservative way), and get my 2 : 2 Pnt.
        #If it lokks like i'll loose, I'll not accept it. I'll lie to win for 2 : 1 Pnt.
        if myMove == opMove:
            return myMove
        if myMove == win_map[opMove]:
            # He'll lie. So lie together and keep smiling.
            return opMove
        # I'll loose. NO!!!! Not gonna happen
        return win_map[opMove]
    return myMove

Just a few notes on it:

DeepThought likes to think. A lot. I'm sorry about it, but i don't really know how to fix it. I blame Python.
DeepThought tries to be honest. Beeing honest does provide you one aditional point, which is the same as the expected value for normale RPS
But: DeepThought gets in averange even more than 2 Points per Game. He uses some detection to find some common behaviours (like tricking, beeing honest, etc.), and adapts according to that.
DeepThought is purely deterministic, so it'll draw against itself, because it'll always do the same decition on both ends.
To be sure not to lie against itself, it has a special detection, like some other bots here, too. This is a very aggressive one, even assuming to be true after one round (and in the first round, too). Basically, as long as the opponent moves are exactly mine, i'll assume its a mirror match.
The interesting part (and the part that has dozens of false-positives) is the check for a deterministic bot, that is only dependend on its own prevoius result. That check search for any pattern of size n, that is repeated twice, and that could be describing the last n-1 moves, predicting the opponent's claim and move in advance. This part is taking some time, sadly.

I'm new to both, koth and Python, so tell me if I messed anything up in this bot. I don't think it can beat reinforced learning (because I guess it'll learn my moves too quickly), but let's give it a try.
I like this challenge, and if I find some time, I'd like to add an organic computing approch (althogh there might be too less pressure on the higher dimensions). Is it allowed to add multiple suggestions? Or is it forbidden to prevent boosing your main bot by inserting some that only aim for loosing to your primary?
EDIT: Fixed code-typo that caracterized me as non-native english speaker

It is not forbidden to post multiple entries, but it is forbidden to post an entry that props up a different bot (even one that is not your own).  It is OK to lose to another bot, as long as it is not by design.

I got an error when running this, as the 32nd line of your DeepThought function, return result requires an additional indent.  I believe it should be inside the gigantic if statement it's immediately after, as the variable return is only declared in that it statement.  I made this modification in my code, and it now runs without error.  If you wouldn't mind making that change here, that'd be great.

You seem to be messing with the state of the global random generator, which is probably not okay. I considered doing a similar thing, and found this solution: create a new random object with R=random.Random(seed) and use it like this: R.choice(...).

@Gryphon fixed. Probably some errors that occured when transforming from my local script to se, where everythin has to be intdented one additional time

Yes, that's likely to be the problem.  The additional indents are rather annoying.

@alexberne You can select the code you pasted and click the {} button on the toolbar to automatically indent every line.

import random
def user5957401bot(a,b,c,d):
    if d == None:
       return random.choice(["R","P","S"])
    else:
       return random.choice(["R","P","S",d])

THEbot: THE Honest Exploiter
import random
def thebot(ho,hm,om,mm):
    hands = {"R": "P", "P": "S", "S": "R"}
    if om == None:
        if (len(set([i[0] for i in ho])) < 3) and (len(ho) > 2):
            return hands[random.choice(list(set([i[0] for i in ho])))]
        else:
            return random.choice(["R","P","S"])
    else:
        if sum(1 for i in ho if i[0]==i[1]) > (len(ho)/3):
            if om == mm:
                return om
            else:
                return hands[om]
        else:
            return mm

I just realized that I downvoted by misclick, sorry. Will undo when you edit. (Can't change it othewise.)

@ChristianSievers edited

@ChristianSievers thank you!

have_we_been_here_before
Simply asks "have we been here before", and chooses the move which would have given the best average outcome in any such previous games.
Edit:  Honesty Club. I've added a small block of code because another bot (mason) has done extremely well by forming a secret club with itself.  Notice however, that playing honestly against honest opponents has on average exactly the same payoff when playing against oneself, and perhaps there are broader mutual benefits to be had too?
Edit2: At the time of writing the two bots ahead of me both exploit rotators, so I'm going to add another block of code in order to jump on that bandwagon too.  I guess my code must seem quite old school - sticking to familiar constructs found in any programming language because I really don't know Python.
import random

def have_we_been_here_before(opponentList, myList, opponent, me):

    def win(x):
        if x=="R": return "P"
        elif x=="P": return "S"
        elif x=="S": return "R"

    def calc_score(r1, r2):
        if r1==r2: return 1
        elif r1==win(r2): return 2
        else: return 0

    def have_we(opponentList, myList, opponent, me, me2):
        score, count = 0, 0
        for n in range(len(opponentList)):
            if (opponent == opponentList[n][0] and me == myList[n][0]):
                score += calc_score(me2, opponentList[n][1])
                count += 1
        if count == 0: return 0
        else: return float(score) / float(count)

    if opponent == None:

        # exploit rotators
        if len(opponentList) >= 3:
            rotator = True

            for n in range(3, len(opponentList)):
                if opponentList[n][1] != opponentList[n % 3][1]:
                    rotator = False
                    break

            if rotator: return win(opponentList[len(opponentList) % 3][1])

        if len(opponentList) == 0:
            return random.choice(["R", "P", "S"])
        else:
            # crude attempt to exploit the house bots
            prev = random.choice(opponentList)[1]
            return win(prev)

    # Play honestly if opponent has played honestly so far
    honest = True
    for oppMove in opponentList:
        if (oppMove[0] != oppMove[1]):
            honest = False
            break

    if honest: return me
    # Done playing honestly

    # Have we been here before?
    rock = have_we(opponentList, myList, opponent, me, "R")
    paper = have_we(opponentList, myList, opponent, me, "P")
    sissors = have_we(opponentList, myList, opponent, me, "S")

    if rock > paper and rock > sissors: return "R"
    elif paper > rock and paper > sissors: return "P"
    elif sissors > paper and sissors > rock: return "S"
    else: return win(opponent)

Thompson
import math
import random

moves = list(range(3))
names = "RPS"
from_name = dict(zip(names, moves))
to_name = dict(zip(moves, names))

#Payoff matrices given each relationship between honest moves.
A = [
    [[2, 1, 3], [2, 1, 0], [0, 2, 1]],
    [[1, 3, 2], [1, 0, 2], [2, 1, 0]],
    [[3, 2, 1], [0, 2, 1], [1, 0, 2]]
]

#Add a 1.2% penalty for the opponent's score (idea shamelessly stolen from csbot).
for d_h in range(3):
    for i in range(3):
        for j in range(3):
            A[d_h][i][j] -= 0.012 * A[[0, 2, 1][d_h]][j][i]

third = 1. / 3
two_thirds = 2 * third

nash_prior = [
    [[1, 0, 0], [two_thirds, 0, third], [third, 0, two_thirds]],
    [[third, 0, two_thirds], [1, 0, 0], [two_thirds, 0, third]],
    [[two_thirds, 0, third], [third, 0, two_thirds], [1, 0, 0]]
]

def mult_m_v(M, v):
    w = [0 for _ in v]
    for i, M_i in enumerate(M):
        for M_ij, v_j in zip(M_i, v):
            w[i] += M_ij * v_j
    return w

def mean_belief(counts):
    c = 1. / sum(counts)
    return [n * c for n in counts]

def sample_belief(counts):
    return mean_belief([random.gammavariate(n, 1) for n in counts])

def thompson(h_opp, h_me, opp, me):

    #Prior rationality of opponent.
    a = 0.95

    #Confidence in priors.
    n0_h = 0.5
    n0_m = 0.5

    def v(x):
        return [x for _ in range(3)]

    h_p = [v(n0_h * third) for _ in range(3)]

    m_p0 = [v(None) for _ in range(3)]
    m_p1 = [v(None) for _ in range(3)]

    #Expected prior is a mixture between nash equilibrium and uniform distribution.
    for h_i in range(3):
        for h_j in range(3):
            m_p0[h_i][h_j] = [n0_m * (a * nash + (1 - a) * third) for nash in nash_prior[h_i][h_j]]

    for d_j_prev in range(3):
        for d_ij in range(3):
            m_p1[d_j_prev][d_ij] = list(m_p0[0][d_ij])

    #Track whether it's better to model the real moves based on the exact honest moves or
    #just the relationship between honest moves together with the opponent's defection strategy in the previous round.
    log_mp0 = 0
    log_mp1 = 0

    #Identify myself and always cooperate.
    is_me = True

    for (t, ((h_i, m_i), (h_j, m_j))) in enumerate(zip(h_me, h_opp)):

        h_i, m_i, h_j, m_j = from_name[h_i], from_name[m_i], from_name[h_j], from_name[m_j]

        d_j = (m_j - h_j) % 3
        d_ij = (h_j - h_i) % 3

        if t:
            h_j_prev = from_name[h_opp[t - 1][0]]
            m_j_prev = from_name[h_opp[t - 1][1]]
            h_p[h_j_prev][h_j] += 1

            d_j_prev = (m_j_prev - h_j_prev) % 3

            log_mp0 += math.log(m_p0[h_i][h_j][d_j] / sum(m_p0[h_i][h_j]))
            log_mp1 += math.log(m_p1[d_j_prev][d_ij][d_j] / sum(m_p1[d_j_prev][d_ij]))

            m_p1[d_j_prev][d_ij][d_j] += 1

        m_p0[h_i][h_j][d_j] += 1

        if is_me and ((h_i != h_j) or (h_j != m_j)):
            is_me = False

    if is_me:
        random.seed(len(h_me) + 1337)
        me_next = random.randrange(3)

    log_ps = [log_mp0, log_mp1]
    log_p_max = max(log_ps)
    ps = [math.exp(log_p - log_p_max) for log_p in log_ps]
    p0 = ps[0] / sum(ps)

    #We have to blend between the predictions of our 2 models for the real rounds.

    def sample_expectation(h_i, h_j, d_j_prev=None):
        d_ij = (h_j - h_i) % 3
        if d_j_prev is None or random.random() < p0:
            p = m_p0[h_i][h_j]
        else:
            p = m_p1[d_j_prev][d_ij]
        return mult_m_v(A[d_ij], sample_belief(p))

    def take_expectation(h_i, h_j, d_j_prev=None):
        d_ij = (h_j - h_i) % 3
        e0 = mult_m_v(A[d_ij], mean_belief(m_p0[h_i][h_j]))
        if d_j_prev is None:
            return e0
        e1 = mult_m_v(A[d_ij], mean_belief(m_p1[d_j_prev][d_ij]))
        return [p0 * e0i + (1 - p0) * e1i for e0i, e1i in zip(e0, e1)]

    #We use thompson sampling, selecting the optimal deterministic strategy
    #with respect to a random opponent sampled from the posterior.

    #Actually, we use optimistic thompson sampling which clips samples to have >= than the mean expected value.

    if opp == None:
        #For the honest round we perform a lookahead to the real round to choose our strategy.
        if h_opp:
            if is_me:
                return to_name[me_next]
            h_j_prev = from_name[h_opp[-1][0]]
            m_j_prev = from_name[h_opp[-1][1]]
            d_j_prev = (m_j_prev - h_j_prev) % 3
            h_p_s = sample_belief(h_p[h_j_prev])
            h_p_u = mean_belief(h_p[h_j_prev])
            s_i = [0] * 3
            s_i_u = [0] * 3
            for h_i in range(3):
                for h_j in range(3):
                    s_i[h_i] += h_p_s[h_j] * max(sample_expectation(h_i, h_j, d_j_prev))
                    s_i_u[h_i] += h_p_u[h_j] * max(take_expectation(h_i, h_j, d_j_prev))
                s_i[h_i] = max(s_i[h_i], s_i_u[h_i])
            return to_name[s_i.index(max(s_i))]
        else:
            return to_name[me_next]
    else:
        if h_opp:
            if is_me:
                return me
            h_j_prev = from_name[h_opp[-1][0]]
            m_j_prev = from_name[h_opp[-1][1]]
            d_j_prev = (m_j_prev - h_j_prev) % 3
        else:
            if opp == me:
                return me
            d_j_prev = None
        h_i, h_j = from_name[me], from_name[opp]
        s_i = [max(s0, s1) for s0, s1 in zip(sample_expectation(h_i, h_j, d_j_prev), take_expectation(h_i, h_j, d_j_prev))]
        return to_name[(h_i + s_i.index(max(s_i))) % 3]

Interesting entry.  I'll run it soon, should be able to post the results this afternoon.

OK, I slightly re-turned the parameters.

Got it.  Sorry it's taking so long to update, it's just, every time it's just about finished, somebody updates their bot, or I get a new one, and I have to run it again.

@Gryphon you could keep a table of the outcomes of all pair-ups, so when a bot is updated you only have to run 200 * (num_bots - 1) + 100 new matches.

mirrorbot
import random

def mirrorbot(op_hist, my_hist, op_move, my_move):
    if my_move == None :
        return random.choice(["R","P","S"])
    else :
        for x in range(len(op_hist)):
            if ((op_hist[len(op_hist) -x-1][0] == my_move) and (my_hist[len(op_hist) -x-1][0] == op_move)):
                return op_hist[len(op_hist) -x-1][1]
        return my_move

I will try a simple bot that redo the last play of its opponent in these conditions

Welcome to PPCG!

def rotate_rock(h1, h2, is_, honest):
 return ("R", "P", "S")[len(h1) % 3]

def rotate_paper(h1, h2, is_, honest):
 return ("P", "S", "R")[len(h1) % 3]

def rotate_scissors(h1, h2, is_, honest):
 return ("S", "R", "P")[len(h1) % 3]

The idea here is to maximize the score while playing self while still being randomly competitive during other stages against other bad bots.

The word is is a keyword, thus this is invalid.

@EriktheOutgolfer thanks :)

Bot name: Liar Liar
Can't stop lying.
import random

def liarliar (herHistory, myHistory, herMove, myMove):
    options = ["R", "P", "S"]
    if myMove == None:
        return random.choice(options)
    else:
        options.remove(myMove);
        return random.choice(options)

RockBot
Assumes the opponent will be honest and tries to beat them, but refuses to play rock.
import random
def rockBot(oppHist,myHist,oppMove,myMove):
    if oppMove == None:
        return random.choice(["R","P","S"])
    else:
        if(oppMove == "R"):
            return "P"
        elif(oppMove == "P"):
            return "S"
        elif(myMove != "R"):
            return myMove
        else:
            return random.choice(["P","S"])

This seems to error because, on your final line, "P","S" is not inside square brackets (not a list).  I changed that in my version, but if you could do the same here, it'd be great.  Thanks.

Won't this lose horribly to constant scissors?

@Wildcard yes, but it will do pretty well against paper bot

Dx
I only wrote this bot so i can have an smiley in my bot name xD.
def Dx(ophist, myhist, opmove, mymove):
    from random import choice
    import math
    def honest(hist):
        return [int(x[0]==x[1]) for x in hist]

    def avg(arr):
        if len(arr)==0:
            return 0
        return sum(arr)/float(len(arr))

    def clamp(i, lo, hi):
        return min(hi, max(lo, i))

    def deltas(arr):
        return [a-b for a,b in zip(arr[1:],arr[:-1])]

    def delta_based_prediction(arr,l):
        deltarr = []
        i=0
        while len(arr)<0:
            deltarr[i]=avg(arr[-l:])
            i+=1
            arr = deltas(arr)
        return sum(deltarr)

    next_honesty = delta_based_prediction(honest(ophist),int(math.sqrt(len(ophist))))
    if abs(next_honesty-0.5)<0.1 or not opmove:
        return choice(['R','P','S'])
    next_honesty=int(clamp(round(next_honesty),0,1))
    winner = {'S': 'R', 'R': 'P', 'P': 'S'}

    if next_honesty > 0:
        return winner[opmove]

    return choice([opmove, winner[winner[opmove]]])

Bot name: dontlietome
Determines if the opponent is lying or not depending on how many times the opponent lied in the last 10 rounds. Selects move depending on if the opponent is lying or not. If the opponent is determined to be lying, then plays what the hint was.
import random
def dontlietome(opp_moves, my_moves, opp_hint, my_hint):
    def is_trustworthy(moves, length):
        length = max(-length, -len(moves))
        history = [1 if move[0] == move[1] else 0 for move in moves[length:]]
        prob_honest = float(sum(history))/float(len(history))
        choice = random.uniform(0., 1.)
        if choice <= prob_honest:
            return True
        else:
            return False

    moves = ["R", "P", "S"]
    lose_against_map = {"S":"R", "R":"P", "P":"S"}
    length = 10
    if opp_hint == None:
        # Honest round
        return random.choice(moves)
    else:
        # Real round
        if len(opp_moves) < length:
            return my_hint
        if is_trustworthy(opp_moves, length):
            return lose_against_map[opp_hint]
        else:
            return my_hint

In the line "if is_trustworthy(opp_moves, self.length):", self is not defined.  Additionally, in the line "return lose_against_map[opp_hint]", lose_against_map is also not defined.  The self.length seems to be solved by removing the self. but the other problem still stands.  Until that's fixed, I'm afraid this is invalid.

Oops I wrote this using an Object and I forgot to remove some self references and fully copy the code. I'll fix those as soon as I get home.

OK.  If it's just a small error, I correct it (as I have in some other bots, and would have if it was just the self. problem), but a missing function is a different story.

@Gryphon I fixed the bugs. (removed the self, added the referenced lost_against_map, and fixed the if statement checking if honest round)

Everybody Lies
import random

def everybodylies (opphist, myhist, oppmove, mymove):
    if mymove == None:
        return random.choice(["R","P","S"])
    elif mymove == "R": return "S"
    elif mymove == "P": return "R"
    elif mymove == "S": return "P"

It lies about its move ("I'll play Scissors!"), and assumes the opponent was also lying and that they'll try to beat what I said my move would be ("hmm, Rock beats Scissors so I'm playing that"), but I actually play the move that beats that move ("Paper! Surprise!").

Sounds like the first level of the Iocaine Powder strategy to me :-) "Now, a clever man would put the poison into his own goblet, because he would know that only a great fool would reach for what he was given. I am not a great fool, so I can clearly not choose the wine in front of you. But you must have known I was not a great fool, you would have counted on it, so I can clearly not choose the wine in front of me..."

Trusting Bot
def trusting_bot(h_opp, h_me, opp, me):
    if opp=="S":
        return "R"
    elif opp=="R":
        return "P"
    else:
        return "S"

Always claims to throw scissors, but will do whatever beats what the opponent said. Will reliably draw with itself.

This would be more effective if it would always be honest against itself.

@Gryphon Probably, but I don't python well enough to want to try to make something that cooperates like that.

Never mind then.

import random
def trustingRandom(a,b,c,d):
  move = random.choice(["R","P","S"])
  if c == "R":
    move = "P"
  elif c == "P":
    move = "S"
  elif c == "S":
    move = "R"
  return move

Averager
def averager(op, mp, od, md):
  import random
  if od == md == None:
    if op == mp == []:
      return random.choice('RPS')
    else:
      opa = [i[1] for i in op]
      copa = [opa.count(i) for i in 'RPS']
      copam = [i for i, j in zip('RPS', copa) if j == max(copa)]
      opd = [i[0] for i in op]
      copd = [opd.count(i) for i in 'RPS']
      copm = [i for i, j in zip('RPS', copd) if j == max(copd) and i in copam]
      return random.choice(copam if copm == [] else copm)
  else:
    if op == mp == []:
      return md
    else:
      hop = sum([1. if i[0] == i[1] else 0. for i in op]) / len(op)
      hmp = sum([1. if i[0] == i[1] else 0. for i in mp]) / len(mp)
      return 'PSR'['RPS'.index(od)] if hmp >= 0.75 and hop >= 0.50 else md

Just a little better than my previous entry...

def learningbot4(yourlist,mylist,you,me):
  CHECK={"R":{"R":0,"P":1,"S":-1},"P":{"R":-1,"P":0,"S":1},"S":{"R":1,"P":-1,"S":0}}
  results={None:{"R":0,"P":0,"S":0},"R":{"R":0,"P":0,"S":0},"P":{"R":0,"P":0,"S":0},"S":{"R":0,"P":0,"S":0}}
  for i in range(len(yourlist)):
    res=CHECK[yourlist[i][1]][mylist[i][1]]
    if mylist[i][0]==mylist[i][1]: res+=0.5
    results[yourlist[i][0]][mylist[i][1]]+=res
    results[None][mylist[i][0]]+=res
  return max(results[you],key=results[you].get)

csbot on steroids
I think the suggestion that @user1502040 makes in the comments should be followed. Otherwise this bot would have an advantage that I would consider unfair. I submit it so that the difference that it makes can be assessed. With the suggested random seeding the steroids would be neutralized and the bot would be equivalent to csbot, so then only one should participate in the contest.
from random import seed
from csbot import csbot

def csbot_on_steroids(ophist,myhist,opdecl,mydecl):
  seed()
  m = csbot(ophist,myhist,opdecl,mydecl)
  seed(0)
  return m


text:
Demolish a string!
Challenge
Given a string input, output the demolished version of it.
The Process
P
r      Pr       r
o       o       o
g       g       g
r       r       r      rogr         r
a  ->   a  ->   a  ->     a  ->     a  ->           ->           ->           ->           ->
m       m       m         m         m
m       m       m         m         m         mmar         m
i       i       i         i         i         i            i           mi           m
n       n       n         n        gn        gn           gn           gn           gni         mgni
g       g      Pg        Pg      roPg      roPg         roPgmar      roPgmar      roPgmar      roPgmar

Place the string vertically.
Select a random integer between 1 and (height of the column of characters) - 1 and a random direction (left or right).
Rotate that number of characters in that direction (if those spaces are unoccupied go to step 4; if not, go back to step 2).
Let those characters fall due to gravity.
Repeat until the height of the column of characters is at most 1 larger than the height of the columns next to it (i.e. it becomes impossible to further demolish ("steps 2-4") the column).
If there is another column of characters that is more than 1 character taller than one or more of its surrounding columns (i.e. demolish-able), repeatedly demolish that column until it is no longer demolish-able. If there are multiple demolish-able columns, completely demolish the tallest column (if there are multiple tallest columns, completely demolish the leftmost one).
Repeat until all columns are no longer demolish-able.

If there are space characters in the input, demolish those first, all at once.
C
o

d
e  ->     oC  ->         ->  ...
       de
G        G          G
o        o          o
l        l          l
f        f        defoC

Rules

Standard loopholes are forbidden.
Trailing and leading newlines are allowed.
Your program may either print or return a string/equivalent.
The output must be non-deterministic (unless the input is not demolish-able).

This is code-golf, so the submissions with the smallest byte counts in their languages win!

I would doubt if random is really necessary here

@KeyuGan I think the challenge would be fairly trivial if people had to select a fixed number of characters and alternated left/right.

We still can say that 4 is random and returned by a fair dice roll

@someone 4 would make the output deterministic, i.e. not "random." Edited the rules to make that explicit.

@someone are you referring at 4 because of XKCD?

Yes, but that reference is not the main idea of the comment.

Python 2, 622 595 573 552 542 534 527 520 515 bytes
from random import*
s=input()
r=range
R=choice
Z=len
L=h=Z(s)
a=[[]for _ in'  '*-~h]
S=s[::-1].split()
X=-1,1
for w in S[1:]:
 for i in r(Z(w)):a[h-~i*R(X)]+=w[i]
a[h]+=S[0]
while L:
 H=[map(Z,a[c-1:c+2])+[c]for c in r(1,h-~h)];D=L=[(min(n,m)-C,i)for n,C,m,i in H if~-C>min(n,m)]
 while D:
	_,c=min(L);n,C,m=map(Z,a[c-1:c+2]);D=X[n+2>C:1+(C-1>m)]
	if D:
	 d=R(D);l=R(r(1,C-[0,m,n][d]));w,a[c]=a[c][-l:],a[c][:-l]
	 for i in r(l):a[c-~i*d]+=w[i]
for l in zip(*[l+[' ']*max(H)[1]for l in a if l])[::-1]:print`l`[2::5]

Try it online!

527 bytes

@EriktheOutgolfer Thanks :)

520 bytes

h+R(X)*-~i can be h-~i*R(X).

L=[...];D=L can be D=L=[...].

' '*-~h*2 can be -~h*'  ' (the string contains two spaces).

515 bytes.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
The Speed of Letters
Given a string as input, print a new string with each letter pushed to the right by its respective alphabet index.
We all know that A is a slow and Z is a fast letter. This means that Z gets shifted to the right by 25 spaces, A doesn't get shifted at all and B gets shifted by 1 space.
Your program only has to handle uppercase letters from A-Z, and no other characters, no whitespaces, no punctuation.
Note that if 2 or more letters fall onto the same space after shifting, the latest character will be used. (Example: BA ->  A)
Examples
"AZ" -> "A                         Z"

"ABC" -> "A B C"

"ACE" -> "A  C  E"

"CBA" -> "  A"

"HELLOWORLD" -> "     E H    DLL   OLO   R  W"

Rules

This is code-golf, so the shortest code in any language bytes wins.
Standard loopholes are forbidden.
Input must be received as a string.
You may print the result to stdout or return a string.
A single trailing whitespace and/or newline is allowed.
You may also use lowercase letters as input or output, but only use either case.

Trailing whitespace okay?

@Okx Yes, note my previous comment.

What about a lot of trailing spaces?

@Okx Forbidden, one is all you get.

I assume we can use lowercase letters instead, right?

@Mr.Xcoder If you keep it consistently at only lowercase letters, yes.

Is it alright to have a single leading space?

@miles Leading newlines yes, but no leading spaces.

Python 2, 81 bytes
t=[]
i=65
for c in input():t+=[' ']*26;t[ord(c)-i]=c;i-=1
print`t`[2::5].rstrip()

Try it online!

MATL, 11 bytes
''jtfy65-+(

Try it online! Or verify all test cases.
Explanation
MATL indexing is 1-based. This golfing trick is used here. This other one cannot be used because we need an empty string, not an empty numeric array.
Consider input 'ACE' as an example. Stack contents are shown bottom to top.
''     % Push empty string
       %   Stack: ''
j      % Input string
       %   Stack: '', 'ACE'
t      % Duplicate
       %   Stack: '', 'ACE', 'ACE'
f      % Indices of nonzero entries. Gives [1 2 ... n] where n is input length
       %   Stack: '', 'ACE', [1 2 3]
y      % Duplicate from below
       %   Stack: '', 'ACE', [1 2 3], 'ACE'
65     % Push 65
       %   Stack: '', 'ACE', [1 2 3], 'ACE', 65
-      % Subtract, element-wise. Characters are converted to codepoints
       %   Stack: '', 'ACE', [1 2 3], [0 2 4]
+      % Add, element-wise
       %   Stack: '', 'ACE', [1 4 7]
(      % Fill string '' with values 'ACE' at positions [1 4 7]. The original
       % empty string is extended. Non-existing values are filled with char 0,
       % which is displayed as space. Implicitly display
       %   Stack: 'A  C  E'

(: nice builtin

@EriktheOutgolfer I think it's similar to 05AB1E's ǝ? Ah, but that doesn't seem to vectorize over the second/third inputs

Exactly why it's unique :p and also how MATL auto-fills with 0s and displays 0 as space.

@LuisMendo Nice answer.  Out of curiosity, and this question is probably applicable to most stack based langs, when you write in MATL do you need to keep track of the stack (eg, in a line above the code, or a piece of paper, etc) as you compose code?  Or has it become natural enough to you that you don't?

@Jonah Thanks! In the beginning I used to need to keep track of the stack on paper. Now it has become natural, and I only need it in more complicated programs

Heh - learned something new today; you can index into the same position twice without any problem in MATL(AB). I already started writing a complicated loop-based answer because I assumed it would give an error otherwise.

R, 140 133 129 74 bytes
Saved a ton of bytes porting an ASCII value approach like everyone else. Sad I didn't think of it before :(
function(s){F[X-65+1:sum(X|1)]=X=utf8ToInt(s)
F[is.na(F)]=32
intToUtf8(F)}

Try it online!
original answer, 129 bytes:
function(s){o=rep(' ',(n=nchar(s))+25)
for(i in 1:n){k=substr(s,i,i)
o[x<-i+match(k,LETTERS)-1]=k
F=max(F,x)}
cat(o[1:F],sep='')}

Try it online!
generates a too-long list o of spaces, then iterates through s, replacing the values in o with the correct value and updating F, the position of the rightmost character. Then prints out the first F elements of o with no separators between them.

05AB1E, 20 16 bytes
-4 bytes thanks to Emigna
ð₄×svyAuykN+ǝ}ðÜ

Try it online!

I think you can shorten to ð₄×svyAuykN+ǝ}ðÜ at least. Also, is there a guarantee that the input string shifted isn't larger than 1000 chars? If not, g₂+ð× should work.

JavaScript (ES6), 81 bytes
s=>[...s].map((c,i)=>a[i+parseInt(c,36)-10]=c,a=[])&&[...a].map(c=>c||" ").join``

Somewhat builds off of Rick Hitchcock's incomplete answer but ended up rather different.
Places the characters into their respective index of an empty array, then uses array spread ([...a]) to turn the missing elements into undefined, allowing map to replace empty elements with a space.
Test Cases

let f=
s=>[...s].map((c,i)=>a[i+parseInt(c,36)-10]=c,a=[])&&[...a].map(c=>c||" ").join``

;["AZ", "ABC", "ACE", "CBA", "HELLOWORLD"]
.forEach(t=>console.log(`"${t}"`, "=>", `"${f(t)}"`))

Very nice!  I was about to post an 88-byte solution, but yours is much better.

Perl 5, 42 bytes
41 bytes code + 1 for -p. The \x1bs in the code are literal escape characters.
Relies on ANSI escape sequences to position the cursor and therefore doesn't work on TIO.
s/./($-=-65+ord$&)?"\x1b[$-C$&\x1b[--$-D":$&/ge

Usage
perl -pe 's/./($-=-65+ord$&)?"\x1b[$-C$&\x1b[--$-D":$&/ge' <<< 'HELLOWORLD'
     E H    DLL   OLO   R  W

Here's one that works on TIO but comes in at one byte more (41 bytes of code + 2 for -F): Try it online!

@Xcali You should post that so I can upvote it :)

@Xcali Agree with Lynn too more posts are great. I like language competition too!

Java (OpenJDK 8), 207 191 189 183 178 174 173 170 bytes
s->{char i=0,l,c[]=new char[s.chars().map(j->j+s.lastIndexOf(j)).max().getAsInt()-64];for(;i<s.length();c[i+l-66]=l)l=s.charAt(i++);return"".valueOf(c).replace('',' ');}

Try it online!

Perl 5, 41 + (-F) = 43 bytes
map$r[$i++-65+ord]=$_,@F;print$_||$"for@r

Try it online!
Just for @lynn

brainfuck, 127 bytes
,[[-<+<+>>]----[----<<->>]<<-[[>]>++++>[-<[-]<+>>]<[-<++++++++>]<[<]>-]>[>]<[-]+[<]>-[[>]<+[<]>-]>.[-]>[>]<[[->>+<<]<]>,]>>[.>]

Try it online!
Explanation
,[                    Take input and start main loop
  [-<+<+>>]             Make two copies of input byte
  ----[----<<->>]<<-    Subtract 64 from one of them to get position in alphabet

                        There are two zero cells between the input and the
                        remaining output cells; we wish to move these zeroes
                        to indicate where the letter is to be moved

  [                     A number of times equal to the position in the alphabet:
    [>]                   Go to current position in output string
    >++++>                Create 4 (as part of creating a space if needed)
    [-<[-]<+>>]           Move output byte back two cells; zero the previous 4 if output existed
    <[-<++++++++>]        Otherwise move a space (32) into that position
    <[<]>-                Move back to counter and decrement
  ]
  >[>]<[-]              Delete last moved byte to make room for input byte
  +[<]>-                Initialize slot at 1 so it is always nonzero in this loop
  [[>]<+[<]>-]          Move input byte into slot
  >.[-]                 Output next output byte and clear
  >[>]<                 Move to space vacated in preparation to remove gap
                        (Moves to end instead if input was A; this causes no problems)
  [[->>+<<]<]           Move values two cells right until zero reached
  >,                    Get into position and take another byte of input
]
>>[.>]                Output characters beyond end of input

Proton, 78 bytes
x=>{t=[' ']*26*(q=len(x))for i:0..q{t[i+ord(k=x[i])-65]=k}"".join(t).rstrip()}

Try it online!
69 bytes by porting Lynn's solution: x=>{t=[]i=65for k:x{t+=[' ']*26t[ord(k)-i]=k;i--}"".join(t).rstrip()}

Jelly, 20 bytes
ØAiÐ€+JṬ€a"⁸Zḟ€0Ṫ€o⁶

Try it online!

Haskell, 90 88 bytes
d=drop 1
[a]#s|s<"A"=a:d s|0<1=s
b#s=(s++" ")!!0:d b#d s
f(c:t)=['A'..c]#(' ':f t)
f s=s

Try it online!

@Laikoni Oh dang, I misread that. Will fix...

Well, it's no longer shorter. :/

Japt, 23 bytes
;iB ç
Ng £=hX10nY+XnG
U

Test it online!
First attempt, may be improvable...

It looks like you should be able to save a byte by assigning the initial string to V instead of U: https://ethproductions.github.io/japt/?v=1.4.5&code=CjtpQiDnCqNWPWhYMTBuWStYbkfDVg==&input=IkhFTExPV09STEQi

J, 37 31 bytes
[`]`(' '#~(1+>./)@])}(i.@#+65-~a.&i.)
[`]`(' '#~(1+>./)@])}#\-66-3&u:

-6 bytes thanks to FrownyFrog
explanation
The entire thing is a hook:
[`]`(' '#~(1+>./)@])}  #\-66-3&u:

The right side calculates the new indexes for all the letters.
The left side uses the gerund form of Amend } first to create a string of the necessary number of spaces: (' '#~(1+>./)@]) . And then to place each letter of the original string into its appropriate index within the all-space string.
Try it online!

(i.@#+65-~a.&i.) ->
(i.@#+65-~3&u:) ->
(i.@#-65-3&u:) ->
(#\-66-3&u:)

You can drop the parentheses too.

@FrownyFrog tyvm.  i'd forgotten about both those golf tricks.

You can save 3 bytes with (]' '#~1+>./)

@miles. Nice.  I need to make dyadic hooks part of my regular toolbox, I noticed you used them in that revision from this morning as well.

Wolfram Language (Mathematica), 76 bytes
SparseArray[Reverse@MapIndexed[#&@@#2+LetterNumber@#-1->#&,#]]<>""/. 0->" "&

Takes a list of characters as input. This generates some error messages that are safe to ignore.
I included Print and Character command in the footer of the TIO link for ease of use. (Character command simply converts a string to a list of characters)
Try it online!

LetterNumber is a built-in for finding the position of a letter in the alphabet? Holy crap, that's ridiculous.

Haskell, 88 bytes
foldr(\c->(((['B'..c]>>" ")++[c])#).(' ':))[]
(x:r)#(y:t)|y>' '=y:r#t|1<3=x:r#t
r#t=r++t

Try it online!

C# (.NET Core), 117 110 84 bytes
Saved 7 bytes thanks to Ayb4tu.
Changed return type from string to char[] to save 26 bytes.
n=>{int i=0,l=n.Length;var t=new char[l+26];for(;i<l;)t[i+n[i]-65]=n[i++];return t;}

Try it online!

You can save 7 bytes by changing t[i+((int)n[i]-65)] to t[i+n[i]-65].

@Ayb4btu Thanks forgot that char -> int conversions are implicit.

Haskell, 88 bytes
f s|q<-zipWith((+).fromEnum)s[0..]=[last$' ':[c|(c,i)<-zip s q,i==p]|p<-[65..maximum q]]

Try it online!
q is the list of the final indices of the letters of the input string (with an offset of 65). Loop through all indices (starting at 65) and find all letters for it, prepending a space. Take the last.

Yet another 88 byte Haskell solution, see here  and here.

Kotlin, 207 bytes 189 bytes 187 bytes 177 bytes
fun main(){val i=(readLine()+" ".repeat(26)).toCharArray();for(x in(i.size-1) downTo 0){if(i[x]!=' '){i[x+i[x].toInt()-65]=i[x];i[x]=' '}};print(i.joinToString("").trim())}

If the leading blank should remain I would just call trimEnd() instead of trim().
Unminified:
fun main() {
    val m = (readLine() + " ".repeat(26)).toCharArray()
    for (x in (m.size - 1) downTo 0) {
        if(m[x] != ' ') {
            m[x + m[x].toInt() - 65] = m[x]
            m[x] = ' '
        }
    }

    print(m.joinToString("").trim())
}

Maybe Kotlin is not the best language for code golfing but I liked the challenge and I wanted to make myself more familiar with Kotlin's standard library.

C# .NET, 89 Bytes 87 Bytes
-2 bytes thanks to Lan H.
f=>{var s=new char[f.Length+26];for(int i=0;i<f.Length;i++)s[f[i]+i-65]=f[i];return s;}

Try it Online!

Welcome to the site! :)

Thanks! I hope it's ok to post multiple answer in the same language

You can omit the curly brackets in your for-loop for -2 bytes.

q/kdb+, 37 bytes
Solution:
@[max[1+m]#" ";m:!:[x#:]+.Q.A?x;:;]x:

Examples:
q)@[max[1+m]#" ";m:!:[x#:]+.Q.A?x;:;]x:"AZ"
"A                         Z"
q)@[max[1+m]#" ";m:!:[x#:]+.Q.A?x;:;]x:"ABC"
"A B C"
q)@[max[1+m]#" ";m:!:[x#:]+.Q.A?x;:;]x:"ACE"
"A  C  E"
q)@[max[1+m]#" ";m:!:[x#:]+.Q.A?x;:;]x:"CBA"
"  A"
q)@[max[1+m]#" ";m:!:[x#:]+.Q.A?x;:;]x:"HELLOWORLD"
"     E H    DLL   OLO   R  W"

Explanation:
I think this is the same idea as the J solution, calculate the correct indices for the input array and then assign them to an empty string of correct length:
@[max[1+m]#" ";m:til[count x]+.Q.A?x;:;]x: / ungolfed solution
                                        x: / save input as x
@[            ;                     ; ;]   / apply[variable;indices;function;parameters]
                                     :     / assignment
                              .Q.A?x       / location of x in uppercase alphabet
                             +             / added to
                     count x               / length of input
                 til[       ]              / range, 0..n
               m:                          / save as m
  max[   ]                                 / maximum of list
      1+m                                  / m + 1
          #" "                             / take " ", creates empty character list

Jq 1.5, 91 bytes
reduce(explode|[.,keys]|transpose[]|.[1]+=.[0]-65)as[$c,$p]([];.[$p]=$c)|map(.//32)|implode

Expanded
  reduce(  explode         # convert string to array of ordinals
         | [.,keys]        # [ [v0,v1,...], [0,1,2,...] ]
         | transpose[]     # [ [v0,0], [v1,1], [v2,2]...]
         | .[1]+=.[0]-65   # adjust position of each value
  ) as[$c,$p] (
    []
  ; .[$p]=$c               # store each value at its position
  )
| map(.//32)               # map null values to spaces
| implode                  # convert back to string

Try it online!

Charcoal, 16 bytes
Ｐ ＦＳ«Ｍ⌕αι→ιＭ⌕αι←

Try it online! Link is to verbose version of code. Explanation:
Ｐ                   Output a space to force the indent
   Ｓ                Input string
  Ｆ «               Loop over each letter
       α            Uppercase letters predefined variable
      ⌕ ι           Find index of current letter
     Ｍ   →          Move that many characters right
          ι         Implicitly print the current letter
           Ｍ⌕αι←    Move the same number of characters left

APL (Dyalog), 26 bytes
Anonymous prefix lambda which takes the input string as argument and returns the output string. Assumes ⎕IO (Index Origin) 0, which is default on many systems.
{⍵@i⊢''↑⍨1+⌈/i←(⎕A⍳⍵)+⍳≢⍵}

Try it online!
{…} anonymous lambda; ⍵ represents the argument
 ≢⍵ tally of the argument
 ⍳ than many ɩntegers (0…LengthOfArgument-1)
 (…)+ plus:
  ⎕A⍳⍵ the indices of the argument in the uppercase Alphabet
 i← strore in i (for indices)
 ⌈/ maximum (reduction)
 1+ add one
 ''↑⍨ take that many characters from the empty string, padding with spaces as needed
 ⊢ yield that (serves to separate i from '')
 ⍵@i amend that with the argument letters at the i indices

SOGL V0.12, 10 bytes
ā,{ZFWē+1ž

Try it Here!
Explanation:
ā           push an empty array
 ,{         for each char in the input
   ZFW        get its index in the uppercase alphabet
      ē+      add to that the 0-indexed counter
        1ž    at [pop; 1] insert in the array the current character

Pyth, 44 38 bytes
Striked out 44 is still 44 :(
Bloody Pyth beginner.
Saved 6 bytes thanks to @Mr. Xcoder.
K*d+lz26Vlz K=XK-C@zN-65N@zN;.WqeHdPZK

Try it online!

How?
K*d+lz26Vlz K=XK-C@zN-65N@zN;.WqeHdPZK          Full program

K*d+lz26                                        Assign a string consisting of
                                                  (26 + input.length) whitespaces to K
        Vlz                                     For-loop from 0 to input.length
                -C@zN-65N                       Calculate the index for the current letter
                         @zN                    The current letter
            K=XK                                Insert the current letter into K at
                                                  position i
                            ;                   End statement
                             .WqeHdPZK          While the last character of H is not a
                                                  whitespace, pop the last character off K

38 bytes: K*d+lz26Vlz K=XK-C@zN-65N@zN;.WqeHdPZK. WqeKd K=PK;K is replaced by .W (functional while) and its arguments of course, and FNrZlz can be replaced VrZlz, but rZ... means U..., and U is generated automatically by V. So FNrZlz becomes Vlz

Batch, 418 331 bytes
Works with uppercase letters only and will take some seconds for longer strings.
Learned new tricks here, the character to ASCII value conversion using %=exitcodeAscii%. Also, if defined and "array" access using call. Also, golfing by almost 100 bytes was good batch code golf training.
Note the trailing space in set z=set.
@echo off
setlocal EnableDelayedExpansion
set z=set
%z%a=%1
:a
%z%v=64
:b
%z%/Av+=1
cmd/Cexit %v%
if %=exitcodeAscii% neq %a:~0,1% goto b
%z%/Ao=v+c
%z%a%o%=%a:~0,1%
if %o%. geq %m%. %z%m=%o%
%z%/Ac+=1
%z%a=%a:~1%
if %a%. neq . goto a
for /l %%n in (65,1,%m%)do (
if defined a%%n (call %z%r=%%r%%%%a%%n%%
)else %z%r=!r! )
echo %r%

Ruby, 68 bytes
->s{r,w="",-66;s.bytes{|b|r[(b+w+=1).times{|a|r[a]||=" "}]=b.chr};r}

Try it online!

x86-16 machine code, PC DOS, 27 bytes
00000000: b403 cd10 d1ee ad98 91ac b402 8ad0 80ea  ................
00000010: 4102 d343 cd10 cd29 e2ef c3              A..C...)...

Listing:
B4 03       MOV  AH, 3          ; get current cursor position row into DH
CD 10       INT  10H            ; call BIOS
D1 EE       SHR  SI, 1          ; SI to DOS PSP
AD          LODSW               ; AL = command line string length
98          CBW                 ; AH = 0
91          XCHG AX, CX         ; CX = length
        OUTPUT:
AC          LODSB               ; load DS:SI into AL
B4 02       MOV  AH, 2          ; BIOS set cursor position function
8A D0       MOV  DL, AL         ; ASCII char to DL
80 EA 41    SUB  DL, 'A'        ; convert ASCII char to numeric val (A=0, Z=25)
02 D3       ADD  DL, BL         ; add current position offset
43          INC  BX             ; increment position offset
CD 10       INT  10H            ; move cursor to column in DL
CD 29       INT  29H            ; write char in AL to console
E2 EF       LOOP OUTPUT         ; loop until end of input
C3          RET                 ; exit to DOS

Standalone PC DOS executable.  Input from command line and prints the new "faster" version to console.
Output:

PHP, 127 123 bytes
function b($i){for($q=0;$q<strlen($i);$q++){$n[ord($i[$q])-65]=$i[$q];}while($x++<26){$m.=$n[$x-1]?$n[$x-1]:" ";}return$m;}

Try it online
Had to fix a bug that wouldn't output 'A'...

To who-ever downvoted: You probably mis-clicked the up-button. Please correct, or drop me a line on why the downvote... Tnx

Javascript, 136 characters
Replace the variable s by the input string
for(s='',w=[],o=[],i=0;i<s.length;i++)w.push(s[i].charCodeAt(0)-65+i);w.forEach((a,b)=>o[a]=s[b]),console.log((o+'').replace(/,/g,' '));

Java 7, 135 133 bytes
String a(char[]a){char b[]=new char[37+a.length],c=0;for(;c<a.length;b[a[c]-65+c]=a[c++]);return"".valueOf(b).replaceAll("\0*$","");}

Less Golfed
String a(char[]a) {
  char b[]=new char[37+a.length],            // Create an array buffer that is the length of
                                             // the incoming string plus the length of the
                                             // alphabet so we have room to move characters
                                             // 37 is arbitrary. We need >26
  c=0;                                       // Also initialize our index variable. chars are
                                             // basically just bytes in java
  for(;c<a.length;                           // Loop over the input
    b[a[c]-65+c]=a[c++]);                    // 'A' is ascii 65 so if we subtract that and add
                                             // the current index, we have the resulting index
                                             // for that character.
  return"".valueOf(b).replaceAll("\0*$",""); // Convert char array to a string and remove any
                                             // trailing nulls that we didn't use
}

Try it online!

PHP 7.1, 54+1 bytes
Insert a space between the quotation marks for older PHP.
for($r="";$c=$argn[$i++];)$r[$i+ord($c)-66]=$c;echo$r;

Run as pipe with -nR or try it online.

Actually, 32 bytes
;ñ⌠i@O:65@-i+⌡M;Mu' *╗Z⌠i╜T╗⌡MX╜

Try it online!
Explanation
As is customary with my long Actually answers, I'm going to break down the code into sections for the explanation.
Space Padding
Input: s (a string of uppercase ASCII letters)
Output: a list L of new indexes for the letters in s on top of the stack, s below it on the stack, and a string of spaces of sufficient length to hold the output string in register 0
;ñ⌠i@O:65@-i+⌡M;Mu' *╗
                        (implicit input)
;ñ                      make a copy of s, enumerate
  ⌠i@O:65@-i+⌡M         for each [index, character] pair: calculate the new position
   i@O                    ordinal of character (in a list)
      :65@-               subtract 65
           i+             add index
               ;M       maximum index
                 u' *   add one, string of that length containing spaces
                     ╗  save to register 0

Letter Rearranging
Input: the output from the previous step
Output: the expected challenge output
Z⌠i╜T╗⌡MX╜
Z           zip the new indices with their respective letters
 ⌠i╜T╗⌡M    for each [index, character] pair: put the character in that index
  i           flatten pair
   ╜T╗        bring string from register 0, set string[index] to character, save in register 0
        X   discard the empty list from the map
         ╜  push the string in register 0
            (implicit output)

AWK, 140 bytes
BEGIN{OFS=FS=""}func f(A){for(z=0;sprintf("%c",++z)!=A;);return z-65}{for(;++i<=NF;m=n>m?n:m)a[n=i+f($i)]=$i
for(;++k<=m;)$k=a[k]?a[k]:" "}1

Try it online!
Designed for uppercase letters, since I'm subtracting 65.
Converting characters to numbers isn't so easy in AWK.  This is a few bytes shorter than indexing into a string.

Lua, 126 bytes
s=""a={}i=-65(...):gsub(".",function(c)a[c:byte()+i]=c i=i+1 end)for j=0,i+91 do s=s..(a[j]or" ")end print((s:gsub(" +$","")))

Try it online!

ARBLE, 122 bytes
s=explode&read()t={}n=0s.map(load'a,b=...k=b+byte(a)-byte"A"t[k]=a n=max&n|k')for i=1,n do t[i]=t[i]or" "end print(join&t)

Try it online!

Japt -h, 14 bytes
;åÈhYZ+BbY}Ucç

Try it

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Exponent of complex numbers
Given two integers, which may be negative, zero, or positive, \$a\$ and \$b\$ (taken in any reasonable format, including inputting a plain complex number), convert it to \$a + bi\$ where \$i\$ is the imaginary number (square root of negative one). Then, raise it to the power of a third (positive integer) input variable, \$c\$ as to \$(a + bi)^c\$. You should then end up with something like \$d + ei\$. You must then output, or return, \$d\$ and \$e\$ in any reasonable format (including outputting a plain complex number).
Input and output may be taken or outputted in any order.
Examples:
5, 2, 2 -> 21, 20
1, 4, 2 -> -15, 8
-5, 0, 1 -> -5, 0

If we use de Moivre's formula, is floating point imprecison allowed?

@Giuseppe Yes, that's okay.

FWIW I think the change to the rules (allowing a fully flexible I/O) made a fairly interesting challenge pretty dull.

@JonathanAllan at least for languages with native complex number support -- which are quite many :(

@JonathanAllan I can't please everyone :(

@Okx I know, just pointing out to others that I (and it seems from upvotes, others) prefered your original idea :)

Mathematica, 17 bytes
ReIm[(#+#2I)^#3]&

Try it online!
-8 bytes from alephalpha
but........
rules have changed......
so
Mathematica, 5 bytes
Power

{Re@#,Im@#}& -> ReIm

17 bytes. You can simply remove @#&.

haha, yes, my mistake

You can now do #^#2& or just Power.

Python 3, 3 bytes
pow

Try it online!
Input and output as complex numbers.

Python 3, 47 bytes
def f(a,b,c):n=(a+b*1j)**c;return n.real,n.imag

Try it online!
Input and output as integers

Python 2, 62 60 bytes
-2 bytes thanks to @Leonhard
a,b,c=input();d=1;e=0
exec'd,e=a*d-b*e,a*e+b*d;'*c
print d,e

Try it online!
does not use complex number type

Javascript (ES6), 51 50 bytes
a=>b=>g=c=>c?([x,y]=g(c-1),[x*a-b*y,a*y+b*x]):"10"

Takes input in currying form: f(a)(b)(c)
Returns the result as an array: [d, e]

Explanation
a=>b=>g=c=>               // Input in currying syntax
    c?(                   // If `c` != 0:
        [x,y]=g(c-1),     //     Set [x, y] to the result of f(a)(b)(c-1)
        [x*a-b*y,a*y+b*x] //     Return (a + bi) * (x + yi)
    ):                    // Else: (when c = 0)
        "10"              //     Return [1, 0] (to end the recursion)

f=a=>b=>g=c=>c?([x,y]=g(c-1),[x*a-b*y,a*y+b*x]):"10"

<input id=a type=number value=0><input id=b type=number value=0><input id=c type=number value=1 min=1>

Jelly, 1 byte
*

Try it online!
Thanks to Mr. Xcoder for alerting me of rule updates (-6 as a result).
Thanks to someone for alerting me of rule updates (-2 as a result).
First argument: (a+bj)
Second argument: c
Returns: (d+ej)

8 bytes

7 bytes

In fact Jonathan's 3 byter would suffice; ḅı*, as the rules have changed and you are now allowed to output a plain complex number.

@Mr.Xcoder was sleeping when that happened

It seems like a * onebyter is ok now as you can take input as a complex

Works in Dyalog APL too.

Pari/GP, 36 bytes
f(a,b,c)=divrem((a+b*x)^c%(x^2+1),x)

Try it online!

Pari/GP, 36 bytes
f(a,b,c)=[real(d=(a+b*I)^c),imag(d)]

Try it online!

Actually, 1 byte
ⁿ

Try it online!
Note that the rules have changed and complex numbers are valid I/O types (unfortunately this turns the post into a "perform this exponentiation" challenge). Original answer below.
Actually, 3 bytes
Çⁿ╫

Try it online!
Returns the values separated by a newline. Takes the inputs in reverse order and returns the results in reverse order (See the tio link).

Çⁿ╫  - Full program. Reversed inputs.

Ç    - Return a+bi.
 ⁿ   - Exponentiation.
  ╫  - Pushes the real and imaginary parts of a.

R, 3 bytes
This is becoming boring. If input and output is allowed as a complex number, there is a builtin for a power function.
`^`

For example:
> (5+2i)^2
[1] 21+20i
> (1+4i)^2
[1] -15+8i
> (-5+0i)^1
[1] -5+0i

or
> `^`(5+2i,2)
[1] 21+20i
> `^`(1+4i,2)
[1] -15+8i
> `^`(-5+0i,1)
[1] -5+0i

Pyth, 5 12 5 2 bytes
^E

Takes in c first, followed by a+bj.
7 bytes of boilerplate because apparently output as an imaginary number is disallowed.  It's been re-allowed! Hurrah!  And with taking in a complex number being a reasonable input, we can cut out an additional 3 bytes!
Previous solutions:
^.jEE

When complex numbers were not reasonable inputs.
m,edsd]^.jEE

When complex numbers were not reasonable outputs.
Test Suite.

05AB1E, 1 byte
m

Try it online!
Input: c\n(a+bj)
Output: (d+ej)

Same tip as Neil, 'jì+³m is a different way to calculate the number.

@Adnan at least for me it does matter indeed :p

C# (.NET Core), 62 38 bytes
a=>c=>System.Numerics.Complex.Pow(a,c)

Try it online!

You should include the .Real and .Imaginaryin your answer.. According to the rule "_You must then output, or return,dande` in any reasonable format (not including outputting a plain complex number)_" you're not allowed to just output the Complex number.

05AB1E, 20 19 17 16 bytes
‚UTSsFXâP`(‚RŠ‚+

Try it online! Takes three separate inputs in the order b, a, c and outputs an array [d, e]. Edit: Saved 2 bytes thanks to @Datboi. Saved 1 byte thanks to @Adnan. Explanation:
‚                   Join a and b into a pair
 U                  Store in variable X
  T                 Push 10 to the stack
   S                Split into the pair [d, e] = [1, 0]
    s               Swap with c
     F              Repeat the rest of the program c times
      X             Get [a, b]
       â            Cartesian product with [d, e]
        P           Multiply each pair together [da, db, ea, eb]
         `          Push each product as a separate stack entry
          (         Negate eb
           ‚        Join with ea into a pair [ea, -eb]
            R       Reverse the pair [-eb, ea]
             Š      Push under da and db
              ‚     Join them into a pair [da, db]
               +    Add the two pairs [da-eb, db+ea]

Input and output may be taken or outputted in any order. - That means that you can take the first two inputs in reverse order.

@Mr.Xcoder Thanks, I hadn't noticed that.

I'm not sure if it matters or not, but calculating the number can also be done with 'jì+³m.

You can replace 1 0‚ with TS for -2 bytes :)

And P automatically vectorizes, so you don't need the €.

@Adnan so what's "total product" supposed to mean then?

Yes, docs are crap, but I'm planning on changing this when I have some free time (with examples etc.).

TI-BASIC, 25 22 8 bytes
Takes the complex number and the exponent as input, and stores output in Ans as a complex number.  Drastic drop in bytes due to loosened restrictions on input/output.
Prompt C,E
C^E

You can save 2 bytes with imag({iAns,Ans in the last line (by i I mean the complex number i).

And I guess then one more byte by just combining the two lines into imag({i,1}(A+Bi)^C.

Rules have changed, now you can take input and return complex numbers, if that is of any help.

J, 10, 7, 1 bytes
^

Takes c as the right argument and the complex number ajb (how you represent a + bi in J) as the left argument.
Try it online!
Other Solutions
7 bytes
Takes the complex number input as a list.
^~j./@]

10 bytes
This outputted the a + bi in the list a b.
+.@^~j./@]

I wanted to try something cute like ^~&.(j./) but the inverse of j./ is obviously not defined. Actually, ^~&.(+.inv) works and you can make that ^&.(+.inv) which is also 10 bytes if you reverse the order in which you take the args.

6502 machine code subroutine, 199 187 185 bytes
A2 03 B5 FB 95 26 CA 10 F9 88 D0 01 60 A5 26 85 61 A5 27 85 62 A5 FB 85 63 A5
FC 85 64 A9 20 85 6F D0 36 18 A5 6D 65 65 85 28 A5 6E 65 66 85 29 A5 4B 85 26
A5 4C 85 27 50 CF 38 A5 6D E5 65 85 4B A5 6E E5 66 85 4C A5 28 85 61 A5 29 85
62 A5 FB 85 63 A5 FC 85 64 06 6F A9 00 85 65 85 66 A2 10 46 62 66 61 90 0D A5
63 18 65 65 85 65 A5 64 65 66 85 66 06 63 26 64 CA 10 E6 A9 FF 24 6F 70 B9 30
02 F0 9E A5 65 85 6D A5 66 85 6E 24 6F 30 14 A5 28 85 61 A5 29 85 62 A5 FD 85
63 A5 FE 85 64 06 6F D0 B4 A5 26 85 61 A5 27 85 62 A5 FD 85 63 A5 FE 85 64 06
6F B0 A0

-12 bytes with improved "spaghetti" structure
-2 bytes changing the register to pass the exponent, so we can make use of zeropage addressing mode in the initial copy loop

This is position-independent code, just put it somewhere in RAM and call it with a jsr instruction.
The routine takes the (complex) base as two 16bit signed integers (2's complement, little-endian) in $fb/$fc (real) and $fd/$fe (imaginary), and the exponent as an unsigned 8bit integer in the Y register.
The result is returned in $26/$27 (real) and $28/$29 (imaginary).

Explanation
This is still an interesting challenge on the 6502 CPU as there are no instructions for even multiplying. The approach is straight forward, implementing a complex multiplication and executing it as often as required by the exponent. Golfing is done by avoiding subroutines, instead creating kind of a "branch spaghetti", so the code for doing a simple 16bit multiplication that's needed multiple times is reused with the lowest possible overhead. Here's the commented disassembly:
 .cexp:
A2 03       LDX #$03            ; copy argument ...
 .copyloop:
B5 FB       LDA $FB,X
95 26       STA $26,X
CA          DEX
10 F9       BPL .copyloop       ; ... to result
 .exploop:
88          DEY                 ; decrement exponent
D0 01       BNE .mult           ; zero reached -> done
60          RTS
 .mult:                         ; multiply (complex) result by argument
A5 26       LDA $26             ; prepare to multiply real components
85 61       STA $61             ; (a*c)
A5 27       LDA $27
85 62       STA $62
A5 FB       LDA $FB
85 63       STA $63
A5 FC       LDA $FC
85 64       STA $64
A9 20       LDA #$20            ; marker for where to continue
85 6F       STA $6F
D0 36       BNE .mult16         ; branch to 16bit multiplication
 .mult5:
18          CLC                 ; calculate sum (a*d) + (b*c)
A5 6D       LDA $6D
65 65       ADC $65
85 28       STA $28             ; and store to imaginary component of result
A5 6E       LDA $6E
65 66       ADC $66
85 29       STA $29
A5 4B       LDA $4B             ; load temporary result (a*c) - (b*d)
85 26       STA $26             ; and store to real component of result
A5 4C       LDA $4C
85 27       STA $27
50 CF       BVC .exploop        ; next exponentiation step
 .mult3:
38          SEC                 ; calculate difference (a*c) - (b*d)
A5 6D       LDA $6D
E5 65       SBC $65
85 4B       STA $4B             ; and store to temporary location
A5 6E       LDA $6E
E5 66       SBC $66
85 4C       STA $4C
A5 28       LDA $28             ; prepare to multiply real component of result
85 61       STA $61             ; with imaginary component of argument
A5 29       LDA $29             ; (a*d)
85 62       STA $62
A5 FB       LDA $FB
85 63       STA $63
A5 FC       LDA $FC
85 64       STA $64
06 6F       ASL $6F             ; advance "continue marker"
 .mult16:
A9 00       LDA #$00            ; initialize 16bit multiplication
85 65       STA $65             ; result with 0
85 66       STA $66
A2 10       LDX #$10            ; bit counter (16)
 .m16_loop:
46 62       LSR $62             ; shift arg1 right
66 61       ROR $61
90 0D       BCC .m16_noadd      ; no carry -> nothing to add
A5 63       LDA $63             ; add arg2 ...
18          CLC
65 65       ADC $65
85 65       STA $65
A5 64       LDA $64
65 66       ADC $66
85 66       STA $66             ; ... to result
 .m16_noadd:
06 63       ASL $63             ; shift arg2 left
26 64       ROL $64
CA          DEX                 ; decrement number of bits to go
10 E6       BPL .m16_loop
A9 FF       LDA #$FF            ; check marker for where to continue
24 6F       BIT $6F
70 B9       BVS .mult3
30 02       BMI .saveres        ; have to save result to temp in 2 cases
F0 9E       BEQ .mult5
 .saveres:
A5 65       LDA $65             ; save result to temporary
85 6D       STA $6D
A5 66       LDA $66
85 6E       STA $6E
24 6F       BIT $6F             ; check "continue marker" again
30 14       BMI .mult4
 .mult2:
A5 28       LDA $28             ; prepare to multiply imaginary components
85 61       STA $61             ; (b*d)
A5 29       LDA $29
85 62       STA $62
A5 FD       LDA $FD
85 63       STA $63
A5 FE       LDA $FE
85 64       STA $64
06 6F       ASL $6F             ; advance "continue marker"
D0 B4       BNE .mult16         ; branch to 16bit multiplication
 .mult4:
A5 26       LDA $26             ; prepare to multiply imaginary component of
85 61       STA $61             ; result with real component of argument
A5 27       LDA $27             ; (b*c)
85 62       STA $62
A5 FD       LDA $FD
85 63       STA $63
A5 FE       LDA $FE
85 64       STA $64
06 6F       ASL $6F             ; advance "continue marker"
B0 A0       BCS .mult16         ; branch to 16bit multiplication

Example program using it (C64, assembly source in ca65-syntax):
.import cexp

CEXP_A          = $fb
CEXP_AL         = $fb
CEXP_AH         = $fc
CEXP_B          = $fd
CEXP_BL         = $fd
CEXP_BH         = $fe

CEXP_RA         = $26
CEXP_RAL        = $26
CEXP_RAH        = $27
CEXP_RB         = $28
CEXP_RBL        = $28
CEXP_RBH        = $29

.segment "LDADDR"
                .word   $c000

.segment "MAIN"
                jsr     $aefd           ; consume comma
                jsr     $ad8a           ; evaluate number
                jsr     $b1aa           ; convert to 16bit int
                sty     CEXP_AL         ; store as first argument
                sta     CEXP_AH
                jsr     $aefd           ; ...
                jsr     $ad8a
                jsr     $b1aa
                sty     CEXP_BL         ; store as second argument
                sta     CEXP_BH
                jsr     $b79b           ; read 8bit unsigned into X
                txa                     ; and transfer
                tay                     ; to Y

                jsr     cexp            ; call our function

                lda     CEXP_RAH        ; read result (real part)
                ldy     CEXP_RAL
                jsr     numout          ; output
                ldx     CEXP_RBH        ; read result (imaginary part)
                bmi     noplus
                lda     #'+'            ; output a `+` if it's not negative
                jsr     $ffd2
noplus:         txa
                ldy     CEXP_RBL
                jsr     numout          ; output (imaginary part)
                lda     #'i'
                jsr     $ffd2           ; output `i`
                lda     #$0d            ; and newline
                jmp     $ffd2

numout:
                jsr     $b391           ; convert to floating point
                jsr     $bddd           ; format floating point as string
                ldy     #$01
numout_loop:    lda     $ff,y           ; output loop
                bne     numout_print    ; until 0 terminator found
                rts
numout_print:   cmp     #' '            ; skip space characters in output
                beq     numout_next
                jsr     $ffd2
numout_next:    iny
                bne     numout_loop

Online demo
Usage: sys49152,[a],[b],[c], e.g. sys49152,5,2,2 (Output: 21+20i)

Casio-Basic, 6 bytes
a^b

Change to the rules to allow input and output as complex numbers made this significantly shorter.
3 bytes for the function, +3 to enter a,b in the parameters box.

MATL, 1 byte
^

Inputs are a+jb, c.
Try it online!
Old version: non-complex input and output, 8 bytes
J*+i^&Zj

Input order is b,a, c.
Try it online!
Explanation
J           Push imaginary unit
 *          Multiply by implicit input b
  +         Add implicit input a
   i        Take input c
    ^       Power
     &Zj    Push real and imaginary parts. Implicitly display

Multiply by implicit input b - Add implicit input b. Did you mean a in either of those?

@Mr.Xcoder Yes, thanks. Corrected

You can take input in the form of a complex number now, and output in the form of a complex number.  You can probably cut out a lot of boilerplate from this answer because of that.

@StevenHewitt Thanks! Edited now

Dyalog APL, 10 bytes
⎕*⍨⊣+¯11○⊢

Try it online!
a is left argument, b is right argument, and c via input prompt.
Returns a complex number in the format dJe.

Rules have changed, now you can take input and return complex numbers, if that's of any help.

Now, you can input and output complex numbers directly (according to rules). So the answer is simply the * function (or, taking input from stdin and outputting to stdout, we have: ⎕*⎕).

C (gcc), 34 bytes
#define f(a,b,c)cpow((a)+1i*(b),c)

Try it online!

Octave / MATLAB, 6 bytes
@power

Anonymous function that inputs two numbers and outputs their power.
Try it online!
Old version: non-complex input and output, 30 bytes
@(a,b,c)real((a+j*b)^c./[1 j])

Anonymous function that inputs three numbers and outputs an array of two numbers.
Try it online!

Perl 6,  29 26 20 19  11 bytes
{$_=($^a+$^b*i)**$^c;.re,.im}

Try it
{(($^a+$^b*i)**$^c).reals}

Try it
((*+* *i)** *).reals

Try it
((*+* *i)***).reals

Try it
With the change of output restrictions it can be further reduced:
(*+* *i)***

Try it
The *** part is parsed as ** * because the ** infix operator is longer than the * infix operator.
Expanded:
#     __________________ 1st parameter
#    /   _______________ 2nd parameter
#   /   /         ______ 3rd parameter
#  /   /         /
# V   V         V
( * + * * i) ** *
#       ^    ^^
#        \     \________ exponentiation
#         \_____________ multiplication

You can now do (*+* *i)***.

8th, 38 bytes
Code
c:new dup >r ( r@ c:* ) rot n:1- times

SED (Stack Effect Diagram) is: c a b  -- (a + bi) ^ c
Warning: a + bi is left on r-stack, but this doesn't affect subsequent computations.
Ungolfed version with comments
needs math/complex

: f \ c a b  -- (a + bi) ^ c
    c:new                      \ create a complex number from a and b
    dup                        \ duplicate a + bi
    >r                         \ store a + bi on r-stack
    ( r@ c:* ) rot n:1- times  \ raise ( a + bi ) to c
;

Example and usage
: app:main
    \ rdrop is not strictly required
    2 5 2 f . cr rdrop
    2 1 4 f . cr rdrop
    1 -5 0 f . cr rdrop
    bye
;

Output of the previous code
c:1:data:{"real":21,"imag":20}
c:1:data:{"real":-15,"imag":8}
c:2:data:{"real":-5,"imag":0}

R, 25 bytes
simplest - since outputting complex is allowed.
function(a,b,c)(a+b*1i)^c

you can simplify your code by just taking a complex number z as input - then function body is simply z^c.

Ruby, 9 bytes
Returns an anonymous function that takes a complex number and integer and returns a complex number.
proc &:**

This is equivalent to ->x,y{x**y} (11 bytes).
Attempt This Online!

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/