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

APL (Dyalog Extended), 82 73 bytes

{p/⍨⍵≡¨⊃¨⊢p←({⍵/⍨⍧⊃¨⍵}⊢,⍥,(,∘-⍨↓⍉⊤5~⍨12 14,⍨⍳8)∘.{10|⍵,⍨⊂⍺+⊃⍵}⊢)⍣≡⊂⊂4⍴0}⊆

p←({⍵/⍨⍧⊃¨⍵}⊢,⍥,(,∘-⍨↓⍉⊤5~⍨12 14,⍨⍳8)∘.{10|⍵,⍨⊂⍺+⊃⍵}⊢)⍣≡⊂⊂4⍴0

p is all the possible paths

({⍵/⍨⍧⊃¨⍵}⊢,⍥,(,∘-⍨↓⍉⊤5~⍨12 14,⍨⍳8)∘.{10|⍵,⍨⊂⍺+⊃⍵}⊢)

This is a train that generates the next possible paths from one list of paths

(,∘-⍨↓⍉⊤5~⍨12 14,⍨⍳8)

List of possible changes, 0 0 0 0, 0 0 0 1, 0 0 0 -1, etc

∘.{10|⍵,⍨⊂⍺+⊃⍵}

Outer product with the dfn {10|⍵,⍨⊂⍺+⊃⍵}

{10|⍵,⍨⊂⍺+⊃⍵}

⊃⍵ unenclose ⍵ + ⊂⍺ enclose ⍺

⍵,⍨ concatenated with ⍵ 10| mod 10

⊢,⍥,stuff concatenate the output with the new paths

{⍵/⍨⍧⊃¨⍵} make it unique

(train)⍣≡⊂⊂4⍴0 apply the train with a fixpoint ⍣≡ to ⊂⊂4⍴0 to generate all paths

{p/⍨⍵≡¨⊃¨⊢p}

⊢p←... the ⊢ shouldn't be needed here, but that's a bug costing me 1 byte

⊃¨p get the first items from each in p

⍵≡¨ find where ⍵ is equal to them

p/⍨ replicate

Try it online!

Old answer:

{p⌷⍨⍸⍵≡¨⍥⊆⊃¨p←({⍵/⍨≠⊃¨⍵}⊢,⍥,((+,-)↓⍉2⊥⍣¯1⊢⎕A⍳'ABCDFGHLN')∘.{10|⍵,⍨⊂⍺+⊃⍵}⊢)⍣≡⊂⊂4⍴0}

Answer 3

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 4

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.

Answer 5

05AB1E --no-lazy, 41 39 37 bytes

Lazy evaluation seems to break it, with it enabled, this doesn't terminate.

[TS4㦎ΣmbÏD(«N>ãεISšÅ»+}T%¤O1‹i¦J»,q

Try it online!

This is really slow, doesn't finish for 1234 and 5555 on TIO.

The general structure of the program is

[           infinite loop, N in 0, 1, ...
 ...        generate list of all possible movements
    ...     take all combinations of N+1 movements and convert them to a sequence of positions
       ...  if the current position list ends with 0000, print and terminate

In more detail:

TS4㦎ΣmbÏD(«     # generate a list of all possible movements
T                 # push 10
 S                # split into digits ["1", "0"]
  4ã              # take ["1", "0"] to the 4th cartesian power
                  # this generates all 4-digit combinations of 0 and 1
    ¦             # remove the first element ("1111")
     ŽΣm          # push compressed integer 20958
        b         # convert to binary
         Ï        # keep the 4-digit combinations at indices where
                  #   the binary representation of 20958 has a 1
          D       # duplicate the list
           (      # negate each number in the copy
            «     # concatenate both lists

Try T4ãʒγ€ÙO}¦€SD(« online!

N>ãεISšÅ»+}T%     # try all possible combinations of movements
 N                # push the iteration counter (starts at 0)
  >               # increment the value
   ã              # take the movement list to the N+1 cartesian power
    ε             # map over each list of N+1 moves
     IS           # push the digits of the input
       š          # prepend it to the move list
        Å»+}      # cumulative left-reduce by addition
                  # this generates all positions of the lock
                  # that are a result of the movements in the list
            T%    # modulo 10

¤O1‹i¦J»,q        # verify and print position sequence
¤                 # get the last position
 O                # sum it
  1‹              # is this less than 1? (equal to 0)
    i             # if this is the case:
     ¦            #   remove the first element (initial position)
      J»          #   join each position and positions by newlines
        ,         #   print the result
         q        #   exit

Answer 6

J, 93 bytes

Doesn't even try to be efficient, will run out of memory for 5555 on TIO. :-)

(0({s#])((,-)|:#:7 59 217 584),/@((],10|(+{:))"1 2/)^:(]0=1#.s=:(4#0)&e."%.)^:_,:^:2)@(".@,.)

Try it online!

• (".@,.) convert '0123' into a list like 0 1 2 3
• ,:^:2 list of list of steps [[0 1 2 3]]
• ^:(]0=1#.s=:(4#0)&e."%.)^:_ until the there is a path of moves with 0 0 0 0 in it:
• ((,-)|:#:7 59 217 584) the possible moves
• ,/@((],10|(+{:))"1 2/) for each possible move and each path: create a new path with the last move + the possible move, mod 10 appended.
• 0({s#]) filter out the paths that caused the loop to stop, and take the first.