## 11198 - Dancing Digits

Moderator: Board moderators

sunshine12
New poster
Posts: 3
Joined: Sun Dec 08, 2013 1:13 pm

### Re: 11198 - Dancing Digits

i still dont get it..

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11198 - Dancing Digits

Suppose the initial digits are:
1 2 4 5 6 7 -3 8
Put the initial digits onto the queue and also keep track of the number of moves.

Pop the front of the queue
Iterate through all pairs of digits until you find a pair where one is positive and one is negative and the sum of the absolute values is prime. Those pairs are: 2 and -3, 4 and -3, -3 and 8.
For each pair, generate all the possible moves: female to the left of the male, female to the right of the male, male to the left of the female, male to the right of the female.
So for pair 2 and -3, the possible moves are:
1 -3 2 4 5 6 7 8 (-3 to 2's left)
1 2 -3 4 5 6 7 8 (-3 to 2's right, this one ends up sorted)
1 4 5 6 7 2 -3 8 (2 to -3's left)
1 4 5 6 7 -3 2 8 (2 to -3's right)
Put each new state to the end of the queue.
Do the same with the other pairs 4 and -3, -3 and 8
Continue until you reach a sorted state or the queue is empty
Check input and AC output for thousands of problems on uDebug!