Expresión más corta para {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}

24

Lista dada de enteros {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}. Para aquellos interesados, estos números se utilizan en el cálculo de los días laborables.

Día de la semana = (m[n] + d + y + y>>2 + y/400 - y/100) % 7;, donde m[n]- expresión que estoy buscando, d- día del mes, y- year - (month <= 2).

Construya una expresión que conste de operadores aritméticos, lógicos y bit a bit, que generarán un número nentero positivo mpara que sea m % 7igual al n-ésimo número en la lista.

No se permiten ramas, operadores ternarios, búsquedas de tablas y punteros.

Puntuación:
1 - para | & ^ ~ >> <<operadores
1.1 - para + - < > <= >= == != ! && ||operadores
1.2 - para *operadores
1.4 - para / %operadores

Responda con la puntuación más baja gana.

Personalmente he encontrado:

(41*n)>>4+((n+61)>>4)<<2con puntaje 6.4. Pensé que esto sería difícil de encontrar, así que proporcioné una expresión propia para comenzar.

Somnium
fuente
Supongo que la desreferenciación de matrices (y los familiares) tampoco está permitida.
John Dvorak
Oh, sí, por supuesto, he editado la pregunta.
Somnium
66
La pregunta mejoraría en gran medida por alguna motivación. ¿De dónde vienen esos números?
Peter Taylor
table lookupsRedacción interesante supongo ...
ɐɔıʇǝɥʇuʎs
44
¿Por qué no contar el% 7 en el puntaje? Quizás haya otra solución que no use%. ¿Es cero positivo , negativo, ambos o nada?
Thomas Weller

Respuestas:

34

2 2.2

Me encanta la aritmética de precisión arbitraria.

0x4126030156610>>(n<<2)

O, si no te gusta el maleficio,

1146104239711760>>(n<<2)

Prueba:

print([(0x4126030156610>>(n<<2))%7 for n in range(1,13)])
[0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
isaacg
fuente
¿Podrías hacer una tabla de búsqueda con ella 4*ny ahorrar 0,2 puntos escribiéndola como n<<2?
xnor
@xnor ¡Absolutamente! Solo para cambiar de octal a hexadecimal. Igual que sec.
isaacg
Guay. Estoy bastante convencido de que nada puede mejorar porque requeriría usar solo una operación, y todos parecen tener demasiada modificación de estructura 7. Mi mejor candidato para la división de piso entero se const/nencuentra con una contradicción con n=4y n=8.
xnor
@xnor Otro cercano es el const%nque podría satisfacer todo excepto n = 1,2 y 3.
isaacg
Iba
32

2,0

(127004 >> i) ^ 60233

o (puntaje 2.2):

(i * 3246) ^ 130159

Todo encontrado con fuerza bruta :-)

Arnaud
fuente
Como tiene el mismo puntaje que la respuesta de Isaac, pero no usa enteros de 64 bits, elijo esto como respuesta aceptada. ¡Gracias por su respuesta!
Somnium
8
@ user2992539 Si bien es bueno que esta respuesta use enteros de 32 bits, no especificó este criterio en su desafío, lo que hace que la respuesta de isaacg sea perfectamente válida. Por lo tanto, las dos respuestas empatan y creo que es justo aceptar la primera que obtuvo este puntaje. (¡Felicitaciones a Super Chafouin, sin embargo, +1!)
Martin Ender
@ m.buettner Tengo que estar de acuerdo contigo. La próxima vez, tendré más cuidado con la descripción y la selección de respuestas.
Somnium
Para que otros aprendan, ¿podría explicar cómo hizo el cálculo de la fuerza bruta?
Thomas Weller
@Thomas Acabo de hacer un doble forbucle, probando todos los valores p, q para la fórmula (p >> i) ^ q, luego fui a tomar un café y 10 minutos después llegué a leer los resultados.
Arnaud
8

35,3

Sospecho que este puede ser el método menos eficiente para crear la lista:

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

Acabo de calcular la regresión polinómica. Estoy tentado de ver qué otro método terrible podría intentarse.

Cabe destacar que podría ahorrar 3,3 puntos si el resultado fuera redondeado. En este punto, no creo que eso importe.

lochok
fuente
5

3.2

Solución basada en cero:

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

Una solución basada:

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

Inicialmente pensé que la %7operación también se contabilizaría y, al %ser una operación costosa aquí, traté de resolverla sin ella.

Llegué a un resultado de 3.2 como este:

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

Me interesarían las optimizaciones utilizando este enfoque (sin %). Gracias.

Thomas Weller
fuente
Esto es genial, tal vez esto me ayude algún día) ¿Cómo crees que tal vez debería crear una pregunta por separado para minimizar la fórmula completa?
Somnium
1
¿Qué tal (0426415305230 >> (i*3)) & 7? Puede ver los dígitos de salida en orden inverso.
CJ Dennis
@CJDennis: Creo que no hay números octales en C #.
Thomas Weller
Pensé que era solo C? No puedo ver ninguna otra referencia a C #.
CJ Dennis
0

Pitón (3)

Como hay bastantes de estas preguntas en estos días, decidí hacer un programa para resolverlas automáticamente en 3 (o 2) tokens. Aquí está el resultado de este desafío:

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

Prueba de que esto funciona:

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
fuente
¿Cómo considera su solucionador el costo de los operandos?
Thomas Weller
@ThomasW. No lo hace, siempre usará un desplazamiento a la derecha, posiblemente un desplazamiento a la izquierda (si los valores no son de 1 bit) y un &.
18ıʇǝɥʇuʎs