Carrera de los dígitos

16

Debería escribir un programa o función que dé un orden de inicio de enteros positivos distintos de un dígito y la longitud de la pista como salidas de entrada o devuelva el orden final de los números.

La entrada [5,1,2,6,7] and 14define la siguiente raza:

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

Reglas de la carrera.

  • La pista se envuelve y los dígitos pueden ir varias vueltas.
  • El orden de los pasos es cíclico y se basa en la posición inicial. En nuestro ejemplo 5 1 2 6 7 5 1 2 ....
  • No puede haber múltiples dígitos en la misma posición.
  • Cada dígito tiene una velocidad de digit_valuecelda por paso. Adelantar un dígito o un bloque continuo de dígitos cuesta un paso adicional. Si el dígito no tiene la velocidad necesaria para eso, se detendrá antes del (bloque de) dígito (s). Ejemplos:

    [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
    
  • Cada dígito tiene que dar digit_valuevueltas antes de que termine. Se completa una vuelta cuando queda la última celda de la pista. Un dígito terminado se elimina de la pista.

  • Tenga en cuenta que un dígito puede alcanzar su posición inicial varias veces a través de un paso y completar varias vueltas.

Entrada

  • Una lista de enteros positivos distintos de un dígito ( 1..9) con al menos un elemento y un solo entero positivo, mayor que la longitud de la lista, la longitud de la pista.

Salida

  • Una lista de dígitos en el orden en que terminaron en cualquier formato inequívoco.

Ejemplos

Un ejemplo visual paso a paso para la entrada 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

Ejemplos en formato 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]

Este es el código de golf, por lo que gana la entrada más corta.

randomra
fuente
Presumiblemente, la matriz de entrada no puede tener elementos duplicados? Se ve de esa manera, pero no veo esa condición explícitamente.
Andrew
@ Andrew Sí, no puede haber dígitos duplicados. Editado la pregunta. Gracias.
randomra
Para el caso de prueba n. ° 6 (longitud = 17) obtengo un resultado ligeramente diferente (últimos dos dígitos invertidos). Me preguntaba dónde está mi error. Mi registro de carrera es este . ¿Puede proporcionarme el suyo para que pueda diferenciar y encontrar mi error?
Cristian Lupascu
@ w0lf Log diferencia aquí. Se salta el movimiento con 6 después de que 1 termina donde comienza la derivación. (Tenga en cuenta que mi registro contiene los dígitos antes de eliminarlos de la pista y el suyo no.)
randomra

Respuestas:

3

Rubí 229 236

Esta es una función que toma dos parámetros: una matriz que representa los dígitos y un int que representa la longitud de la pista. Devuelve una matriz, que representa el orden en que los dígitos terminan la carrera.

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}

Pruébelo en línea: http://ideone.com/KyX5Yu

Editar: descubrí algunos trucos para guardar más caracteres.

Versión sin golf:

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
fuente
2

Python 2, 345 bytes

Lástima que no sea más corto que @ w0lf, pero como sea. (Tenga en cuenta que las sangrías grandes son pestañas, que se traducen en 4 espacios cuando publico).

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
fuente
0

aquí está mi código mágico acolchado

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

Nota : necesita más mejoras ...

EDITAR: código acortado ... - sizeof (int) = 4, function = v, aún queda alguna variable que reemplazar para hacer.

Abr001am
fuente
Mi C está oxidada, pero sizeofparece que esas llamadas podrían ser reemplazadas por un número mágico. Tal vez no sería tan portátil, pero bueno, este es el código golf.
DLosc
Su código parece tener 453 caracteres de largo, no 457. Además, creo que puede acortarlo aún más eliminando espacios en blanco innecesarios y dando un nombre más corto a la función.
Cristian Lupascu
bueno, gracias por las propuestas, pero lo importante para mí es que logré empaquetar todo en dos funciones, para loop e printf, la única falla que alenté, el programa sigue imprimiendo caracteres vacíos en lugar de nulos. pero la carrera todavía termina correctamente si eliminamos ese vacío impotente entre dígitos
Abr001am
Las variables Iirc son int por defecto. Entonces: v(int*M,int m){e=32;f=48;u=0;l=m;char a,... Además, casi todo ese espacio en blanco es innecesario; ,V[m];for(i=0;... )printf(... );getch();}.
wizzwizz4