Гонка цифр

16

Вы должны написать программу или функцию, которая задает начальный порядок различных однозначных натуральных чисел и длину дорожки в качестве входных данных или возвращает конечный порядок чисел.

Вход [5,1,2,6,7] and 14определяет следующую расу:

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

Правила гонки

  • Трек оборачивается и цифры могут проходить несколько кругов.
  • Порядок шагов является циклическим и основывается на начальной позиции. В нашем примере 5 1 2 6 7 5 1 2 ....
  • В одной и той же позиции не может быть нескольких цифр.
  • Каждая цифра имеет скорость digit_valueячейки за шаг. Обгон цифры или непрерывный блок цифр стоит один дополнительный шаг. Если цифра не имеет необходимой скорости для этого, она остановится перед (блоком) цифрой (ами). Примеры:

    [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
    
  • Каждая цифра должна пройти digit_valueкруг до того, как она закончится. Круг заканчивается, когда остается последняя ячейка дорожки. Готовая цифра удаляется с трека.

  • Обратите внимание, что цифра может достигать своей начальной позиции несколько раз за шаг и пройти несколько кругов.

вход

  • Список различных однозначных положительных целых чисел ( 1..9), по крайней мере, с одним элементом и одним положительным целым числом, превышающим длину списка и длину дорожки.

Выход

  • Список цифр в порядке их окончания в любом однозначном формате.

Примеры

Визуальный пошаговый пример для ввода 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

Примеры в формате 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]

Это код-гольф, поэтому выигрывает самый короткий вход.

randomra
источник
Предположительно, входной массив не может иметь повторяющиеся элементы? Это выглядит так, но я не вижу этого условия в явном виде.
Андрей
@ Андрей Да, там не должно быть повторяющихся цифр. Отредактировал вопрос. Благодарю.
Рандомра
Для теста № 6 (длина = 17) я получаю немного другой результат (последние две цифры поменялись местами). Мне было интересно, где моя ошибка. Мой гоночный журнал это . Можете ли вы предоставить свои, чтобы я мог найти и найти свою ошибку?
Кристиан Лупаску
@ w0lf Зарегистрируйте разницу здесь. Вы пропускаете перемещение с 6 после 1 окончания, где начинается деривация. (Обратите внимание, что мой журнал содержит цифры перед удалением с трека, а ваши нет.)
randomra

Ответы:

3

Рубин 229 236

Это функция, которая принимает два параметра: массив, представляющий цифры, и int, представляющий длину дорожки. Возвращает массив, представляющий порядок, в котором цифры заканчивают гонку.

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}

Протестируйте это онлайн: http://ideone.com/KyX5Yu

Изменить: выяснил некоторые хитрости, чтобы сохранить еще несколько символов.

Безголовая версия:

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
}
Кристиан Лупаску
источник
2

Python 2, 345 байт

Жаль, что он не короче, чем у @ w0lf, но все равно. (Обратите внимание, что большие отступы - это вкладки, которые переводятся в 4 пробела при публикации).

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
источник
0

вот мой волшебный код

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

Примечание : нужно больше улучшений ...

РЕДАКТИРОВАТЬ: код сокращен ... - sizeof (int) = 4, function = v, все еще остается некоторая переменная, заменяющая на do.

Abr001am
источник
Мой C ржавый, но sizeofкажется, что эти звонки могут быть заменены на магический номер. Может быть, это было бы не так портативно, но эй - это кодовый гольф.
DLosc
Ваш код имеет длину 453 символа, а не 457. Кроме того, я думаю, вы можете сократить его еще больше, удалив ненужные пробелы и присвоив функции более короткое имя.
Кристиан Лупаску
Хорошо, спасибо за предложения, но главное для меня, мне удалось упаковать все это в две функции, для loop и printf, единственный недостаток, который я обнаружил, программа продолжает печатать пустые символы вместо nils. но гонка все равно закончится правильно, если мы отбросим эти важные цифры между
пустотами
Переменные Iirc по умолчанию являются int. Итак: v(int*M,int m){e=32;f=48;u=0;l=m;char a,... Кроме того, почти весь этот пробел является ненужным; ,V[m];for(i=0;... )printf(... );getch();}.
wizzwizz4