Hints for bypassing TLE

I was trying to generate all sub-strings this way but it takes so much time. Definitely too much.
There was a suggestion to use meet in the middle approach. You generate all combination starting from the first and the second string in the same time and generate all next strings from those generated (keeping in mind what is the origin of each string). At some point strings from one group should reach second group. But I didn’t try it yet.
You should rather ask on English forum. This part is mostly focusing on tasks from Polish SPOJ.

My code is based on finding all substring combinations. It is using set() and FIFO queue… and as expected I received TLE not only because the code is written in Python, but principally because the algorithm is way too slow, however number of steps is calculated correctly.
Nevertheless, I am using this code to calculate number of steps for test cases for more readable or legible data:
From_string is various, To_string is always 0123456789 (or less digits)
So for example 4769810352 0123456789 runs 23 sec and gives 5 steps.
I noticed that in many cases I can find solution almost as fast as this sluggish algorithm. One of such cases is 1032547698 0123456789 runs 5 sec and gives 5 steps. One (after some training) can clearly see that we need to invert 5 pairs simply. Another case is 9876501234 0123456789 which gives 2 steps after 0.004sec…but you may notice easily that first step is to invert all and then first five digits, or alternatively first last 5 and then invers all - it is based on the digits sequence observation, etc.
That is why I am trying to translate my way of thinking now. Wish me luck.

I didn’t solve it yet (TLE) so no update from my side. I tried meet in the middle approach but it’s too slow. I need to improve it somehow

I tried an algorithm that uses some best step estimation, or scores with one step forward evaluation. Let me explain:
Every inversion can be described as relative displacement plus starting position:
Inversion # of positions within 10 fields
[-1, 1] 9
[-2, 0, 2] 8
[-3, -1, 1, 3] 7
[-4, -2, 0, 2, 4] 6
[-5, -3, -1, 1, 3, 5] 5
[-6, -4, -2, 0, 2, 4, 6] 4
[-7, -5, -3, -1, 1, 3, 5, 7] 3
[-8, -6, -4, -2, 0, 2, 4, 6, 8] 2
[-9, -7, -5, -3, -1, 1, 3, 5, 7, 9] 1
Hence, you have 1+2+3+4+5+6+7+8+9 = 45 combinations to find best score.
Comparing to 1x2x3x4xx5x6x7x8x9= 9! = 362 880 if you want to check all possible combinations.
Instead, I tried 2-step approach for scoring, which requires 45*45=2025. As a result, this code is acceptable fast and max execution time is not very case dependent. Some examples below.
As I already mentioned, I used also a code which is finding all substring combinations, plus random generation of strings. What I found is:
Maximum number of steps for 10 digits is 8 (based on 110 samples). The result is the same in both directions (from to = to from). Execution time on my laptop using Python 3.9 are from milliseconds up to minutes for a single case. Some examples:
Case
3817964250 0123456789 steps 8, exec=371 sec, my result steps 7, exec=0.06 sec
2935740816 0123456789 steps 7 exec=328 sec , my result steps 7, exec= 0.06 sec
3851796420 0123456789 steps 7 exec=298 sec, my result steps 7, exec=0.06 sec
4258910673 0123456789 steps 6 exec=45 sec, my result steps 6, exec=0.04 sec
1032547698 0123456789 steps 5 exec=4 sec, my result steps 5, exec==0.04 sec
4368792105 0123456789 steps 4 exec=1 sec, my result steps 5, exec==0.04 sec
9126543780 0123456789 steps 3 exec=0.05 sec, my result steps 3, exec==0.02 sec
9423108765 0123456789 steps 3 exec=0.03 sec, my result steps 3, exec==0.03 sec
9123456780 0123456789 steps 2 exec=0.002 sec, my result steps 2, exec==0.01 sec
Too good to be true. There are cases when my code fails:
8967452301 0123456789 steps 5 exec=5 sec, my result steps 6, exec=0.05 sec (try find yourself what are these 5 steps and you will understand why my code failed)
Next:
4536091728 0123456789 steps 6 exec=46 sec, my result steps 7, exec=0.05 sec however after exchanging from-to direction:
0123456789 4536091728 steps 6 exec=83 sec, my result steps 6, exec=0.04 sec so ok, but the cost of checking in both directions to select lower number of steps is 2x, and do not help in each case like:
5293014768 6012349758 steps 5 exec=15sec, my result steps 6 (both directions) exec=0.04 sec
Cases which seem trivial:
1357902468 0123456789 steps 7 exec=161sec, my result steps 7 exec=0.05 sec
3456012789 0123456789 steps 3, exec=0.01sec, my result steps 3 exec=0.02 sec

Summarizing: my code is fast, but in some case may overestimate steps, however, by just one step.
So depending on the application, it may be acceptable or not. I case of this “old fashioned jukebox” I would prefer not to wait minutes or even seconds to save just one step!
BTW: I have not submitted this code, since probably I would get WA if just one case failed.
I am not Python geek, nor programming expert, and cannot find better solution.

… I forgot to mention that scoring is based on sum of abs(displacements), where displacements are calculated as a shift of a digit to its “correct” position. For example:
From:
3021465798
To:
0123456789
Displacements:
3, -1, 0, -2, 0, 1, -1, 0, 1, -1
So total score = 10

I will continue testing, introduce check in both directions, confirm max error in steps.

Anyway, if you are interested in just getting AC in Spoj, look at https://www.geeksforgeeks.org/shortest-path-using-meet-in-the-middle/3 and modify this approach accordingly to the task.

Update:
I tried " meet in the middle approach" – as suggested also by quenthui,
Using the above hint/link, and modifying the code, I received the following:
As an example: - the results for the case 2935740816 0123456789 are as follows:

• Brute force to check all combinations: execution time 328 seconds
• Meet in the middle approach: execution time 2.4 seconds
• Best step scoring approach 0.1 second
  Meet in the middle approach really works but because it is written in Python, I am still getting TLE.
  BTW: My Best step scoring approach results in impressive 0.1 second, and gives correct answer (7 steps) but as I wrote, this is not always the case, which may be ok depending on application and “good enough” (I can imagine what the execution time could be for strings of length far above 10, probably not acceptable using Meet in the middle)

What do you think?