Hi. This year I became interested in developing python solvers. I couldn’t make my own solver for Turing Tumble completely, so I took the idea of the barnex algorithm from GitHub. At the moment, I have implemented part of the algorithm without gears, the arrangement of details for these solutions and a file with a solution for the simulator. Look at the picture.
Is there anything known about ready-made solvers and at what level they work?
As you can see, the solution is output according to the barnex’ solver standard with minor changes. The speed of the solution on python coincides with the time of the solution on Rust. I can’t explain the reason yet.
1 Like
The text of the solver on python. To start, replace all the ‘~’ characters with spaces. The solution includes only the passes of the bit parts. To get a complete solution, you need to arrange the ramps and crossovers in accordance with the solution.
In the initial position of the bit, the ball goes to the address in the second column of the solution, after turning to the address in the first column. B and R are the blue and red levers.
#!/usr/bin/python
#~--~coding:~utf-8~--
import~time~as~ttime
#~A~complete~search~of~all~possible~transitions~in~list~out
def~get_chain(from_in,len_in):
#~from_in~-~initial~instruction~number
#~len_in~-~number~of~instructions~~~
~~~~chain=[]
~~~~for~i~in~range(from_in,len_in):
~~~~~~~~chain.append(i+1)
~~~~chain.extend([-1,-2])~~~~
~~~~for~i~in~range(len(chain)):
~~~~~~~~for~j~in~range(len(chain)):
~~~~~~~~~~~~out.append((chain[i],chain[j]))
~~~~return~out~~~~~~~~
#**********************************************
def~solve_bits(n,~in_seq,~max_solutions):
~~~~global~total_qnt
~~~~max_instr=n~~~~#~n~instructions~can~be~used
~~~~str_in=in_seq~~#~output~balls~sequence~(from~left~to~right)
~~~~max_sols=max_solutions~#~max_sols~solutions~can~be~find~for~one~task
~~~~#~instr00~-~all~combinations~for~1~instruction
~~~~#~instrnm~-~all~combinations~for~n~step~from~m~instructions~and~so~on
~~~~#~for~example:~we~try~to~find~solution~with~5~ins
~~~~"""
~~~~instr55=[(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr45=[(5,5),(5,-1),(5,-2),(-1,5),(-2,5),(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr44=[(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr35=[(4,4),(4,5),(5,4),(4,-1),(4,-2),(-1,4),(-2,4),(5,5),(5,-1),(5,-2),(-1,5),(-2,5),(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr34=[(4,4),(4,-1),(4,-2),(-1,4),(-2,4),(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr33=[(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr25=[(3,3),(3,4),(3,5),(3,-1),(3,-2),(4,3),(5,3),(-1,3),(-2,3)]
~~~~instr25.extend(instr35)
~~~~instr24=[(3,3),(3,4),(4,3),(3,-1),(3,-2),(-1,3),(-2,3),(4,4),(4,-1),(4,-2),(-1,4),(-2,4),(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr23=[(3,3),(3,-1),(3,-2),(-1,3),(-2,3),(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr22=[(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr15=[(2,2),(2,3),(2,4),(2,5),(2,-1),(2,-2),(3,2),(4,2),(5,2),(-1,2),(-2,2)]
~~~~instr15.extend(instr25)
~~~~instr14=[(2,2),(2,-1),(2,-2),(-1,2),(-2,2),(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr14.extend(instr24)
~~~~instr13=[(2,2),(2,3),(3,2),(2,-1),(2,-2),(-1,2),(-2,2),(3,3),(3,-1),(3,-2),(-1,3),(-2,3),(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr12=[(2,2),(2,-1),(2,-2),(-1,2),(-2,2),(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr11=[(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr05=[(1,1),(1,2),(1,3),(1,4),(1,5),(1,-1),(1,-2),(2,1),(3,1),(4,1),(5,1),(-1,1),(-2,1)]
~~~~instr05.extend(instr15)
~~~~instr04=[(1,1),(1,2),(1,3),(1,4),(1,-1),(1,-2),(2,1),(3,1),(4,1),(-1,1),(-2,1)]
~~~~instr04.extend(instr14)
~~~~instr03=[(1,1),(1,2),(1,3),(1,-1),(1,-2),(2,1),(3,1),(-1,1),(-2,1)]
~~~~instr03.extend(instr13)
~~~~instr02=[(1,1),(1,2),(2,1),(1,-1),(1,-2),(-1,1),(-2,1)]
~~~~instr02.extend(instr12)
~~~~instr01=[(1,1),(1,-1),(1,-2),(-1,1),(-2,1),(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~instr00=[(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
~~~~"""
~~~~qnt=0~~~~~~~~~~~~~~~~~~~~~#~task's~counter
~~~~i_sols=0~~~~~~~~~~~~~~~~~~#~solutions'~counter
~~~~m1=[[],[],[],[],[],[]]~~~~#~first~address~in~instruction
~~~~m2=[[],[],[],[],[],[]]~~~~#~second~address~in~instruction
~~~~color_ball=["R","B"]
~~~~max_entry=[1,2,3,4,4,4]~~~#~maximum~for~entry~balls
~~~~#*******************************
~~~~max_balls=min(len(str_in),30)~~#~maximum~balls
~~~~Find_sols=False~~~#~no~solutions~yet
~~~~#*******************************
~~~~if~max_instr==1:
~~~~~~~~instrc0=get_chain(0,0)~#instr00
~~~~~~~~instrc1=[(6,6)]
~~~~~~~~instrc2=[(6,6)]
~~~~~~~~instrc3=[(6,6)]
~~~~~~~~instrc4=[(6,6)]
~~~~~~~~instrc5=[(6,6)]
~~~~if~max_instr==2:
~~~~~~~~instrc0=get_chain(0,1)~#instr01
~~~~~~~~instrc1=get_chain(1,1)~#instr11
~~~~~~~~instrc2=[(6,6)]
~~~~~~~~instrc3=[(6,6)]
~~~~~~~~instrc4=[(6,6)]
~~~~~~~~instrc5=[(6,6)]
~~~~if~max_instr==3:
~~~~~~~~instrc0=get_chain(0,2)~#instr02
~~~~~~~~instrc1=get_chain(1,2)~#instr12
~~~~~~~~instrc2=get_chain(2,2)~#instr22
~~~~~~~~instrc3=[(6,6)]
~~~~~~~~instrc4=[(6,6)]
~~~~~~~~instrc5=[(6,6)]
~~~~if~max_instr==4:
~~~~~~~~instrc0=get_chain(0,3)~#instr03
~~~~~~~~instrc1=get_chain(1,3)~#instr13
~~~~~~~~instrc2=get_chain(2,3)~#instr23
~~~~~~~~instrc3=get_chain(3,3)~#instr33
~~~~~~~~instrc4=[(6,6)]
~~~~~~~~instrc5=[(6,6)]
~~~~if~max_instr==5:
~~~~~~~~instrc0=get_chain(0,4)~#instr04
~~~~~~~~instrc1=get_chain(1,4)~#instr14
~~~~~~~~instrc2=get_chain(2,4)~#instr24
~~~~~~~~instrc3=get_chain(3,4)~#instr34
~~~~~~~~instrc4=get_chain(4,4)~#instr44
~~~~~~~~instrc5=[(6,6)]
~~~~if~max_instr==6:
~~~~~~~~instrc0=get_chain(0,5)~#instr05
~~~~~~~~instrc1=get_chain(1,5)~#instr15
~~~~~~~~instrc2=get_chain(2,5)~#instr25
~~~~~~~~instrc3=get_chain(3,5)~#instr35
~~~~~~~~instrc4=get_chain(4,5)~#instr45
~~~~~~~~instrc5=get_chain(5,5)~#instr55
~~#~A~complete~search~of~all~possible~transitions~for~6~bits~
~~~~for~m1[0],m2[0]~in~instrc0:~~~#~bit~0
~~~~~~~~for~m1[1],m2[1]~in~instrc1:~~#~bit~1
~~~~~~~~~~~~for~m1[2],m2[2]~in~instrc2:~~#~bit~2
~~~~~~~~~~~~~~~~for~m1[3],m2[3]~in~instrc3:~~#~bit~3
~~~~~~~~~~~~~~~~~~~~for~m1[4],m2[4]~in~instrc4:~~#~bit~4
~~~~~~~~~~~~~~~~~~~~~~~~for~m1[5],m2[5]~in~instrc5:~~#~bit~5
~~~~~~~~~~~~~~~~~~~~~~~~~~~~#~made~the~solution~number~qnt
~~~~~~~~~~~~~~~~~~~~~~~~~~~~#~check~this~solution
~~~~~~~~~~~~~~~~~~~~~~~~~~~~for~entry_mem_r~in~range(max_entry[max_instr-1]):
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~for~entry_mem_b~in~range(max_entry[max_instr-1]):
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~if~entry_mem_b~==~0~or~entry_mem_r~==~0:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#~all~entry~points~entry_mem_b~or~entry_mem_r
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~qnt~+=~1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~total_qnt~+=~1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~No_error=True
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~mem=[True~for~i~in~range(max_instr)]~#~start~memory
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ball="B"~~~~~#~B~always~first
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~str_out=""
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~qnt_balls=0
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~while~No_error~and~qnt_balls<max_balls:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~if~mem[i_mem]:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~i_mem=m1[i_mem]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~else:~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~i_mem=m2[i_mem]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~if~i_mem>=0:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~continue
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~else:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~if~qnt_balls<max_balls-1~and~color_ball[i_mem+2]~!=~str_in[qnt_balls+1]:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~break
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~if~i_mem==-1:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~str_out~+=~ball~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ball="B"
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~qnt_balls~+=~1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~i_mem=entry_mem_b
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~if~str_in[0:qnt_balls]~!=~str_out[0:qnt_balls]:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~No_error=~False
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~if~i_mem==-2:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~str_out~+=~ball~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ball="R"
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~qnt_balls~+=~1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~i_mem=entry_mem_r
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~str_len~=~len(str_out)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~if~str_in[0:qnt_balls]~!=~str_out[0:qnt_balls]:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~No_error=~False
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~if~str_in==str_out:~~#~print~the~solution
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~print~(f'\nballs~out:~"{str_out}"')
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~print~("solution~:=>",i_sols+1)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~print~("\nstart_blue:~",entry_mem_b)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~print~("start_red:~~",entry_mem_r)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~for~j~in~range(max_instr):
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~stri=str(j)+':~ijmp~'+str(j)+'~'+str(m1[j])+'~'+str(m2[j])
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~stri=stri.replace('-1','B')~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~stri=stri.replace('-2','R')
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~print~(stri)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~print~("counter:~",qnt)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~print~("==========================")
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~toc~=~ttime.perf_counter()
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ttm=(toc-tic)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ttc=int(ttm%60)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ttm=int(ttm/60)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~print(f"this~task:~{ttm}~min~~{ttc}~sec")
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~i_sols~+=~1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Find_sols=True
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~if~i_sols>=max_sols:~~~#~check~for~maxsimum~solutions
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~return~Find_sols
~~~~return~Find_sols~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#~test~fuction~1
def~find_all():
~~~~global~total_qnt
~~~~ticz~=~ttime.perf_counter()
~~~~total_qnt=0
~~~~max_solutions~=~1
~~~~test_str="BBBBBRRRRBBBRRB"~~#"BRRBBBRRRRBBBBB"
~~~~print(test_str)
~~~~print("\n\nmax~solutions~per~task:~",max_solutions)
~~~~for~i~in~range(1,len(test_str)+1):
~~~~~~~~for~n_instr~in~[1,2,3,4,5,6]:~#~Find~the~minimum~number~of~bits~for~a~string~of~length~from~0
~~~~~~~~~~~~if~solve_bits(n_instr,~test_str[0:i],~max_solutions):
~~~~~~~~~~~~~~~~break
~~~
~~~~print("total~counter:~",total_qnt)
~~~~tocz~=~ttime.perf_counter()
~~~~ttm=(tocz-ticz)
~~~~ttc=int(ttm%60)
~~~~ttm=int(ttm/60)
~~~~print(f"total:~{ttm}~min~~{ttc}~sec")
~~~~
#~test~function~2
def~find_one():
~~~~global~total_qnt
~~~~ticz~=~ttime.perf_counter()
~~~~total_qnt=0
~~~~test_str="BRRBBBRRRRBBBBB"
~~~~max_solutions~=~3
~~~~print("\n\nmax~solutions~per~task:~",max_solutions)
~~~~for~n_instr~in~[3,4,5,6]:~~#~Find~the~minimum~number~of~bits~for~a~string~
~~~~~~~~if~solve_bits(n_instr,~test_str,~max_solutions):
~~~~~~~~~~~~break
~~
~~~~print("total~counter:~",total_qnt)
~~~~tocz~=~ttime.perf_counter()
~~~~ttm=(tocz-ticz)
~~~~ttc=int(ttm%60)
~~~~ttm=int(ttm/60)
~~~~print(f"total:~{ttm}~min~~{ttc}~sec")
~~~
find_all()
find_one()