46
\$\begingroup\$

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. Combination bike lock

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.

\$\endgroup\$
  • 18
    \$\begingroup\$ Welcome to PPCG; very nice first challenge! \$\endgroup\$ – Doorknob Jan 11 '16 at 23:34
  • 4
    \$\begingroup\$ This looks solid to me! Welcome to PPCG! \$\endgroup\$ – Mego Jan 11 '16 at 23:34
  • 1
    \$\begingroup\$ Nice challenge. Can i ask what should be the output for cases : 7478 and 3737? \$\endgroup\$ – noisyass2 Jan 12 '16 at 10:48
  • 1
    \$\begingroup\$ @noisyass2 Thanks; flawr's answer gives the following: 7478 8588 9698 0708 0808 0908 0008 0009 0000 and 3737 2627 1517 0407 0307 0207 0107 0007 0008 0009 0000 Just looking at the 3737, this makes sense: Looking at the first 3 digits only: If I move all of the first three at the same time, it takes 3 movements for digits 1 and 3, and then another 4 movements for digit 2, thus a total of seven. Whereas if I move each individually, each takes 3 moves, thus 9 movements. \$\endgroup\$ – Lui Jan 12 '16 at 20:14
  • 1
    \$\begingroup\$ I'm wondering whether the title "Combination Lock" (or "Bike Lock") might attract more viewers. \$\endgroup\$ – DavidC Jan 12 '16 at 20:36
10
\$\begingroup\$

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,''])
\$\endgroup\$
  • \$\begingroup\$ Nice! Being a mostly Matlab user myself I was wondering about how well it would fare. \$\endgroup\$ – Lui Jan 12 '16 at 20:09
  • 1
    \$\begingroup\$ For input 6444 your code gives 6444 7554 8664 9774 0884 0994 0004 0003 0002 0001 0000, whereas I find the answer to be 6444 6333 6222 6111 6000 7000 8000 9000 0000. My answer is 8 steps, yours is 10. I can't see the issue, and it appears to be there in both the golfed and ungolfed version. This is fixed in your latest edit. \$\endgroup\$ – Lui Jan 12 '16 at 20:22
  • 1
    \$\begingroup\$ I just corrected a small error in the code. In s the last row should be [0,1,1,1]. Then you get a 8 step solution too! I'm sorry for the inconvenience=) \$\endgroup\$ – flawr Jan 12 '16 at 20:26
  • 1
    \$\begingroup\$ @Lui There is a matlab/octave chatroom, among other stuff it is some kind of Base for the Matlab-derived golfing languange MATL. \$\endgroup\$ – flawr Jan 12 '16 at 21:12
  • 1
    \$\begingroup\$ for 4826, i found an 11 move solution : 4826 3716 2606 1506 0406 0306 0206 0106 0007 0008 0009 0000 \$\endgroup\$ – noisyass2 Jan 13 '16 at 4:04
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I haven't looked at your answer in great depth, but I am struggling to follow your logic in the first paragraph. Which example specifically are you referring to? And your example of going from 1234 to 0224 is not one movement. The idea is that with using only two fingers I can grasp up to three consecutive rings with a single grip. \$\endgroup\$ – Lui Jan 13 '16 at 0:43
  • \$\begingroup\$ I meant, if you can move 3 consecutive rings, it's reasonable to think that you can also move the first and the third one, avoiding the second one. Or should I change my code? \$\endgroup\$ – noize Jan 13 '16 at 0:44
  • \$\begingroup\$ Your assumption is wrong; you should change your code. Do you see the logic as explained in the above comment? \$\endgroup\$ – Lui Jan 13 '16 at 0:46
  • \$\begingroup\$ Code fixed. I checked with several different types of combinations and it looks to me like it always takes the shorter way. \$\endgroup\$ – noize Jan 13 '16 at 1:07
  • \$\begingroup\$ This seems to only count downwards, so it takes longer than necessary for combinations with high numbers (e.g. 18 moves for 9999) \$\endgroup\$ – faubi Jan 13 '16 at 1:26
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Seems like a solid basis for your approach. I've not experience with Haskell, nor (that I know of) any means of compiling/running it. A quick google doesn't give me anywhere I can try it, either. Are you able to give a link which lets me try it? Thanks. \$\endgroup\$ – Lui Jan 13 '16 at 0:45
  • \$\begingroup\$ @Lui It can be compiled with the Glasgow Haskell Compiler, but apart from downloading and using that I don't know of any way to run it. \$\endgroup\$ – faubi Jan 13 '16 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.