Save the pilot!
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.
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.
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())