Wyścig cyfr

16

Powinieneś napisać program lub funkcję, która poda początkową kolejność wyraźnych liczb całkowitych dodatnich i długość ścieżki jako dane wyjściowe lub zwraca kolejność końcową liczb.

Dane wejściowe [5,1,2,6,7] and 14definiują następujący wyścig:

--------------
76215 ->
--------------

Zasady wyścigu

  • Tor zawija się, a cyfry mogą przechodzić wiele okrążeń.
  • Kolejność kroków jest cykliczna i oparta na pozycji początkowej. W naszym przykładzie 5 1 2 6 7 5 1 2 ....
  • W tej samej pozycji nie może być wielu cyfr.
  • Każda cyfra ma prędkość digit_valuekomórki na krok. Wyprzedzanie cyfry lub ciągłego bloku cyfr kosztuje jeden dodatkowy krok. Jeśli cyfra nie ma wymaganej prędkości, zatrzyma się przed (blokiem) cyfr (y). Przykłady:

    [41   ] => [ 1 4 ]  4 overtakes 1
    
    [2 1  ] => [ 21  ]  2 can only move 1 as it can't move 3 to overtake 1
    
    [4 12 ] => [ 412 ]  4 can only move 1 as it can't move 5 to overtake 12     
    
    [   3 ] => [ 3   ]  3 starting a new lap
    
  • Każda cyfra musi przejść digit_valueokrążenia, zanim się skończy. Okrążenie jest ukończone, gdy pozostała ostatnia komórka toru. Gotowa cyfra jest usuwana ze ścieżki.

  • Zauważ, że cyfra może osiągnąć swoją pozycję początkową wiele razy przez krok i ukończyć wiele okrążeń.

Wejście

  • Lista wyraźnych jednocyfrowych dodatnich liczb całkowitych ( 1..9) z co najmniej jednym elementem i pojedynczą dodatnią liczbą całkowitą, większą niż długość listy, długość ścieżki.

Wynik

  • Lista cyfr w kolejności, w jakiej zakończyły się, w dowolnym jednoznacznym formacie.

Przykłady

Wizualny przykład wprowadzania danych krok po kroku starting_order = [5,9,2] and length = 6

295   | Start position
29   5| digit 5 moves
2  9 5| digit 9 moves, finishing lap #1
  29 5| digit 2 moves
 529  | digit 5 moves, finishing lap #1
 52  9| digit 9 moves, finishing lap #2
 5  29| digit 2 moves
   529| digit 5 moves
 9 52 | digit 9 moves, finishing laps #3 and #4
29 5  | digit 2 moves, finishing lap #1
29   5| digit 5 moves
2  9 5| digit 9 moves, finishing lap #5
  29 5| digit 2 moves
 529  | digit 5 moves, finishing lap #2
 52  9| digit 9 moves, finishing lap #6
 5  29| digit 2 moves
   529| digit 5 moves
 9 52 | digit 9 moves, finishing laps #7 and #8
 9 5  | digit 2 moves, finishing lap #2 --> remove 2 from the track
59    | digit 5 moves, finishing lap #3
5     | digit 9 moves, finishing lap #9 --> remove 9 from the track
     5| digit 5 moves
    5 | digit 5 moves, finishing lap #4
      | digit 5 moves, finishing lap #5 --> remove 5 from the track
------
Finish order: 2 9 5

Przykłady w formacie Input => Output

[3], 2  =>  [3]

[9, 5], 3  =>  [9, 5]

[5, 9, 2], 6  =>  [2, 9, 5]

[5, 9, 2], 10  =>  [5, 9, 2]

[5, 7, 8, 1, 2], 10  =>  [1, 5, 7, 8, 2]

[5, 1, 6, 8, 3, 2], 17  =>  [1, 6, 8, 2, 3, 5]

[1, 2, 3, 7, 8, 9], 15  =>  [1, 7, 8, 9, 2, 3]

[9, 8, 7, 3, 2, 1], 15  =>  [8, 7, 9, 1, 2, 3]

[1, 2, 3, 4, 5, 6, 7, 8, 9], 20  =>  [1, 2, 3, 4, 5, 6, 7, 8, 9]

[9, 8, 7, 6, 5, 4, 3, 2, 1], 20  =>  [8, 7, 5, 9, 6, 1, 2, 4, 3]

To jest golf golfowy, więc wygrywa najkrótszy wpis.

randomra
źródło
Czy tablica wejściowa nie może mieć zduplikowanych elementów? Tak to wygląda, ale nie widzę wyraźnie tego warunku.
Andrew
@Andrew Tak, nie może być żadnych zduplikowanych cyfr. Edytowałem pytanie. Dzięki.
randomra
W przypadku testowym nr 6 (długość = 17) otrzymuję nieco inny wynik (dwie ostatnie cyfry są odwrócone). Zastanawiałem się, gdzie jest mój błąd. Mój dziennik wyścig jest to . Czy możesz podać swoje, abym mógł znaleźć różnicę i znaleźć mój błąd?
Cristian Lupascu
@ w0lf Zaloguj się tutaj różnica. Pomijasz ruch z 6 po 1 zakończeniu, w którym rozpoczyna się wyprowadzanie. (Uwaga: mój dziennik zawiera cyfry przed usunięciem ze ścieżki, a twój nie.)
randomra

Odpowiedzi:

3

Rubinowy 229 236

Jest to funkcja, która przyjmuje dwa parametry: tablicę reprezentującą cyfry i liczbę całkowitą reprezentującą długość ścieżki. Zwraca tablicę reprezentującą kolejność, w której cyfry kończą wyścig.

F=->d,l{
i=0
t=d.map{|x|[x,d.size-(i+=1)]}
r=[]
d.cycle.map{|n|
t==[]&&break
(c=t.find{|x,_|x==n})&&(s=n
w=c[1]
o=p
(a=(t-[c]).map{|_,p|p%l}
s-=1;w+=1
a&[w%l]==[]?(o=p;c[1]=w):o||s-=o=1)while s>0
c[1]>=n*l&&(t.delete c;r<<n))}
r}

Przetestuj online: http://ideone.com/KyX5Yu

Edycja: Wymyśliłem kilka sztuczek, aby zapisać więcej znaków.

Wersja bez golfa:

F=->digits,length{
  digit_positions = digits.map.with_index{|d,i|[d,digits.size-i-1] }

  result = []

  digits.cycle.map{|n|
    break if digit_positions==[]
    crt = digit_positions.find{|x,_|x==n}
    next unless crt

    steps_left = n
    pos = crt[1]
    taking_over = false

    while steps_left > 0
      other_pos = (digit_positions-[crt]).map{|_,p|p%length}

      steps_left-=1
      pos += 1

      if other_pos.include? (pos%length)
        steps_left -= 1 unless taking_over
        taking_over = true
      else
        taking_over = false
        crt[1] = pos
      end
    end

    if crt[1] >= n*length
      digit_positions.delete(crt)
      result<<n
    end
  }
  result
}
Cristian Lupascu
źródło
2

Python 2, 345 bajtów

Szkoda, że ​​nie jest krótszy niż @ w0lf, ale co. (Uwaga: duże wcięcia to tabulatory, które tłumaczą się na 4-spacje).

def r(o,l):
 n=len(o);s,t,a,d=dict(zip(o,range(n)[::-1])),-1,{_:0 for _ in o},[]     
 while len(s):
    t+=1;g=o[t%n]
    if g in d:continue
    y,k=s[g],1;i=z=w=0
    for _ in[0]*g:
     i+=1;m=y+i;e,p=m%l,m/l
     if-~a[g]+w>=g<d>m>=l:a[g]+=1;del s[g];d+=[g];break
     if e in s.values()and e!=y:i-=k;k=0
     else:k,s[g],(w,z)=1,e,[(w,z),(z,p)][z<p]
    a[g]+=z
 print d
sirpercival
źródło
0

oto mój magiczny wyściełany kod

C (457 430b)

int v(int*M,int m){
int i,n,c,d,e=32,f=48,u=0,g=10,h,k,r,l=m,j;char a,*b=&a,*B,V[m];
for (i=0;u<m*m*m;i=(++u%m),*B=*b=(u<=l)?*b:e,b=B=&a)
printf("%c%c",0*(V[i]=(u<l?u>=(r=l-sizeof(M)/4)?M[u-r]+f:e:V[i])),((((V[c=(((V[i]=u<l?e:V[i])-f)/10<u/m)?j>=0&h<i|((h=(j=strchr(V+((k=(m+(d=(i-(V[i]-f)%g+1)))%m)),e)-V)<0?(int)(strchr(V,e)-V):(int)j)>=k)*(k>i)?h:m :m])=((V[c]==e)?(*(b=V+i)+(d<0)*g):V[c])))-f)%11==0?(*(B=V+c)-f)%g+f:0);
getch();
}

Uwaga : wymaga dalszej poprawy ...

EDYCJA: kod skrócony ... - sizeof (int) = 4, funkcja = v, nadal pozostaje zmienna do zrobienia.

Abr001am
źródło
Moje C jest zardzewiałe, ale te połączenia sizeofwydają się być zastąpione magiczną liczbą. Może nie byłby tak przenośny, ale hej - to jest golf golfowy.
DLosc
Twój kod wydaje się mieć długość 453 znaków, a nie 457. Myślę też, że możesz go skrócić, usuwając niepotrzebne białe znaki i nadając funkcji krótszą nazwę.
Cristian Lupascu
Cóż, dziękuję za propozycje, ale najważniejsze dla mnie, udało mi się spakować całość w dwóch funkcjach, dla pętli i printf, jedynej wady, na jaką się natknąłem, program drukuje puste znaki zamiast zera. ale wyścig nadal kończy się poprawnie, jeśli odrzucimy te bezsilne cyfry pustej betweed
Abr001am
Zmienne Iirc są domyślnie int. Tak więc: v(int*M,int m){e=32;f=48;u=0;l=m;char a,... Prawie cała ta biała spacja jest niepotrzebna; ,V[m];for(i=0;... )printf(... );getch();}.
wizzwizz4