Tuenti Challenge 3

Challenge 16 - Legacy code

At Tuenti, we have a lot of legacy code - not everything is PHP and JavaScript. We have scripts in different languages running all over the place. As a part of the migration to the new Tuenti, we found a very, very old undocumented script written for a Turing Machine. It has been working for a while and it has never given us a problem so we've left it as is, but now our Turing Machine broke and there's no techical support for it.

We don't really know what the algorithm programmed for this Turing Machine does, we just gave it the input data and it returned the right output. The task now is to create something to do the same thing. It would be a good idea to think about the scalability now, because it always seemed to take a long time to process some type of inputs.

All we know about our broken Turing Machine is:

  • it has an almost infinite tape to the right, but not to the left
  • the language it used had only 6 chars: 0, 1, #, $, %, _
  • the '_' was the default character for the tape, equivalent to a blank space
  • it had to perform a write operation on each state transitition
  • it could stay in the same place after a state transition, so the valid movements were defined by R(ight), L(eft) and S(tay)
  • all of its programs started at the 'start' state with a '#' on it's tape head
  • the 'end' state indicated the end of the execution
  • the instructions format was the following: state,character:character_to_write,movement,new_state

And most importantly, we were able to recover the script that was in the machine when it died, and here it is:

start,#:%,R,state0
state0,0:0,R,state0
state0,1:1,R,state0
state0,#:#,S,state1
state1,#:#,L,state1
state1,$:$,L,state1
state1,1:0,R,state2
state1,0:1,L,state1
state2,1:1,R,state2
state2,0:0,R,state2
state2,#:#,L,state3
state2,$:$,L,state3
state3,0:0,L,state3
state3,1:1,R,state4
state3,%:%,R,state5
state4,0:0,R,state4
state4,1:1,R,state4
state5,1:1,R,state5
state5,0:0,R,state5
state5,#:#,S,state6
state5,$:$,S,state6
state4,#:#,S,state7
state4,$:$,S,state7
state7,#:$,R,state8
state7,$:$,R,state9
state8,1:1,R,state8
state8,0:0,R,state8
state8,#:#,R,state8
state8,_:_,L,state10
state10,#:$,L,state11
state11,1:1,L,state11
state11,0:0,L,state11
state11,#:#,L,state11
state11,$:$,R,state9
state9,1:_,R,state12
state9,0:_,R,state13
state9,#:_,R,state14
state9,$:$,S,state15
state12,1:1,R,state12
state12,0:0,R,state12
state12,#:#,R,state12
state12,$:$,R,state12
state12,_:1,L,state16
state16,1:1,L,state16
state16,0:0,L,state16
state16,#:#,L,state16
state16,$:$,L,state16
state16,_:1,R,state9
state13,1:1,R,state13
state13,0:0,R,state13
state13,#:#,R,state13
state13,$:$,R,state13
state13,_:0,L,state17
state17,1:1,L,state17
state17,0:0,L,state17
state17,#:#,L,state17
state17,$:$,L,state17
state17,_:0,R,state9
state14,1:1,R,state14
state14,0:0,R,state14
state14,#:#,R,state14
state14,$:$,R,state14
state14,_:#,L,state18
state18,1:1,L,state18
state18,0:0,L,state18
state18,#:#,L,state18
state18,$:$,L,state18
state18,_:#,R,state9
state15,1:1,R,state15
state15,0:0,R,state15
state15,#:#,R,state15
state15,$:$,R,state15
state15,_:#,L,state19
state19,1:1,L,state19
state19,0:0,L,state19
state19,#:#,L,state19
state19,$:$,L,state20
state20,1:1,L,state20
state20,0:0,L,state20
state20,#:#,L,state20
state20,$:$,S,state1
state6,1:1,R,state6
state6,0:0,R,state6
state6,#:#,R,state6
state6,$:#,R,state6
state6,_:_,L,state21
state21,#:#,L,state22
state22,1:1,L,state22
state22,0:0,L,state22
state22,#:#,L,state23
state22,%:#,S,end
state23,1:1,R,state23
state23,0:0,R,state23
state23,#:#,R,state23
state23,_:_,L,state24
state24,#:#,L,state25
state25,0:0,L,state25
state25,1:1,R,state26
state25,#:#,R,state27
state26,0:0,R,state26
state26,1:1,R,state26
state27,1:1,R,state27
state27,0:0,R,state27
state27,#:_,L,state28
state26,#:#,L,state29
state29,1:0,L,state30
state29,0:1,L,state29
state30,1:1,L,state30
state30,0:0,L,state30
state30,#:#,L,state31
state31,1:0,L,state31
state31,0:1,R,state32
state32,1:1,R,state32
state32,0:0,R,state32
state32,#:#,R,state32
state32,_:_,L,state21
state28,1:_,L,state28
state28,0:_,L,state28
state28,#:#,S,state21

Now we need this work to be done again and we need to find a solution soon, so we thought it would be a great idea to make our contest participants (you) help us.

Input

Machine tape

Output

Machine tape ignoring the trailing blank spaces.

Sample input

#1#1#

Sample output

#1#

Limits

Input: max 256 chars

Problem stats

Completion time: 10 percentile: 2:02 h
90 percentile: 22:51 h
Submit exec time: min: 0.62 s
10 percentile: 0.73 s
90 percentile: 26.44 s
max: 1783.00 s
Test tries: min: 1
10 percentile: 3
90 percentile: 26
max: 1080
# of completions:33