Combination bike lock

Question

The scenario

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.

The challenge

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 5737 to 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 5737 to 6837 or to 5626. Moving from 5737 to 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.

Examples

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.

Answer 1

Matlab, 412 327 bytes

Golfed (Thanks to @AndrasDeak for golfing s!):

s=dec2bin('iecbmgdoh'.'-97)-48;s=[s;-s];T=1e4;D=Inf(1,T);P=D;I=NaN(T,4);for i=1:T;I(i,:)=sprintf('%04d',i-1)-'0';end;G=input('');D(G+1)=0;for k=0:12;for n=find(D==k);for i=1:18;m=1+mod(I(n,:)+s(i,:),10)*10.^(3:-1:0)';if D(m)==Inf;D(m)=k+1;P(m)=n-1;end;end;end;end;n=0;X='0000';while n-G;n=P(n+1);X=[I(n+1,:)+48;X];end;disp(X)

This codes uses some dynamic programming for finding the shortest 'path' from the given number to 0000 using only the possible steps. The challenge is basically a shortest path prioblem (alternatively you could perhaps consider the steps as a commutatuve group.) but the difficulty was coming up with an efficient implementation. The basic structures are two 10000-element arrays, one for storing the number of steps to get to that index, the other one to store a pointer to the previous 'node' in our graph. It simultaneously calculates the 'paths' to all other possible numbers.

Examples:

9871
0981
0091
0001
0000

1210
0100
0000

Examples by @noisyass:

7478
8578
9678
0788
0899
0900
0000

3737
2627
1517
0407
0307
0207
0107
0007
0008
0009
0000

Own Example (longest sequence, shared with 6284)

4826
3826
2826
1826
0826
0926
0026
0015
0004
0003
0002
0001
0000    

Full Code (inlcuding some comments):

%steps
s=[eye(4);1,1,0,0;0,1,1,0;0,0,1,1;1,1,1,0;0,1,1,1];
s=[s;-s];


D=NaN(1,10000);%D(n+1) = number of steps to get to n
P=NaN(1,10000);%P(n+1) was last one before n

I=NaN(10000,4);%integer representation as array
for i=0:9999; 
    I(i+1,:)=sprintf('%04d',i)-'0';
end

G=9871; % define the current number (for the golfed version replaced with input('');
D(G+1)=0;
B=10.^(3:-1:0); %base for each digit

for k=0:100; %upper bound on number of steps;
    L=find(D==k)-1;
    for n=L; %iterate all new steps
        for i=1:18; %search all new steps
            m=sum(mod(I(n+1,:)+s(i,:),10) .* [1000,100,10,1]);
            if isnan(D(m+1))
                D(m+1) = k+1;
                P(m+1)=n;
            end
        end
    end
end
n=0;%we start here
X=[];
while n~=G
    X=[I(n+1,:)+'0';X];
    n=P(n+1);
end
disp([I(G+1,:)+'0';X,''])

Answer 2

Batch - 288 bytes

Even if you said they have to be consecutive (the rings), I assume by logic (following the example) that I can skip the middle one, as from 1234 to 0224.

set/p x=
set a=%x:~0,1%&set b=%x:~1,1%&set c=%x:~2,1%&set d=%x:~3,1%
:l
@echo %x%&if %a%==0 (if %d% NEQ 0 set/a d=d-1) else set/a a=a-1
@if %b% NEQ 0 set/a b=b-1
@if %c% NEQ 0 set/a c=c-1
@if %x% NEQ 0000 set x=%a%%b%%c%%d%&goto l

This is my Batch solution: 236 bytes.

---

Edit: corrected solution

set/p x=
set a=%x:~0,1%&set b=%x:~1,1%&set c=%x:~2,1%&set d=%x:~3,1%
:l
@echo %x%&set k=1&if %a%==0 (if %d% NEQ 0 set/a d=d-1&set k=0) else set/a a=a-1&set k=1
@if %b% NEQ 0 if %k%==1 set/a b=b-1&set k=0
@if %c% NEQ 0 if %k%==0 set/a c=c-1
@if %x% NEQ 0000 set x=%a%%b%%c%%d%&goto l

The new solution (fixed according to the underlying comments) is 288 bytes heavy.

Answer 3

Haskell - 310 bytes

import Data.Char
import Data.List
r=replicate
h=head
a x=map(:x)[map(`mod`10)$zipWith(+)(h x)((r n 0)++(r(4-j)q)++(r(j-n)0))|j<-[1..3],n<-[0..j],q<-[1,-1]]
x!y=h x==h y
x#[]=(nubBy(!)$x>>=a)#(filter(![(r 4 0)])x)
x#y=unlines.tail.reverse.map(intToDigit<$>)$h y
main=do x<-getLine;putStrLn$[[digitToInt<$>x]]#[]

This works by repeatedly building a new list of combinations by applying each possible turn to each combination already reached until one of them is the right combination. Duplicates are removed from the list on each iteration to keep memory usage from growing exponentially.

As a brute force solution, this is very inefficient and can take several minutes to run.

I don't have much experience with Haskell, so some thing could probably be done better.