Expressão mais curta para {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}

24

Dada lista de números inteiros {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}. Para aqueles interessados, esses números são usados ​​no cálculo dos dias úteis.

Dia da semana = (m[n] + d + y + y>>2 + y/400 - y/100) % 7;, onde m[n]- expressão que estou procurando, d- dia do mês, y- year - (month <= 2).

Construa a expressão que consiste em operadores aritméticos, lógicos e bit a bit, que produzirão um número ninteiro positivo mpara que m % 7seja igual ao n-ésimo número na lista.

Ramos, operadores ternários, pesquisas de tabela e ponteiros não são permitidos.

Pontuação:
1 - para | & ^ ~ >> <<operadores
1.1 - para + - < > <= >= == != ! && ||operadores
1.2 - para *operador
1.4 - para / %operadores

Responda com vitórias mais baixas.

Pessoalmente eu encontrei:

(41*n)>>4+((n+61)>>4)<<2com pontuação 6.4. Eu pensei que isso seria difícil de encontrar, de modo a fornecer uma expressão própria para começar.

Somnium
fonte
Eu acho que desreferenciamento de matriz (e parentes) também não é permitido?
John Dvorak
Ah, sim, claro, eu editei a pergunta.
Somnium
6
A questão seria muito melhorada por alguma motivação. De onde vêm esses números?
22414 Peter Peter Taylor
table lookupsInteressante fraseado, suponho ... #
1616
4
Por que não contar o% 7 na pontuação? Talvez haja outra solução que não esteja usando%. Zero positivo , negativo, ambos ou nada?
21416 Thomas Weller

Respostas:

34

2 2.2

Eu amo aritmética de precisão arbitrária.

0x4126030156610>>(n<<2)

Ou, se você não gosta de hex,

1146104239711760>>(n<<2)

Teste:

print([(0x4126030156610>>(n<<2))%7 for n in range(1,13)])
[0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
isaacg
fonte
Você poderia criar uma tabela de pesquisa 4*ne economizar 0,2 pontos escrevendo-a como n<<2?
Xnor
@xnor Absolutamente! Apenas para mudar de octal para hexadecimal. Assim como seg.
Isaacg
Legal. Estou bastante convencido de que nada pode fazer melhor, porque exigiria o uso de apenas uma operação, e todas elas parecem ter muito mod de estrutura 7. Meu melhor candidato da divisão de piso inteiro const/nentra em contradição com n=4e n=8.
Xnor
@xnor Outro perto é const%n o que poderia satisfazer tudo excepto n = 1,2 e 3.
isaacg
Eu ia fazer a mesma coisa, mas você me venceu ...
Julıʇǝɥʇuʎs 17/07
32

2.0

(127004 >> i) ^ 60233

ou (pontuação 2.2):

(i * 3246) ^ 130159

Todos encontrados com força bruta :-)

Arnaud
fonte
Como isso tem a mesma pontuação que a resposta de isaacg, mas não usa números inteiros de 64 bits, estou escolhendo esta como resposta aceita. Obrigado pela resposta!
Somnium
8
@ user2992539 Embora seja bom que esta resposta use números inteiros de 32 bits, você não especificou esse critério no seu desafio, o que torna a resposta do isaacg perfeitamente válida. Portanto, as duas respostas estão empatadas e acho justo aceitar a primeira que obteve essa pontuação. (Kudos para Super Chafouin, porém, +1!)
Martin Ender
@ m.buettner Eu tenho que concordar com você. Da próxima vez, terei mais cuidado com a descrição e a seleção de respostas.
Somnium
Para que outros aprendam, você poderia elaborar como fez o cálculo da força bruta?
21416 Thomas Weller
@ Thomas Acabei de fazer um forloop duplo , testando todos os valores p, q para a fórmula (p >> i) ^ q, depois fui tomar um café e 10 minutos depois vim ler os resultados.
Arnaud
8

35,3

Eu suspeito que este pode ser o método menos eficiente para criar a 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

Acabei de calcular a regressão polinomial. Estou tentado a ver que outro método terrível poderia ser tentado.

Notavelmente, eu poderia economizar 3,3 pontos se o resultado fosse arredondado. Neste ponto, não acho que isso importe.

Lochok
fonte
5

3.2.

Solução baseada em zero:

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

Uma solução baseada:

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

Inicialmente, pensei que a %7operação seria contada também e% sendo uma operação cara aqui, tentei resolvê-la sem ela.

Cheguei a um 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);
}

Eu estaria interessado em otimizações usando essa abordagem (sem %). Obrigado.

Thomas Weller
fonte
Isso é legal, talvez isso me ajude algum dia) Como você acha, talvez eu deva criar uma pergunta separada para minimizar toda a fórmula?
Somnium
11
Que tal (0426415305230 >> (i*3)) & 7? Você pode ver os dígitos da saída na ordem inversa.
CJ Dennis
@CJDennis: Acho que não há números octais em C #.
Thomas Weller
Eu pensei que era apenas C? Não consigo ver nenhuma outra referência ao c #.
CJ Dennis
0

Python (3)

Como existem muitas dessas perguntas atualmente, decidi criar um programa para resolvê-las automaticamente em 3 (ou 2) tokens. Aqui está o resultado para este desafio:

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

Prova de que isso 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
fonte
Como o seu solucionador considera o custo dos operandos?
21416 Thomas Weller
@ThomasW. Não, sempre usará o deslocamento à direita, possivelmente o deslocamento à esquerda (se os valores não forem 1 bit) e um &.
ɐɔıʇǝɥʇuʎs