Najkrótsze wyrażenie dla {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}

24

Podana lista liczb całkowitych {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}. Dla tych, którzy są zainteresowani, te liczby są wykorzystywane w obliczeniach dnia tygodnia.

Dzień tygodnia = (m[n] + d + y + y>>2 + y/400 - y/100) % 7;, gdzie m[n]- szukam wyrażenia, d- dzień miesiąca, y- year - (month <= 2).

Skonstruuj wyrażenie składające się z operatorów arytmetycznych, logicznych i bitowych, które będą generować dodatnią liczbę ncałkowitą dodatnią, mtak aby była m % 7równa n-tej liczbie na liście.

Oddziały, operatory trójskładnikowe, wyszukiwanie tabel i wskaźniki są niedozwolone.

Ocena:
1 - dla | & ^ ~ >> <<operatorów
1,1 - dla + - < > <= >= == != ! && ||operatorów
1,2 - dla *operatora
1,4 - dla / %operatorów

Odpowiedź z najniższym wynikiem wygrywa.

Osobiście znalazłem:

(41*n)>>4+((n+61)>>4)<<2z wynikiem 6,4. Myślałem, że będzie to trudne do znalezienia, więc pod warunkiem własnego wyrażenia na początek.

Somnium
źródło
Wydaje mi się, że dereferencje tablicowe (i krewnych) też są niedozwolone?
John Dvorak,
O tak, oczywiście, zredagowałem pytanie.
Somnium
6
Pytanie to znacznie poprawiłoby motywacja. Skąd pochodzą te liczby?
Peter Taylor
table lookupsCiekawy frazowanie przypuszczam ...
ɐɔıʇǝɥʇuʎs
4
Dlaczego nie policzyć% 7 w wyniku? Może jest inne rozwiązanie, które nie używa%. Czy zero jest dodatnie , ujemne, jedno czy drugie?
Thomas Weller,

Odpowiedzi:

34

2 2.2

Uwielbiam arytmetykę dowolnej precyzji.

0x4126030156610>>(n<<2)

Lub, jeśli nie lubisz hexa,

1146104239711760>>(n<<2)

Test:

print([(0x4126030156610>>(n<<2))%7 for n in range(1,13)])
[0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
isaacg
źródło
Czy mógłbyś 4*nzamiast tego zrobić tabelę przeglądową i zapisać 0,2 punktu, pisząc ją jako n<<2?
xnor
@xnor Absolutnie! Wystarczy zmienić z ósemkowego na szesnastkowy. Tak jak sek.
isaacg
Fajne. Jestem całkiem przekonany, że nic nie może zrobić lepiej, ponieważ wymagałoby to użycia tylko jednej operacji, a wszystkie wydają się mieć zbyt wiele modyfikacji struktury 7. Mój najlepszy kandydat do podziału na liczby całkowite const/nwpada w sprzeczność z n=4i n=8.
xnor
@xnor Kolejny bliski jest, const%nktóry może zadowolić wszystko oprócz n = 1,2 i 3.
isaacg
Miałem zrobić to samo, ale pobiłeś mnie do tego ...
2014
32

2.0

(127004 >> i) ^ 60233

lub (ocena 2.2):

(i * 3246) ^ 130159

Wszystko znaleziono z brutalną siłą :-)

Arnaud
źródło
Ponieważ ma ten sam wynik co odpowiedź Isaacga, ale nie używa 64-bitowych liczb całkowitych, wybieram tę odpowiedź jako zaakceptowaną. Dziękuję za odpowiedź!
Somnium
8
@ user2992539 O ile to miłe, że ta odpowiedź używa 32-bitowych liczb całkowitych, nie podałeś tego kryterium w swoim wyzwaniu, co sprawia, że ​​odpowiedź isaacga jest całkowicie poprawna. Dlatego te dwie odpowiedzi łączą się i myślę, że sprawiedliwe jest zaakceptowanie pierwszej, która uzyskała ten wynik. (Uznanie dla Super Chafouina, +1!)
Martin Ender
@ m.buettner Muszę się z tobą zgodzić. Następnym razem będę bardziej ostrożny przy wyborze opisu i odpowiedzi.
Somnium
Aby inni mogli się dowiedzieć, czy mógłbyś rozwinąć sposób obliczenia brutalnej siły?
Thomas Weller,
@Thomas Właśnie zrobiłem podwójną forpętlę, testując wszystkie wartości p, q dla formuły (p >> i) ^ q, a potem poszedłem na kawę, a po 10 minutach przyszedłem przeczytać wyniki.
Arnaud,
8

35,3

Podejrzewam, że może to być najmniej wydajna metoda tworzenia listy:

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

Właśnie obliczyłem regresję wielomianową. Kusi mnie, aby zobaczyć, jaką inną okropną metodę można by zastosować.

Mógłbym zaoszczędzić 3,3 punktu, gdyby wynik był zaokrąglony. W tym momencie nie sądzę, żeby to miało znaczenie.

Lochok
źródło
5

3.2

Rozwiązanie oparte na zerach:

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

Jedno oparte rozwiązanie:

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

Początkowo myślałem, że %7operacja również zostanie policzona, a ponieważ %jest to droga operacja, próbowałem ją rozwiązać bez niej.

Doszedłem do wyniku 3.2 takiego:

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

Byłbym zainteresowany optymalizacjami wykorzystującymi to podejście (bez %). Dzięki.

Thomas Weller
źródło
To jest fajne, może kiedyś mi to pomoże) Jak myślisz, może powinienem stworzyć osobne pytanie dotyczące minimalizacji całej formuły?
Somnium
1
Jak o (0426415305230 >> (i*3)) & 7? Możesz zobaczyć cyfry wyjściowe w odwrotnej kolejności.
CJ Dennis
@CJDennis: Myślę, że w C # nie ma liczb ósemkowych.
Thomas Weller
Myślałem, że to tylko C? Nie widzę żadnego innego odniesienia do C #.
CJ Dennis,
0

Python (3)

Ponieważ w dzisiejszych czasach jest ich sporo, postanowiłem stworzyć program, który automatycznie rozwiąże je w 3 (lub 2) tokenach. Oto wynik tego wyzwania:

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

Dowód, że to działa:

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ʎs
źródło
Jak twój solver ocenia koszt argumentów?
Thomas Weller,
@ThomasW. Nie działa, zawsze użyje przesunięcia w prawo, ewentualnie przesunięcia w lewo (jeśli wartości nie są 1-bitowe) i &.
18ıʇǝɥʇuʎs