text:
Bijection: tree-like lists - natural numbers
We define a tree-like list, or trist for short, as the empty list or a list containing only previously constructed trists.
The natural numbers can either include 0 or not, according to your preference.
The task is to create a pair of functions or complete programs f and g (they don't have to be named like this or even named at all) that implement a bijection between trists and the natural numbers.  In other words:

f must be able to turn any trist into a natural number
g must be able to turn any natural number into a trist
f(g(n)) must equal n for any natural number n
g(f(l)) must be equivalent to l for any trist l

You can assume that all arguments and results fit in the usual numeric type for your language.
Alternatively, instead of the numeric type you could represent a natural number as a list of binary digits, either consistently little- or consistently big-endian.
The shortest solution per language wins. If your functions are recursive, you must name them. If your language requires a statement separator or a newline between the two functions/programs, you don't have to count it.
This is a sample algorithm in Python3 (you are free to implement the bijection in any way you like):
def f(x):
    r = 0
    for y in x:
        r = (2 * r + 1) * 2**f(y)
    return r

def g(n):
    r = []
    while n:
        m = 0
        while n % 2 == 0:
            n //= 2
            m += 1
        n //= 2
        r = [g(m)] + r
    return r

tests = [
    [],
    [[]],
    [[],[]],
    [[[]],[],[[[]],[]]],
    [[[[[]]]]],
]
for l in tests: print(g(f(l)) == l)

for n in range(20): print(f(g(n)) == n)

It uses the following representation:
\$
\begin{array}{|l}
f([~])=0\\
f([a_0,a_1,\ldots,a_{n-1}])=\overline{
1\underbrace{0\ldots0}_{f(a_0)\\\text{zeroes}}~
1\underbrace{0\ldots0}_{f(a_1)\\\text{zeroes}}~
\ldots~
1\underbrace{0\ldots0}_{f(a_{n-1})\\\text{zeroes}}}
{}_{(2)}
\end{array}
\$
Challenge inspired by @LeakyNun's question in chat.

Related

The similarity to Decode the Void is striking. Duplicate indeed, and I suck at searching PPCG.

PPCG sucks at being searched.

Python 2, 118 114 109 105 103 97 94 bytes
f=lambda x:x>[]and f(x[:-1])*2+1<<f(x[-1])
g=lambda n:[g(len(w))for w in bin(n).split('1')[1:]]

Try it online!
Same encoding as the example...

@Lynn, it seems i can remove n and and it still works

@TFeld I'm afraid this meta implies that f= and g= should be counted. Sorry for the confusion. You can still omit the newline, as I intended the byte count to be the sum of two separate functions/programs.

@ngn, No problem, I've counted them in my counts already (and omitted the newline)


text:
Beware of the matrix tornado!
The matrix tornado is just like any other tornado: it consists of things rotating around a center. In this case, elements of the matrix instead of air.
Here is an example of a matrix tornado:

First we start by sectioning the matrix into square rings, each section consists of elements that are farther away from the border by the same distance. These sections will be rotated clockwise around the center. In real tornadoes, the severity increases towards the center, and so does the rotation step in a matrix tornado: the outermost section (the red one) is rotated by 1 step, the next (the yellow) one is rotated by 2, and so on. A rotation step is a 90° rotation around the center.
Task:
Your task, should you accept it, is to write a function or program that takes as input a square matrix, apply the tornado effect to it and then output the resulting matrix.
Input:
The input should be a square matrix of order n where n >= 1. No assumption is to be made about the elements of the matrix, they could be anything.
Output:
A square matrix of the same order which would be the result of applying the tronado effect to the input matrix.
Examples:
A matrix of order n = 1:
[['Hello']]               ===>    [['Hello']]

A matrix of order n = 2:
[[1 , 2],                 ===>    [[5 , 1],
 [5 , 0]]                          [0 , 2]]

A matrix of order n = 5:
[[A , B , C , D , E],             [[+ , 6 , 1 , F , A],
 [F , G , H , I , J],              [- , 9 , 8 , 7 , B],
 [1 , 2 , 3 , 4 , 5],     ===>     [/ , 4 , 3 , 2 , C],
 [6 , 7 , 8 , 9 , 0],              [* , I , H , G , D],
 [+ , - , / , * , %]]              [% , 0 , 5 , J , E]]

I think that you want to clarify that the rotations are 90° rotations.

Also, have you taken this challenge from somewhere else? If so, you must provide attribution.

@EriktheOutgolfer 1) I've clarified that. 2) This challenge is mine.

90 degrees clockwise or anti-clockwise?

@Giuseppe Depends on which hemisphere you're in ;)

First I'd like to say I think this is a good challenge: nice work! But I'd also like to plug this point because I think your choice to say that it could be any type of data leaves your challenge in an awkward spot. Similarly with your statement about the input being a list of lists, you have restricted the languages that can solve this problem without doing overhead work somewhat. I think the challenge is better if these requirements are relaxed. I hope you continue to post nice challenges like this! :)

@FryAmTheEggman Thank you for your input! I've removed that restriction.

Python 3, 100 97 96 bytes
-3 bytes thanks to Graipher by changing rot90(a,axes=(1,0)) to rot90(a,1,(1,0))
-1 byte thanks to Kevin Cruijssen by removing a space
import numpy
def f(a):
 if len(a):a=numpy.rot90(a,1,(1,0));a[1:-1,1:-1]=f(a[1:-1,1:-1]);return a

Try it online!

Classic Python, just dropping a[1:-1,1:-1]=f(a[1:-1,1:-1]) like it's the most normal thing in the world to directly get and set the entire inside of a 2-dimensional array

@ETHproductions To be fair, part of that is syntax inherited from numpy

numpy.rot90(a,1,(1,0)) is shorter by 3 bytes and should also work.

What's the point of the TIO-link without any test cases?.. :S Here it is with (dropped the space at if len(a):a=... for -1 byte).

71 bytes by using a[::-1].T instead of numpy.rot90(a): (so you don't need to import numpy) Try it online!

Charcoal, 44 bytes
≔ＥθＳθＷθ«≔Ｅθ⮌⭆θ§§θνλθθＭ¹⁻¹Ｌθ≔Ｅ✂θ¹±¹¦¹✂κ¹±¹¦¹θ

Try it online! Link is to verbose version of code. Only works on character squares because Charcoal's default I/O doesn't do normal arrays justice. Explanation:
≔ＥθＳθ

Read the character square.
Ｗθ«

Loop until it's empty.
≔Ｅθ⮌⭆θ§§θνλθ

Rotate it.
θＭ¹⁻¹Ｌθ

Print it, but then move the cursor to one square diagonally in from the original corner.
≔Ｅ✂θ¹±¹¦¹✂κ¹±¹¦¹θ

Trim the outside from the array.

Jelly, 27 bytes
J«þ`UṚ«Ɗ‘ịZU$LÐ¡ŒĖḢŒHEƊƇṁµG

Try it online!
I think this could be far shorter.
           Input: n×n matrix A.
J          Get [1..n].
 «þ`       Table of min(x, y).
    UṚ«Ɗ   min with its 180° rotation.

Now we have a matrix like: 1 1 1 1 1
                           1 2 2 2 1
                           1 2 3 2 1
                           1 2 2 2 1
                           1 1 1 1 1

‘ị          Increment all, and use as indices into...
     LÐ¡    List of [A, f(A), f(f(A)), …, f^n(A)]
  ZU$       where f = rotate 90°

Now we have a 4D array (a 2D array of 2D arrays).
We wish to extract the [i,j]th element from the [i,j]th array.

ŒĖ     Multidimensional enumerate

This gives us: [[[1,1,1,1],X],
                [[1,1,1,2],Y],
                ...,
                [[n,n,n,n],Z]]

ḢŒHEƊƇ     Keep elements whose Ḣead (the index) split into equal halves (ŒH)
           has the halves Equal to one another. i.e. indices of form [i,j,i,j]
           (Also, the head is POPPED from each pair, so now only [X] [Y] etc remain.)

ṁµG        Shape this like the input and format it in a grid.

You can probably just put µG in the footer and claim that your submission is 25.

Perl 6, 78 73 72 bytes
Thanks to nwellnhof for -5 bytes!
$!={my@a;{(@a=[RZ] rotor @_: sqrt @_)[1..*-2;1..@a-2].=$!}if @_;@a[*;*]}

Try it online!
Recursive code block that takes a flattened 2D array and returns a similarly flattened array.
Explanation:
$!={      # Assign code block to pre-declared variable $!
    my@a; # Create local array variable a
   {
     (@a=[RZ]  # Transpose:
             rotor @_: sqrt @_;  # The input array converted to a square matrix
     )[1..*-2;1..@a-2].=$!  # And recursively call the function on the inside of the array
   }if @_;    # But only do all this if the input matrix is not empty
   @a[*;*]  # Return the flattened array
}

You can use @a[*;*] instead of map |*,@a to flatten the array. (It would be nice if there was a way to work with unflattened arrays and multi-dimension subscripts, but I can't think of one.)

But @a[1..*-2;1..@a-2].=$! works.

Octave,  86 81 bytes
f(f=@(g)@(M,v=length(M))rot90({@(){M(z,z)=g(g)(M(z=2:v-1,z)),M}{2},M}{1+~v}(),3))

Try it online!
I'm aware that recursive anonymous functions are not the shortest method to do things in Octave, but they're the most fun method by far. This is the shortest anonymous function I could come up with, but I'd love to be outgolfed.
Explanation
The recursive function is defined according to this tips answer by ceilingcat. q=f(f=@(g)@(M) ... g(g)(M) ... is the basic structure of such an anonymous function, with g(g)(M) the recursive call. Since this would recurse indefinitely, we wrap the recursive call in a conditional cell array: {@()g(g)(M),M}{condition}(). The anonymous function with empty argument list delays evaluation to after the condition has been selected (although later, we see that we can use that argument list to define z). So far it has just been basic bookkeeping.
Now for the actual work. We want the function to return rot90(P,-1) with P a matrix on which g(g) has been recursively called on the central part of M. We start by setting z=2:end-1 which we can hide in the indexing of M. This way, M(z,z) selects the central part of the matrix that needs to be tornadoed further by a recursive call. The ,3 part ensures that the rotations are clockwise. If you live on the southern hemisphere, you may remove this bit for -2 bytes.
We then do M(z,z)=g(g)M(z,z). However, the result value of this operation is only the modified central part rather than the entire P matrix. Hence, we do {M(z,z)=g(g)M(z,z),M}{2} which is basically stolen from this tips answer by Stewie Griffin.
Finally, the condition is just that the recursion stops when the input is empty.

+1 for southern hemisphere

I haven't tried to wrap my head around recursion in anonymous functions yet, so I won't give it an attempt, but I'm curious to see if recursion is shorter than loops in this one.

@StewieGriffin I shall see what I can do :)

@StewieGriffin By the way, please feel challenged to post a loop-based version to this challenge in Octave. I really wonder if you can beat the recursive approach.

Python 2, 98 bytes
def f(a):
 if a:a=zip(*a[::-1]);b=zip(*a[1:-1]);b[-2:0:-1]=f(b[-2:0:-1]);a[1:-1]=zip(*b)
 return a

Try it online!

R, 87 bytes
function(m,n=nrow(m)){for(i in seq(l=n%/%2))m[j,j]=t(apply(m[j<-i:(n-i+1),j],2,rev));m}

Try it online!

credits to this StackOverFlow answer for the rotation code

84 bytes rotating in the opposite direction as the examples

Is it allowed? The image shows a clockwise arrow and the description below it states clockwise rotation...

I must have read the question ten times and never noticed it states clockwise (hence my comment). Alas.

Eheh, tell me about it... I'm the king of misreading posts :D

I think you can just use seq(n/2) rather than seq(l=n%/%2) : seq(3.5) returns 1 2 3 for example

Unfortunately the 1x1 matrix won't work (because seq(0.5) returns 1 instead of empty vector  )

MATL,  25 24 23 22
t"tX@Jyq-ht3$)3X!7Mt&(

Try it online!
Indexing in MATL is never easy, but with some golfing it actually beats the current best Jelly answer...
t                       % Take input implicitly, duplicate.
 "                      % Loop over the columns of the input*
   X@                   % Push iteration index, starting with 0. Indicates the start of the indexing range.
     Jyq-               % Push 1i-k+1 with k the iteration index. Indicates the end of the indexing range
         t              % Duplicate for 2-dimensional indexing.
  t       3$)           % Index into a copy of the matrix. In each loop, the indexing range gets smaller
             3X!        % Rotate by 270 degrees anti-clockwise
                7Mt&(   % Paste the result back into the original matrix.

*For an n x n matrix, this program does n iterations, while you really only need n/2 rotations. However, the indexing in MATL(AB) is sufficiently flexible that indexing impossible ranges is just a no-op. This way, there's no need to waste bytes on getting the number of iterations just right.

JavaScript (ES6), 99 bytes
f=(a,k=m=~-a.length/2)=>~k?f(a.map((r,y)=>r.map(v=>y-m>k|m-y>k|--x*x>k*k?v:a[m+x][y],x=m+1)),k-1):a

Try it online!
How?
Given a square matrix of width \$W\$, we define:
$$m=\frac{W-1}{2}\\
t_{x,y}=\max(|y-m|,|x-m|)$$
Example output of \$t_{x,y}\$ for a 5x5 matrix (\$W=5\$, \$m=2\$):
$$\begin{pmatrix}
2 & 2 & 2 & 2 & 2 \\
2 & 1 & 1 & 1 & 2 \\
2 & 1 & 0 & 1 & 2 \\
2 & 1 & 1 & 1 & 2 \\
2 & 2 & 2 & 2 & 2
\end{pmatrix}$$
We start with \$k=m\$ and perform a 90° clockwise rotation of all cells \$(x,y)\$ satisfying:
$$t_{x,y}\le k$$
while the other ones are left unchanged.
This is equivalent to say that a cell is not rotated if we have:
$$(y-m>k) \text{ OR } (m-y>k) \text{ OR } (X^2>k^2)\text{ with }X=m-x$$
which is the test used in the code:
a.map((r, y) =>
  r.map(v =>
    y - m > k | m - y > k | --x * x > k * k ?
      v
    :
      a[m + x][y],
    x = m + 1
  )
)

Then we decrement \$k\$ and start again, until \$k=-1\$ or \$k=-3/2\$ (depending on the parity of \$W\$). Either way, it triggers our halting condition:
~k === 0

K (ngn/k), 41 39 38 bytes
{s#(+,/'4(+|:)\x)@'4!1+i&|i:&/!s:2##x}

Try it online!
{ } function with argument x
#x length of x - the height of the matrix
2##x two copies - height and width (assumed to be the same)
s: assign to s for "shape"
!s all indices of a matrix with shape s, e.g. !5 5 is
(0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4
 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4)

This is a 2-row matrix (list of lists) and its columns correspond to the indices in a 5x5 matrix.
&/ minimum over the two rows:
0 0 0 0 0 0 1 1 1 1 0 1 2 2 2 0 1 2 3 3 0 1 2 3 4

i&|i: assign to i, reverse (|), and take minima (&) with i
0 0 0 0 0 0 1 1 1 0 0 1 2 1 0 0 1 1 1 0 0 0 0 0 0

These are the flattened ring numbers of a 5x5 matrix:
4!1+ add 1 and take remainders modulo 4
(+|:) is a function that rotates by reversing (| - we need the : to force it to be monadic) and then transposing (+ - since it's not the rightmost verb in the "train", we don't need a :)
4(+|:)\x apply it 4 times on x, preserving intermediate results
,/' flatten each
+ transpose
( )@' index each value on the left with each value on the right
s# reshape to s

I'll be glad to see the explanation of your code

@GalenIvanov Sure. I don't think I can golf this any further, so I might as well try to explain it.

Thanks! Your solutions make me want to start learning k (or even ngn/k :) )

@GalenIvanov Being familiar with J (and APL?), you are half-way there already. K is smaller and simpler, so I would highly recommend learning it and, of course, I'm happy to chat about it in the Orchard anytime. ngn/k is only a subset of the real thing but I do aim to make it fast and practical.

Yes, I think I'm going to try it.

Jelly, 24 bytes
ṙ⁹ṙ€
ḊṖ$⁺€ßḷ""ç1$ç-ZUµḊ¡

Try it online!

I think this could be far shorter.

– Lynn

I wondered about a solution like this! That ḷ"" looks magical to me ^^ care to add an explanation?

@Lynn The last thing I expected was to hear that ḷ"" is magical. It's just ḷ" with an extra "... oh, there's a slight possibility that ḷ" is also something I've "invented" that hasn't been used that much since it can oftentimes be replaced with a single atom (not in this case, as the input can contain 0 too).

Haskell, 108 bytes
e=[]:e
r=foldl(flip$zipWith(:))e
g!(h:t)=h:g(init t)++[last t]
f[x,y]=r[x,y]
f[x]=[x]
f x=r$(r.r.r.(f!).r)!x

Try it online!
I used Laikoni's transpose and modified it a little, to rotate an array 90°:
  e=[]:e;foldr(zipWith(:))e.reverse
≡ e=[]:e;foldl(flip$zipWith(:))e

Explanation
r rotates an array by 90°.
(!) is a higher-level function: “apply to center”. g![1,2,3,4,5] is [1] ++ g[2,3,4] ++ [5].
f is the tornado function: the base cases are size 1 and 2 (somehow 0 doesn't work).
The last line is where the magic happens: we apply r.r.r.(f!).r on the middle rows of x and then rotate the result. Let's call those middle rows M. We want to recurse on the middle columns of M, and to get at those, we can rotate M and then use (f!). Then we use r.r.r to rotate M back into its original orientation.

J, 37 bytes
<./~@g`(|:@|.^:(1<@+>./@g=.#\.<.#\))}

Try it online!
Independently solved, but this approach is very similar to Lynn's.
It is also one of the most perfect problems for J's little used "composite item" } (in gerund form) that I have come across.

Java 10, 198 192 181 174 173 bytes
m->{int d=m.length,b=-1,i,j;var r=new Object[d][d];for(;b<d/2;){for(i=b++;++i<d-b;)for(j=b;j<d-b;)r[j][d+~i]=m[i][j++];for(i=d;i-->0;)m[i]=r[i].clone();}return r;}

-25 bytes thanks to @ceilingcat
Try it online.
Explanation:
m->{                      // Method with Object-matrix as both parameter & return-type
  int d=m.length,         //  Dimensions of the matrix
      b=-1,               //  Boundaries-integer, starting at -1
      i,j;                //  Index-integers
  var r=new Object[d][d]; //  Result-matrix of size `d` by `d`
  for(;b<d/2;){           //  Loop `b` in the range (-1,`d/2`]:
    for(i=b++;++i<d-b;)   //   Inner loop `i` in the range [`b`,`d-b`):
      for(j=b;j<d-b;)     //    Inner loop `j` in the range [`b`,`d-b`):
        r[j][d+~i]=       //     Set the `j,d-i-1`'th result-cell to:
          m[i][j++];      //      The `i,j`'th cell-value of the input-matrix
    for(i=d;i-->0;)       //   Inner loop `i` in the range (`d`,0]:
      m[i]                //    Change the `i`'th row of the input-matrix
        =r[i].clone();}   //     to a copy of the `i`'th row of the result-matrix
  return r;}              //  Return the result-matrix

b is basically used to indicate which ring we're at. And it will then rotate this ring (including everything inside it) once clockwise during every iteration.
The replacement of the input-matrix is done because Java is pass-by-reference, so simply setting r=m would mean both matrices are modified when copying from cells, causing incorrect results. We therefore instead have to copy the values in every cell one row at a time, without copying their reference (by using .clone()).

Haskell, 274 bytes
w is the main function, which has  the type [[a]] -> [[a]] that you would expect.
I'm sure a more experienced Haskell golfer could improve on this.
w m|t m==1=m|0<1=let m'=p m in(\a b->[h a]++x(\(o,i)->[h o]++i++[f o])(zip(tail a)b)++[f a])m'(w(g m'))
p m|t m==1=m|0<1=z(:)(f m)(z(\l->(l++).(:[]))(r(x h(i m)):(p(g m))++[r(x f(i m))])(h m))
t[]=1
t[[_]]=1
t _=0
h=head
f=last
x=map
i=tail.init
g=x i.i
z=zipWith
r=reverse

You may want to check out our tips for golfing in Haskell, e.g. Using guards instead of conditionals will save some bytes.

MATLAB, 93 bytes
function m=t(m),for i=0:nnz(m),m(1+i:end-i,1+i:end-i)=(rot90(m(1+i:end-i,1+i:end-i),3));end;end

I'm sure this can be golfed some more somehow.
Explanation
function m=t(m),                                                                          end % Function definition
                for i=0:nnz(m),                                                       end;    % Loop from 0 to n^2 (too large a number but matlab indexing doesn't care)
                                                            m(1+i:end-i,1+i:end-i)            % Take the whole matrix to start, and then smaller matrices on each iteration
                                                      rot90(                      ,3)         % Rotate 90deg clockwise (anti-clockwise 3 times)
                               m(1+i:end-i,1+i:end-i)=                                        % Replace the old section of the matrix with the rotated one

C (gcc), 128 118 115 bytes
-15 bytes from @ceilingcat
j,i;f(a,b,w,s)int*a,*b;{for(j=s;j<w-s;j++)for(i=s;i<w-s;)b[~i++-~j*w]=a[i*w+j];wmemcpy(a,b,w*w);++s<w&&f(a,b,w,s);}

Try it online!

Haskell, 144 bytes
import Data.List
k=transpose
v=init.tail
t[[o]]=[[o]]
t m=k.reverse.(head m:).(++[last m]).
 k.((v.head$k m):).(++[v.last$k m]).
 k.t.map(v).v$m

Try it online!
v cuts out center (rows). map v cuts out center columns.
t recurses into the tornado. k exposes columns as rows.
(++[v.last$k m]) appends center of last column.
((v.head$k m):) prepends center of first column.
k flips rows out again.
(++[last m]) appends last row unprocessed.
(head m:) prepends last row unprocessed.
k.reverse rotates matrix.

JavaScript (Node.js), 93 bytes
f=(a,k=0,L=a.length+~k)=>L?f(a.map((b,x)=>b.map((c,y)=>x<k|y<k|x>L|y>L?c:a[k+L-y][x])),k+1):a

Try it online!
f=(
  a,             // Input
  k=0,           // Range Left
  L=a.length+~k  // Range Right
)=>L?            // More than enough
  f(
    a.map((b,x)=>b.map((c,y)=>x<k|y<k|x>L|y>L?c:
      a[k+L-y][x]// k+L=a.length-1
  )),k+1)
:a

Uiua SBCS, 25 bytes
∧(⍜(↘⊙↻|≡⇌⍉)×¯2.⊟.)⇡⌈÷2⧻.

Try it!
Fun problem.
∧(⍜(↘⊙↻|≡⇌⍉)×¯2.⊟.)⇡⌈÷2⧻.
                   ⇡⌈÷2⧻.  # create range for each ring
∧(                )        # fold over range and matrix, using matrix as accumulator
                ⊟.         # create pair indicating how much to rotate matrix on each axis
            ×¯2.           # and another pair indicating how much to drop from each axis
  ⍜(   |   )               # call the left part, then the right, then the inverse of left
        ≡⇌⍉                # rotate matrix clockwise
    ↘⊙↻                    # but only the interior

source: Stack Exchange

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

sort: votes


text:
Help me with my polyrhythms
I'm a musician, and I need more polyrhythms in my life!
A polyrhythm occurs in music (and in nature) when two events (claps, notes, fireflies flashing etc.) are occurring at two different regular intervals. The two kinds of event happen a different number of times in the same interval.
If I tap with my left hand twice, and with my right hand 3 times, in the same space of time, it looks a little bit like this:
  ------
R . . .
L .  .

The hyphens at the top denote the length of the polyrthmic pattern, which is the lowest common multiple or 2 and 3. This can be understood as the point at which the pattern repeats.
There's also a 'metarhythm', which is the pattern produced when either hand is tapping:
  ------
R . . .
L .  .
M . ...

This is a simple, and very common polyrhythm, with a ratio of 3:2.
Let's just say I don't want to do a simple polyrhythm that I can work out in my head, so I need something to work it out for me. I could do it long-form on paper, or...

Rules:

Write some code to generate and display a polyrhythm diagram, as described above.
Any old language, try for the fewest bytes.
Your code takes two arguments:

Number of taps with the Left hand (positive integer)
Number of taps with the right hand (positive integer)

It will work out the length, which is the lowest common multiple for the two arguments.
The top line will consist of two whitespace characters followed by hyphens displaying the length (length * '-')
The second and third lines will show the pattern for the right and left hands:

It will start with an R or L, do denote which hand it is, followed by a space.
The interval for that hand is the length divided by it's argument.
The taps will start at the third character, denoted by any character you choose. From then on it will display the same character 'interval' characters apart.
It will not be longer than the length line.

The fourth line is the metarhythm:

It will start with an upper case M, followed by a space.
From the third character onwards, it will show a character (any character you choose) in every position where there's a tap on either the right or the left hand.

Trailing whitespace is irrelevant.

Test cases:
r = 3, l = 2
  ------
R . . .
L .  .
M . ...

r = 4, l = 3
  ------------
R .  .  .  .
L .   .   .
M .  .. . ..

r = 4, l = 5
  --------------------
R .    .    .    .
L .   .   .   .   .
M .   ..  . . .  ..

r = 4, l = 7
  ----------------------------
R .      .      .      .
L .   .   .   .   .   .   .
M .   .  ..   . . .   ..  .

r = 4, l = 8
  --------
R . . . .
L ........
M ........

Happy golfing!

Your test cases include lots of trailing whitespace, can we omit them/add more?

Do we have to accept r and l as two separate values? Could we accept a two-element array instead, for example? How about the order of them, is that strictly r followed by l?

@Sok That's acceptable as an interpretation of 'two arguments'

Does it need to actually print the diagram out, or can it simply return it?

@iamnotmaynard returning is fine.

Isn't this basically the same as Illustrate the Lowest Common Multiple, but with an extra line?

@JoKing it’s similar, the combined line is a different challenge, tho.

JavaScript (ES6), 131 bytes
Outputs 0 as the tap character.
r=>l=>`  ${g=n=>n?s.replace(/./g,(_,x)=>[,a=x%(k/r),x%=k/l,a*x][n]&&' '):++k%l|k%r?'-'+g():`-
`,s=g(k=0)}R ${g(1)}L ${g(2)}M `+g(3)

Try it online!
How?
We use the same helper function \$g()\$ for two different purposes.
When \$g()\$ is called with no argument or an argument equal to \$0\$, it recursively builds the hyphen string of length \$k=\operatorname{lcm}(l,r)\$ with a trailing linefeed:
g = _ => ++k % l | k % r ? '-' + g() : `-\n`

This string is saved in \$s\$.
When \$g()\$ is called with \$1 \le n \le 3\$, it generates a tap string by replacing each hyphen at position \$x\$ in \$s\$ with either a space or \$0\$:
g = n => s.replace(/./g, (_, x) => [, a = x % (k / r), x %= k / l, a * x][n] && ' ')

Python 2, 187 185 183 174 166 156 148 147 145 bytes
Uses - as the tap character
a,b=r,l=input()
while b:a,b=b,a%b
w=r*l/a
for x,y,z in zip(' RLM',(w,r,l,r),(w,r,l,l)):print x,''.join('- '[i%(w/y)!=0<i%(w/z)]for i in range(w))

Try it online!

Saved:

-2 bytes, thanks to Jonathan Frech

[i%(w/y)and i%(w/z)>0] could be [i%(w/y)!=0<i%(w/z)].

@JonathanFrech Thanks :)

Java 11, 226 234 233 219 bytes
String h(int r,int l,int m){var s="";for(;m>0;)s+=m%r*(m--%l)<1?'.':32;return s;}

r->l->{int a=r,b=l,m;for(;b>0;b=a%b,a=m)m=b;m=r*l/a;return"  "+repeat("-",m)+"\nR "+h(m/r,m+1,m)+"\nL "+h(m/l,m+1,m)+"\nM "+h(m/r,m/l,m);}

Kind of lengthy; too bad Java does not have an lcm() function. Try it online here (TIO does not have Java 11 yet, so this uses a helper method instead of String.repeat()).
My initial version took the interval between taps instead of the number of taps. Fixed now. Thanks to Kevin Cruijssen for golfing 1 byte.
Ungolfed:
String h(int r, int l, int m) { // helper function returning a line of metarhythm; parameters are: tap interval (right hand), tap interval (left hand), length
    var s = ""; // start with an empty String
    for(; m > 0; ) // repeat until the length is reached
        s += m % r * (m-- % l) < 1 ? '.' : 32; // if at least one of the hands taps, add a dot, otherwise add a space (ASCII code 32 is ' ')
    return s; // return the constructed line
}

r -> l -> { // lambda taking two integers in currying syntax and returning a String
    int a = r, b = l, m; // duplicate the inputs
    for(; b > 0; b = a % b, a = m) // calculate the GCD of r,l using Euclid's algorithm:
        m=b; // swap and replace one of the inputs by the remainder of their division; stop once it hits zero
    m = r * l / a; // calculate the length: LCM of r,l using a=GCD(r,l)
    return // build and return the output:
    "  " + "-".repeat(m) // first line, m dashes preceded by two spaces
    + "\nR " + h(m / r, m + 1, m) // second line, create the right-hand rhythm; by setting l = m + 1 for a metarhythm, we ensure there will be no left-hand taps
    + "\nL " + h(m / l, m + 1, m) // third line, create the left-hand rhythm the same way; also note that we pass the tap interval instead of the number of taps
    + "\nM " + h(m / r, m / l, m); // fourth line, create  the actual metarhythm
}

It's not much, but -1 byte by changing ?".":" " to ?'.':32.

@KevinCruijssen Every byte counts :-) Thanks!

Python 2, 185 228 223 234 249 bytes
def f(r,l):
     c='.';d=' ';M,R,L=[r*l*[d]for _ in d*3]
     for i in range(r*l):
      if i%r<1:L[i]=M[i]=c
      if i%l<1:R[i]=M[i]=c
      if r<R.count(c)and l<L.count(c):R[i]=L[i]=M[i]=d;break
     print d,i*'-','\nR',''.join(R),'\nL',''.join(L),'\nM',''.join(M)

Try it online!

I've just copy-pasted this into TIO and taken the generated format from there. Turns out it's done in fewer bytes than you thought ;)

@Tfeld r=4, l=8 works fine for me

The length is supposed to be the lowest common multiple. With r=4, l=8, that should be 8, but it appears your output is much longer (8*4?).

I forgot about that bit, thanks. I've added an updated version, but it is a lot longer.

That still does not give the LCM; eg for 15,25, it gives 375, but it should be 75.

@O.O.Balance I think that's fixed it.

It seems it takes r,l as the interval between taps rather than the number of taps. My answer initially had the same issue. Also, could you please update the headline (byte-count) and TIO when you make changes?

@O.O.Balance I think I've fixed everything now. Please point out anything else I've missed though :)

That seems to print too few dashes, although I can't see why: https://tinyurl.com/ybpx5sfv Two golfing ideas: Could you use an infinite loop instead of range(r*l) since you're breaking the loop anyway? And might you replace r==R.c … and L.c … by something like r*l==R.count(c)*L.count(c)? Python is not my best language, but it could save you a few bytes.

I believe the last check can be replaced by i%r+i%l+0**i<1. Also, you can remove previous versions of code, as they will be preserved in your edit history of anyone wants to see them

@O.O.Balance I think it prints too few dashes because it's not taking into account the pause after the last beat. The r*l idea wouldn't work because it would display nothing if either r or l were 0. The infinite loop version seems to end up longer than the restricted one with the fix for the hyphens, but I'll keep trying to see if i cant get it lower.

@JoKing I'll remove the last versions on the next update then. I couldn't remember if SO kept the edit history because I don't spend much time on here now, and when I do it's on mobile.

I know I'm a bit late to point this out, but you don't need to account for r==0 or l==0. The challenge specifies positive integers.

Perl 6, 85 80 78 bytes
-2 bytes thanks to Jo King.
{«'  'R L M»Z~'-'x($!=[lcm] @_),|(@_.=map:{' '~(0~' 'x$!/$_-1)x$_}),[~|] @_}

Try it online!
Returns a list of four lines.

Jelly, 32 bytes
æl/Ḷ%Ɱµa/ṭ=0ị⁾. Z”-;ⱮZ“ RLM”żK€Y

Try it online!
Takes input as a list [L,R].
æl/       Get LCM of this list.
   Ḷ      Range [0..LCM-1]
    %Ɱ    Modulo by-each-right (implicitly the input, [L,R]):
           [[0%L ... (LCM-1)%L], [0%R ... (LCM-1)%R]]
µ         Take this pair of lists, and:
 a/ṭ      Append their pairwise AND to the pair.
    =0    Is zero? Now we have a result like:
              [[1 0 0 1 0 0 1 0 0 1 0 0 1 0 0]
               [1 0 0 0 0 1 0 0 0 0 1 0 0 0 0]
               [1 0 0 1 0 1 1 0 0 1 1 0 1 0 0]]

ị⁾.       Convert this into dots and spaces.
Z”-;ⱮZ    Transpose, prepend a dash to each, transpose. Now we have
              ['---------------'
               '.  .  .  .  .  '
               '.    .    .    '
               '.  . ..  .. .  ']

“ RLM”ż       zip(' RLM', this)
       K€     Join each by spaces.
         Y    Join the whole thing by newlines.

C++ (gcc), 197 bytes
int f(int a,int b){std::string t="  ",l="\nL ",r="\nR ",m="\nM ";int c=-1,o,p=0;for(;++p%a||p%b;);for(;o=++c<p;t+="-")l+=a*c%p&&++o?" ":".",r+=b*c%p&&++o?" ":".",m+=o-3?".":" ";std::cout<<t+l+r+m;}

Try it online!

Suggest ++p%a+p%b instead of ++p%a||p%b

C (gcc), 204 bytes
p(s){printf(s);}
g(a,b){a=b?g(b,a%b):a;}
h(r,l,m){for(;m;)p(m%r*(m--%l)?" ":".");}
f(r,l,m,i){m=r*l/g(r,l);p("  ");for(i=m;i-->0;)p("-");p("\nR ");h(m/r,m+1,m);p("\nL ");h(m/l,m+1,m);p("\nM ");h(m/r,m/l,m);}

Port of my Java answer. Call with f(number_of_right_hand_taps, number_of_left_hand_taps). Try it online here.

200 bytes

Pyth, 53 bytes
j.b+NYc"  L R M "2++*\-J/*FQiFQKm*d+N*\ t/JdQsmeSd.TK

Definitely room to golf.  Will do so when I have time.
Try it here
Explanation
j.b+NYc"  L R M "2++*\-J/*FQiFQKm*d+N*\ t/JdQsmeSd.TK
                       J/*FQiFQ                        Get the LCM.
                    *\-                                Take that many '-'s.
                               Km*d+N*\ t/dJQ          Fill in the taps.
                                             smeSd.TK  Get the metarhythm.
                  ++                                   Append them all.
      c"  L R M "2                                     Get the prefixes.
 .b+NY                                                 Prepend the prefixes.
j                                                      Join with newlines.

C# (Visual C# Interactive Compiler), 254 bytes

Golfed Try it online!
(r,l)=>{int s=l>r?l:r,S=s;while(S%l>0|S%r>0)S+=s;string q(int a){return"".PadRight(S/a,'.').Replace(".",".".PadRight(a,' '));}string R=q(S/r),L=q(S/l),M="";s=S;while(S-->0)M=(R[S]+L[S]>64?".":" ")+M;return"  ".PadRight(s+2,'-')+$"\nR {R}\nL {L}\nM {M}";}

Ungolfed
( r, l ) => {
    int
        s = l > r ? l : r,
        S = s;

    while( S % l > 0 | S % r > 0 )
        S += s;

    string q( int a ) {
        return "".PadRight( S / a, '.' ).Replace( ".", ".".PadRight( a, ' ' ) );
    }

    string
        R = q( S / r ),
        L = q( S / l ),
        M = "";

    s = S;

    while( S-- > 0 )
        M = ( R[ S ] + L[ S ] > 64 ? "." : " " ) + M;

    return "  ".PadRight( s + 2, '-') + $"\nR {R}\nL {L}\nM {M}";
}

Full code
Func<Int32, Int32, String> f = ( r, l ) => {
    int
        s = l > r ? l : r,
        S = s;

    while( S % l > 0 | S % r > 0 )
        S += s;

    string q( int a ) {
        return "".PadRight( S / a, '.' ).Replace( ".", ".".PadRight( a, ' ' ) );
    }

    string
        R = q( S / r ),
        L = q( S / l ),
        M = "";

    s = S;

    while( S-- > 0 )
        M = ( R[ S ] + L[ S ] > 64 ? "." : " " ) + M;

    return "  ".PadRight( s + 2, '-') + $"\nR {R}\nL {L}\nM {M}";
};

Int32[][]
    testCases = new Int32[][] {
        new []{ 3, 2 },
        new []{ 4, 3 },
        new []{ 4, 5 },
        new []{ 4, 7 },
        new []{ 4, 8 },
    };

foreach( Int32[] testCase in testCases ) {
    Console.Write( $" Input: R: {testCase[0]}, L: {testCase[1]}\nOutput:\n{f(testCase[0], testCase[1])}" );
    Console.WriteLine("\n");
}

Console.ReadLine();

Releases

v1.0 - 254 bytes - Initial solution.

Notes

None

Ruby, 130 126 bytes
->*a{puts"  "+?-*s=a[0].lcm(a[1])
r,l=a.map!{|e|(?.+' '*(s/e-1))*e}
[?R,?L,?M].zip(a<<r.gsub(/ /){l[$`.size]}){|e|puts e*" "}}

Try it online!

Charcoal, 52 bytes
≔θζＷ﹪ζη≧⁺θζζ↙≔⮌Ｅζ⟦¬﹪×ιθζ¬﹪×ιηζ⟧ζＦζ⊞ι⌈ι↓Ｅζ⭆ι§ .λ←↓RLM

Try it online! Link is to verbose version of code. Explanation:
≔θζＷ﹪ζη≧⁺θζ

Calculate the LCM of the inputs by taking the first multiple of R that's divisible by L.
ζ↙

Print the LCM, which automatically outputs the necessary row of -s. Then move to print the rhythm from right to left.
≔⮌Ｅζ⟦¬﹪×ιθζ¬﹪×ιηζ⟧ζ

Loop over the numbers from the LCM down to 0 and create an array of lists representing the beats of the right and left hands.
Ｆζ⊞ι⌈ι

Loop over the beats and add the metarhythm.
↓Ｅζ⭆ι§ .λ

Print the reversed beats downwards, but as this is an array they end up leftwards.
←↓RLM

Print the header.

Python 2, 117 bytes
a,b=input();n=a
while n%b:n+=a
for i in-1,1,2,3:print'_RLM '[i],''.join(' -'[i%2>>m*a%n|i/2>>m*b%n]for m in range(n))

Try it online!

Pyth, 49 bytes
J/*FQiFQjC+c2" RLM    "ms@L" -"!M++0d*Fdm%Ld/LJQJ

Expects input in the form [r,l]. Uses - to display taps. Try it online here, or verify all test cases at once here.
J/*FQiFQjC+c2" RLM    "ms@L" -"!M++0d*Fdm%Ld/LJQJ   Implicit: Q=eval(input())
 /*FQiFQ                                            Compute LCM: (a*b)/(GCD(a,b))
J                                                   Store in J
                                        m       J   Map d in [0-LCM) using:
                                            /LJQ      Get number of beats between taps for each hand
                                         %Ld          Take d mod each of the above
                                                    This gives a pair for each beat, with 0 indicating a tap
                       m                            Map d in the above using:
                                     *Fd              Multiply each pair (effecively an AND)
                                 ++0d                 Prepend 0 and the original pair
                               !M                     NOT each element
                        s@L" -"                       Map [false, true] to [' ', '-'], concatenate strings
                                                    This gives each column of the output
           c2" RLM    "                             [' RLM','    ']
          +                                         Prepend the above to the rest of the output
         C                                          Transpose
        j                                           Join on newlines, implicit print

R, 161 149 146 bytes
function(a,b){l=numbers::LCM(a,b)
d=c(0,' ')
cat('  ',strrep('-',l),'\nR ',d[(x<-l:1%%a>0)+1],'\nL ',d[(y<-l:1%%b>0)+1],'\nM ',d[(x&y)+1],sep='')}

Try it online!
I definitely feel like there's room for improvement here, but I tried a few different approaches and this is the only one that stuck. Getting rid of the internal function definition would make me quite happy, and I tried a bunch of restructures of the cat() to make it happen. Nevermind, as soon as I posted I realised what I could do. Still definitely some efficiency savings to be found.
There are other LCM functions in libraries with shorter names, but TIO has numbers and I considered that more valuable at this point.

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


text:
Optimize Compiler for simple Reverse Polish Notation Programming Language
Description
Imaginary programming language (IPL) uses Polish Reverse Notation. It has the following commands:

i -- input number and push it to the stack
o -- non-destructive output top of the stack (number stays on the stack)
d -- discard top of stack
integer number -- push this number to the stack
+-* -- pop two numbers from the stack, perform corresponding operation and push back the result. There is no division in IPL.

IPL works only with integers and is used for simple calculations. An IPL program is written on one line and separated by spaces.
Empty string is a valid IPL program.
IPL Program:
i i + o

Inputs two numbers, adds them together and outputs the result.
Input numbers and integers that can be pushed to stack are in range [-999, 999], however output can be any. If your language do not support big numbers it is okay though.
Input/output format
You may choose any input/output format as long as it clear to understand and read/write: string, list, tokens etc.
Task
You are given some IPL program, you need to optimize it (reduce length):
i 12 + 3 + o d 2 3 + d

After optimization will become
i 15 + o

You do not have to preserve stack state, but amount of inputs and outputs and their order should match for the original and optimized program.
So IPL program:
-40 i * 2 * o i + 3 1 + o i 2 *

After optimisation will become
i -80 * o i 4 o i

or
-80 i * o i 4 o i

(note that you have to save all inputs, even if they are irrelevant).
There should be no hardcoding for test cases, code should work on any arbitrary IPL program and produce shortest possible IPL program that meets the requirements.
Scoring
Default code-golf scoring.
UPDATE: changed scoring to pure code golf scoring, as per @Sanchises suggestion.
Test cases:
Input:
(empty string)

Possible output:
(empty string)

Input:
i 4 * 2 + 3 * 6 - o

Possible output:
i 12 * o

Input:
1 1 + o

Possible output:
2 o

Input:
i 2 + 3 + o d 2 3 + d

Possible output:
i 5 + o

Input:
-40 i * 2 * o i + 3 1 + o i 2 *

Possible output:
-80 i * o i 4 o i

Input:
i i 1 + i 1 + i 1 + i 1 + d d d d o

Possible output:
i i i i i d d d d o

Input:
i i i 0 * * * o

Possible output:
i i i 0 o

Input:
i i i 1 * * * o

Possible output:
i i i * * o

Input:
i 222 + i 222 - + o

Possible output:
i i + o

Input:
i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o

Possible output:
i i i i i o 1 o

Input:
i 1 + 2 * 1 + o

Possible output:
i 2 * 3 + o

Input:
1 1 + o i 2 + 3 + o d 2 3 + d 4 i * 2 * o i + 3 1 + o i 2 * i i 1 + i 1 + i 1 + i 1 + d d d d o i i i 0 * * * o i i i 1 * * * o i 2 + i 2 - + o i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o

Possible output:
2 o i 5 + o 8 i * o i 4 o i i i i i i d d d d o i i i 0 o i i i * * * o i i + o i i i i i o 1 o

A question: can you simplify i  i d o to i o i (the input is in order and the output is in order) or should you not simplify it? (the set of input and outputs should be in order)

@Sanchises no, inputs and outputs should be in order. If original program inputs 2 numbers before outputing anything optimised should do the same.

Welcome to PPCG! Nice first Challenge!

May there be d or o when stack is empty?

Should we reduce number of tokens or number of bytes in the IPL program?

@user202729 no, input code is always valid

@user202729 number of tokens

i i - o  cannot be optimized to i i 0 o cause inputs can be different, so there is could be any output not only zero

@АндрейЛомакин, yes, sorry, that optimization would be questionable. Still, if the code cannot be shortened, is it valid to alter it without altering its functionality, i.e. optimizing i 2 * o to 2 i * o?

@JonathanFrech Ithink it is fine to reorder as long as it remains optimal. And I added test case, thanks.

From review queue, I do not think this challenge is unclear. If you do, please comment about why.

@mbomb007 I'm certainly not sure what is meant by "no hardcoding cases".

@WW I think the OP means that you should not hardcode only the test cases listed in the question. You have to support arbitrary input. There should be no hardcoding for test cases, code should work on any arbitrary IPL program

Wolfram Language (Mathematica), 733 728 690 564 516 506 513 548 bytes
j=Integer;f=Flatten;s=SequenceReplace;A=FixedPoint[f@s[#,{{x_j,p,y_j,t}->{y,t,x*y,p},{x_j,y_j,p}->x+y,{x_j,y_j,t}->x*y,{x_j,p,y_j,p}->{x+y,p},{x_j,t,y_j,t}->{x*y,t},{0,p}|{1,t}->{},{0,t}->{d,0}}]//.{a___,Except[i|o]}->{a}&,#]&;B=Expand@Check[f@FoldPairList[f/@Switch[#2,i,{{i},{#,i@c++}},o,{{Last@#},#},d,{{},Most@#},p,{{},{#[[;;-3]],Tr@#[[-2;;]]}},t,{{},{#[[;;-3]],#[[-2]]*Last@#}},_,{{},{##}}]&,c=0;{},#],x]&;F=MinimalBy[w=A@f[#/.m->{-1,t,p}];z=B@w;s[#,{-1,t,p}->m]&/@A/@Select[Permutations@Join[w,Cases[z /.i@_->i,_j,∞]],B@#==z&],Length][[1]]&

Try it online!
This is a four-step tour-de-force that (1) replaces "-" with "-1 * +" so that we don't have to deal with subtractions, (2) simplifies the list of commands a bit, (3) makes a list of all permutations of this list of commands and picks out those that give the same result when parsed (executed), and (4) simplifies these lists of commands a bit and picks the shortest, after converting certain operations back to subtractions.
This code is terribly inefficient because it goes through the list of all permutations of the input code. For long input codes I don't recommend running this code; but as I read it there are no runtime or memory restrictions in this challenge.
This code does the optimization step after converting all "-" operations to "+" operations with signs flipped, and only at the end re-introduces the "-" operator when converting code back to strings. This implies for example that "i -1 i * + o" is correctly optimized to "i i - o".
As the i/o format requirement is quite loose, this code takes and returns code as lists, where the symbols "+", "-", "*" are represented by p, m, t, tokens respectively. The conversion from and to strings is done in the wrapper function given on TIO:
G[S_] := StringReplace[{"p" -> "+", "m" -> "-", "t" -> "*"}]@StringRiffle@
         Quiet@F@
         ToExpression[StringSplit[S] /. {"+" -> p, "-" -> m, "*" -> t}]

Un-golfed version, including the string-format wrapper and minimizing the final code string length instead of the number of tokens, and including a few more transformation niceties:
(* convert code string to list of operators *)
inputfilter[s_] := ToExpression[Flatten[StringSplit[s] /.
  {"i" -> i, "o" -> o, "d" -> d, "+" -> p, "-" -> {-1, t, p}, "*" -> t}]]

(* convert list of operators to code string *)
outputfilter[s_] := StringReplace[StringRiffle@Flatten@SequenceReplace[s,
  {{-1, t, p} -> m,                         (* convert "-1 t p" back to "-"             *)
   {x_ /; x < 0, p} -> {-x, m},             (* convert "y x +" to "y -x -" when x<0     *)
   {x_ /; x < 0, t, p} -> {-x, t, m}}],     (* convert "y x * +" to "y -x * -" when x<0 *)
  {"m" -> "-", "p" -> "+", "t" -> "*"}]     (* backsubstitution of symbols              *)

(* simplify a list of operators somewhat *)
simplifier[s_] := FixedPoint[Flatten@SequenceReplace[#,
  {{x_Integer, p, y_Integer, t} -> {y, t, x*y, p},  (*  "x + y *" -> "y * (xy) +"       *)
   {x_Integer, y_Integer, p} -> x + y,              (*  "x y +" -> "(x+y)"              *)
   {x_Integer, y_Integer, t} -> x*y,                (*  "x y *" -> "(xy)"               *)
   {x_Integer, p, y_Integer, p} -> {x + y, p},      (*  "x + y +" -> "(x+y) +"          *)
   {x_Integer, t, y_Integer, t} -> {x*y, t},        (*  "x * y *" -> "(xy) *            *)
   {0, p} | {1, t} -> {},                           (*  "0 +" and "1 *" are deleted     *)
   {x_Integer, i, p} -> {i, x, p},                  (*  "x i +" -> "i x +"              *)
   {x_Integer, i, t} -> {i, x, t},                  (*  "x i *" -> "i x *"              *)
   {0, t} -> {d, 0}}] //.                           (*  "0 *" -> "d 0"                  *)
  {a___, Except[i | o]} -> {a} &, s]                (* delete trailing useless code     *)

(* execute a list of operators and return the list of generated outputs *)
parse[s_] := Expand@Quiet@Check[Flatten@FoldPairList[  (* stack faults are caught here     *)
  Function[{stack, command},                        (* function called for every command*)
    Flatten /@ Switch[command,                      (* code interpretation:             *)
    i, {{i}, {stack, i[inputcounter++]}},           (* output "i" and add input to stack*)
    o, {{stack[[-1]]}, stack},                      (* output top of stack              *)
    d, {{}, Most[stack]},                           (* delete top of stack              *)
    p, {{}, {stack[[;; -3]], stack[[-2]] + stack[[-1]]}},  (* add two stack elements    *)
    t, {{}, {stack[[;; -3]], stack[[-2]]*stack[[-1]]}},    (* multiply two stack elements*)
    _, {{}, {stack, command}}]],                    (* put number onto stack            *)
    inputcounter = 0; {},                           (* start with zero input counter and empty stack*)
    s],                                             (* loop over code list              *)
  x]                                                (* return "x" if an error occurred  *)

(* the main function that takes a code string and returns an optimized code string *)
F[s_] := Module[{w, q},
  w = simplifier@inputfilter@s;      (* convert input to useful form *)
  q = parse[w];                      (* execute input code *)
  MinimalBy[
    outputfilter@*simplifier /@      (* simplify and stringify selected codes          *)
      Select[Permutations[w],        (* all permutations of code list                  *)
             parse[#] == q &],       (* select only those that give the correct output *)
    StringLength] // Union]          (* pick shortest solution by length               *)

Thanks to @redundancy for catching a bug: The parser needs a Expand applied to the output in order to handle distributive equivalence. 506→513
update
Now also optimizes 1 o 1 + o to 1 o 2 o. This was a surprisingly difficult case and made the code much slower. 513→548

Seems like this gives an error on test case i i 1 + i 1 + i 1 + i 1 + d d d d o.

@Grimy as I said, this code doesn't run for large problems because it goes through an exhaustive combinatorical search of code space. Your error is an out-of-memory fault on TIO, and not due to my code.

@Grimy for "i i 1 + d o" my code gives "i i d o", which I consider optimized. For "i i 1 + i 1 + d d o" it gives "i i i + d o", which has the same number of tokens as the more obvious "i i i d d o" optimization. I have not tried longer inputs.

I believe input i 2 * i 2 * + o should produce optimized output i i + 2 * o, but this code returns the (unoptimized) input.

Thanks @redundancy, it's fixed and your example is now one of the included test cases.

Thanks a lot for the bounty! This was a tough problem and I think I've presented a crummy solution.

APL (Dyalog Unicode), 268 bytes
r←¯999+⍳1999
{⍺←,⊂(⍵∊,¨'io')/⍵⋄p←⊃⍺⋄≡/{⍺←⍬⍬⋄s o←⍺⋄0=≢⍵:o⋄h←¯2↓s⋄t←¯2↑s⋄u←⊃⍵⋄v←1↓⍵⋄∨/u∊⎕D:(s,⊂,⍎u)o∇v⋄'i'=u:((s,⊂,0)o∇v),¨(s,⊂,1)o∇v⋄0=≢s:.1⋄'o'=u:s(o,¯1↑s)∇v⋄'d'=u:(¯1↓s)o∇v⋄1≥≢s:.1⋄(h,,¨∘.(⍎u)/t)o∇v}¨p⍵:p⋄((1↓⍺),,(⍳≢p)∘.{(⍺↑p),(⊂⍵),⍺↓p}(,¨'d+-×'),('-'@('¯'=⊢)⍕)¨r)∇⍵}

Try it online!
An anonymous function that takes tokenized program as input, and gives the tokenized minimal program as output. Uses × instead of * for multiplication.
The idea is that each output can only be linearly dependent on each input. This means that if we want to check the equivalence of two programs, it is enough to compute and compare the outputs for each input being 0 or 1 (2^n cases if the original program has n input commands). We can entirely avoid symbolic computation this way.
Since trying out ~2000 constants takes forever, I put the variable r outside of the function so that we can test for small ranges and observe that the code actually solves the challenge.
Pseudocode
Take a tokenized program.
Create the minimal candidate program by removing all commands except I/O.
Create a queue of candidate programs.
While the head of the queue is not equivalent to the original program
  Pop the head
  For all possible tokens except I/O (Note 1)
    For all possible positions in the program (Note 2)
      Insert the token at the given position of the program
      Push it at the end of the queue
Output the minimal equivalent program

Note 1: All possible tokens include d, +-×, and the numbers -999 to 999 (inclusive).
Note 2: Given a program of length n, only the positions 0 to n-1 need to be considered. The head (position 0) is needed to account for the cases like 1 i - o. The tail (position n) is not needed because it doesn't affect the output(s) in any way.
Ungolfed with comments
⍝ takes tokenized words, 'i' 'o' 'd' '+' '-' '×' or 'num'
⍝ [stk out] runIPL tokens → output
runIPL←{
  ⍺←⍬⍬  ⍝ Initialize stack and output
  stk out←⍺
  0=≢⍵:out  ⍝ Nothing to process
  h←¯2↓stk ⋄ t←¯2↑stk
  u←⊃⍵ ⋄ v←1↓⍵

  ⍝ If the next token is num, push it
  ∨/u∊⎕D: (stk,⊂,⍎u)out∇v
  ⍝ If it is 'i', collect the results for 0 and 1
  'i'=u: ((stk,⊂,0)out∇v),¨(stk,⊂,1)out∇v
  ⍝ Stack underflow; break out and output an invalid value
  0=≢stk: .1
  ⍝ Output
  'o'=u: stk(out,¯1↑stk)∇v
  ⍝ Drop
  'd'=u: (¯1↓stk)out∇v
  1≥≢stk: .1
  ⍝ Arithmetic
  (h,,¨∘.(⍎u)/t)out∇v
}

⍝ strip non-IOs
⍝ takeIO tokens → IO tokens
takeIO←{(⍵∊,¨'io')/⍵}

range←¯1+⍳15

⍝ search for the shortest program whose output exactly matches the original
⍝ should terminate eventually when it meets the original program
⍝ [prog.queue] search tokens → tokens of equivalent program
search←{
  ⍝ Initialize the queue with single program with only I/O commands
  ⍺←,⊂takeIO⍵
  ⍝ List of tokens to try inserting
  newToks←(,¨'d+-×'),('-'@('¯'=⊢)⍕)¨range
  prog←⊃⍺ ⋄ rest←1↓⍺
  ⍝ List of indexes to insert the token
  idxs←⍳≢prog
  ⍝ If the program's output matches the original, it is the answer
  (runIPL prog)≡runIPL⍵: prog
  ⍝ Otherwise, add all possible insertions to the queue
  (rest,,idxs ∘.{(⍺↑prog),(⊂⍵),⍺↓prog} newToks)∇⍵
}

Try it online!

Nice! Fails on i 0 * o though, returning i 1 o instead of i 0 o.

@Roman The program expects × instead of *.

Thanks. Still fails on i 0 × o by returning i  1  1  -  o instead of i 0 o.

@Roman It is probably because it is running after the line r←1 2, which forces the program to use just the two numbers as constant tokens. Include a zero like r←0 1 2 and try again. I get i 0 o as expected.

Thanks for the help!

authors: Андрей Ломакин