Expression la plus courte pour {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}

24

Liste donnée d'entiers {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}. Pour ceux qui sont intéressés, ces chiffres sont utilisés dans le calcul en semaine.

Jour de la semaine = (m[n] + d + y + y>>2 + y/400 - y/100) % 7;, où m[n]- expression que je recherche, d- jour du mois, y- year - (month <= 2).

Construisez une expression composée d'opérateurs arithmétiques, logiques et au niveau du bit, qui sortiront pour un entier npositif de mfaçon à ce qu'il m % 7soit le nième nombre dans la liste.

Les branches, les opérateurs ternaires, les recherches de table et les pointeurs ne sont pas autorisés.

Note:
1 - pour les | & ^ ~ >> <<opérateurs
1.1 - pour les + - < > <= >= == != ! && ||opérateurs
1.2 - pour l' *opérateur
1.4 - pour les / %opérateurs

Répondez avec le score le plus bas.

Personnellement, j'ai trouvé:

(41*n)>>4+((n+61)>>4)<<2avec un score de 6,4. Je pensais que ce serait difficile à trouver, à condition de disposer de sa propre expression pour commencer.

Somnium
la source
Je suppose que le déréférencement de tableaux (et les parents) n'est pas autorisé non plus?
John Dvorak
Oh, oui bien sûr, j'ai édité la question.
Somnium
6
La question serait grandement améliorée par une certaine motivation. D'où viennent ces chiffres?
Peter Taylor
table lookups
Formulation
4
Pourquoi ne pas compter le% 7 dans le score? Il existe peut-être une autre solution n'utilisant pas%. Est-ce que zéro est positif , négatif, les deux ou rien?
Thomas Weller

Réponses:

34

2 2,2

J'adore l'arithmétique de précision arbitraire.

0x4126030156610>>(n<<2)

Ou, si vous n'aimez pas l'hexagone,

1146104239711760>>(n<<2)

Tester:

print([(0x4126030156610>>(n<<2))%7 for n in range(1,13)])
[0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
isaacg
la source
Pourriez-vous peut-être créer une table de recherche avec à la 4*nplace et économiser 0,2 point en l'écrivant comme n<<2?
xnor
@xnor Absolument! Juste pour passer d'octal à hexadécimal. Tout aussi sec.
isaacg
Cool. Je suis assez convaincu que rien ne peut faire mieux car cela ne nécessiterait qu'une seule opération, et ils semblent tous avoir trop de structure mod 7. Mon meilleur candidat pour la division des étages entiers const/nest en contradiction avec n=4et n=8.
xnor
@xnor Un autre proche est celui const%nqui pourrait tout satisfaire sauf n = 1,2 et 3.
isaacg
J'allais faire la même chose, mais tu m'as battu ...
ɐɔıʇǝɥʇuʎs
32

2.0

(127004 >> i) ^ 60233

ou (note 2,2):

(i * 3246) ^ 130159

Tous trouvés avec force brute :-)

Arnaud
la source
Puisque cela a le même score que la réponse d'isaacg, mais n'utilise pas d'entiers 64 bits, je choisis cela comme réponse acceptée. Merci de votre réponse!
Somnium
8
@ user2992539 Bien qu'il soit agréable que cette réponse utilise des entiers 32 bits, vous n'avez pas spécifié ce critère dans votre défi, ce qui rend la réponse d'isaacg parfaitement valide. Par conséquent, les deux réponses sont égales et je pense qu'il est juste d'accepter la première qui a obtenu ce score. (Bravo à Super Chafouin, cependant, +1!)
Martin Ender
@ m.buettner Je dois être d'accord avec vous. La prochaine fois, je serai plus prudent avec la description et la sélection des réponses.
Somnium
Pour que d'autres apprennent, pourriez-vous expliquer comment vous avez fait le calcul de la force brute?
Thomas Weller
@Thomas Je viens de faire une double forboucle, testant toutes les valeurs p, q pour la formule (p >> i) ^ q, puis je suis allé prendre un café, et 10 mn après je suis venu lire les résultats.
Arnaud
8

35,3

Je soupçonne que cela peut être la méthode la moins efficace pour créer la liste:

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

Je viens de calculer la régression polynomiale. Je suis tenté de voir quelle autre méthode terrible pourrait être tentée.

Notamment, je pourrais gagner 3,3 points si le résultat était arrondi. À ce stade, je ne pense pas que cela compte.

lochok
la source
5

3.2

Solution basée sur zéro:

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

Une solution unique:

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

J'ai d'abord pensé que l' %7opération serait également prise en compte et %étant une opération coûteuse ici, j'ai essayé de la résoudre sans elle.

Je suis arrivé à un résultat de 3,2 comme ceci:

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

Je serais intéressé par des optimisations utilisant cette approche (sans %). Merci.

Thomas Weller
la source
C'est cool, peut-être que cela m'aidera un jour) Comment pensez-vous que je devrais peut-être créer une question distincte pour la minimisation de la formule entière?
Somnium
1
Et alors (0426415305230 >> (i*3)) & 7? Vous pouvez voir les chiffres de sortie dans l'ordre inverse.
CJ Dennis
@CJDennis: Je pense qu'il n'y a pas de nombre octal en C #.
Thomas Weller
Je pensais que c'était juste C? Je ne vois aucune autre référence à C #.
CJ Dennis
0

Python (3)

Comme il y a beaucoup de ces questions ces jours-ci, j'ai décidé de créer un programme pour les résoudre automatiquement en 3 (ou 2) jetons. Voici le résultat de ce défi:

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

Preuve que cela fonctionne:

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
la source
Comment votre solveur considère-t-il le coût des opérandes?
Thomas Weller
@ThomasW. Ce n'est pas le cas, il utilisera toujours un décalage à droite, éventuellement un décalage à gauche (si les valeurs ne sont pas à 1 bit) et un &.
ɐɔıʇǝɥʇuʎs