Matematika Metagolf Mania!

12

Spesifikasi Mathemania:

Setiap bagian dari kode Mathemania dimulai dengan angka 2. Dari 2, Anda dapat melakukan operasi berikut:

  • e: Eksponensial. Default perintah ini adalah mengkuadratkan angka.
  • f: Faktorial. Default perintah ini menggunakan faktorial tunggal pada angka ( using f on 2 = 2! = 2).
  • r: Root. Default perintah ini adalah rooting kuadrat angka.
  • c: Fungsi langit-langit.
  • l: Fungsi lantai.

Untuk menghasilkan angka di Mathemania, Anda harus merangkai perintah-perintah ini, yang dilakukan dari kiri ke kanan pada nomor tersebut 2.

Contoh:

ef = (2^2)! = 4! = 24
rl = floor(sqrt(2)) = floor(1.4...) = 1
er = sqrt(2^2) = sqrt(4) = 2
efrrc = ceil(sqrt(sqrt((2^2)!)))
      = ceil(sqrt(sqrt(24)))
      = ceil(sqrt(4.89...))
      = ceil(2.21...)
      = 3

Perintah e, fdan rdapat diubah dengan perintah Mathemania tambahan (yang juga dimulai dengan 2angka "dasar") untuk menghasilkan eksponensial, faktorial, dan akar yang berbeda dengan menempatkan tanda kurung setelah fungsi yang diubah dan menempatkan perintah Mathemania di dalamnya.

Sebagai contoh, untuk mem-kubus angka daripada mengkuadratkannya, Anda dapat menempatkan perintah 3setelah eseperti:

e(efrrc) -> cube a number, "efrrc" = 3

CATATAN: untuk tujuan kita, perintah faktorial ( f) dimulai dengan 2sebagai faktorial tunggal. Jadi jika Anda melakukannya f(efrrc), itu akan dievaluasi menjadi faktorial ganda, bukan faktorial tiga.

Untuk n-faktorial (mis. Faktorial ganda = 2-faktorial, tiga faktorial = 3-faktorial, dll.), Bilangan dasar dikalikan dengan angka yang nkurang dari itu, dan nlebih sedikit dari itu, dan seterusnya sampai angka terakhir tidak dapat dikurangi dengan ntanpa menjadi 0atau negatif.

Sebagai contoh:

7!! = 7 * 5 * 3 * 1 = 105 (repeatedly subtract 2, 1 is the last term as
                           1 - 2 = -1, which is negative)
9!!! = 9 * 6 * 3 = 162 (repeatedly subtract 3, 3 is the last term as
                        3 - 3 = 0, which is 0)

Untuk informasi lebih lanjut, lihat di sini .

Anda dapat memasukkannya di mana saja, dan itu akan diperlakukan oleh Mathemania sebagai fungsi tunggal:

e(efrrc)rc = ceil(sqrt(2^3))
           = ceil(2.82...)
           = 3

Anda juga diizinkan untuk bersarang di dalam satu sama lain:

e(e(e)) = e(4th power)
        = (2^4)th power
        = 16th power

Untuk penerjemah kode Mathemania, klik di sini (sorakan, @ BradGilbertb2gills!)

Tugas:

Tugas Anda adalah membuat program yang, ketika diberi bilangan bulat positif nsebagai input, menghasilkan program Mathemania yang ketika dijalankan, kembali n.

Namun, program Mathemania yang Anda hasilkan harus sekecil (golfed) mungkin, dan skor akhir Anda ditentukan oleh jumlah dari jumlah byte dalam program Mathemania yang dihasilkan dari sampel, yang merupakan bilangan bulat 10,000untuk 10,100. Skor terendah menang.

Aturan dan spesifikasi:

  • Program Anda harus menampilkan program Mathemania yang valid untuk bilangan bulat positif, tetapi hanya angka-angka di antara 10,000dan 10,100akan diuji.
  • Anda tidak diizinkan membuat program Mathemania yang tidak menghasilkan bilangan bulat. Jika Anda melakukannya, program Anda didiskualifikasi.
  • Untuk perintah e, fdan r, kode Mathemania di dalam fungsi-fungsi itu (misalnya e(efrrc), di mana efrrckode di dalam fungsi) harus mengevaluasi ke bilangan bulat positif di atas 2. Jika program Anda tidak mengikuti aturan ini, itu juga didiskualifikasi.
  • Program Anda harus mengembalikan program Mathemania untuk salah satu dari 101 bilangan bulat pengujian paling lama 30 menit dengan laptop modern.
  • Program Anda harus mengembalikan solusi yang sama untuk bilangan bulat apa pun setiap kali dijalankan. Misalnya, ketika suatu program diberikan input 5dan output efrc, itu harus menampilkan bahwa setiap kali input 5diberikan.
  • Anda tidak boleh membuat hard-code solusi apa pun untuk bilangan bulat positif.
  • Untuk memaksimalkan potensi golf pada hasil Anda, program Anda harus dapat menangani bilangan bulat besar yang sewenang-wenang. Ini bukan persyaratan, meskipun semoga berhasil jika bahasa Anda tidak mendukung ini.

Ini adalah , jadi skor terendah menang!

clismique
sumber
2
Saya menulis evaluator untuk bahasa ini di Perl 6 pada TIO Nexus.
Brad Gilbert b2gills
@ BradGilbertb2gills Wow, terima kasih! Saya akan memasang tautan di tantangan.
clismique
Jika inputnya efmisalnya, apakah kode diizinkan untuk "melewati" dan hanya menampilkan hasilnya sebelum efoperasi?
devRicher
@devRicher Jika Anda bermaksud bahwa program "ef" telah dikodekan sebelumnya, maka di bawah aturan saat ini, ya Anda diizinkan untuk melakukan itu, karena "ef" tidak berada dalam kisaran 10.000 hingga 10.100. Saya tidak yakin itu yang Anda maksudkan, dan saya mungkin mengubah aturan karena hardcoding membuat tantangannya terlalu mudah, IMO.
clismique
1
Saya telah menulis sebuah program untuk tantangan ini selama beberapa jam terakhir. Saya pikir saya memiliki kode yang berfungsi, tetapi saya tidak dapat mengujinya dengan benar karena beberapa angka yang dihasilkan oleh faktorial sangat besar dan Python (di mana saya memiliki program dan juru bahasa saya) tidak dapat mengambil akar kuadratnya. Saya tidak yakin apa yang harus dilakukan dengan program ini pada saat ini. Di samping catatan, saya awalnya salah membaca dan berpikir SEMUA kasus uji 101 harus sesuai dalam batas waktu, yang tampaknya hampir mustahil. Siapa pun tampaknya jauh lebih masuk akal.
notjagan

Jawaban:

1

Python 3.5, Skor ??

Sampai sekarang saya tidak memiliki output untuk semua 101 input, tetapi begitu saya menjalankan program untuk semua kasus uji saya akan memperbarui dengan skor saya.

from math import *

memoized = {}
same = {}

def _(mathmania, n):
    memoized[n] = mathmania
    return mathmania

def is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False
    for divisor in range(3, int(sqrt(n)) + 1, 2):
        if n % divisor == 0:
            return False
    return True

def pair_key(pair):
    low, high = pair
    diff = high - low
    if diff == 0:
        return 100
    low_done, high_done, diff_done = low in memoized, high in memoized, diff in memoized
    if high_done and memoized[high] == None or low_done and memoized[low] == None:
        return -1
    return (high_done + diff_done + (diff + 1 == low)) * 33 + low / high

def major_pairs(n):
    for i in range(n, int(sqrt(n)), -1):
        d = n / i
        if i - d < d - 1:
            break
        if d == int(d):
            yield (int(d), i)

def fact_key(pair):
    i, f = pair
    if i in memoized:
        if memoized[i] == None:
            return -1
        return 1
    return i / f

def near_fact(n, level):
    s = 4
    if n in same:
        s = same[n]
    for i in range(s, n ** 2 ** level):
        f = factorial(i)
        if f > (n - 1) ** 2 ** level:
            if f < (n + 1) ** 2 ** level:
                same[n] = i
                yield (i, f)
            else:
                return

def generate_mathmania(n):
    if n in memoized and memoized[n] != None:
        return memoized[n]
    memoized[n] = None
    binx = log(n, 2)
    if binx == int(binx):
        if binx == 2:
            return _("e", n)
        if binx == 1:
            return _("er", n)
        if binx == 0:
            return _("rl", n)
        return _("e(" + generate_mathmania(int(binx)) + ")", n)
    sq = sqrt(n)
    if sq == int(sq):
        return _(generate_mathmania(int(sq)) + "e", n)
    low, high = max(major_pairs(n), key=pair_key)
    if pair_key((low, high)) == -1:
        level = 1
        while True:
            try:
                i, f = max(near_fact(n, level), key=fact_key)
            except:
                level += 1
                continue
            if fact_key((i, f)) == -1:
                return _(generate_mathmania((n - 1) ** 2 + 1) + "rc", n)
            if f == n ** 2 ** level:
                return _(generate_mathmania(i) + "f" + "r" * level, n)
            if f < n ** 2 ** level:
                return _(generate_mathmania(i) + "f" + "r" * level + "c", n)
            return _(generate_mathmania(i) + "f" + "r" * level + "l", n)
    if low != 1:
        if low == high:
            return _(generate_mathmania(low) + "e", n)
        if high - low == 1:
            return _(generate_mathmania(high) + "f", n)
        return _(generate_mathmania(high) + "f(" + generate_mathmania(high - low + 1) + ")", n)
    good = None
    for i in range(n ** 2 - 1, (n - 1) ** 2, -1):
        if i in memoized:
            return _(generate_mathmania(i) + "rc", n)
        if not is_prime(i):
            good = i
    if good:
        return _(generate_mathmania(good) + "rc", n)
    for i in range((n + 1) ** 2 - 1, n ** 2, -1):
        if i in memoized:
            return _(generate_mathmania(i) + "rl", n)
        if not is_prime(i):
            good = i
    if good:
        return _(generate_mathmania(good) + "rl", n)
    return _(generate_mathmania((n - 1) ** 2 + 1), n)

Selain itu, saya tidak dapat memverifikasi output dari beberapa kasus uji yang saya coba karena ukuran angka belaka, dan pada saat itu interpreter online @ BradGilbertb2gills habis. Semoga semua output bekerja.

notjagan
sumber
Saya memiliki seorang juru bahasa di Python 2 (mungkin 3) yang seharusnya dapat menangani presisi yang sewenang-wenang di sini . Salin dan tempel ke IDE Anda untuk menjalankannya.
clismique
Apa saja beberapa output sehingga saya bisa mengoptimalkannya.
Brad Gilbert b2gills