Pytanie

Zostajemy schwytani przez armię robotów na ich stacji kosmicznej. Nasz pilot statku kosmicznego znajduje się w więzieniu na poziomie 1. Istnieje tylko jeden sposób na ucieczkę i uratowanie pilota statku kosmicznego. Oznacza przejście z poziomu N na poziom 1. Jednak ponieważ jest bardzo ryzykowne, musisz dostać się do więzienia w jak najmniejszej liczbie kroków.

Warunki

• Istnieją 4 sposoby poruszania się:

  1. Przejdź z poziomu N na poziom N - 1 e.g. from 12 to 11
  2. Przejdź z poziomu N na poziom N + 1 e.g. from 12 to 13
  3. Użyj teleportacji z poziomu 2k na poziom k e.g. from 12 to 6
  4. Użyj teleportacji z poziomu 3k na poziom k e.g. from 12 to 4

• Teleporty są tylko w jedną stronę (możesz dostać od 12 do 4, ale nie można dostać od 4 do 12)

• Każde działanie wymaga jednego kroku

Wejście

Dane wejściowe należy odczytać ze STDIN lub najbliższej alternatywy w języku programowania. Dane wejściowe składają się z liczby całkowitej, ngdzie 1 <= n <= 10^8.

Wynik

Wynikiem powinna być minimalna liczba kroków, które trzeba wykonać, aby przejść ndo poziomu 1.

Przykłady

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

Spróbuj zaprogramować program, który pomoże nam jak najszybciej uratować naszego pilota statku kosmicznego przed więzieniem i wrócić do domu!

Najkrótszy kod wygra!

Pyth, 32 bajty

L?<b3tbhSsmm+h%_Wkbdy/+kbd2tS3yQ

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

Trochę zmieniłem problem. Definiuję 4 nowe operacje, które zastępują 4 operacje pytania.

• level / 2(liczy się jako (level % 2) + 1kroki, ponieważ w celu teleportacji może być konieczne najpierw przesunięcie poziomu w dół)
• (level + 1) / 2(liczy się jako (level % 2) + 1kroki)
• level / 3(liczy się jako (level % 3) + 1kroki)
• (level + 1) / 3(liczy się jako (-level % 3) + 1kroki)

Zgodnie z projektem operacje te mogą być stosowane do każdego numeru, jeśli liczba jest 0 mod 2, 1 mod 2, 0 mod 3, 1 mod 3lub 2 mod 3.

Możesz łatwo pomyśleć, dlaczego to działa. Główną ideą jest to, że istnieje co najmniej jedno optymalne rozwiązanie, które nie ma dwóch (ruch w dół) lub dwóch (ruch w górę) ruchów z rzędu. Dowód: jeśli masz rozwiązanie, które ma dwa takie ruchy z rzędu, możesz je wymienić i sprawić, by rozwiązanie było mniejsze lub równe długości. Na przykład możesz zastąpić (przesuń w górę, przesuń w górę, teleportuj z 2k do k) przez (teleportuj z 2k do k, przesuń w górę) i podobnie we wszystkich innych przypadkach.

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

Funkcja yużywa niejawnie zapamiętywania, dlatego środowisko wykonawcze nie eksploduje.

Python, 176 bajtów

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]

Brutalna siła przez całą drogę; lista wszystkich liczb 1 to 100,000,000na komputerze 64-bitowym to ~ 800 MB pamięci.

Indeks listy reprezentuje liczby, wartości reprezentują odległość od 1 w dozwolonych krokach ratunkowych.

• Ustaw listę [1] = 0, co oznacza „osiągalny w 0 krokach”.
• dla każdej liczby na liście, która jest osiągalna w 0 krokach (tj. 1)
  • ustaw liczbę + 1, liczbę-1, liczbę * 2, liczbę * 3 osiągalną w 1 kroku
• dla każdej liczby na liście, która jest osiągalna w 1 kroku (tj. 0,2,2,3)
  • ustaw liczbę + 1, liczbę-1, liczbę * 2, liczbę * 3 osiągalną w 2 krokach
• ... itd. aż do osiągnięcia każdego indeksu listy.

Czas działania wynosi nieco ponad 10 minut. * ahem *.

Komentarze do kodu

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.

Inny

• Jeśli uruchomisz go w PythonWin, możesz później uzyskać dostęp do listy L w tłumaczu.
• Każdy pokój ma ścieżkę do kapitana w 30 ruchach lub mniej.
• Tylko jeden pokój oddalony jest o 30 ruchów - pokój 72.549.411 - i są 244 pokoje oddalone o 29 ruchów.
• Może mieć straszną charakterystykę czasu wykonywania dla maksymalnej liczby przypadków, ale jednym z komentarzy do pytania jest: „ @Geobits wszystkie programy, które powinny znaleźć najkrótsze sposoby na 20000 przypadków testowych w 5 minut ” i testuje 1-20,001 w <6 sekund.

Python 2 ... 1050

źle napisany, nieprzystosowany do gry, nieoptymalny.

Odczytuje poziom początkowy na stdin, drukuje minimalną liczbę kroków na 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())

32-bitowy kod maszynowy x86, 59 bajtów

W hex:

31c9487435405031d231dbb103f7f14a7c070f94c301d008d353e8e3ffffff5b00c3585331d2b102f7f152e8d2ffffff5a00d05a38d076019240c3

Język maszyna per se nie ma pojęcia standardowego wejścia. Ponieważ wyzwanie jest czysto obliczeniowe, zdecydowałem się napisać funkcję przyjmującą parametr wejściowy EAXi zwracającą wynik AL.

Matematyka kryjąca się za kodem jest ładnie wyjaśniona przez @Jakube: wyszukiwanie odbywa się tylko wśród ścieżek z teleportacjami przeplatanymi nie więcej niż jednym ruchem o jeden poziom. Wydajność wynosi około 12000 przypadków testowych na sekundę w dolnym końcu zakresu wejściowego i 50 przypadków na sekundę w górnym końcu. Zużycie pamięci wynosi 12 bajtów miejsca na stosie na poziom rekurencji.

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