|
Post by xcessive on Oct 17, 2012 8:15:55 GMT -5
Write a function that computes the sequence of steps required to unlock a special, magical bicycle lock.
The lock works like this. The lock starts at a 4 digit number eg 3024 it can also be 0001. So in practice it is any number from 0000 to 9999. There are several operations you can do on this lock to unlock it. You can add 2 to the current number, you can subtract 3 from the current number, or you can multiply it by two. All of these operations work up to and down to the 0000 and 9999 limits. So for example 9998*2 or 9998+2 both result in 9999.
You must write a function that takes the current lock number and the number required to open the lock, and returns the sequence of steps required to unlock it. You get bonus points if the sequence of steps is the shortest possible sequence of steps required.
Here is a worked example: The initial lock number is 2843 and the target is 5683. First we use the 'multiply by two' operation on the lock. 2843 * 2 = 5686 Then subtract 3: 5686 - 3 = 5683 Unlocked!
|
|
Jordan
Incredibly Beginning
Posts: 36
|
Post by Jordan on Oct 17, 2012 22:07:32 GMT -5
Part two of the problem should be to write a proof that proves that your algorithm solves the problem in the fewest amount of steps possible.
Just kidding, but I'd encourage people to try this one.
|
|
|
Post by xcessive on Oct 17, 2012 23:39:27 GMT -5
Its actually a deceptively simple proof if you do it by contradiction.
|
|