Ekspresi terpendek untuk {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}

24

Daftar bilangan bulat yang diberikan {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4} . Bagi mereka yang tertarik angka-angka ini digunakan dalam perhitungan hari kerja.

Hari Kerja = (m[n] + d + y + y>>2 + y/400 - y/100) % 7;, di mana m[n]- ekspresi yang saya cari, d- hari dalam sebulan, y-year - (month <= 2) .

Bangun ekspresi yang terdiri dari operator aritmatika, logika, dan bitwise, yang akan menghasilkan bilangan nbulat integer positif msehingga m % 7sama dengan angka ke-n dalam daftar.

Cabang, operator ternary, pencarian tabel dan pointer tidak diperbolehkan.

Nilai:
1 - untuk | & ^ ~ >> <<operator
1.1 - untuk + - < > <= >= == != ! && ||operator
1.2 - untuk *operator
1.4 - untuk / %operator

Jawab dengan kemenangan skor terendah.

Secara pribadi saya telah menemukan:

(41*n)>>4+((n+61)>>4)<<2dengan skor 6.4. Saya pikir ini akan sulit ditemukan sehingga disediakan ekspresi sendiri untuk memulai.

Somnium
sumber
Saya kira array dereferencing (dan kerabat) juga tidak diperbolehkan?
John Dvorak
Oh, ya tentu saja, saya telah mengedit pertanyaannya.
Somnium
6
Pertanyaannya akan sangat ditingkatkan oleh beberapa motivasi. Dari mana angka-angka itu berasal?
Peter Taylor
table lookupsUngkapan menarik saya kira ...
16ıʇǝɥʇu
4
Mengapa tidak menghitung% 7 dalam skor? Mungkin ada solusi lain yang tidak menggunakan%. Apakah nol positif , negatif, keduanya atau tidak sama sekali?
Thomas Weller

Jawaban:

34

2 2.2

Saya suka aritmatika presisi sewenang-wenang.

0x4126030156610>>(n<<2)

Atau, jika Anda tidak suka hex,

1146104239711760>>(n<<2)

Uji:

print([(0x4126030156610>>(n<<2))%7 for n in range(1,13)])
[0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
isaacg
sumber
Bisakah Anda membuat tabel pencarian 4*nsaja, dan menyimpan 0,2 poin dengan menuliskannya n<<2?
xnor
@xnor Tentu Saja! Hanya untuk beralih dari oktal ke heksadesimal. Sec.
isaacg
Keren. Saya cukup yakin tidak ada yang bisa melakukan lebih baik karena itu akan memerlukan hanya menggunakan satu operasi, dan mereka semua tampaknya memiliki struktur mod terlalu banyak 7. Kandidat terbaik saya dari divisi lantai integer const/nmengalami kontradiksi dengan n=4dan n=8.
xnor
@xnor Satu lagi yang dekat adalah const%nyang bisa memuaskan semuanya kecuali n = 1,2 dan 3.
isaacg
Saya akan melakukan hal yang sama, tetapi Anda mengalahkan saya untuk itu ...
17ıʇǝɥʇu
32

2.0

(127004 >> i) ^ 60233

atau (skor 2.2):

(i * 3246) ^ 130159

Semua ditemukan dengan kekerasan :-)

Arnaud
sumber
Karena ini memiliki skor yang sama dengan jawaban isaacg, tetapi tidak menggunakan bilangan bulat 64-bit, saya memilih ini sebagai jawaban yang diterima. Terimakasih untuk jawaban!
Somnium
8
@ user2992539 Meskipun menyenangkan bahwa jawaban ini menggunakan bilangan bulat 32-bit, Anda tidak menentukan kriteria ini dalam tantangan Anda, yang membuat jawaban isaacg benar-benar valid. Oleh karena itu, kedua jawaban itu sesuai dan saya pikir adil untuk menerima jawaban pertama yang mendapatkan skor ini. (Kudos to Super Chafouin, +1!)
Martin Ender
@ m.buettner, saya harus setuju dengan Anda. Lain kali, saya akan lebih berhati-hati dengan deskripsi dan pemilihan jawaban.
Somnium
Untuk dipelajari orang lain, dapatkah Anda menguraikan bagaimana Anda melakukan perhitungan brute force?
Thomas Weller
@ Thomas Saya baru saja membuat forloop ganda , menguji semua nilai p, q untuk formula (p >> i) ^ q, kemudian pergi untuk minum kopi, dan 10 mn setelah datang untuk membaca hasilnya.
Arnaud
8

35.3

Saya menduga ini mungkin metode yang paling tidak efisien untuk membuat daftar:

1.7801122128869781e+003 * n - 
1.7215267321373362e+003 * n ^ 2 + 
8.3107487075415247e+002 * n ^ 3 - 
2.0576746235987866e+002 * n ^ 4 + 
1.7702949291688071e+001 * n ^ 5 + 
3.7551387326116981e+000 * n ^ 6 - 
1.3296432299817251e+000 * n ^ 7 + 
1.8138635864087030e-001 * n ^ 8 - 
1.3366764519057219e-002 * n ^ 9 + 
5.2402527302299116e-004 * n ^ 10 - 
8.5946393615396631e-006 * n ^ 11 -
7.0418841304671321e+002

Saya baru saja menghitung regresi polinomial. Saya tergoda untuk melihat metode mengerikan apa yang bisa dicoba.

Khususnya, saya bisa menghemat 3,3 poin jika hasilnya dibulatkan. Pada titik ini, saya pikir itu tidak penting.

lochok
sumber
5

3.2

Solusi berbasis nol:

7 & (37383146136 >> (i*3))

Satu solusi berbasis:

7 & (299065169088 >> (i*3))

Saya awalnya berpikir bahwa %7operasi akan dihitung juga dan %menjadi operasi yang mahal di sini, saya mencoba menyelesaikannya tanpa itu.

Saya sampai pada hasil 3,2 seperti ini:

// Construction of the number
// Use 3 bits per entry and shift to correct place
long c = 0;
int[] nums = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
for (int i = nums.Length - 1; i >= 0; i--)
{
    c <<= 3;
    c += nums[i];
}
// c = 37383146136

// Actual challenge
for (int i = 0; i < 13; i++)
{
    Console.Write("{0} ",7 & 37383146136 >> i*3);
}

Saya akan tertarik pada optimasi menggunakan pendekatan ini (tanpa %). Terima kasih.

Thomas Weller
sumber
Ini keren, mungkin ini akan membantu saya suatu hari nanti) Bagaimana menurut Anda, mungkin saya harus membuat pertanyaan terpisah untuk meminimalkan seluruh rumus?
Somnium
1
Bagaimana dengan (0426415305230 >> (i*3)) & 7? Anda dapat melihat digit output dalam urutan terbalik.
CJ Dennis
@ CJDennis: Saya pikir tidak ada angka oktal di C #.
Thomas Weller
Saya pikir itu hanya C? Saya tidak bisa melihat referensi lain ke C #.
CJ Dennis
0

Python (3)

Karena ada beberapa dari pertanyaan-pertanyaan ini hari ini, saya memutuskan untuk membuat program untuk secara otomatis menyelesaikannya dalam 3 (atau 2) token. Inilah hasil untuk tantangan ini:

G:\Users\Synthetica\Anaconda\python.exe "C:/Users/Synthetica/PycharmProjects/PCCG/Atomic golfer.py"
Input sequence: 0 3 2 5 0 3 5 1 4 6 2 4
f = lambda n: (72997619651120 >> (n << 2)) & 15
f = lambda n: (0x426415305230L >> (n << 2)) & 15
f = lambda n: (0b10000100110010000010101001100000101001000110000 >> (n << 2)) & 15

Process finished with exit code 0

Bukti bahwa ini bekerja:

f = lambda n: (72997619651120 >> (n << 2)) & 15

for i in range(12):
   print i, f(i)

0 0
1 3
2 2
3 5
4 0
5 3
6 5
7 1
8 4
9 6
10 2
11 4
ɐɔıʇǝɥʇu
sumber
Bagaimana solver Anda mempertimbangkan biaya operan?
Thomas Weller
@ Thomas. Tidak, itu akan selalu menggunakan shift kanan, mungkin shift kiri (jika nilainya tidak 1 bit) dan sebuah &.
ɐɔıʇǝɥʇuʎ