Кратчайшее выражение для {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}

24

Дан список целых чисел {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}. Для тех, кто заинтересован, эти цифры используются при расчете дня недели.

Weekday = (m[n] + d + y + y>>2 + y/400 - y/100) % 7;, где m[n]- выражение, которое я ищу, d- день месяца, y- year - (month <= 2).

Создайте выражение, состоящее из арифметических, логических и побитовых операторов, которые будут выводить целое положительное целое nчисло m, m % 7равное n-му числу в списке.

Ветви, троичные операторы, таблицы и указатели не допускаются.

Оценка:
1 - для | & ^ ~ >> <<операторов
1.1 - для + - < > <= >= == != ! && ||операторов
1.2 - для *оператора
1.4 - для / %операторов

Ответ с наименьшим количеством побед.

Лично я нашел:

(41*n)>>4+((n+61)>>4)<<2с оценкой 6.4. Я думал, что это будет трудно найти, так что при условии собственного выражения для начала.

Somnium
источник
Я думаю, что разыменование массива (и род) также не допускается?
Джон Дворак
О да, конечно, я редактировал вопрос.
Сомниум
6
Вопрос был бы значительно улучшен некоторой мотивацией. Откуда эти цифры?
Питер Тейлор
table lookupsИнтересно фразировка я полагаю ...
ɐɔıʇǝɥʇuʎs
4
Почему бы не посчитать% 7 в счете? Может быть, есть другое решение, не использующее%. Ноль положительный , отрицательный, оба или ничего?
Томас Веллер

Ответы:

34

2 2,2

Я люблю произвольную точность арифметики.

0x4126030156610>>(n<<2)

Или, если вам не нравится гекс,

1146104239711760>>(n<<2)

Тест:

print([(0x4126030156610>>(n<<2))%7 for n in range(1,13)])
[0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
isaacg
источник
Не могли бы вы 4*nвместо этого составить справочную таблицу и сохранить 0,2 балла, записав ее как n<<2?
xnor
@xnor Абсолютно! Просто чтобы переключиться с восьмеричного на шестнадцатеричное. Так же, как с.
Исаак
Круто. Я почти уверен, что ничто не может сделать лучше, потому что это потребует использования только одной операции, и у них, похоже, слишком много структурного мода 7. Мой лучший кандидат на целочисленное деление const/nна полы противоречит n=4и n=8.
xnor
@xnor Еще один близкий, const%nкоторый может удовлетворить все, кроме n = 1,2 и 3.
Исаак
Я собирался сделать то же самое, но ты избил меня до этого ...
Julıʇǝɥʇuʎs
32

2,0

(127004 >> i) ^ 60233

или (оценка 2,2):

(i * 3246) ^ 130159

Все найдено с грубой силой :-)

Arnaud
источник
Поскольку он имеет тот же результат, что и ответ isaacg, но не использует 64-битные целые числа, я выбрал его в качестве принятого ответа. Спасибо за ответ!
Сомниум
8
@ user2992539 Хотя приятно, что в этом ответе используются 32-разрядные целые числа, вы не указали этот критерий в своем задании, что делает ответ isaacg совершенно верным. Поэтому два ответа связаны, и я думаю, что будет справедливо принять первый , получивший этот балл. (Слава Супер Шафуину, тем не менее, +1!)
Мартин Эндер
@ m.buettner Я должен с тобой согласиться. В следующий раз я буду более осторожен с описанием и выбором ответа.
Сомниум
Чтобы другие могли узнать, не могли бы вы рассказать о том, как вы делали расчет грубой силы?
Томас Уэллер
@Thomas Я только что сделал двойной forцикл, протестировав все значения p, q для формулы (p >> i) ^ q, затем пошел пить кофе, и через 10 минут пришел, чтобы прочитать результаты.
Арно
8

35,3

Я подозреваю, что это может быть наименее эффективным методом для создания списка:

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

Я только что рассчитал полиномиальную регрессию. Я испытываю желание увидеть, какой другой ужасный метод может быть предпринят.

Примечательно, что я мог бы сэкономить 3,3 балла, если бы результат был округленным. На данный момент, я не думаю, что это имеет значение.

lochok
источник
5

3,2

Нулевое решение:

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

Одно решение на основе:

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

Сначала я думал, что %7операция будет засчитана, и% будучи здесь дорогостоящей операцией, я пытался решить ее без нее.

Я пришел к результату 3,2, как это:

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

Я был бы заинтересован в оптимизации с использованием этого подхода (без %). Спасибо.

Томас Веллер
источник
Это круто, может быть, это поможет мне когда-нибудь) Как вы думаете, может быть, я должен создать отдельный вопрос для минимизации всей формулы?
Сомниум
1
Как насчет (0426415305230 >> (i*3)) & 7? Вы можете увидеть выходные цифры в обратном порядке.
CJ Деннис
@CJDennis: я думаю, что в C # нет восьмеричных чисел.
Томас Уэллер
Я думал, что это просто C? Я не вижу никаких других ссылок на C #.
CJ Деннис
0

Python (3)

Поскольку в наши дни таких вопросов довольно много, я решил создать программу, которая автоматически решит их в 3 (или 2) жетонах. Вот результат для этой задачи:

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

Доказательство того, что это работает:

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
источник
Как ваш решатель учитывает стоимость операндов?
Томас Уэллер
@ThomasW. Это не так, он всегда будет использовать сдвиг вправо, возможно, сдвиг влево (если значения не 1 бит) и an &.
ɐɔıʇǝɥʇuʎs