After a long day's work slogging in the office and browsing stackexchange.com, I finally walk out the door at 16:58, already weary with the day. Because I am still only an intern, my current mode of transportation is on bicycle. I head over to my trusty Peugeot Reynolds 501, but before I can sail away on it, I need to unlock it. The lock is a standard four digit combination lock (0-9), through the frame and the front wheel. As I try to stay awake, I pull my hand up to enter in the combination.
Because my fingers are so weary, I want to turn the lock to the correct combination with the fewest movements. One movement is defined as a rotation by one position (36 degrees), for example there is one movement from
5738. However, I am able to grasp up to any three consecutive rings at the same time, and rotate them as one, which only counts as a single movement. For example there is also only one movement from
6837 or to
5626. Moving from
6838 is not one movement, as digits number 1,2 and 4 have moved in the same direction, but independently of digit number 3.
Therefore, for a given combination I can see on the bike lock (any 4-digit integer), what is the lowest number of movements I can make to get it unlocked, and yes, I can rotate in either direction at any time. By this I mean that I can turn some digits in one direction and other digits in the other direction: not all of my movements will be anitclockwise or clockwise for each unlock.
Because I am lazy, my unlock code is 0000.
This is code golf I can't be bothered writing much code, so the shortest program in number of bytes wins.
Input is from stdin, and your code should output the combinations I can see at each step after each movement, including the 0000 at the end. Each of the combinations output should be separated by a space/newline/comma/period/ampersand.
Input: 1210 0100 0000 Input: 9871 9870 0980 0090 0000 Input: 5555 4445&3335&2225&1115&0005&0006&0007&0008&0009&0000 Input: 1234 0124 0013 0002 0001 0000
I tried posting this on http://bicycles.stackexchange.com, but they didn't like it...
Disclaimer: First golf, so anything that is broken/any missing information let me know! Also I did all the examples by hand, so there may be solutions which involve less movements!
EDIT: For answers which have multiple solution paths with equal number of movements (practically all of them), there is no preferred solution.