16
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Presumably, the input array cannot have duplicate elements? It looks that way, but I don't see that condition stated explicitly. \$\endgroup\$ – Andrew May 2 '15 at 15:30
  • \$\begingroup\$ @Andrew Yes, there can't be any duplicate digits. Edited the question. Thanks. \$\endgroup\$ – randomra May 2 '15 at 15:32
  • \$\begingroup\$ 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? \$\endgroup\$ – Cristian Lupascu May 3 '15 at 10:01
  • \$\begingroup\$ @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.) \$\endgroup\$ – randomra May 3 '15 at 10:14
3
\$\begingroup\$

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
}
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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 .

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – DLosc May 6 '15 at 5:57
  • \$\begingroup\$ 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. \$\endgroup\$ – Cristian Lupascu May 6 '15 at 7:00
  • \$\begingroup\$ 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 \$\endgroup\$ – Abr001am May 6 '15 at 8:46
  • \$\begingroup\$ 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();}. \$\endgroup\$ – wizzwizz4 Apr 13 '17 at 9:20

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.