10067 - Playing with Wheels

Difficulty : medium

Solution Description :

BFS Problem

I represent the 4 digit as integer i.e. if 4 digits are 0 2 0 1 then I represent is 201, or 1 2 3 1 represent 1231

At first pregenerate all adjacency for 0 to 9999
For each value you got 8 adjacency value

Example If the 4 digit are 0 1 0 0 so, the value is 100
---set n=value
---set m=n%10, so m=100%10=0
---set L=R=value-m*1 now L=R=100
---set L =L + (m+1)%10 * 1 and R = R+ (m+9)%10 * 1 so, L=101 and R=109 . (101 and 109 are adjacency of 100)

---set n=n/10=100/10=10
---set m=n%10, so m=10%10=0
---set L=R=value-m*10 now L=R=100
---set L =L + (m+1)%10 * 10 and R = R+ (m+9)%10 * 10 so, L=110 and R=190 . (110 and 190 are adjacency of 100)

---set n=n/10=10/10=1
---set m=n%10, so m=1%10=1
---set L=R=value-m*100 now L=R=0
---set L =L + (m+1)%10 * 100 and R = R+ (m+9)%10 * 100 so, L=200 and R=0 . (200 and 0 are adjacency of 100)

---set n=n/10=1/10=0
---set m=n%10, so m=0%10=0
---set L=R=value-m*1000 now L=R=100
---set L =L + (m+1)%10 * 1000 and R = R+ (m+9)%10 * 1000 so, L=1100 and R=9100 . (1100 and 9100 are adjacency of 100)

Finally you got all adjacency for 100 are 101,109,110,190,200,0,1100,9100

Now run BFS from initial configuration
If you reach to target configuration then print length of shortest path.
other wise print -1