The goal of this competition is to develop sorting/solving methods for permutation transformations appeared in Elvira Strasser-Rapaport important work in 1959, but still not fully understood by mathematical community.  The problem represents a wide class of sorting/pathfinding/planning/reinforcements learning problems, which are important in mathematics, computer science, bionformatics, communication theory, etc.   And can serve as one of the benchmarks for modern pathfinding methods. The challenge is almost identical to the [Kaggle Santa 2023 challenge ](https://www.kaggle.com/competitions/santa-2023), and later similar challenges accompying CayleyPy project: [LRX1](https://www.kaggle.com/competitions/lrx-oeis-a-186783-brainstorm-math-conjecture),  [LRX2](https://www.kaggle.com/competitions/lrx-discover-math-gods-algorithm) , [LRX3](https://www.kaggle.com/competitions/lrx-binary-in-search-of-gods-number), [Tetraminx](https://www.kaggle.com/competitions/cayley-py-professor-tetraminx-solve-optimally), [Megaminx](https://www.kaggle.com/competitions/cayley-py-megaminx)...

You need to find a sequence of 3 transformations (proposed by E.Rapaport motivated by music and bell ringing in churches): **I,S,K** which will bring unsorted input vector to the sorted form (it is known to be always possible). Where **S** is **S**wap of positions 0 and 1, **I** is "**I**nterleaver" - swaping positions 0⇆1, 2⇆3,4⇆5,6⇆7, .... and **K** is its "**K**onjugate Interleaver": swaping positions 1⇆2, 3⇆4,5⇆6,7⇆8, etc. 

The ideal goal is to develop method which will make sorting optimally, i.e. to find solutions with minimal possible number of moves. That is called [God's algorithm](https://en.wikipedia.org/wiki/God%27s_algorithm) it is not known for these transformations,  neither the [God's number](https://en.wikipedia.org/wiki/God%27s_algorithm) (i.e. worst case peformance, or in the other words the diameter of the Cayley graph) is known.  

There is highly important conjecture in mathematics that predicts that God's number (i.e. worst case performace, or diameter of Cayley graph) is less than n², where n is length of vector. I.e. in the worst case you will need not more than n² operations to sort. (Next sections provide more context).  The conjecture is known to be very hard and resits all efforts for more than 50 years. The conjecture concerns very general class of transformations. But it is even unknown whether it is true or not for these particular Rapaport M2 transformations. Solving the challenge you will shed light on that important question, and hopeflly help to find/estimate the God's number. 

The score is sum of lengths of the solutions - the smaller - the better.
For the challenge you are welcome to use any methods you prefer, only score matters. The advanced machine learning methods are proposed e.g. in [CayleyPy project](https://cayleypy.github.io/cayleypy-docs/api.html), [CayleyPy-Cube](https://arxiv.org/abs/2502.13266), [CayleyPy-RL](https://arxiv.org/abs/2502.18663), [CayleyPy-Growth](https://www.arxiv.org/abs/2509.19162). CayleyPy is open-source crowd-sourcing project to develop effective AI-based library for mathematics - you are welcome to contribute - contact us. 

**Examples of similar sorting problems**
The simplest [bubble sort](https://en.wikipedia.org/wiki/Bubble_sort) allows only transpositions of neighbour positions. It is optimal algorithm for such transformations. [Pancakes sorting](https://en.wikipedia.org/wiki/Pancake_sorting) is another example (with Bill Gates involved - not a joke). 

**Broader Mathematical Context - groups and Cayley graphs**
From a mathematical  perspective  it is a typical task in mathematics: decompose an element of a group into a product of given generators ("moves"), or, in the other words, find a path on the [Cayley graph](https://en.wikipedia.org/wiki/Cayley_graph) of a group. For example - [bubble sort](https://en.wikipedia.org/wiki/Bubble_sort) algorithm provides the shortest paths on the the [permutohedron](https://en.wikipedia.org/wiki/Permutohedron) Cayley graph - with nodes all n! permutations, and edges connect permutations different only in neighbour positions - thus represents a permutation as a sequence of neighbour transpositions. Length of the decomposition (path) is called "[word metric](https://en.wikipedia.org/wiki/Word_metric)" in group theory. Research on Cayley graphs is of fundamental importance for mathematics and the field contains many notoriously hard problems, which has been addressed by renowned mathematicians such as [M. Gromov](https://en.wikipedia.org/wiki/Mikhael_Gromov_(mathematician)) ([theorem](https://en.wikipedia.org/wiki/Gromov%27s_theorem_on_groups_of_polynomial_growth)) and [T. Tao](https://en.wikipedia.org/wiki/Terence_Tao) ([posts](https://terrytao.wordpress.com/2010/07/10/cayley-graphs-and-the-geometry-of-groups/)), among others. Moreover, it has numerous applications, ranging from bioinformatics (e.g., estimating evolutionary distance—"[Transform men into mice](https://ieeexplore.ieee.org/abstract/document/492588/)" 😃), to the optimisation of [interprocessor networks](https://ieeexplore.ieee.org/document/21148), and beyond.  Famous computer scientist [Donald Knuth ](https://en.wikipedia.org/wiki/Donald_Knuth) contributed to [improving the algorithm](https://arxiv.org/abs/math/9201304) to solve the problems like that. Such algorithm is implemented in computer algebra systems like [GAP/SAGE](https://doc.sagemath.org/html/en/reference/groups/sage/groups/perm_gps/cubegroup.html), however these methods are [not efficient](https://mathoverflow.net/q/482661/10446) ([notebook](https://www.kaggle.com/code/alexandervc/gap-cannot-solve-rubik-s-cube-444)) on large groups. And the challenge is to improve them. 

**Broader RL Context - RL with severely sparse reward**
The problem is a typical reinforcement learning problem - vectors (nodes of Cayley graph) is a space of states, transformations (edges of Cayley graph) - are actions  (here only three actions I,S,K for each state), while rewards (penalties) are always "1", unless you found the solution (sorted vector). 
The cumulative reward (penalty) becomes exactly the length of the path to the solution state (sorted vector). And the goal is to minimize it, i.e. to solution with minimal possible number of actions, i.e.  find the shortest path on the Cayley graph. Value function has very clear and natural interpretation - length of the path. Bellman equation for the value function comes from trivial relation on path length. (See [CayleyPy-RL](https://arxiv.org/abs/2502.18663) for more details). There is a severe  "sparse reward problem", since "always 1" is meaningless reward (only tiny detail that for the solution state reward is not 1, but 0, makes setup meaningful). Thus advancing the challenge you will contribute to development of RL methods overcoming the "sparse reward problem" on extremely huge spaces up to google size and beyond.

**Similar Challenges**
[Kaggle Santa 2023 challenge ](https://www.kaggle.com/competitions/santa-2023) - several puzzles: cubes, rings, globes. 
LRX series – [OEIS-A186783 conjecture](https://www.kaggle.com/competitions/lrx-oeis-a-186783-brainstorm-math-conjecture),  [Towards God's algorithm](https://www.kaggle.com/competitions/lrx-discover-math-gods-algorithm) , [Binary states 0/1](https://www.kaggle.com/competitions/lrx-binary-in-search-of-gods-number) - just three moves - L,R - left/right cyclic shifts, X - eXchange positions 0 and 1.   Questions go back to  "one of the founding fathers of Soviet cybernetics" [V.M. Glushkov](https://en.wikipedia.org/wiki/Victor_Glushkov) 1968 seminal work and are still unsolved. See survey [link1](https://library.keldysh.ru/prep_vw.asp?lg=e&pid=8508) , [link2](https://www.kaggle.com/datasets/alexandervc/cayleypy-development-3-growth-computations/data?select=Glukhov_Zubov1999review.pdf) (pages 21-22).

[Pancake sorting](https://www.kaggle.com/competitions/CayleyPy-pancake)
[Transposons](https://www.kaggle.com/competitions/cayleypy-transposons)
[Reversals](https://www.kaggle.com/competitions/cayleypy-reversals)
[Glushkov problem](https://www.kaggle.com/competitions/cayleypy-glushkov)
[RapapportM2](https://www.kaggle.com/competitions/cayleypy-rapapport-m2)
[Rubik's cube 444](https://www.kaggle.com/competitions/cayley-py-444-cube)
[Professor Tetraminx](https://www.kaggle.com/competitions/cayley-py-professor-tetraminx-solve-optimally)
[Megaminx](https://www.kaggle.com/competitions/cayley-py-megaminx)
[Christophers jewel](https://www.kaggle.com/competitions/cayleypy-christophers-jewel)
[SuperCube from IHES](https://www.kaggle.com/competitions/cayleypy-ihes-cube)