12
\$\begingroup\$

Question

We are captured by robot army on their space station. Our space ship pilot is in the prison which is in level 1. There is only one way how to escape and it's rescuing your space ship pilot. It mean's moving from level N to level 1. However because it's very risky you need to get to the prison in the least number of steps as possible.

Conditions

  • There are 4 ways how to move:

    1. Move from level N to level N - 1 e.g. from 12 to 11
    2. Move from level N to level N + 1 e.g. from 12 to 13
    3. Use teleport from level 2k to level k e.g. from 12 to 6
    4. Use teleport from level 3k to level k e.g. from 12 to 4
  • Teleports are only one-way (you can get from 12 to 4 but it's imposible to get from 4 to 12)

  • Every action takes one step

Input

Input should be read from STDIN, or the closest alternative in your programming language. Input consists of an integer n where 1 <= n <= 10^8.

Output

The output should be the minimum number of steps it takes to go from n to level 1.

Examples

Level         Minimum number of steps
1             0
8             3
10            3
267           7
100,000,000   25

Try to code program that will help us to save our space ship pilot from the prison in the shortest time and return home!

The shortest code will win!

\$\endgroup\$
  • 7
    \$\begingroup\$ It is advisable (but not obligatory) to wait at least one week before accepting an answer. Even if you intend to change the accepted answer if a shorter one gets posted in the future, others may get the impression that this contest is "over" and refrain from participating. \$\endgroup\$ – Dennis Oct 2 '15 at 4:46
  • 1
    \$\begingroup\$ This challenge reminds me of a game I used to play with my calculator: I would type a number that fills up the screen and try to divide by 2, 3, or 5 as much as I can, then adding/subtracting 1 and continuing. \$\endgroup\$ – Arcturus Oct 3 '15 at 22:20
8
\$\begingroup\$

Pyth, 32 bytes

L?<b3tbhSsmm+h%_Wkbdy/+kbd2tS3yQ

Try it online: Demonstration or Test Suite

Explanation:

I transformed the problem a little bit. I define 4 new operations, that replace the 4 operations of the question.

  • level / 2 (counts as (level % 2) + 1 steps, because you might need to do move a level down first in order to teleport)
  • (level + 1) / 2 (counts as (level % 2) + 1 steps)
  • level / 3 (counts as (level % 3) + 1 steps)
  • (level + 1) / 3 (counts as (-level % 3) + 1 steps)

By design these operations can be applied to each number, if the number is 0 mod 2, 1 mod 2, 0 mod 3, 1 mod 3 or 2 mod 3.

You can easily think about, why this works. The main idea is, that there is at least one optimal solution, that doesn't have two (move down) or two (move up) motions in a row. Proof: If you have a solution, that has two such motions in a row, than you can replace them and make the solution smaller or equal in length. For instance you could replace (move up, move up, teleport from 2k to k) by (teleport from 2k to k, move up) and similar in all other cases.

L?<b3tbhSsmm+h%_Wkbdy/+kbd2tS3yQ
L                                 define a function y(b), which returns:
 ?<b3                               if b < 3:
     tb                               return b-1
                                    else:
          m                tS3        map each d in [2, 3] to:
           m              2             map each k in [0, 1] to:
              %_Wkbd                      (b mod d) if k == 0 else (-b mod d)
             h                            +1, this gives the additional steps
            +       y/+kbd                + f((b+k)/d) (recursive call)
         s                            combine the two lists
       hS                             and return the minimum element
                               yQ call y with input number

The function y uses implicitly memoization and therefore the runtime doesn't explode.

\$\endgroup\$
  • 1
    \$\begingroup\$ The main idea is, that there are never two (move down) or two (move up) motions in a row in the optimal solution. - what about 29 -> 28 -> 27 -> 9 -> 3 -> 1 ? If that is an optimal solution, how did you decide that there's always an alternative to the two-up/two-down path, which doesn't lead off into a more awkward region of numbers? \$\endgroup\$ – TessellatingHeckler Oct 2 '15 at 5:13
  • 1
    \$\begingroup\$ @TessellatingHeckler Maybe I should have be more precise. There is at least one optimal solution, that doesn't have two (move down) or two (move up) motions in a row. E.g. 29 -> 30 -> 10 -> 9 -> 3 ->1 \$\endgroup\$ – Jakube Oct 2 '15 at 9:08
  • \$\begingroup\$ I don't say that it's wrong, only that I can't "easily think about why it works". I was reasoning: the fastest route to room 1 is starting at a power of three, divide by three every move. So the fastest route for numbers near a power of three is repeated subtraction or addition to get to the power of three, then divide repeatedly by 3. If instead they start by moving moving n/2, they get further from the power of three, and therefore past the fastest possible route. I don't see how they will /always/ find another route equally short; it seems they are in a region with 'worse' choices now. \$\endgroup\$ – TessellatingHeckler Oct 2 '15 at 12:52
4
\$\begingroup\$

Python, 176 bytes

n=int(1e8);s,f,L=0,input(),[1,0]+[n]*(n-1)
def h(q):
 if 0<=q<=n and L[q]>s:L[q]=s+1
while n in L:
 for i,v in enumerate(L):
  if v==s:map(h,(i-1,i+1,i*2,i*3))
 s+=1
print L[f]

Brute force all the way; a list of all numbers 1 to 100,000,000 on a 64bit computer is ~800Mb of memory.

The list index represents the numbers, values represent the distance from 1 in allowed rescue steps.

  • Set list[1]=0 meaning "reachable in 0 steps".
  • for every number in the list which is reachable in 0 steps (i.e. 1)
    • set number+1, number-1, number*2, number*3 reachable in 1 step
  • for every number in the list which is reachable in 1 step (i.e 0,2,2,3)
    • set number+1, number-1, number*2, number*3 reachable in 2 steps
  • ... etc. until every list index is reached.

Runtime is a bit over 10 minutes. *ahem*.

Code comments

n=int(1e8)           # max input limit.
s=0                  # tracks moves from 1 to a given number.
f=input()            # user input.

L=[1,0]+[n]*(n-1)    # A list where 0 can get to room 1 in 1 step,
                     # 1 can get to itself in 0 steps,
                     # all other rooms can get to room 1 in 
                     # max-input-limit steps as a huge upper bound.


def helper(q):
    if 0<=q<=n:      # Don't exceed the list boundaries.
      if L[q]>s:     # If we've already got to this room in fewer steps
                     # don't update it with a longer path.
          L[q]=s+1   # Can get between rooms 1 and q in steps+1 actions.


while n in L:        # until there are no values still at the 
                     # original huge upper bound

 for i,v in enumerate(L):
  if v==s:                            # only pick out list items
                                      # rechable in current s steps,
      map(helper,(i-1,i+1,i*2,i*3))   # and set the next ones reachable
                                      # in s+1 steps.

 s+=1                                 # Go through the list again to find
                                      # rooms reachable in s+1 steps

print L[f]                            # show answer to the user.

Other

  • If you run it in PythonWin, you can access the list L in the interpreter afterwards.
  • Every room has a path to the captain in 30 moves or less.
  • Only one room is 30 moves away - room 72,559,411 - and there are 244 rooms which are 29 moves away.
  • It may have terrible runtime characteristics for the maximum case, but one of the question comments is "@Geobits all programs that should find shortest ways for 20000 test cases in 5 minutes" and it tests 1-20,001 in <6 seconds.
\$\endgroup\$
2
\$\begingroup\$

Python 2 ... 1050

poorly written, ungolfed, unoptimal.

Reads the start level on stdin, prints the minimum number of steps on stdout.

def neighbors(l):
    yield l+1
    yield l-1
    if not l%3:yield l/3
    if not l%2:yield l/2

def findpath(start, goal):
    closedset = set([])
    openset = set([start])
    came_from = {}
    g_score = {}
    g_score[start] = 0
    f_score = {}
    f_score[start] = 1
    while len(openset) > 0:
        current = min(f_score, key=f_score.get)
        if current == goal:
            return came_from
        else:
            openset.discard(current)
        del f_score[current]
        closedset.add(current)
        for neighbor in neighbors(current):
            if neighbor in closedset:
                continue
            tentative_g_score = g_score[current] + 1
            if (neighbor not in openset) or (tentative_g_score < g_score[neighbor]):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = tentative_g_score + 1
                openset.add(neighbor)
def min_path(n):
    path = findpath(n,1)
    i,current = 0,1
    while current <> n:
        i+=1
        current = path[current]
    return i
print min_path(input())
\$\endgroup\$
2
\$\begingroup\$

32-bit x86 machine code, 59 bytes

In hex:

31c9487435405031d231dbb103f7f14a7c070f94c301d008d353e8e3ffffff5b00c3585331d2b102f7f152e8d2ffffff5a00d05a38d076019240c3

The machine language per se has no concept of standard input. Since the challenge is pure computational, I opted to write a function taking input parameter in EAX and returning result in AL.

The math behind the code is nicely explained by @Jakube: the search is conducted only among the paths having teleports interspersed with no more than one one-level moves. The performance is about 12000 test cases per second in the lower end of input range and 50 cases per second in the upper end. The memory consumption is 12 bytes of stack space per recursion level.

0:  31 c9               xor ecx, ecx  
_proc:
2:  48                  dec eax       
3:  74 35               je _ret       ;if (EAX==1) return 0;
5:  40                  inc eax       ;Restore EAX
6:  50                  push eax      
7:  31 d2               xor edx, edx  ;Prepare EDX for 'div'
9:  31 db               xor ebx, ebx  
b:  b1 03               mov cl, 3     
d:  f7 f1               div ecx       ;EAX=int(EAX/3); EDX=EAX%3
f:  4a                  dec edx       ;EDX is [-1..1]
10: 7c 07               jl _div3      ;EDX<0 (i.e. EAX%3==0)
12: 0f 94 c3            sete bl       ;BL=EDX==0?1:0
15: 01 d0               add eax, edx  ;If EAX%3==2, we'd go +1 level before teleport
17: 08 d3               or bl, dl     ;BL=EAX%3!=0
_div3:
19: 53                  push ebx      ;Save register before...
1a: e8 e3 ff ff ff      call _proc    ;...recursive call
1f: 5b                  pop ebx       
20: 00 c3               add bl, al    ;BL is now # of steps if taken 3n->n route (adjusted) less one
22: 58                  pop eax       ;Restore original input parameter's value
23: 53                  push ebx      
24: 31 d2               xor edx, edx  
26: b1 02               mov cl, 2     
28: f7 f1               div ecx       ;EAX=EAX>>1; EDX=EAX%2
2a: 52                  push edx      ;Save register before...
2b: e8 d2 ff ff ff      call _proc    ;...another recursive call
30: 5a                  pop edx       
31: 00 d0               add al, dl    ;AL is now # of steps if using 2n->n route (adjusted) less one
33: 5a                  pop edx       
34: 38 d0               cmp al, dl    ;Compare two routes
36: 76 01               jbe _nsw      
38: 92                  xchg eax, edx ;EAX=min(EAX,EDX)
_nsw:
39: 40                  inc eax       ;Add one for the teleport itself
_ret:
3a: c3                  ret           
\$\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.