Ваша задача, учитывая положительное целое число n
, создать выражение, равное числу n
.
Загвоздка в том, что вам разрешен только номер 1
в выводе.
Операторы в вашем распоряжении:
+
,-
,*
И/
/
является делением с плавающей точкой (так5/2 = 2.5
).
sqrt
(какs
)ceil
иfloor
(какc
иf
соответственно)!
(факториал)- В этом случае факториал работает только для натуральных чисел.
Вам также разрешено складывать 1
их вместе, поэтому что-то подобное 11
допустимо в выводе. Тем не менее, они считаются тем же числом 1
, что и в числе (поэтому 11
считается как 2 1
).
Вы также должны включить скобки в выходные данные, чтобы выражение в выходных данных при выполнении в порядке операций приводило к вводу. Хотя они не считаются операциями.
Примеры:
- Вход = 24, один возможный выход =
(1+1+1+1)!
- Вход = 11, один возможный выход =
11
- Вход = 5, один возможный выход =
c(s((1+1+1+1)!))
- Потолок квадратного корня
24
есть5
.
- Потолок квадратного корня
Правила:
- Вам гарантировано, что входное значение является положительным целым числом от
1
до2^31-1
. - Ваша программа должна работать для любого целого положительного числа
2^31-1
, даже если они не проверены. - Ваша программа должна завершить обработку всех выходов для всех номеров в наборе за 1 час.
- Результаты для каждого прогона программы должны быть одинаковыми - также нет семян.
- Вам разрешено жестко кодировать выражения максимум для 10 числовых значений.
- Вы не можете иметь мнимые числа где-либо на выходе (так что нет
s(some negative number)
). - Вам также не разрешено иметь числа, большие
2^31-1
или меньшие, чем-2^31+1
где-либо в выходных данных, даже если они обозначены какsqrt
ed или/
ed (так что no(((1+1+1)!)!)!
или((1+1+1+1)!)!
).
Набор номеров:
945536, 16878234, 32608778, 42017515, 48950830, 51483452, 52970263, 54278649, 63636656, 78817406, 89918907, 90757642, 95364861, 102706605, 113965374, 122448605, 126594161, 148064959, 150735075, 154382918, 172057472, 192280850, 194713795, 207721209, 220946392, 225230299, 227043979, 241011012, 248906099, 249796314, 250546528, 258452706, 276862988, 277140688, 280158490, 286074562, 308946627, 310972897, 322612091, 324445400, 336060042, 346729632, 349428326, 352769482, 363039453, 363851029, 392168304, 401975104, 407890409, 407971913, 425780757, 459441559, 465592122, 475898732, 482826596, 484263150, 506235403, 548951531, 554295842, 580536366, 587051904, 588265985, 588298051, 590968352, 601194306, 607771869, 618578932, 626776380, 667919873, 681786366, 689854904, 692055400, 697665495, 711608194, 734027104, 750869335, 757710567, 759967747, 777616154, 830071127, 833809927, 835873060, 836438554, 836945593, 863728236, 864158514, 871273503, 881615667, 891619600, 897181691, 918159061, 920521050, 924502226, 929983535, 943162304, 950210939, 950214176, 962610357, 974842859, 988572832
(Это 100 случайных чисел от 1 до 1 млрд.)
Система баллов:
Ваша оценка определяется следующим образом:
- Ваша программа будет проверена на случайные числа в наборе.
- Вы должны предоставить выходные данные, сгенерированные с использованием случайных чисел в наборе (либо внутри вашего ответа, либо в виде ссылки для вставки).
- Затем у вас есть два «балла»: первичный балл и вторичный балл.
- Ваш основной счет
(no. of 1's in output)*(no. of operators in output)
. Если ваш основной балл самый низкий, вы выигрываете. - Ваш вторичный счет - это время загрузки, время по Гринвичу и 24 часа. Итак, если вы загрузите свою программу 12 сентября в 00:00 по Гринвичу, тогда ваш счет будет
12/09/2016, 00:00
(используйтеDD/MM/YYYY HH:MM
для форматирования).
- Ваш основной счет
Отображать ваш счет так:
(language name)
Primary Score = (primary score)
Secondary Score = (secondary score)
(no. of 1's) `1`'s, (no. of operators) operators
Замените все вещи в скобках на имя вашего языка, первичную и вторичную оценки соответственно.
Текущий победитель:
Текущий победитель - @ChrisJefferson, у которого есть основной счет 3,810,660
.
math
code-challenge
metagolf
test-battery
clismique
источник
источник
Ответы:
C ++ 11
Далее небольшое обновление: Делайте намного меньше добавлений, и попробуйте все числа формы A * B + C. Я считаю, что в установленные сроки это довольно близко к оптимальному, при условии, что вы используете только
+
,*
и!
. Я оставляю других операторов людям, у которых больше времени, чем у меня!Небольшое обновление: старайтесь использовать факториалы и числа вроде 11 .... 111. Также исправлена ошибка, которая не учитывалась
!
при расчете стоимости.Новый результат:
Основная оценка = 3 810 660
Вторичный счет = 12/09/2016 20:00
2532
1
с, 1505 операторов.Различные трюки вместе взятые. Моя программа начинается с установки самой короткой программы для всех факториалов и чисел в форме 111..111 (я не думаю, что это противоречит жесткому правилу, так как это самые короткие способы сделать эти числа. Я мог бы переставить мой код, поэтому я проверяю эти шаблоны в моем динамическом программировании, если хотите). Затем примените частичный подход к динамическому программированию, пробуя различные формы:
К сожалению, я не могу попробовать все способы разложения числа, поэтому я выбираю факториал и 11 ... 11, чтобы пробовать только ближайшее число, для A + B, чтобы пробовать вещи рядом с A / 2, и для A * B + С тем, чтобы попробовать только совсем маленький As.
Было бы легко расширить это, чтобы попробовать некоторые из них, пытаясь иногда слегка отклониться от нормы (особенно в A * B - C), но мне очень нравится только пытаться расти.
Кроме того, очень трудно оптимизировать условия оптимизации (мне это не нравится!), Потому что в принципе вы не можете придумать «лучшее» значение для каждого отдельного числа, вы должны рассмотреть свой набор ответов глобально (что я не собираюсь делать).
Предупреждение. Для этой программы требуется 64-разрядный компьютер и около 10 ГБ памяти (поскольку я неэффективно создаю гигантский массив для всех частично вычисленных результатов).
Программа:
Полученные результаты:
источник
!
. Я думаю, что это 1632 оператора, а не 1407. (Что, тем не менее, приводит к большому счету.)long maxval
ворчание ворчаниеHaskell
Основная оценка: 27242281
Вторичный счет: 09.12.2016 09:01
11891
1
, 2291 операторОн в основном находит самый короткий способ сделать это, используя только + и -
Выход:
источник
Python, оценка 17136288
дополнительный счет: 09.12.2016, 08:53
(4784 и 3582 операции)
Работа в процессе, но ОП попросил мой текущий код ...
Вывод - обратите внимание , что
t
это факториал функция, поэтому не следует путать сf
дляfloor
если он привыкает - я оценил каждый с помощью функцииt
(выше) , чтобы проверить дважды , что они все правильно:источник
t
в выходной?JavaScript (ES6), 27212498, 2016-09-12 09: 46: 34Z
Используются только + и -. Основываясь на моем ответе, чтобы минимизировать эти
источник
питон
Основная оценка = 2214138604871819402525
Вторичный счет = 12/09/2016, 07:53
Вот код:
Просто чтобы мяч катился.
В основном вывод
1+1+1...+1
, где число1
's в выведенном выражении равноn
.В общем, есть
47054634305
1
для набора чисел и47054634205
операторов (которые все+
).Я не собираюсь публиковать здесь, потому что вы поняли идею.
источник
2**31-1
.n-1
? Он отлично работает для меня.AWK
основной балл 46933701
дополнительный балл 12.09.2016 19:20
(6901 из них, 6801 опс)
Просто печатает двоичное представление, рассчитанное слева направо.
Например, 19 - это 10011, который ((((( 1 ) * 2 + 0 ) * 2 + 0 ) * 2 + 1 ) * 2 + 1 ).
Я просто опускаю
+0
и пишу2
как(1+1)
.Мне было просто любопытно, как этот метод будет забивать.
Выход:
источник
Python 3
Основная оценка:
69720516
Вторичная оценка:
09:30 14/09/2016
Изменить: теперь использует умножение, чтобы значительно уменьшить счет.
Это делает большое использование факториалов и рекурсии. Всего программа использует:
5958
те,11702
операторыИдео это!
источник
ДЖАВА
Основная оценка
1045978739
Вторичная оценка
12/09/2016 16:05
37193
1s
28123
operators
источник
1
в начале каждого(1*11*11*...*11)
.Emacs Lisp
Основная оценка: 81638725
Дополнительная оценка: 09.12.2016 09:35
В основном строит сумму по области (1, 11, 111, ...), которая эквивалентна n.
источник
111+11+1+1
, верно? (Поправьте меня, если я ошибаюсь.)1
s по всему выводу 100 чисел и умножили это на общее количество+
операций по всему выводу?AWK , 15642720
Вторичный счет = 30/05/2017, 21:11
Попробуйте онлайн!
Один: 4590
Ops: 3408 Основная оценка = 15642720 Дополнительная оценка = 30/05/2017 21:11
источник