# Race of the Digits

You should write a program or function which given a starting order of distinct one-digit positive integers and the length of the track as input outputs or returns the finish order of the numbers.

The input [5,1,2,6,7] and 14 defines the following race:

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


## Rules of the race

• The track wraps around and digits can go multiple laps.
• Order of steps is cyclic and based on the starting position. In our example 5 1 2 6 7 5 1 2 ....
• There can be no multiple digits in the same position.
• Every digit has a speed of digit_value cell per step. Overtaking a digit or a continuous block of digits costs one extra step. If the digit doesn't have the necessary speed for that it will stop before the (block of) digit(s). Examples:

[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

• Every digit has to go digit_value laps before it finishes. A lap is completed when the last cell of the track is left. A finished digit is removed from the track.

• Note that a digit might reach its starting position multiple times through a step and complete multiple laps.

## Input

• A list of distinct one-digit positive integers (1..9) with at least one element and a single positive integer, greater than the length of the list, the length of the track.

## Output

• A list of digits in the order they finished in any unambiguous format.

## Examples

A visual step-by-step example for the input 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


Examples in format 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]


This is code-golf so the shortest entry wins.

• Presumably, the input array cannot have duplicate elements? It looks that way, but I don't see that condition stated explicitly. – Andrew May 2 '15 at 15:30
• @Andrew Yes, there can't be any duplicate digits. Edited the question. Thanks. – randomra May 2 '15 at 15:32
• For test case #6 (length=17) I get a slightly different result (last two digits reversed). I was wondering where my mistake is. My race log is this. Can you please provide yours so I can diff and find my mistake? – Cristian Lupascu May 3 '15 at 10:01
• @w0lf Log difference here. You skip moving with 6 after 1 finishes where the derivation starts. (Note my log contains the digits before removed from the track and yours don't.) – randomra May 3 '15 at 10:14

# Ruby 229 236

This is a function that takes two parameters: an array representing the digits and an int representing the length of the track. It returns an array, representing the order in which the digits finish the race.

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}


Test it online: http://ideone.com/KyX5Yu

Edit: Figured out some tricks to save some more chars.

Ungolfed version:

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
}


# Python 2, 345 bytes

Too bad it's not shorter than @w0lf's, but whatev. (Note that the large indents are tabs, which translate to 4-space when I post.)

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


here is my magical padded code

## 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();
}


Note: it needs more improvement ...

EDIT: code shortened ... - sizeof(int)=4 , function=v , still remains some variable replacing to do .

• My C is rusty, but those calls to sizeof seem like they could be replaced by a magic number. Maybe it wouldn't be as portable, but hey--this is code golf. – DLosc May 6 '15 at 5:57
• Your code seems to be 453 chars long, not 457. Also, I think you can shorten it further by removing unnecessary whitespace and giving the function a shorter name. – Cristian Lupascu May 6 '15 at 7:00
• well thanks for proposals , but the important thing for me , i succeeded to pack the whole thing in two functions , for loop and printf , the only flaw i encoutered , the program keep printing empty characters instead of nils . but the race still ends properly if we knock away that impotant void betweed digits – Abr001am May 6 '15 at 8:46
• Iirc variables are int by default. So: v(int*M,int m){e=32;f=48;u=0;l=m;char a,... Also, almost all of that whitespace is unneccesary; ,V[m];for(i=0;...)printf(...);getch();}. – wizzwizz4 Apr 13 '17 at 9:20