TopCoder problem "BikeLock" used in SRM 245 (Division I Level Two)

Problem Statement


One kind of combination lock often used on bicycles and notebook computers consists of several parallel disks with the digits '0' to '9' printed in order on the outside surface of the disks. To dial a combination, you turn the disks so that the appropriate digit on each disk lines up with a reference mark. Each time you turn a disk, you rotate it up to three positions clockwise or counterclockwise. By grasping several disks with your fingertips, you can simultaneously turn up to three adjacent disks by the same amount. Note that '0' and '9' are adjacent on the disks.

Given the current numbers showing on each disk (as a String) and the desired numbers (also as a String), find the minimum number of turns needed to dial the desired combination. For example, if the current numbers are "555" and the desired numbers are "464", then one way to dial the combination would be to turn each disk separately, taking 3 turns altogether. However, a better way to dial the combination is to turn all three disks simultaneously to "444" and then turn the middle disk by itself to "6", taking 2 turns altogether.



Parameters:String, String
Method signature:int minTurns(String current, String desired)
(be sure your method is public)


-current contains between 3 and 50 characters, inclusive.
-desired is the same length as current.
-current contains only digits ('0'-'9').
-desired contains only digits ('0'-'9').


Returns: 2
The example above.
Returns: 2
If you could turn four disks simultaneously, you could do this in 1 turn. But you can't turn more than three disks at once, so it takes 2 turns.
Returns: 0
Returns: 5
Returns: 34

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming