Race of the Digit

16

Anda harus menulis sebuah program atau fungsi yang memberikan urutan awal bilangan bulat positif satu digit dan panjang lintasan sebagai input output atau mengembalikan urutan selesai angka.

Input [5,1,2,6,7] and 14mendefinisikan perlombaan berikut:

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

Aturan lomba

  • Lintasan membungkus dan angka bisa beberapa putaran.
  • Urutan langkah bersifat siklik dan berdasarkan pada posisi awal. Dalam contoh kita 5 1 2 6 7 5 1 2 ....
  • Tidak ada beberapa digit di posisi yang sama.
  • Setiap digit memiliki kecepatan digit_valuesel per langkah. Melampaui satu digit atau satu blok digit yang terus menerus membutuhkan satu langkah ekstra. Jika digit tidak memiliki kecepatan yang diperlukan untuk itu akan berhenti sebelum (blok) digit. Contoh:

    [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
    
  • Setiap digit harus melewati digit_valueputaran sebelum selesai. Lap selesai ketika sel terakhir dari trek ditinggalkan. Digit yang sudah selesai dihapus dari trek.

  • Perhatikan bahwa digit mungkin mencapai posisi awal beberapa kali melalui langkah dan menyelesaikan beberapa putaran.

Memasukkan

  • Daftar bilangan bulat positif satu digit yang berbeda ( 1..9) dengan setidaknya satu elemen dan satu bilangan bulat positif, lebih besar dari panjang daftar, panjang trek.

Keluaran

  • Daftar digit dalam urutan yang mereka selesaikan dalam format apa pun yang tidak ambigu.

Contohnya

Contoh langkah demi langkah visual untuk 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

Contoh dalam 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]

Ini adalah kode-golf sehingga entri terpendek menang.

randomra
sumber
Agaknya, array input tidak dapat memiliki elemen duplikat? Kelihatannya seperti itu, tetapi saya tidak melihat kondisi yang dinyatakan secara eksplisit.
Andrew
@ Andrew Ya, tidak ada digit duplikat. Mengedit pertanyaan. Terima kasih.
randomra
Untuk kasus uji # 6 (panjang = 17) saya mendapatkan hasil yang sedikit berbeda (dua digit terakhir dibalik). Saya bertanya-tanya di mana kesalahan saya. Log ras saya adalah ini . Bisakah Anda memberikan milik Anda sehingga saya dapat membedakan dan menemukan kesalahan saya?
Cristian Lupascu
@ w0lf Log perbedaan di sini. Anda melompat bergerak dengan 6 setelah 1 selesai di mana derivasi dimulai. (Perhatikan log saya berisi digit sebelum dihapus dari trek dan milik Anda tidak.)
randomra

Jawaban:

3

Ruby 229 236

Ini adalah fungsi yang mengambil dua parameter: array yang mewakili digit dan int yang mewakili panjang trek. Ini mengembalikan array, mewakili urutan digit menyelesaikan balapan.

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}

Uji secara online: http://ideone.com/KyX5Yu

Sunting: Menemukan beberapa trik untuk menghemat lebih banyak karakter.

Versi tidak disatukan:

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

Python 2, 345 byte

Sayang sekali itu tidak lebih pendek dari @ w0lf, tetapi whatev. (Perhatikan bahwa indentasi besar adalah tab, yang diterjemahkan menjadi 4 spasi ketika saya memposting.)

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

di sini adalah kode empuk ajaib saya

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

Catatan : perlu lebih banyak perbaikan ...

EDIT: kode disingkat ... - sizeof (int) = 4, function = v, masih ada beberapa variabel yang harus diganti.

Abr001am
sumber
C saya berkarat, tetapi panggilan itu sizeofsepertinya bisa digantikan dengan angka ajaib. Mungkin itu tidak akan seperti portabel, tapi hei - ini kode golf.
DLosc
Kode Anda tampaknya 453 karakter, bukan 457. Selain itu, saya pikir Anda dapat mempersingkat lebih jauh dengan menghapus spasi yang tidak perlu dan memberikan fungsi nama yang lebih pendek.
Cristian Lupascu
baik terima kasih untuk proposal, tetapi yang penting bagi saya, saya berhasil mengemas semuanya dalam dua fungsi, untuk loop dan printf, satu-satunya kelemahan saya encoutered, program terus mencetak karakter kosong, bukan nil. tetapi perlombaan masih berakhir dengan baik jika kita menyingkirkan angka impotensi yang kosong antara angka
Abr001am
Variabel Iirc adalah int secara default. Jadi: v(int*M,int m){e=32;f=48;u=0;l=m;char a,... Juga, hampir semua spasi putih itu tidak perlu; ,V[m];for(i=0;... )printf(... );getch();}.
wizzwizz4