text:
Modular broadcasting
This challenge is related to some of the MATL language's features, as part of the May 2018 Language of the Month event.

Introduction
In MATL, many two-input functions work element-wise with broadcast. This means the following:

Element-wise (or vectorized): the function takes as inputs two arrays with matching sizes. The operation defined by the function is applied to each pair of corresponding entries. For example, using post-fix notation:
[2 4 6] [10 20 30] +

gives the ouput
[12 24 36]

This also works with multi-dimensional arrays. The notation [1 2 3; 4 5 6] represents the 2×3 array (matrix)
1 2 3
4 5 6

which has size 2 along the first dimension (vertical) and 3 along the second (horizontal). So for example
[2 4 6; 3 5 7] [10 20 30; 40 60 80] *

gives
[20 80 180; 120 300 560]

Broadcasting or (singleton expansion): the two input arrays do not have matching sizes, but in each non-matching dimension one of the arrays has size 1. This array is implicitly replicated along the other dimensions to make sizes match; and then the operation is applied element-wise as above. For example, consider two input arrays with sizes 1×2 and 3×1:
[10 20] [1; 2; 5] /

Thanks to broadcasting, this is equivalent to
[10 20; 10 20; 10 20] [1 1; 2 2; 5 5] /

and so it gives
[10 20; 5 10; 2 4]

Similarly, with sizes 3×2 and 3×1 (broadcasting now acts along the second dimension only),
[9 8; 7 6; 5 4] [10; 20; 30] +

gives
[19 18; 27 26; 35 34]

The number of dimensions may even be different. For example, inputs with sizes 3×2 and 3×1×5 are compatible, and give a 3×2×5 result. In fact, size 3×2 is the same as 3×2×1 (there are arbitrarily many implicit trailing singleton dimensions).
On the other hand, a pair of 2×2 and 3×1 arrays would give an error, because the sizes along the first dimension are 2 and 3: they are not equal and none of them is 1.

Definition of modular broadcasting
Modular broadcasting is a generalization of broadcasting that works even if none of the non-matching sizes are 1. Consider for example the following 2×2 and 3×1 arrays as inputs of the function +:
[2 4; 6 8] [10; 20; 30] +

The rule is as follows: for each dimension, the array that is smaller along that dimension is replicated modularly (cyclically) to match the size of the other array. This would make the above equivalent to
[2 4; 6 8; 2 4] [10 10; 20 20; 30 30] +

with the result
[12 14; 26 28; 32 34]

As a second example,
[5 10; 15 20] [0 0 0 0; 1 2 3 4; 0 0 0 0; 5 6 7 8; 0 0 0 0] +

would produce
[5 10 5 10; 16 22 18 24; 5 10 5 10; 20 26 22 28; 5 10 5 10]

In general, inputs with sizes a×b and c×d give a result of size max(a,b)×max(c,d).
The challenge
Implement addition for two-dimensional arrays with modular broadcasting as defined above.
The arrays will be rectangular (not ragged), will only contain non-negative integers, and will have size at least 1 in each dimension.
Aditional rules:

Input and output can be taken by any reasonable means. Their format is flexible as usual.
Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
Shortest code in bytes wins.

Test cases
The following uses ; as row separator (as in the examples above). Each test case shows the two inputs and then the output.
[2 4; 6 8]
[10; 20; 30]
[12 14; 26 28; 32 34]

[5 10; 15 20]
[0 0 0 0; 1 2 3 4; 0 0 0 0; 5 6 7 8; 0 0 0 0]
[5 10 5 10; 16 22 18 24; 5 10 5 10; 20 26 22 28; 5 10 5 10]

[1]
[2]
[3]

[1; 2]
[10]
[11; 12]

[1 2 3 4 5]
[10 20 30]
[11 22 33 14 25]

[9 12 5; 5 4 2]
[4 2; 7 3; 15 6; 4 0; 3 3]
[13 14 9;12 7 9;24 18 20;9 4 6;12 15 8]

[9 12 5; 5 4 2]
[4 2 6 7; 7 3 7 3; 15 6 0 1; 4 0 1 16; 3 3 3 8]
[13 14 11 16; 12 7 9 8; 24 18 5 10; 9 4 3 21; 12 15 8 17]

[6 7 9]
[4 2 5]
[10 9 14]

"Implement addition for two-dimensional arrays" - there are one dimensional test cases.

May we assume that we get no ragged arrays input? (looks like it)

@JonathanAllan Sorry for not being clear. Yes, you can assume no ragged arrays. They will be rectangular arrays. The "one dimensional" ones should be regarded as two-dimensional with size 1×n (such as [1 2 3]) or n×1 (such as [1; 2; 3])

The broadcasting you describe seems more limited than MATLAB or NumPy broadcasting; in your description, the inputs have to have the same number of dimensions, a restriction not present in MATLAB or NumPy. Is this a MATL restriction, or a simplification for the purposes of the challenge (since the challenge is limited to 2D input)?

@user2357112 Yes, it was a simplification in the description. MATL's broadcasting is the same as in MATLAB: you can have 3×2 and 3×1×5 inputs and get a 3×2×5 result. Actually, 3×2 is equivalent to 3×2×1 (implicit trailing dimensions). I think it is similar in Numpy (but with leading dimensions). I've clarified that in the introduction

Jelly, 10 bytes
ṁ€ZL$Z€Ɗ⁺S

Takes a matrix pair (two arrays of rows) as input and returns a matrix.
Try it online!
How it works
ṁ€ZL$Z€Ɗ⁺S  Main link. Argument: [M, N] (matrix pair)

  Z $       Zip M with N (i.e., transpose the matrix of arrays [M, N], ...
   L            then take the length (number of rows) of the result.
ṁ€          Mold M and N like the indices, cyclically repeating their rows as many
            times as needed to reach the length to the right.
     Z€     Zip each; transpose both M and N.
       Ɗ⁺   Combine the three links to the left into a chain and duplicate it.
            The first run enlarges the columns, the second run the rows.
         S  Take the sum of the modified matrices.

Of course... I see all these golfing languages as somewhat compatible in terms of bytes necessary for a challenge (Jelly, 05AB1E, Pyth, APL, etc.) Most of the current answers are about 20 bytes, and here comes Wizard Dennis along with an answer halve of that.. ;) Pretty funny when memes and truth are one and the same: "Nobody outgolfs Dennis!.."

@KevinCruijssen APL is not a golfing language.

@Adám I know, I know. But it's still very short (despite being first developed in the 1960s). Maybe I should have said short languages instead of golfing languages. Ah well..

Charcoal, 25 23 bytes
ＡθＩＥ⌈ＥθＬιＥ⌈ＥθＬ§λ⁰ΣＥθ§§νιλ
Try it online! Link is to verbose version of code. Takes input as a 3-dimensional array. Explanation:
Ａθ

Input everything.
    θ                   Input
   Ｅ                    Map over arrays
      ι                 Current array
     Ｌ                  Length
  ⌈                     Maximum
 Ｅ                      Map over implicit range
          θ             Input
         Ｅ              Map over arrays
             λ          Current array
            § ⁰         First element
           Ｌ            Length
        ⌈               Maximum
       Ｅ                Map over implicit range
                 θ      Input
                Ｅ       Map over arrays
                    ν   Current array
                   § ι  Cyclically index using outer loop index
                  §   λ Cyclically index using inner loop index
               Σ        Sum
Ｉ                       Cast to string
                        Implicitly print on separate lines and paragraphs

:P (it's longer though >_>)

MATL, 25 24 bytes
,iZy]vX>XKx,@GK:KP:3$)]+

Try it online!
Finally! It only took a week for the Language of the Month-inspired challenge to be answered by the Language of the Month!
My guess is that it's not quite as short as possible, but I'm happy enough because my initial version was over 40 bytes. edit: I was right, Luis found another byte to squeeze out!
,iZy]	# do twice: read input and find the size of each dimension
vX>	# find the maximum along each dimension
XKx	# save this into clipboard K and delete from stack. Stack is now empty.
,	# do twice:
 @G	# push the input at index i where i=0,1.
	# MATL indexes modularly, so 0 corresponds to the second input
 K:	# push the range 1...K[1]
 KP:	# push the range 1...K[2]
 3$)	# use 3-input ) function, which uses modular indexing
	# to expand the rows and columns to the appropriate broadcasted size
]	# end of loop
+	# sum the now appropriately-sized matrices and implicitly display

waits for Luis Mendo to golf off 5 more bytes ;-)

:-D My program for the test cases had 26 bytes, well done! Nice use of : with vector input

Python 3, 127 126 125 bytes
golfed a byte by changing sum(m) to m+n
One more byte thanks to @Jonathan Frech
lambda y:[[m+n for n,m,j in Z(l)]for*l,i in Z(y)]
from itertools import*
Z=lambda y:zip(*map(cycle,y),range(max(map(len,y))))

Takes input as a list of two 2-dimensional arrays.

The Z lambda takes two arrays as input and returns an iterator yielding an index and merged values from both arrays, until the index reaches the largest array's length. The index variable isn't useful to me and costs me bytes, but I don't know how to do without it... (related)
The main lambda just takes the input arrays and calls Z on the outer and inner arrays. The innermost values are added together.

Try it online!
Using itertools.cycle feels a bit like cheating but I think I've been punished enough by the sheer import statement length :)
I'm sure this could be golfed some more, especially the iteration method that leaves these useless i and j variables. I would be grateful on any tips on how to golf that, I'm probably missing something obvious.

Could you swap your zip's arguments, reverse f's comprehension assignment and thus remove one space (for i,*l -> for*l,i)? (125 bytes)?

One more byte, thank you ! I'll update my post.

05AB1E, 15 bytes
2FεIζg∍ø]øεø¨}O

Try it online!

Old version, 25 bytes
é`DŠg∍)Σнg}`DŠнgδ∍€˜)ø€øO

Try it online!
Explanation
15-byter:

2FεIζg∍ø]øεø¨}O – Full program. Takes input as a 3D [A, B] list from STDIN.
2F              – Apply twice:
  ε             – For each in [A, B]:
   Iζ             – Transpose the input (filling gaps with spaces).
     g            – Length (retrieve the number of rows).
      ∍           – Extend the current item (A or B) to the necessary length.
       ø          – Transpose.
        ]       – Close all loops.
         ø      – Transpose again.
          ε     – For each row in ^ (column of the loops result):
           ø    – Transpose the column.
            ¨}  – Remove the last element and close the map-loop.
              O – Sum.

25-byter:

é`DŠg∍)Σнg}`DŠнgδ∍€˜)ø€øO – Full program. Takes input as a 3D list from STDIN.
é                         – Sort the list by length.
 `D                       – Dump contents separately onto the stack, duplicate the ToS.
   Š                      – Perform a triple swap. a, b, c -> c, a, b.
    g                     – Get the length of the ToS.
     ∍                    – Extend the shorter list (in height) accordingly.
      )Σ  }               – Wrap the whole stack into a list and sort it by:
        нg                – The length of its first item.
           `DŠ            – Same as above.
              нg          – The length of the first element.
                δ∍€˜      – Extend the shorter list (in width) accordingly.
                    )ø    – Wrap the stack into a list and transpose (zip) it.
                      €ø  - Then zip each list.
                        O – Apply vectorised summation.

JavaScript (ES6), 131 bytes
Not the right tool for the job, and probably not the right approach either. Oh well...  ¯\_(ツ)_/¯
a=>b=>(g=(a,b,c)=>[...Array((a[b[L='length']]?a:b)[L])].map(c))(a,b,(_,y)=>g(a[0],b[0],(_,x)=>(h=a=>a[y%a[L]][x%a[0][L]])(a)+h(b)))

Try it online!
How?
The helper function g() creates an array which is as large as the largest input array (a or b) and invokes the callback function c over it:
g = (a, b, c) =>
  [...Array(
    (a[b[L = 'length']] ? a : b)[L]
  )].map(c)

The helper function h() reads the 2D-array a at (x, y) with modular broadcasting:
h = a => a[y % a[L]][x % a[0][L]]

The main code now simply reads as:
a => b =>
  g(a, b, (_, y) =>
    g(a[0], b[0], (_, x) =>
      h(a) + h(b)
    )
  )

Recursive version, 134 bytes
a=>b=>(R=[],g=x=>a[y]||b[y]?a[0][x]+1|b[0][x]+1?g(x+1,(R[y]=R[y]||[])[x]=(h=a=>a[y%a.length][x%a[0].length])(a)+h(b)):g(+!++y):R)(y=0)

Try it online!

R, 136 104 103 95 93 bytes
Golfed down a whopping 33 35 bytes following Giuseppe's advice. Managed to get under 100 bytes by using an operator as a function name.
See history for more legible code.
function(x,y,d=pmax(dim(x),dim(y)))y/d[2]/d[1]+x/d[2]/d[1]
"/"=function(x,j)apply(x,1,rep,,j)

Try it online!

Nice! I've golfed this down to 104 bytes but using apply and rep.len is what I had considered, although I hadn't gotten around to coding it up myself.

@Giuseppe Thanks! The 104 version does not give the expected output though.

Ugh, I keep leading you astray! this one should work

@Giuseppe Love the use of dim, much cleaner and opens the door to a multi-dimensional generalization with recursive calls to r

I've been trying to use outer(x,y,"+") which contains all the right sums, and in a clear pattern. Can't figure out how to extract them efficiently.

apply(x,1,rep,,j) works for another byte down.

This is a prime example of where operator precedence is efficient; by using / rather than - (we can't use * because it screws something up, probably rep(?)), we can remove the parentheses. Try it online!

and just for fun, you can use ! in place of dim for the same byte count.

@Giuseppe Very nice indeed!

APL (Dyalog Classic), 23 21 bytes
↑{+⌿⍺[⍵|[0]⍳⍴⍺]}2,¨⍴¨

Try it online!
this could be the only time ever I get a chance to use |[0]

K (ngn/k), 23 bytes
{+/2{+:'(|/#:'x)#'x}/x}

Try it online!

05AB1E, 18 bytes
éR`UvXNèy‚é`©g∍®+ˆ

Try it online!
Explanation
éR                  # sort by length, descending
  `U                # store the shorter list in X
    v               # for each list y, index N in the longer list
     XNè            # get the nth element of the shorter list
        y‚é         # pair with y and sort by length
           `©g∍     # repeat the shorter list to the same length as the longer
               ®+   # elementwise addition of the lists
                 ˆ  # add to global list
                    # implicitly print global list

Pyth, 24 bytes
KeSmlhdQmm+Fm@@bdkQKeSlM

Try it here
Explanation
KeSmlhdQmm+Fm@@bdkQKeSlM
                    eSlMQ  Get the maximum length of (implicit) input...
KeSmlhdQ           K       ... and the maximum row length.
        mm                 For each 2d index ...
          +Fm@@bdkQ        ... get the sum of the appropriate elements.

Java 8, 172 bytes
A->B->{int m=A.length,o=A[0].length,d=B.length,u=B[0].length,l=m>d?m:d,a=o>u?o:u,r[][]=new int[l][a],$;for(;l-->0;)for($=a;$-->0;)r[l][$]=A[l%m][$%o]+B[l%d][$%u];return r;}

Try it online.
Explanation:
A->B->{                   // Method with integer-matrix as both parameters and return-type
  int m=A.length,         //  Rows of `A`                        (we got an     M)
      o=A[0].length,      //  Columns of `A`                     (we got an     O)
      d=B.length,         //  Rows of `B`                        (we got a      D)
      u=B[0].length,      //  Columns of `B`                     (we got a      U)
      l=m>d?m:d,          //  Maximum of both rows               (we got an     L)
      a=o>u?o:u,          //  Maximum of both columns            (we got an     A)
      r[][]=new int[l][a],//  Result-matrix of size `l` by `a`   (and we got an R)
      $;                  //  Temp integer                       (which $pells? ;P)
  for(;l-->0;)            //  Loop over the rows
    for($=a;$-->0;)       //   Inner loop over the columns
      r[l][$]=            //    Set the current cell in the result-matrix to:
        A[l%m][$%o]       //     The value at {`l` modulo-`m`, `$` modulo-`o`} in `A`
        +B[l%d][$%u];     //     Plus the value at {`l` modulo-`d`, `$` modulo-`u`} in `B`
  return r;}              //  Return the result matrix

Python 2, 124 116 bytes
l=len
A,B=sorted(input(),key=l)
A*=l(B)
for i in eval(`zip(A,B)`):a,b=sorted(i,key=l);a*=l(b);print map(sum,zip(*i))

Try it online!
Explanation:
Takes list of two 2-d lists as input.
l=len
A,B=sorted(input(),key=l)         # Sort inputed lists by length
A*=l(B)                           # Extend shorter list
for i in eval(`zip(A,B)`):        # Zip and remove copied references
  a,b=sorted(i,key=l)             # Sort lists in each pair (keep references)
  a*=l(b)                         # Extend shorter list
  print map(sum,zip(*i))          # Zip and sum

I took ideas from both our solutions and came down to 105 bytes. I had to use Python 2 though, and i got the multiplication trick from your code, so it wouldn't feel right to update my answer :)

@etene You should post it, it's good solution!

Damn, pretty stupid mistakes on my part, thank you (again) !

@etene Just noticed, this solution had issues with 2 and 6 test cases. Need to remove copied references

@etene Back to 105 bytes :C

I'll fix it, that was too good to be true :D

Python 2, 101 97 105 bytes
Edit: Thanks (again !) to Dead Possum for saving 4 bytes
Edit 2: lost 8 bytes, some tests cases weren't passing
A mix between Dead Possum's earlier solution (thanks to him !), and my own Python 3 solution.
lambda y:[map(sum,P(i))for i in P(y)]
def P(y):y=sorted(y,key=len);y[0]*=len(y[1]);return eval(`zip(*y)`)

Try it online!
Same input as my Python 3 solution (a pair of 2 dimensional lists).
Commented code:
# Iterate over the nested lists, resized & joined by P(),
# and sum the inner joined items
lambda y:[map(sum,P(i))for i in P(y)]
def P(y):
 y=sorted(y,key=len)  # Sort the two input lists by length
 y[0]*=len(y[1])      # Multiply the smallest one by the biggest one's length
                      # (The smallest list is now the previously largest one)
 return eval(`zip(*y)`)  # Return paired list elements up to the smallest list's length

Julia 0.6, 85 83 bytes
M\N=(((r,c),(s,d))=size.((M,N));repmat(M,s,d)+repmat(N,r,c))[1:max(r,s),1:max(c,d)]

Try it online!
(Replace ⧻ with \ thanks to Jo King)
Works by repeating each matrix horizontally and vertically so they both have the same size (product of row sizes x product of column sizes), adding those up and extracting out the correct region from that. (Row vector inputs or column vector inputs need a reshape call to be cast as 2-dimensional arrays, which I'm assuming is fine since the question specifies "Implement addition for two-dimensional arrays" and "Input and output can be taken by any reasonable means. Their format is flexible as usual.")


text:
Tips for golfing in The Powder Toy
Have fun with this one, The Powder Toy is a interesting challenge for golf, especially with filt logic.
The thing that makes TPT a challenge is the many many many many ways to approach a problem: Should I use Cellular Automaton rules, SWCH logic, Filt logic, subframe filt logic, and/or wall logic?
As such, a location for tips for TPT golfing would be quite helpful, so I made this question thread.
This thread will likely use a lot of abbreviations. A lot of them will be in-game elements, so searching them up on the Wiki will bring you a lot of information about them, like what they are.
Here are the most common ones you'll likely see in this thread, with their ingame description attached (and their full name), for people who don't want to go searching:

SPRK: Electricity. The basis of all electronics in TPT, travels along wires and other conductive elements.
FILT: Filter. Filter for photons, changes the color.
ARAY: Ray Emitter. Rays create points when they collide.
BTRY: Battery. Generates infinite electricity.
DRAY: Duplicator ray. Replicates a line of particles in front of it.
CRAY: Particle Ray Emitter. Creates a beam of particles set by its ctype, with a range set by tmp.
SWCH: Switch. Only conducts when switched on. (PSCN switches on, NSCN switches off)

List of all elements

@mbomb007 Thanks for adding the link. I was just going to ask for that. I don't know TPT and thought it was a challenge about toys that used to be -- and maybe still are -- found in packs of detergent... :/

@Arnauld Haha. Whoops. Thanks mbomb007 :P

How do you even calculate the score?

@12Me21 At the moment, the score is based on save file. You can discuss that in this meta post

Only use subframe logic when it's smaller
And, for more complex machines, it's often much smaller.
Subframe generally imposes the overhead of creating solid SPRK (about 3 pixels for most directions, an extra pixel compared to just a BTRY), FILT 'channels' (for fast BRAY transfer), and minimizing the amount of nonsubframe logic, even if it's smaller, due to it being many times (4x to 20x-30x slower!) slower.
Subframe logic is often good for complex operations (which is most of the challenges here), but for simpler ones, subframe logic is probably not optimal.

pls add images tyvm

@ASCII-only Will do when I get home.

It'd be nice if you could spell things out instead of using so many abbreviations. Not everyone is familiar with the game, but some might find it interesting.

@mbomb007 Just going to note, FILT, BTRY, BRAY, SPRK, etc are just names for in-game particles. The game itself uses those names. Shall I put the game's wiki in the main post instead? People can search those names there and figure out what they are quite easily.

Know your FILT modes
FILT is, at least for FILT and subframe logic, the cornerstone of computing in TPT. And as such, it has a bunch of tricks to make your life easier, in the form of it's various modes. You set a FILT mode using tmp, but a comprehensive list that describes the intricacies of these modes isn't really a thing right now. FILT takes two inputs: it's own color (CTYPE) and the color of what it's interacting with, either BRAY or CRAY. I'll label these FILTC and INTRC, respectively, for this list.

Mode 0:
The simplest mode, it sets INTRC to the value of FILTC, nothing more.
INTRC = FILTC

Mode 1:
This is a binary AND, it ands together INTRC and FILTC, setting INTRC
to the result.
INTRC = INTRC & FILTC

Mode 2:
This is a binary OR, it ors together INTRC and FILTC, setting INTRC to the result.
INTRC = INTRC & FILTC

Mode 3:
This mode is slightly more complicated, it ands together the inverse of FILTC and INTRC, setting INTRC to the result.
INTRC = INTRC & (~FILTC)

Mode 4:
This mode is a bit harder to describe. It's a red shift (binary left shift),
The catch here is that the amount it shifts by is controlled by it's temperature, with the equation (Temperature-273.0)*0.025, defaulting to a shift by 1 if the value is less than 1. You can acheive a shift of any required amount by multiplying the number of bits you need by 40, and adding 273.0. I'll call the amount shifted X.
As such, INTRC is shifted left by X, setting INTRC to the result.
X = (temperature-273.0)*0.025
INTRC = INTRC << X

Mode 5:
This is essentially mode 4, but with a right shift instead. See the information on mode 4 for how to use it.
X = (temperature-273.0)*0.025
INTRC = INTRC >> X

Mode 6:
Does nothing.
INTRC = INTRC

Mode 7:
Performs a binary XOR on INTRC and FILTC, setting INTRC to the result.
INTRC = INTRC ^ FILTC

Mode 8:
Performs a binary NOT on INTRC, setting INTRC to the result.
INTRC = ~INTRC

Mode 9:
Sets INTRC to a random color.
INTRC = rand()

Mode 10:
Performs a different version of a red shift.
[TODO: figure out how to describe]
LSB = FILTC & (-FILTC)
INTRC = INTRC * LSB

Mode 11:
Performs a different version of a blue shift.
[TODO: figure out how to describe]
LSB = FILTC & (-FILTC)
INTRC = INTRC / LSB

source: Stack Exchange

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

sort: votes


text:
Bringing a pair of integers to equality
This was inspired by a math problem I saw somewhere on the internet but do not remember where (UPDATE: The original problem was found on the math riddles subreddit with a proof provided that it is possible, also see this Math SE post), asking for a proof if the following process is possible for any arbitrary pair of integers (from what I remember, it was possible for any given pair):
Given a pair of integers, j and k, double one of them and add one to the other, resulting in a pair of new integers, i.e., (j, k) -> (j+1, k*2) or (j*2, k+1). Then repeat this process with those integers, with the objective of having the pair of integers be equal.
These given examples are not necessarily optimal but show how this process can be done on any integers, positive, negative or zero:
(2, 5) -> (3, 10) -> (6, 11) -> (12, 12)

(5, 6) -> (6, 12) -> (7, 24) -> (14, 25) -> (28, 26) -> (56, 27) -> (112, 28) -> (113, 56) -> (226, 57) -> (227, 114) -> (228, 228)

(0, 2) -> (1, 4) -> (2, 5) -> (3, 10) -> (6, 11) -> (12, 12)

(-4, 0) -> (-3, 0) -> (-2, 0) -> (-1, 0) -> (0, 0)

(3, -1) -> (6, 0) -> (12, 1) -> (13, 2) -> (14, 4) -> (15, 8) -> (16, 16)

(-4, -3) -> (-8, -2) -> (-16, -1) -> (-32, 0) -> (-31, 0) -> ... -> (0, 0)

Challenge
Create a program that given two integers, outputs the list of steps required to make those integers equal by repeatedly incrementing one and doubling the other
Specifications

The solution does not have to be optimal but it must solve in a finite number of steps for any arbitrary pair
Input must be two integers
Output may be any reasonable output that clearly denotes the resulting integers of each step, for example:

a string with two distinct delimiters (any symbol, whitespace, etc), one for each integer in a pair and one for each pair

e.g., input j, k: 2, 5 -> output: 3,10;6,11;12,12

a list of lists of integers

e.g. input j, k: 2, 5 -> output: [[3, 10], [6, 11], [12, 12]]

If the input is a pair of equal numbers, you may output anything as long as it's consistent with other nontrivial answers

for example

if input [2, 5] has output [[3, 10], [6, 11], [12, 12]], which does not include the input pair, then input [4, 4] should output nothing.
if input [2, 5] has output [[2, 5], [3, 10], [6, 11], [12, 12]], which does include the input pair, then input [4, 4] should output [[4, 4]].

Standard IO methods apply and standard loopholes banned
This is code golf so shortest answer in bytes wins

This is a nice first challenge, BTW. Welcome to PPCG!

@Arnauld Thank you! Also thanks for pointing the error out, I did all the examples by hand and really should implement a solution myself first

Can the output be in reverse? E.g. [(12,12),(6,11),(3,10),(2,5)] for input (2,5)?

@Laikoni Considering all the steps required are still outputted, I think it's fine

Can it be the case that the two input numbers are the same? If so, maybe add an example with that

@LuisMendo I think since it's trivial, as long as the output is consistent with nontrivial answers, it's fine. I'll add that to the post

Is it fine to output a list of the type of each step, instead of the result of each step?

@miles The type of step as in if you're doubling the j or k? I think since there are already solutions to this and they all output the result of each step, then it should be consistent. I'll add it to the post as well

double one of them and add one to the other, I initially read "add one to the other" as meaning "add them together".

Just to be on the safe side, you should point out that it is always possible to reach the state of both integers being equal. I would even suggest a proof, but that likely involves using some concrete, simple algorithm which always works, and that ruins part of the challenge.

@Arthur, if there's a "concrete, simple algorithm which always works", there's no guarantee that it's minimal.

@PeterKagey I'm no golfer, but the simpler algorithms are usually shorter implemented. Sure, the one I have in mind might not be optimal, especially not for every language, but still.

This post spawned a question on Math Stack Exchange: Given a pair of integers, double one and increment the other until equality.

@PeterKagey Reddit /r/mathriddles! That's where I saw the original question. I'll add that to the post

I added this to the OEIS as A304027. The pair (34,23) seems to be especially difficult.

JavaScript (ES6), 111 90 83 bytes
f=(a,b,p=q=[],u=[...p,[a,b]])=>a-b?f(...(q=[[a*2,b+1,u],[a+1,b*2,u],...q]).pop()):u

Try it online!
Commented
f = (                       // f = recursive function taking:
  a, b,                     //   (a, b) = input integers
  p =                       //   p[] = current path
  q = [],                   //   q[] = queue
  u = [...p, [a, b]]        //   u[] = updated path with [a, b] appended to it
) =>                        //
  a - b ?                   // if a is not yet equal to b:
    f(...                   //   recursive call, using spread syntax:
      (q = [                //     prepend the next 2 possible moves in the queue:
        [a * 2, b + 1, u],  //       a * 2, b + 1
        [a + 1, b * 2, u],  //       a + 1, b * 2
        ...q                //
      ]).pop()              //     use the move on the top of the queue
    )                       //   end of recursive call
  :                         // else:
    u                       //   success: return the (updated) path

Haskell, 70 69 bytes
f(w@((i,j):_):r)|i==j=w|1<2=f$r++[(i+1,j*2):w,(i*2,j+1):w]
g x=f[[x]]

Try it online!
A simple BFS. Keeps track of the steps in a list of list of pairs.
g x=f[[x]]                -- start with a single list where the only
                          -- step is the starting pair
f (w@((i,j):_):r) =       -- let w be the first list of steps
                          --     (i,j) the last pair of the first list of steps
                                       ('last' as in last operated on. As we store
                                        the steps in reverse order it's the
                                        first element in the list)
                          --     r all other lists of steps
   i==j=w                 -- if i==j stop and return the first list
   1<2= f                 -- else make a recursive call
          r++             -- where the new input list is r followed by
                          -- the first list extended one time by
          [(i+1,j*2):w,         (i+1,j*2) and one time by
             (i*2,j+1):w]       (i*2,j+1)

Python 3, 90 74 72 bytes
-2 bytes thanks to Dennis.
def f(a,*x):j,k=a[0];return(j==k)*a or f(*x,[(2*j,k+1)]+a,[(j+1,2*k)]+a)

Try it online!
Takes input as a singleton list.

Ungolfed
def f(a,*x):              # function taking at least one argument
                          # a is the first argument, all other are stored in x
  j, k = a[0]             # get the newest values of the current path
  return (j==k)*a         # if j is equal to k return the current path
                  or      # else ...
   f(                     # continue ...
     *x,                  # with the remaining paths ...
     [(2*j,k+1)]+a        # and split the current path ...
     [(j+1,2*k)]+a        # in two new ones
    )

Pyth, 41 bytes
J]]QL,hhb*2ebWt{KehJ=J+tJm+hJ]d,yK_y_K)hJ

Try it here
Explanation
This is pretty straightforward breadth-first search.  Keep a queue of possible sequences (J), and until we get a matching pair, take the next sequence, stick on each of the possible moves, and put them at the end of the queue.
For the sake of brevity, we define a function y (using the lambda expression L) to perform one of the moves, and apply it both forward and in reverse.

MATL, 24 bytes
`vxG1r/q:"tt1rEk(+]td0=~

Running time is random, but it is finite with probability 1.
The code is very inefficient. Inputs requiring more than 4 or 5 steps have a large probability of timing out in the online interpreter.
Try it online!
Explanation
`         % Do...while
  vx      %   Concatenate stack and delete. This clears the stack from contents
          %   of previous iterations
  G       %   Push input
  1       %   Push 1
  r       %   Push random number uniformly distributed on (0,1)
  /       %   Divide
  q       %   Subtract 1. The result is a random number, t, that has nonzero
          %   probability of being arbitrarily large. Specifically, t is in
          %   the interval (0,1) with probability 1/2; in (1,2) with probability
          %   1/6; ... in (k,k+1) with probability 1/((k+1)*(k+2).
  :       %   Range [1 2 ... floor(t)]
  "       %   For each (that is: do thw following floor(t) times)
    tt    %     Duplicate twice
    1     %     Push 1
    rEk   %     Random number in (0,1), times 2, round down. This produces a
          %     number i that equals 0 or 1 with probability 1/2
    (     %     Write 1 at entry i. So if the top of the stack is [a b], this
          %     transforms it into either [1 b] or [a 1]
    +     %     Add, element-wise. This gives either [a+1 2*b] or [2*a b+1]
  ]       %   End for each
  td      %   Duplicate, consecutive difference between the two entries
  0=~     %   Is it not zero? If so, the do...while loop continues with a new
          %   iteration. Normally the code 0=~ could be omitted, because a
          %   nonzero consecutive difference is truthy. But for large t the
          %   numbers a, b may have gone to infinity, and then the consecutive
          %   difference gives NaN
          % End do...while (implicit). Display (implicit)

Retina, 72 bytes
\d+
*
/\b(_+),\1\b/^+%`(_+),(_+)$
$&;_$&$2¶$=;$1$&_
G`\b(_+),\1\b
_+
$.&

Try it online! Only two test cases due to the limitations of unary arithmetic. Explanation:
\d+
*

Convert to unary.
/\b(_+),\1\b/^+

While the input does not contain a pair of identical numbers...
%`(_+),(_+)%

...match the last pair on each line...
$&;_$&$2¶$=;$1$&_

...and turn the line into two lines, one suffixed with the first number incremented and second doubled, the other suffixed with the first number doubled and second incremented.
G`\b(_+),\1\b

Keep the line with the matching pair.
_+
$.&

Convert back to decimal. 89 88-byte unsigned decimal arithmetic version (works with 0 as well):
/\b(\d+),\1\b/^+%`(\d+),(\d+)$
$&;$.(_$1*),$.(2*$2*)¶$=;$.(2*$1*),$.(_$2*
G`\b(\d+),\1\b

Try it online!

Jelly, 20 bytes
ḃ2d2;@+*¥\
0çṪEɗ1#Ḣç

Try it online!

(note: this takes a singleton list of a 2-element list, for example [[2,5]])

05AB1E, 25 22 20 bytes
Takes a doubly nested list as input and outputs a jagged list with each step at one nest-depth.
[ć¤Ë#¤xs>R‚ø`R‚s¸sâ«

Try it online!
Explanation
[                      # start a loop
 ć                     # extract the first element of the current list (current path)
  ¤Ë#                  # break if all elements in the head are equal
     ¤xs>              # duplicate one copy of the head and increment another
         R             # reverse the incremented copy
          ‚ø           # zip them together
            `R‚        # reverse the tail of the zipped list
               s¸sâ    # cartesian product with the rest of the current path
                   «   # append to the list of all current paths

Stax, 29 26 bytes
ä⌠|Tô&cm♂NV↓↔╗╣¢♠╜╒█¡Φ≈ñY@

Run and debug it
It's a breadth first search.  It seems reasonably fast.
It takes a doubly-array-wrapped pair of integers.  The output is a space separated list of values.  Every two values represents one pair in the path to the solution.

Haskell, 95 bytes
g s|a:_<-[a|a@((x,y):_)<-s,x==y]=a
g s=g$do a@((x,y):_)<-s;[(x*2,y+1):a,(x+1,y*2):a]
h t=g[[t]]

Try it online! Outputs in reverse order, e.g. h(2,5) yields [(12,12),(6,11),(3,10),(2,5)].

Red, 142 bytes
Takes the input as a doubly nested block of the pair of integers in Red's format (2, 5) -> 2x5
Returns the result as a list ot Red pairs, for example 2x5 3x10 6x11 12x12. Includes the initial pair.
func[c][a: copy[]foreach d c[l: last d if l/1 = l/2[return d]do replace/all{%+ 1x0 * 1x2
%* 2x1 + 0x1}"%""append/only a append copy d l "]f a]

Try it online!
Strict input:
The input is two numbers, for example 2 5
Red, 214 bytes
func[a b][g: func[c][a: copy[]foreach d c[l: last d if l/1 = l/2[return d]append/only a append copy d l + 1x0 * 1x2
append/only a append copy d l * 2x1 + 0x1]g a]c: copy[]insert/only c reduce[do rejoin[a 'x b]]g c]

Try it online!
Explanation:
f: func[a b][
g: func[c][                                   ; recursive helper function
  a: copy[]                                   ; an empty block
  foreach d c[                                ; for each block of the input
    l: last d                                 ; take the last pair
    if l/1 = l/2[return d]                    ; if the numbers are equal, return the block
    append/only a append copy d l + 1x0 * 1x2 ; in place of each block append two blocks
    append/only a append copy d l * 2x1 + 0x1 ; (j+1, k*2) and (j*2, k+1)
  ]                                           ; using Red's arithmetic on pairs
  g a                                         ; calls the function anew
]
c: copy[]insert/only c reduce[do rejoin[a 'x b]]; prepares a nested block from the input
g c                                           ; calls the recursive function
]

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


text:
The Add-Multiply-Add Sequence
(Related)
Given an integer n > 1,
1) Construct the range of numbers n, n-1, n-2, ... 3, 2, 1 and calculate the sum
2) Take the individual digits of that number and calculate the product
3) Take the individual digits of that number and calculate the sum
4) Repeat steps 2 and 3 until you reach a single digit. That digit is the result.
The first twenty terms of the sequence are below:
3, 6, 0, 5, 2, 7, 9, 2, 7, 9, 1, 9, 0, 0, 9, 6, 7, 0, 0, 6

Note: This sequence is NOT in OEIS.
I/O and Rules

Numbers will get very large quickly, so the solution must be able to handle input numbers up to 100,000 without failure (it's fine if your code can handle past that).
The input and output can be given by any convenient method.
Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples
n     output
1234   9
3005   3
5007   5
9854   8
75849  8
100000 0

+1 for a sequence challenge that's not in the OEIS

Whenever n ≤ 100000, only two iterations of steps 2 and 3 are sufficient to get the result. Can we take advantage of that or should the algorithm we choose work for larger values of n?

@Dennis The algorithm should work for any value of n. The solution posted only has to work up to n = 100000.

@AdmBorkBork That seems like a subjective winning criteria. If you say that the algorithm only has to work up to N=100k and will only be tested up to 100k, how can you say whether or not it's "correct" for larger values?

@AdmBorkBork Maybe just remove 100k altogether, submissions don't have to work for all possible inputs practically, only theoretically.

Numbers will get very large quickly no it doesn't

@l4m2 Not the output. But 100000 + 99999 + ... + 1 = 5000050000 is a 33-bit number, which your language of choice may or may not have trouble representing.

Should we add this to OEIS? :)

@Dennis "quickly" usually mean exponential increasing don't it?

Python 2, 77 72 71 62 60 bytes
lambda n:reduce(lambda x,c:eval(c.join(`x`)),'*+'*n,-n*~n/2)

Thanks to @xnor for golfing off 2 bytes!
Try it online!

I just switched to a for loop, but I'll have to remember that trick for the future.

Where´s the repeat until you reach a single digit?

@Titus I simply perform n iterations of steps 2 and 3, which is always enough. In fact, since n ≤ 100000, three iterations would be sufficient.

Now that you mention it: Actually, the smallest input that would require three iterations is 236172; and that´s the only one below 1 million.

You can reduce

@xnor Thanks! I think this is the first time I've reduced in a Python answer.

05AB1E, 7 bytes
LOΔSPSO

Try it online!
Exlpanation
L         # push range [1 ... input]
 O        # sum range
  Δ       # loop until top of stack stops changing
   SP     # product of digits
     SO   # sum of digits

Almost ASCII-only! :D

@AdmBorkBork: Yeah, not terribly common :P

Jelly, 8 bytes
RSDPDƲÐL

Try it online!
Full program (it returns a singleton array containing the result, but the brackets aren't visible in STDOUT).

This is the most "natural-looking" Jelly answer I've seen yet. There are only 2 non-ASCII characters

@Soaku https://codegolf.stackexchange.com/questions/69424/compute-the-multinomial-coefficient/69426#69426

Uh, can we please not have the discussion over here, thanks. :P TNB could be an alternative place to discuss this, if no noise is made. ;)

MATL, 15 13 bytes
In tribute to the Language of the month:
:`sV!UpV!Utnq

Try it online!
I don't think there's a simpler way to get the digits of a number than to convert the number to a string V, then transposing it !, and converting this vertical vector back to a numeric one U.
Saved 2 bytes thanks to the Creator1 himself! I forgot the implicit end, meaning I could remove ], and instead of comparing the number of elements with 1, I could simply decrement that value and use it as a boolean directly.
So, the explanation goes like this:
                 % Grab input n implicitly
:                % Range from 1 ... n inclusive
 `               % Do ... while
  s               % sum the vector
   V!U            % Convert the number to digits
      p           % Take the product of these digits
       V!U        % Convert the product into digits
          t       % Duplicate the result
           n      % Count the number of elements
            q     % Decrement the number of elements
                  % Loop until the number of elements is 1
                 % Implicit end

1... of MATL, Luis Mendo.

JavaScript (ES6), 60 bytes
f=(n,k=n*++n/2)=>k>9?f(!n,eval([...k+''].join('*+'[+!n]))):k

Try it online!
Commented
f = (                     // f = recursive function taking:
  n,                      //   n = original input
  k = n * ++n / 2         //   k = current value, initialized to sum(i=1..n)(i)
) =>                      //
  k > 9 ?                 // if k has more than 1 digit:
    f(                    //   recursive call to f() with:
      !n,                 //     a logical NOT applied to n
      eval(               //     the result of the expression built by:
        [...k + '']       //       turning k into a list of digits
        .join('*+'[+!n])  //       joining with '*' on even iterations or '+' on odd ones
      )                   //     end of eval()
    )                     //   end of recursive call
  :                       // else:
    k                     //   stop recursion and return the last value

Alternate version, 59 bytes (non-competing)
A non-recursive version that only works for n < 236172. (It covers the requested range but does not qualify as a valid generic algorithm.)
n=>[...'*+*+'].map(o=>n=eval([...n+''].join(o)),n*=++n/2)|n

Try it online!

your main version breaks when N >= 77534568790. It works when N=7753456879; not sure exactly where the breakpoint is. Of course, this doesn't matter because the requirment is only to handle up to N=100,000, so I'm not sure why I wrote this ....

@RossPresser As a rough estimate, I'd say it rather works up to Number.MAX_SAFE_INTEGER ** 0.5 ~= 94906265.

Haskell, 72 71 63 bytes
g=map(read.pure).show
f n=until(<10)(sum.g.product.g)$sum[1..n]

Thanks to @BMO for a byte and @nimi for 8 bytes!
Try it online!

Stax,  14   13  10 bytes
ñu┌↕a√äJ²┐

Run and debug it
Was pretty fun to make. I wonder if there is a more concise way to do the comparison at the end.
Explanation
|+wE:*E|+c9>                 # Full Program Unpacked
|+                           # Create range and sum it
   wE:*                      # Start loop, digitize number, product of digits
       E|+                   # Digitize number, sum digits
          c9>                # Duplicate, check length is = 1
                             # Otherwise loop back to the 'w' character

-1 bytes thanks to ovs
-3 bytes thanks to Scrooble

R, 152 130 109 bytes
function(w,x=w*(w+1)/2,y=prod(d(x)),z=sum(d(y)))"if"(z>9,f(,z),z)
d=function(x)x%/%10^(0:max(0,log10(x)))%%10

Try it online!
@Giuseppe found 21 42 bytes with various R things I'm not used to yet, along with a way to get the digits of a number without coercing to string and back, and with fewer bytes!
# Old
d=function(x)strtoi(el(strsplit(paste(x),"")))
# New
d=function(x)x%/%10^(0:max(0,log10(x)))%%10

options(scipen=9) is was required for the case of 9854 for the old function, because the first product stage ends up as 80000, which R prints as 8e+05.

Ah, I see. Scientific notation output. Good catch!

Finally got around the scipen: Try it online! note the max(0,log10(x)) is because if x=0, then log10(0)=-Inf which causes an error.

APL (Dyalog Unicode), 16 bytes
-4 thanks to @user
f←{⍎¨⍕×/⍎¨⍕+/⍵}⍣≡⍳

Try it online!

Try putting the sum inside. Not sure if it's safe, but it should probably work.

Husk, 7 bytes
ωöΣdΠdΣ

Try it online!

Pyth, 11 bytes
usj*FjGTTsS

Try it here!

usj*FjGTTsS – Full program. N = The input.
          S – Range. Yield [1, N] ⋂ ℤ.
         s  – Sum.
u           – While no two consecutive iterations yield the same result, do (var: G):
   *FjGT    – Digital product.
 sj     T   – Digital sum.

Gaia, 8 bytes
┅⟨Σ₸∨Π⟩°

Try it online!
The old explanation (before fixing a bug that is Gaia’s fault IMO :P):

┅⟨ΣΠ⟩° – Full program. N = The input.
┅      – Range. Push [1, N] ⋂ ℤ to the stack.
 ⟨  ⟩° – While no two consecutive iterations yield the same result, do:
  Σ    – Sum (or digital sum, when applied to an integer).
   Π   – Digital product.

Saved 1 byte thanks to Dennis.

┅⟨ΣΠ⟩° saves a byte.

This doesn’t work for values were the digital sum is 0, like 4

@JoKing Fixed, thanks for spotting that. Unfortunately, in Gaia, taking the digits of 0 results in [] for some reason :(

Japt, 16 14 13 bytes
_ì ×ìx}gN®õ x

Try it

Explanation
                  :Implicit input of integer U
         ®        :Map
        N         :The array of inputs (which just contains U)
          õ       :  Range [1,U]
            x     :  Reduce by addition
_     }g          :Take the last element of N, run it through the following function and push the result to N
                  : Repeat U times and then return the last element of N
 ì                :  Split to an array of digits
   ×              :  Reduce by multiplication
    ìx            :  Split to an array of digits and reduce by addition

Neat, I tried to solve this one myself but didn't find a good solution so it's interesting to see yours.

Thanks, @Nit. There's gotta be a shorter way, though.

@Nit, got it! Still convinced there has to be a shorter way, though.

Charcoal, 18 bytes
≔Σ…·¹ＮθＷ›θ⁹≔ΣΠθθＩθ

Try it online! Link is to verbose version of code. Explanation:
≔Σ…·¹Ｎθ

Sum the integers up to the input.
 Ｗ›θ⁹≔ΣΠθθ

While the result is greater than 9, take the sum of digits of the product of digits.
Ｉθ

Cast the result to string and implicitly print it.

Ruby, 57 bytes
->n{("*+"*n).chars.reduce(-~n*n/2){|x,y|eval x.digits*y}}

Try it online!

F#, 175 bytes
let d n=seq{for i in(string n).ToCharArray() do yield string i|>uint64}
let c n=
 let mutable r=Seq.sum{1UL..n}
 while r>9UL do r<-d r|>Seq.reduce(fun a x->x*a)|>d|>Seq.sum
 r

Try it online!
The only caveat to the function is that the input value must be of type uint64.
Ungolfed it's a little like this:
let d n=seq{for i in(string n).ToCharArray() do yield string i|>uint64}

let c n =
 let mutable r = Seq.sum {1UL..n}
 while r > 9UL do
  r<-d r
  |> Seq.reduce(fun a x->x*a)
  |> d
  |> Seq.sum
 r

The function d n converts the number n into its component digits. It first converts to a string, then gets each character in the string. Each character must then be converted back into a string, otherwise the characters will be converted to their ASCII values instead of their "real" values.
The c n function is the main function, with n as the initial value. In this function r is our running value. The while loop does the following:

Convert r into its component digits (d r).
Get the product of all those digits. This uses Seq.reduce which takes a function with the accumulated value (a) and the next value in the sequence (x) and in this case returns the product. The initial value is the first element in the sequence.
Convert this product value into its component digits (d).
Sum the digits from before, and assign this to r.

Befunge, 136 bytes
101p&::*+2/>:82+%01g*01p82+/:#v_$01gv
X      v_v# #:/+82p10+g10%+82: <p100<
v:g10$ >#<#^                 #<^
>82+/#v_.@
      >101p^

You can try it here.
While not all interpreters have a large enough cell size, it works with small numbers for pretty much anyone out there. For a larger number of n you might need a interpreter like BefunExec.

Gol><>, 35 33 bytes
1AY:P*2,TYMR*YR+:a(?Bt
:a(qlBaSD$

Try it online!
-2 bytes by Jo King.
Extensive use of functions and implicit infinite loops.
Example full program & How it works
1AGIE;GN
2AY:P*2,YlMR*YlR+:a(?B8R!
:a(?BaSD$

<main program>
1AG       Register row 1 as function G
   IE;    Take number input; halt on EOF
      GN  Call G and print the result as number
          Repeat indefinitely

<function G>
2AY            Register row 2 as function Y
   :P*2,       Sum of 1 to n
        Y      Call Y (break into digits)
         lMR*  Product
Y              Call Y
 lR+           Sum (an implicit zero is used)
    :a(?B      Return if the result is less than 10
         8R!   Skip initial 8 commands
               Repeat indefinitely

<function Y>
:a(?B      Return if the top is less than 10
     aSD   Divmod by 10; [... n] => [... n/10 n%10]
        $  Swap top two, so the "div" goes to the top

33 bytes

PHP 7, 89 bytes
for($a=$argn*-~+$argn/2;$a>9;)$a=array_sum(($s=str_split)(array_product($s($a))));echo$a;

Run as pipe with -r or try it online.

PHP always takes input as string, so I have to use + to cast to int for ~ to work as wanted.
Pre-increment would not work: no matter where I put it, it would effect both operands.
But: It doesn´t matter if the single digit takes place before or after the iteration (additional iterations wouldn´t change a thing); so I can use for() instead of do ... while().
PHP 7 or later is required for the inline assignment of the function name.
Older PHP requires one more byte: for($s=str_split,$a=...;$a>9;)$a=array_sum($s(...));
(Not assigning str_split to a variable at all would waste another byte.)

Tcl, 118 bytes
proc S n {set r [expr $n*($n+1)/2]
while \$r>9 {set r [expr [join [split [expr [join [split $r ""] *]] ""] +]]}
set r}

Try it online!

Failed outgolf, 119

PowerShell Core, 91 101 93 bytes
Function F($a){$o=$a*($a+1)/2;1,2|%{$o=[char[]]"$([char[]]"$o"-join'*'|iex)"-join'+'|iex};$o}

Try it online!
Ungolfed a little...
Function F ($a)
{
    $o=$a*($a+1)/2;
    1..2 | % {
        $o = [char[]]"$o"-join '*' | iex;
        $o = [char[]]"$o"-join '+' | iex;
    }
    $o | Write-Output
}

First steps were to split the integers into digits -- did this by splitting the integer into an array of stringscharacters.  Afterwards, insert the operand, and then evaluate the string as a command.  Then, it's a matter of doing the multiple-add cycle until the input is one digit.
iex is an alias for Invoke-Command which evaluates a string passed into the first param position.
Edit:  As requested by @AdmBorkBork, I have added a function header to the byte count.  Also, I did a little math and realized that an upper bound on the number of iterations is < log log 10^6 < log 6 < 2, so that saved another six bytes.
Edit x2:  @AdmBorkBork found a more terse way of converting the integer into a math expression, and then suggested piping it into iex.  This saved 8 bytes.  Thank you!

Nice to see another PowerSheller around! However, I think you need to include the function definition Function F($a){ } in your byte count. However, you should be able to save some using [char[]] instead of -split''-ne'', I think.

[char[]]1234=Ӓ, which is invalid; I might be able to make it work, but it might not obvious just now.  Thanks for the suggestion!

Sorry I wasn't clear -- [char[]]"$o" and a |iex rather than iex( ).

This tip shaved 8% of my code off.  Awesome.  Thanks!

Perl 6, 49 bytes
{($_*.succ/2,{[+] ([*] .comb).comb}...9>=*).tail}

Try it online!

You can use [*](.comb).comb instead of ([*] .comb).comb

Perl 5 -p, 61 bytes
$_*=$_/2+.5;$_=eval((eval s/./$&*/gr.1)=~s/./+$&/gr)while$_>9

Try it online!

Java 8, 129 bytes
n->{long r=1,i=n;for(;i>1;r+=i--);for(;r>9;r=(i+"").chars().map(p->p-48).sum(),i=1)for(int s:(r+"").getBytes())i*=s-48;return r;}

Try it online.
Explanation:
n->{            // Method with integer parameter and long return-type
  long r=1,     //  Result-long, starting at 1
       i=n;     //  Temp integer, starting at the input `n`
  for(;i>1;     //  Loop as long as `i` is not 1 yet
      r+=i--);  //   And increase `r` by `i`
  for(;r>9      //  Loop as long as `r` is not a single digit yet
      ;         //    After every iteration:
       r=(i+"").chars().map(p->p-48).sum(),
                //     Set `r` to the sum of digits of `i`
       i=1)     //     And reset `i` to 1
    for(int s:(r+"").getBytes())i*=s-48;
                //    Set `i` to the product of the digits of `r`
  return r;}    //  Return `r` as result

Julia 0.6, 56 bytes
f(n,k=(n+1)n÷2)=k>9?f(0,sum(digits(prod(digits(k))))):k

Try it online!
Pretty straightforward: calculate (n+1)n÷2 for sum from 1..n, check if it's a single digit number (>9), if it's not, try again with k set to the sum of the digits of the product of the digits of k, else return k.

J-uby, 38 bytes
This is me resisting forking J-uby to add a bunch of single-character aliases for useful functions.
:+|:sum|:!~&((d=:digits)|:/&:*|d|:sum)

Attempt This Online!
Explanation
:+ | :sum | :!~ & ((d = :digits) | :/ & :* | d | :sum)

:+ | :sum |                                             # Range 1..n, then sum, then
            :!~ & (                                  )  # Until a fixed point is reached...
                  ((d = :digits) |                      #   Get digits (while saving the function to d for later), then
                                   :/ & :* |            #   Reduce with product, then
                                             d | :sum   #   Get digits, then sum


text:
Mutually Attacking Queens
Let an 8x8 chessboard be represented by any two distinct values, with one value being an empty square and the other being a queen. In the following examples, I use 0s as the empty squares and 1s as queens. For example:

is given by
1 0 1 1 1 0 0 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 1 0 1
1 0 0 0 1 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 1

Consider the number of pairs of queens that are attacking each that are at least one square away (as a reminder, queens attack orthogonally and diagonally). In the above example, the following incredible ugly diagram shows all these pairs as arrows.

There are 43 pairs found above giving the following test case:
Input:
1 0 1 1 1 0 0 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 1 0 1
1 0 0 0 1 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 1
Output: 43

Challenge
Write a program that, given a board state represented by two distinct values, outputs the number of pairs of queens that attack each other with at least one square in between them.

You may input in whatever format is most convenient that uses two values to represent the empty squares and queens, e.g., a string of 64 "."s for empty squares and "Q"s for queens by rows from bottom to top, an 8x8 matrix of booleans, a list of list of integers 0 and 1 etc, as long as it is explained in your solution
Output is an integer
Standard I/O methods apply and standard loopholes forbidden
This is code golf so shortest answer in bytes wins

Test cases:
Using the 0 and 1 format, with 0 being empty squares and 1 being queens:
Input:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Output: 0

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 0

Input:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Output: 1

Input:
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0
0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0
Output: 10

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 4

Input:
1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 11

I should have asked before posting my 2nd version: are 254 for a queen and 0 for an empty square acceptable input values?

@Arnauld You may input in whatever format is most convenient that uses two values to represent the empty squares and queens. So that's fine for sure

Thanks. I asked because I think this rule might be a bit too permissive if taken literally. I could ask to pass a string containing most of the JS code for queens and just evaluate that in the program. (But it may be prevented by a default loophole. I'm not sure.)

@Arnauld standard loophole that forbids that

Python 2, 105 bytes
lambda b:sum(b[i+d::d][:(8,7-i%8,i%8)[d%8%5]].find('1')*int(c)>0for i,c in enumerate(b)for d in[1,7,8,9])

Try it online!
Explanation
We take the input as a string of 64 characters '0' or '1'. Using step slices, we cast four "lines of sight" from every queen we encounter. For example, when i = 10 and d = 7, marking the queen as ♥ and the tiles selected by b[i+d::d] as █:
1 0 1 1 1 0 0 0
1 0 ♥ 0 1 0 1 1
1 █ 1 0 1 1 0 1
█ 1 0 1 0 1 0 █
0 1 1 0 0 1 █ 1
1 0 0 0 1 █ 0 0
0 1 0 0 █ 1 1 1
0 1 1 █ 0 1 0 1

Clearly, we don't actually want vision to wrap around the board like this. So we compute how far away the edge of the board is in each direction, and view the tiles at b[i+d::d][:…].
For each tile-direction pair we count:
ray.find('1')*int(c)>0

This will fail whenever

c is not a queen; or
the queen this ray sees is too close (find returns 0); or
this ray sees no queen (find returns −1).

Each pair of queens is only checked once, since rays are always casted forward in reading order, from an "earlier" queen to a "later" one.

JavaScript (ES7), 86 bytes
Takes input as an array of 64 integers with 254 for a queen and 0 for an empty square.
a=>[s=0,6,7,8].map(d=>a.map(g=(n,p)=>(p%8-(p+=~d)%8)**2<n%4?a[p]?s+=n&1:g(n/2,p):0))|s

Try it online!
This version abuses arithmetic underflow to get a stop condition in the recursive part.

JavaScript (ES7), 89 bytes
Takes input as an array of 64 bits.
a=>[s=0,6,7,8].map(d=>a.map(g=(n,p,x)=>(p%8-(p+=~d)%8)**2>1|p<0?0:a[p]?s+=!x&n:g(n,p)))|s

Try it online!
How?
We recursively call a named callback function of map() to walk through the squares in a given direction. Although we don't really need the content of the third parameter of the callback (the array map() was called upon), we indirectly use it nonetheless to know whether it is the first iteration or not.

arr.map(function callback(currentValue[, index[, array]])

This is the x variable in the code.
a =>                        // given the input array a[]
  [ s = 0,                  // initialize the sum s to 0
    6, 7, 8 ].map(d =>      // for each direction d in [0, 6, 7, 8]:
    a.map(g = (n, p, x) =>  //   for each square n at position p in a[]:
      (                     //     we are out of the board if:
        p % 8 -             //       - abs(p % 8 - p' % 8) is greater than 1
        (p += ~d) % 8       //         where p' = p - (d + 1)
      ) ** 2 > 1 |          //         (squaring is shorter than using Math.abs)
      p < 0 ?               //       - or p' is less than 0
        0                   //       if so, stop recursion
      :                     //     else:
        a[p] ?              //       if there's a queen on the target square:
          s +=              //         increment s if:
            !x &            //           x is undefined (this is not the 1st iteration)
            n               //           and n = 1 (there's a queen on the source square)
        :                   //       else:
          g(n, p)           //         do a recursive call to g(), with x undefined
    )                       //   end of inner map()
  ) | s                     // end of outer map(); return s

Snails, 14 bytes
A
rdaa7\1\0+\1

Try it online!
Input is the 0/1 format, without spaces within lines.
Snails was created for a 2D pattern matching language design PPCG challenge. Most importantly, it by default outputs the number of matches found, which is perfect for this challenge.

A sets the "all paths" option, so that if a queen is in multiple pairs, each of those pairs would generate a match.
rdaa7 sets the match direction to S, SE, E, and NE. Setting to all directions (z) would cause double counting.
\1\0+\1 matches a 1, then one or more 0s, then another 1.

APL (Dyalog Classic), 41 39 32 bytes
(+/+⌿-⌈⌿)2<⌿0⍪⊢,⍉,8 31⍴⊢,≠⍨,⌽,≠⍨

Try it online!
≠⍨ is "not equal to itself" - an 8x8 all-zero matrix
⊢,≠⍨,⌽,≠⍨ - if the original matrix is ABC..., this expression returns:
A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0 0
I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0 0 0
Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0 0 0 0
Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0 0 0 0 0
G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0 0 0 0 0 0
O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0 0 0 0 0 0 0
W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0 0 0 0 0 0 0 0
E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E 0 0 0 0 0 0 0 0

8 31⍴ reshapes it from 8x32 to 8x31, reusing the elements in row-major order:
A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0
0 I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0
0 0 Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0
0 0 0 Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0
0 0 0 0 G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0
0 0 0 0 0 O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0
0 0 0 0 0 0 W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0
0 0 0 0 0 0 0 E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E

⊢,⍉, prepends the original matrix and its transpose (extra spaces for clarity):
A B C D E F G H  A I Q Y G O W E  A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0
I J K L M N O P  B J R Z H P X F  0 I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0
Q R S T U V W X  C K S A I Q Y G  0 0 Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0
Y Z A B C D E F  D L T B J R Z H  0 0 0 Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0
G H I J K L M N  E M U C K S A I  0 0 0 0 G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0
O P Q R S T U V  F N V D L T B J  0 0 0 0 0 O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0
W X Y Z A B C D  G O W E M U C K  0 0 0 0 0 0 W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0
E F G H I J K L  H P X F N V D L  0 0 0 0 0 0 0 E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E

2<⌿0⍪ adds 0s on top and compares using < every element against the element below it, so we get a 1 for the leading 1 in every vertical group of 1s, and we get 0s everywhere else
+⌿-⌈⌿ the sums by column minus the maxima by column - we compute the number of gaps between the 1-groups in every column, 0 if there are none
+/ sum

Jelly, 22 20 bytes
t0ŒgL:2
Z,U;ŒD$€ẎÇ€S

Try it online!

How does this work?

@lirtosiast I don't remember...

@lirtosiast The first link counts number of pairs in 1D, the second link takes the sum of the first link over all lines in the table.

K (ngn/k), 45 43 bytes
-2 bytes thanks to @coltim
{+/0|-1+/0|-':x,'+x,+8 31#,/+x,a,(|x),a:^x}

Try it online!

Can trim a pair of bytes with -1+/ instead of -1++/, and ^x in place of 0*x

Retina 0.8.2, 60 58 bytes
1
¶1$';___¶
_
$n$%`7$*_
(.)(?=.*;(_)*)(?<-2>.)*
$1
m`^10+1

Try it online! Takes input as 8 comma-separated 8-character binary strings, but the header converts the provided format for you. Explanation:
1
¶1$';___¶

Create all of the substrings of the board starting at a queen. Suffix a marker value to each substring. Edit: Saved 2 bytes by leaving some garbage strings behind; these are effectively ignored.
_
$n$%`7$*_

Split each marker up into an inclusive range, and add 7 to the non-zero elements.
(.)(?=.*;(_)*)(?<-2>.)*
$1

Delete every run of characters that equals the length of the marker. This is equivalent to finding each east, southwest, south or southeast ray from each queen.
m`^10+1

Count all the rays that pass through at least one empty square before meeting another queen.

JavaScript (ES6) + SnakeEx, 38 bytes
s=>snakeEx.run('m:<*>10+1',s).length/2

Takes input in the form '10111000\n10101011\n10101101\n01010100\n01100101\n10001000\n01000111\n01110101'. Turns out, SnakeEx can still be used outside of its original challenge!


text:
Noisy Iterated Prisoner's Dilemma
In this challenge, you will play the noisy iterated prisoner's dilemma.
The Prisoner's dilemma is a scenario in game theory where there are two players, each with two options: cooperate, or defect. Each player does better for themself if they defect than if they cooperate, but both players would prefer the outcome where both players cooperate to the one where both players defect.
The iterated prisoner's dilemma is the same game, except you play against the same opponent repeatedly, and you know what your opponent has played in the past. Your objective is always to accumulate the highest score for yourself, regardless of how your opponent does.
The noisy iterated prisoner's dilemma introduces some noise into the communication. Your knowledge of what your opponent has played in the past will have some noise introduced. You will also know what moves you made in the past. The noise rate is constant over a round against the same opponent, but different between different rounds.
Challenge
In this challenge, you will write a Python 3 program to play the noisy iterated prisoner's dilemma.
Your program will receive three inputs:

Your own moves, without random flips applied.
Your opponent's moves, with random flips applied.
A state variable, which starts as an empty list each round, and which you can modify if you want. You can ignore this if you don't want to use it.

Your program should output 'c' to cooperate or 'd' to defect.
For instance, here's a program that cooperates if the opponent has cooperated at least 60% of the time in the past, after random flips were applied, and for the first 10 flips:
def threshold(my_plays, their_flipped_plays, state):
    if len(their_flipped_plays) < 10:
        return 'c'
    opp_c_freq = their_flipped_plays.count('c')/len(their_flipped_plays)
    if opp_c_freq > 0.6:
        return 'c'
    else:
        return 'd'

If you don't know Python, write your submission in pseudocode, and someone (me or another member of the site) can make the corresponding Python program.
Gameplay
The tournament runner can be found here: noisy-game. Run noisy-game.py to run the tournament. I'll keep that repository updated with new submissions. Example programs can be found in basic.py.
A program's overall score is the total of its score over 100 plays of the game.
A game consists of round-robin matchups of each player against each player, including itself. A matchup consists of 100 rounds. A round consists of 300 moves, each of which involves outputting 'c' or 'd'.
Your submission will play a matchup against every submission, including your own. Each matchup will consist of 100 rounds. During each round, a flip probability will be chosen uniformly randomly from [0, 0.5].
Each round will consist of 300 moves. On each move, both programs will receive all previous plays they have attempted, and all previous plays the other program has made, after flips are applied, and a state variable, which is a mutable list which the program can modify if it wants to. The programs will output their moves.
Moves are scored as follows: If a program plays a 'c', the opposing program gets 2 points. If a program plays a 'd', that program gets 1 point.
Then, each move is flipped independently with probability equal to the flip probability, and stored for showing to the opponent.
After all of the rounds have been played, we sum the number of points each player got in each matchup. Then, we use the following scoring system to calculate each player's score for the game. This scoring is performed after all of the matchups are complete.
Scoring
We will use evolutionary scoring. Each program starts with equal weight. Then, weights are updated as follows, for 100 iterations, using the point totals from the game:
Each program's new weight is proportional to the product of its previous weight and its average point total, weighted by the weights of its opponents.
100 such updates are applied, and the final weights are each program's score for that run of the game.
The overall scores will be the sum over 100 runs of the game.
The players will be all valid answers to this challenge, plus six basic programs to get us started.
Caveats
Do not modify the inputs. Do not attempt to affect the execution of any other program, except via cooperating or defecting. Do not make a sacrificial submission that attempts to recognize another submission and benefit that opponent at its own expense. Standard loopholes are banned.
EDIT: Submissions may not exactly duplicate any of the basic programs or any earlier submission.
If you have any questions, feel free to ask.
Current results
nicht_genug: 40.6311
stealer: 37.1416
enough: 14.4443
wait_for_50: 6.947
threshold: 0.406784
buckets: 0.202875
change_of_heart: 0.0996783
exploit_threshold: 0.0670485
kickback: 0.0313357
tit_for_stat: 0.0141368
decaying_memory: 0.00907645
tit_for_whoops: 0.00211803
slider: 0.00167053
trickster: 0.000654875
sounder: 0.000427348
tit_for_tat: 9.12471e-05
stubborn_stumbler: 6.92879e-05
tit_for_time: 2.82541e-05
jedi2sith: 2.0768e-05
cooperate: 1.86291e-05
everyThree: 1.04843e-05
somewhat_naive: 4.46701e-06
just_noise: 1.41564e-06
growing_distrust: 5.32521e-08
goldfish: 4.28982e-09
vengeful: 2.74267e-09
defect: 3.71295e-10
alternate: 2.09372e-20
random_player: 6.74361e-21

Results with only answers to this question and basic programs that ignore the opponent's play:
nicht_genug: 39.3907
stealer: 33.7864
enough: 20.9032
wait_for_50: 5.60007
buckets: 0.174457
kickback: 0.0686975
change_of_heart: 0.027396
tit_for_stat: 0.024522
decaying_memory: 0.0193272
tit_for_whoops: 0.00284842
slider: 0.00153227
sounder: 0.000472289
trickster: 0.000297515
stubborn_stumbler: 3.76073e-05
cooperate: 3.46865e-05
tit_for_time: 2.42263e-05
everyThree: 2.06095e-05
jedi2sith: 1.62591e-05
somewhat_naive: 4.20785e-06
just_noise: 1.18372e-06
growing_distrust: 6.17619e-08
vengeful: 3.61213e-09
goldfish: 3.5746e-09
defect: 4.92581e-10
alternate: 6.96497e-20
random_player: 1.49879e-20

Winning
The competition will stay open indefinitely, as new submissions are posted. However, I will declare a winner (accept an answer) based on the results 1 month after this question was posted.

How does tit_for_whoops ignore the opponent's play?

@LyricLy I assume the category refers to the basic programs provided by Isaac which ignore their opponents.

tit_for_whoops is not a basic program by Isaac, nor does it ignore the opponent.

@LyricLy Sorry, that category is for any answers to this question, plus the opponent ignoring basic programs

I've added a state variable. Submissions should be updated accordingly.

Do not make a sacrificial submission that attempts to recognize another submission and benefit that opponent at its own expense. is already a standard loophole. ;)

Do I understand right that you can use the state variable to record all your moves as you submit them, and therefore know both your true moves and flipped moves, and estimate the flip probability?

@xnor You always get told your true moves. It's only the opponents moves that may get flipped.

@Mnemonic Man, I read "Your own moves, without random flips applied" as "with random flips" like 3 times. Let me italicize that.

@isaacg I tried copying exploit_threshold() several times as exploit_threshold1(), etc and added them to the players list. Why do I get vastly different results for identical strategies?

@isaacg I updated my strategy (stubborn_stumbler) again, can the original code I submitted be replaced?

The different results might be from having more submissions that use random().

@ngn I can't seem to reproduce your results currently. How many copies of exploit_threshold did you make, and what were the results exactly? Note that differing results that are all under 1 are mostly result of random noise

@EriktheOutgolfer I think the standard loophole you linked is mostly talking about joke sacrificial submissions, whereas I'm talking about sacrificial submissions that are trying to make another submission win.

I realised my code had a bug, where I was only running the game once. I fixed it to 100 times, but then it took too long. I'm running the game 10 times now, but keeping the scale the same

@isaacg for instance using 4 copies of stubborn_stumbler instead of 1, with the latest sources I get results 49, 14, 12, 1.8 (rounded)

@ngn I think this was happening because I wasn't running the enough games. I said I'd do 100, I was actually doing 1, which leads to a lot of luck taking over. Now I'm doing 10, which is better.

Genug ist nicht genug
(could also be called enough2 or stealback)
def nicht_genug(m,t,s):
    if not s:
        s.append("c")
        return "c"
    if s[0]=="t":
        return "d"
    if m[-42:].count("d")>10 or len(t)+t.count("d")>300:
        s[0]="t"
        return "d"
    if t[-1]=="d":
        if s[0]=="d":
            s[0]="c"
            return "d"
        else:
            s[0]="d"
            return "c"
    else:
        if t[-3:].count("d")==0:
            s[0]="c"
        return "c"

I learned that the original tit for two tats did wait for two consecutive tats like tit_for_whoops does, and indeed it seems we should forgive and forget (well, almost...) earlier single tats. And a lot of players defect in the last rounds. I still prefer to be nice when everything has been fine so far, but the bot's tolerance bar keeps getting lower.

Tit-For-Whoops
Inspired by a strategy from ncase.me/trust
def tit_for_whoops(m, t, s):
    if len(t) < 2:
        return 'c'
    else:
        return 'd' if all([x == 'd' for x in t[-2:]]) else 'c'

Defects only if the other player has defected twice in a row, to prevent misunderstandings.

Thanks for your submission! Keep in mind that since the flip probability averages 1/4, there's going to be a double-flip once every 16 moves or so.

I added a state variable, which you can ignore if you don't want to use it.

Strategy Stealer
Inspired by enough, change_of_heart, and tit-for-whoops.
Should be a little more forgiving. I tried to tweak the numbers for best results but they didn't want to change much.
def stealer(mine, theirs, state):
    if len(mine) == 0:
        state.append('c')
        return 'c'
    elif len(mine) > 250:
        return "d"
    elif state[0] == 't':
        return 'd'
    elif mine[-40:].count('d') > 10:
        state[0] = 't'
        return 'd'
    elif theirs[-1] == 'd':
        if state[0] == 'd':
            state[0] = 'c'
            return 'd'
        else:
            state[0] = 'd'
            return 'c'
    elif all([x == 'c' for x in theirs[-3:]]):
        state[0] = 'c'
        return 'c'
    else:
        return 'c'

welcome to PPCG!

Congratulations on taking the lead!

Change of Heart
def change_of_heart(m, t, s):
    return 'c' if len(t) < 180 else 'd'

Has a change of heart partway through. Does surprisingly well.

Congratulations on taking the lead/second place. I'm impressed and surprised that an opponent ignoring strategy does so well.

Tit-For-Time
def tit_for_time(mine, theirs, state):
    theirs = theirs[-30:]
    no_rounds = len(theirs)
    return "c" if no_rounds < 5 or random.random() > theirs.count("d") / no_rounds else "d"

If you've been spending most of the time hurting me, I'll just hurt you back. Probably.

Nice submission! You're currently in 1st place without the opponent-aware basic programs.

Growing Distrust
import random

def growing_distrust(mine, theirs, state):
    # Start with trust.
    if len(mine) == 0:
        state.append(dict(betrayals=0, trust=True))
        return 'c'

    state_info = state[0]

    # If we're trusting and we get betrayed, trust less.
    if state_info['trust'] and theirs[-1] == 'd':
        state_info['trust'] = False
        state_info['betrayals'] += 1

    # Forgive, but don't forget.
    if random.random() < 0.5 ** state_info['betrayals']:
        state_info['trust'] = True

    return 'c' if state_info['trust'] else 'd'

The more the opponent betrays me, the less I can trust it was just noise.

Yeah, the no state thing is unfortunate, but I wanted the submissions to be uniform, so this is the best I could think of. Do you have any idea for how to add a state?

Just have a state argument that by default is a list? Lists are mutable, so the state would be modifiable easily.

How so? I don't see how that could be.

@Mnemonic I think I know how to implement this. I'll give it a whirl.

I added a state variable, which is intially an empty list, and which you can modify.

Jedi2Sith
Starts off all nice and selfless, but with time the influence of the dark side grows steadily stronger, until the point of no return. There's no stopping this influence, but all the bad things it sees happening just contribute to the power of the dark side...
def jedi2sith(me, them, the_force):
  time=len(them)
  bad_things=them.count('d')
  dark_side=(time+bad_things)/300
  if dark_side>random.random():
    return 'd'
  else:
    return 'c'

Try it online!

Stubborn Stumbler
def stubborn_stumbler(m, t, s):
    if not t:
        s.append(dict(last_2=[], last_3=[]))
    if len(t) < 5:
        return 'c'
    else:
        # Records history to state depending if the last two and three
        # plays were equal
        s = s[0]
        if t[-2:].count(t[-1]) == 2:
            s['last_2'].append(t[-1])
        if t[-3:].count(t[-1]) == 3:
            s['last_3'].append(t[-1])
    c_freq = t.count('c')/len(t)
    # Checks if you've consistently defected against me
    opp_def_3 = s['last_3'].count('d') > s['last_3'].count('c')
    opp_def_2 = s['last_2'].count('d') > s['last_2'].count('c')
    # dist func from 0 to 1
    dist = lambda x: 1/(1+math.exp(-5*(x-0.5)))
    # You've wronged me too much
    if opp_def_3 and opp_def_2:
        return 'd'
    # Otherwise, if you're consistently co-operating, co-operate more
    # the less naive you are
    else:
        return 'c' if random.random() > dist(c_freq) - 0.5 else 'd'

Based off of your exploit threshold strategy with only consistent plays kept track for switching between defect and mostly co-operate
UPDATE: Keeps track of both two consecutive and three consecutive plays, punishing only under harsher conditions and adding a random choice when not sure
UPDATE 2: Removed condition and added distribution function

Contratulations on writing the first program to take the lead!

Slider
def slider(m, t, s):
    z = [[2, 1], [0, 1], [2, 3], [2, 1]]
    x = 0
    for y in t:
      x = z[x][y == 'c']
    return 'c' if x < 2 else 'd'

Starts off with 'c', and gradually slides towards or away from 'd'.

I did a functionally equivalent rewrite of this to use the state variable, because it was running pretty slowly. You don't need to change anything, however.

Noise Bot
def just_noise(m,t,s):
    return 'c' if random.random() > .2 else 'd'

I'm definitely cooperate bot. That's just noise.

Enough is Enough
def enough(m,t,s):
    if not s:
        s.append("c")
        return "c"
    if s[0]=="t":
        return "d"
    if m[-42:].count("d")>10:
        s[0]="t"
        return "d"
    if t[-1]=="d":
        if s[0]=="d":
            s[0]="c"
            return "d"
        else:
            s[0]="d"
            return "c"
    else:
        return "c"

Starts as tit for two tats where the two tats don't have to be consecutive (unlike tit_for_whoops). If it has to play d too often it goes d-total.

Congratuations on taking the lead!

trickster (reinstated again)
Only the last 10 plays are accounted for, but divided into two blocks of five, which are averaged with each classified as good or bad.
If the opponent plays on average "nice", the trickster plays less and less nice. If the results are ambiguous the trickster plays nice to lure the opponent into safety.
  If the opponent appears to be playing "bad" the trickster retaliates.
The idea is to gather points now and then from naïve players, while catching deceitful ones early.
import random
def trickster(player,opponent,state):
    pBad = 0.75
    pNice = 0.8
    pReallyBad =0.1
    decay = 0.98
    r = random.random()

    if len(player)<20: #start off nice
        return 'c'
    else: #now the trickery begins
        last5 = opponent[-5:].count('c')/5.0 > 0.5
        last5old = opponent[-10:-5].count('c')/5.0  > 0.5
        if last5 and last5old: #she is naive, punish her
            pBad = pBad*decay #Increase punishment
            if r<pBad:
                return 'c'
            else:
                return 'd'
        elif last5 ^ last5old: #she is changing her mind, be nice!
            if r<pNice:
                return 'c'
            else:
                return 'd'
        else: #she's ratting you out, retaliate
            pReallyBad = pReallyBad*decay #Retaliate harder
            if r<pReallyBad:
                return 'c'
            else:
                return 'd'

Disclaimer: I have never posted here before, if I am doing something wrong >please tell me and I'll correct.

Welcome to the site! Unfortunately, your code doesn't work currently. You have an elif after an else. Could you fix it? Thanks

I'm guessing everything from the elif onward should be indented once more?

Correct, I'll indent.

@isaacg
I have updated my answer with a new code. I do not have reputation enough to tell it to you in the question-comments.
I am not certain that I am using the state variable correctly, I assume it is an empty list which I can append whatever I want to, correct?

That won't work. After each turn, it is decided whether the current move is flipped or not (independently for the two players). That decission is then fixed. You will always see the same first move which may be flipped or not, but it won't change.

Your use of state is fine. However, you are unconditionally accessing opponent[1], which will cause an error on the first move. Also, Christian Sievers is right: old items in opponent never change, they are either originally given flipped, or originally given unchanged, and they stay that way.

Ah, I understood it as it was being flipped every turn. Then this strategy is not as clever as I thought. Back to the drawing table.

Goldfish Bot
def goldfish(m,t,s):
    return 'd' if 'd' in t[-3:] else 'c'

A goldfish never forgives, but it quickly forgets.

Decaying Memory
def decaying_memory(me, them, state):
    m = 0.95
    lt = len(them)

    if not lt:
        state.append(0.0)
        return 'c'

    # If it's the last round, there is no reason not to defect
    if lt >= 299: return 'd'

    state[0] = state[0] * m + (1.0 if them[-1] == 'c' else -1.0)

    # Use a gaussian distribution to reduce variance when opponent is more consistent
    return 'c' if lt < 5 or random.gauss(0, 0.4) < state[0] / ((1-m**lt)/(1-m)) else 'd'

Weighs recent history more. Slowly forgets the past.

Kickback
def kickback(m, t, s):
  if len(m) < 10:
    return "c"
  td = t.count("d")
  md = m.count("d")
  f = td/(len(t)+1)
  if f < 0.3:
    return "d" if td > md and random.random() < 0.1 else "c"
  return "c" if random.random() > f+2*f*f else "d"

Some vague ideas...

Congratulations on taking the lead in the version where adaptive basic spells are removed.

Thanks. I think it's amazing how different the two results are!

Doesn't Really Get The Whole "Noise" Thing
def vengeful(m,t,s):
    return 'd' if 'd' in t else 'c'

Never forgives a traitor.

sounder:
edit: added retaliation in probably low noise scenarios
basically, if all 4 first moves are cooperate, that means we should expect less noise than usual. defect a little bit every so often to make up for the less points we would get from never defecting, and have it be able to be blamed on noise. we also retaliate if they defect against us
if our opponent does a lot of defecting in those turns (2 or more) we just defect back at them. if it was just noise, the noise would affect our moves anyway.
otherwise, if only 1 move was defect, we just do simple tit for tat the rest of the game.
def sounder(my, their, state):
    if len(my)<4:
        if their.count("d")>1:
            return "d"
        return "c"
    elif len(my) == 4:
        if all(i == "c" for i in their):
            state.append(0)
            return "d"
        elif their.count("c") == 3:
            state.append(1)
            return "c"
        else:
            state.append(2)
    if state[0] == 2:
        return "d"
    if state[0] == 0:
        if not "d" in my[-4:]:
            return "d"
        return their[-1]
    else:
        return their[-1]

Alternate
def alternate(m, t, s):
    if(len(m)==0):
        return 'c' if random.random()>.5 else 'd'
    elif(len(m)>290):
        return 'd'
    else:
        return 'd' if m[-1]=='c' else 'c'

Picks randomly in the first round, then alternates. Always defects in the last 10 rounds.

Wait for 50
def wait_for_50(m, t, s):
  return 'c' if t.count('d') < 50 else 'd'

After 50 defects, let 'em have it!

I fixed your python while preserving your intent.

Congratulations on moving into 3rd place.

Every Three
def everyThree(me,him,s):
    if len(me) % 3 == 2:
        return "d"
    if len(me) > 250:
        return "d"
    if him[-5:].count("d")>3:
        return "d"
    else:
        return "c"

Defects every three turns regardless. Also defects the last 50 turns. Also defects if his opponent defected 4 out of 5 of the last rounds.

Buckets
def buckets(m, t, s):
    if len(m) <= 5:
        return 'c'
    if len(m) >= 250:
        return 'd'
    d_pct = t[-20:].count('d')/len(t[-20:])
    if random.random() > (2 * d_pct - 0.5):
        return 'c'
    else:
        return 'd'

Plays nice to begin. Looks at their last 20, if < 25% d, returns c, > 75% d, returns d, and in between chooses randomly along a linear probability function. Last 50, defects. Had this at last 10 but saw lots of last 50 defects.
First time here so let me know if something needs to be fixed (or how I can test this).

If you want to test things locally, you can clone the repository, and run noisy-game.py. It takes a while, so you might want to remove some of the opponents in players for quick iterations.

Thanks Isaac - I'll have to play with it and do some tinkering.

Somehwat naive
def somewhat_naive(m, t, s):
    p_flip = 0.25
    n = 10
    if len(t) < n:
        return 'c' if random.random() > p_flip else 'd'
    d_freq = t[-n:].count('d')/n
    return 'c' if d_freq < p_flip else 'd'

I'll just assume that if you've defected less than the flip probability (roughly) in the last n turns, it was noise and not that you're mean!
Haven't figures out the best n, might look further into that.

Tit-for-Tat (pseudocode)
I'm surprised no one has put a basic tit-for-tat
Also, is the challenge considered over because not a lot of people have posted, and is it against the stack exchanges rules to post on an old thread?
    def tit_for_tat (my-moves, op-moves) {
      if (op-moves[last] == 'D')
        return D
      else
        return C
    }

Welcome to Code Golf! No worries about the late post, that's allowed. If it's an old challenge it's just likely that nobody will bother rerunning the controller :p

Ok. I'll make an actual account rather than posting as a guest when I have access to my android devices. Unfortunately, I'm not great at coding yet, so I won't be able to do much, but I am moderately good at making pseudocode.

Hi 4D4850. Thanks for the submission. However, the reason that no one submitted this is that it's one of the basic programs that I seeded the competition with in basic.py.

Tit-For-Stat
Defects if the opponent has defected more than half the time.
def tit_for_stat(m, t, s):
  if t.count('d') * 2 > len(m):
    return 'd'
  else:
    return 'c'