Seberapa kuat angka-angka nonary?

10

Anda diberi integer non-negatif (basis 9) yang terdiri dari digit 0 hingga 8 seperti biasa. Namun jumlah digit dalam angka ini (tanpa nol di depan) adalah kotak prefek.

Karena itu, jumlahnya dapat diatur dalam kotak persegi (dengan urutan bacaan masih dipertahankan).

Contoh dengan 1480 (1125 basis 10):

14
80

Sekarang mari kita setiap digit dalam grid nonary seperti itu menunjukkan gerakan ke ruang grid lain (dengan kondisi batas periodik ):

432
501
678

Ini mengatakan itu

0 = stay still
1 = move right
2 = move right and up
3 = move up
...
8 = move right and down

Jadi, jika dalam grid 1480 Anda mulai dari 4, Anda kemudian bergerak ke atas (ingat pbc) dan pergi ke 8, yang berarti Anda bergerak ke kanan dan ke bawah kembali ke 4, memulai siklus dengan periode 2.

Secara umum proses ini dilanjutkan sampai Anda mendapatkan 0 atau siklus diperhatikan. (A 0 dianggap sebagai siklus dengan periode 1.)

Dalam kasus 1480, periode akhirnya mencapai pada masing-masing 4 digit awal 2 2 2 1masing - masing.

Untuk kisi yang lebih besar angka-angka ini mungkin lebih besar dari 8, tetapi kita masih dapat menggunakannya sebagai "digit" dalam angka nonary baru (hanya koefisien 9 ^ seolah-olah mereka digit):

2*9^3 + 2*9^2 + 2*9 + 1 = 1639 (base 10) = 2221 (base 9)

Kami akan menyebutnya kekuatan dari nomor nonary aslinya. Jadi kekuatan 1480 adalah 1639 (basis 10) atau, setara, 2221 (basis 9).

Tantangan

Tuliskan program terpendek yang memberitahukan apakah kekuatan angka nonary lebih besar dari, kurang dari, atau sama dengan angka nonary itu sendiri. (Anda tidak perlu menghitung kekuatannya.)

Input akan berupa nomor nonary non-negatif yang berisi angka kuadrat (dan tidak ada angka nol di depan selain kasus khusus 0 itu sendiri). Itu harus berasal dari baris perintah atau stdin.

Outputnya harus masuk ke stdout sebagai:

G if the strength is larger than the original number (example: 1480 -> strength = 2221)
E if the strength is equal to the original number (example: 1 -> strength = 1)
L if the strength is less than the original number (example: 5 -> strength = 1)

Tantangan Bonus Menyenangkan:
Apa input tertinggi yang dapat Anda temukan yang setara dengan kekuatannya? (Apakah ada batasan?)


sumber
Adapun input, apakah itu diberikan sebagai angka desimal digit yang sama dengan angka nonary atau sebagai representasi desimal (atau biner) dari angka nonary? yaitu: untuk 1480 (bukan) apakah inputnya menjadi 1480 atau 1125?
overactor
@overactor Dalam format nonary.
2
Saya cukup yakin bahwa tidak seorang pun akan menemukan input yang lebih tinggi yang sama dengan kekuatannya daripada 10 ^ 71-1 (non) yaitu, angka 64 digit yang hanya terdiri dari 8
overactor
@ overactor Mungkin saja dengan siklus periode lebih besar dari 8, saya pikir.
Martin Ender
@ MartinBüttner saya akan sangat terkesan jika Anda menemukan salah satunya.
overactor

Jawaban:

2

Python 2, 213 209 202

Sunting: Dihapus hubungan arus pendek, yang kadang-kadang salah. Lihat di bawah.

(Sebagian besar) Algoritma yang sama dengan @ KS, tetapi sangat banyak golf.

n=`input()`
s=int(len(n)**.5)
c=0
for i in range(s*s):
 a=[]
 while(i in a)<1:a+=[i];x='432501678'.find(n[i]);i=(i+x%3-1)%s+((i/s+x/3-1)%s)*s
 c=c*9+len(a)-a.index(i)
d=long(n,9)
print'EGL'[(c>d)-(c<d)]

Golf:

  • 213: Solusi hubungan pendek, cacat.

  • 209: Solusi kerja pertama.

  • 202: Menggabungkan dua string lookup menjadi satu.

Sunting: Saya baru menyadari bahwa program ini, dan juga KSab, cacat karena mengabaikan panjang siklus multidigit. Contoh kegagalan:

3117
2755
3117
7455

Sementara 3 memiliki panjang siklus 2, dan dengan demikian algoritma di atas hubung singkat ke 'L', ini sebenarnya harus mengembalikan 'G', karena panjang siklus 14 pada digit kedua lebih dari mengatasi itu. Karena itu saya telah mengubah program. Itu juga menjadi lebih pendek, cukup lucu. Untuk menguji program Anda, gunakan 3117275531177455. Itu harus kembali G.

isaacg
sumber
Wow saya pikir saya bermain golf cukup adil tetapi Anda melakukan beberapa hal yang cukup pintar di sana.
KSab
@Tab Terima kasih - algoritma Anda sangat pintar untuk memulai - Saya tidak bisa menemukan cara yang lebih baik untuk melakukannya.
isaacg
2

Python 296

Sebenarnya tidak terlalu efisien, hanya memeriksa digit sebanyak yang diperlukan.

n=raw_input();s=int(len(n)**.5);t=0
for i in range(s**2):
    l=[]
    while i not in l:l.append(i);c=n[i];i=(i%s+(-1 if c in'456'else 1 if c in'218'else 0))%s+((i/s+(-1 if c in'432'else 1 if c in'678'else 0))%s)*s
    t=t*9+len(l)-l.index(i)
print'EGL'[cmp(t,long(n,9))]

Adapun angka sama dengan kekuatan mereka, saya pikir satu-satunya solusi adalah, untuk setiap N x N persegi hingga N = 8 persegi yang mengandung N di setiap ruang. Pemikiran saya adalah karena setiap angka dalam satu lingkaran harus memiliki angka yang sama (panjang lingkaran), setiap loop harus semuanya dalam satu arah. Ini tentu saja berarti bahwa ukuran loop harus N (dan setiap elemen harus N). Saya cukup yakin bahwa logika ini dapat diterapkan untuk kuadrat dan loop dari berbagai ukuran, yang berarti tidak ada kuadrat yang sama dengan kekuatan mereka selain yang pertama 8.

KSab
sumber
Meskipun tidak mungkin, loop mungkin lebih besar dari 8.
overactor
2
Saya pikir ini memberikan hasil yang salah 3117275531177455, karena ukuran lingkaran lebih besar dari 8. Lihat posting saya.
isaacg
1
@isaacg Oh saya tidak melihat itu, saya mengubahnya untuk membuatnya bekerja tetapi saya tidak akan mencoba dan golf lebih jauh karena itu akan cukup hanya menyalin jawaban Anda. Oh dan saya pikir Anda dapat meningkatkan dua baris terakhir Anda dengan menggunakan cmp.
KSab
1

CJam - 81

q:X,:L,{[L2*{_[_Lmqi:Smd@X=432501678s#3md]2/z{~+(S+S%}%Sb}*]L>_&,\X=~-}%9bg"EGL"=

Cobalah di http://cjam.aditsu.net/

Mungkin bisa bermain golf lagi.

aditsu berhenti karena SE adalah JAHAT
sumber
0

Lua - Belum main golf

Hanya menempatkan di sini untuk diamankan. Saya akan bermain golf (dan menerapkan "Untuk grid yang lebih besar angka-angka ini mungkin lebih besar dari 8, tetapi kita masih dapat menggunakannya sebagai" digit "") nanti. Namun bekerja.

d={{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}}
d[0]={0,0}ssd=''
n=arg[1]
q=math.sqrt(#n)t={}

    for y=1,q do
    table.insert(t,y,{})
    for x =1,q do
        v=(y-1)*q+x
        table.insert(t[y],x,n:sub(v,v)+0)
        io.write(t[y][x])
    end
end
for y=1,q do
    for x=1,q do
        cx=x cy=y pxy=''sd=0
        while pxy:match(cx..':%d*:'..cy..' ')==nil do
            pxy=pxy..cx..':'..sd..':'..cy.." "
            ccx=cx+d[t[cx][cy]][2]
            ccy=cy+d[t[cx][cy]][1]
            cx=ccx cy=ccy
            if cx<1 then cx=q elseif cx>q then cx=1 end
            if cy<1 then cy=q elseif cy>q then cy=1 end
            sd=sd+1
        end
        dds=(pxy:sub(pxy:find(cx..':%d+:'..cy)):match(':%d*'))
        ssd=ssd..(sd-dds:sub(2))
    end
end
print(ssd)
nn=tonumber(n,9) tn=tonumber(ssd,9)
if tn>nn then print("G") elseif tn==nn then print("E") else print("L") end
AndoDaan
sumber