55
\$\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\$
10
  • 21
    \$\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\$
    – user45941
    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\$
8
  • \$\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
6
+200
\$\begingroup\$

APL (Dyalog Extended), 82 73 bytes

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

Updated with dyalog extended stuffs and works on TIO now! :D

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}

\$\endgroup\$
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\$
9
  • \$\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\$
2
  • \$\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
2
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Nice, knew I'd get one-upped by a golf lang eventually \$\endgroup\$
    – rak1507
    Nov 4 '20 at 23:21
0
\$\begingroup\$

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.
\$\endgroup\$

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.