StickStack - это очень простой язык программирования, основанный на стеке, с двумя инструкциями:
|
толкает длину стека на стек-
извлекает два верхних элемента из стека и возвращает их разницу (second topmost - topmost
)
Детали языка
- Стек пуст в начале программы.
- Все инструкции выполняются последовательно слева направо.
- Если в стеке меньше 2 чисел,
-
инструкция недопустима. - В конце выполнения стек должен содержать ровно одно число .
Любое целое число может быть сгенерировано программой StickStack. Например:
|||--||-- generates the number 2 through the following stack states:
[]
[0]
[0, 1]
[0, 1, 2]
[0, -1]
[1]
[1, 1]
[1, 1, 2]
[1, -1]
[2]
Для оценки вашего кода StickStack вы можете использовать этот онлайн (CJam) оценщик . (Спасибо за @Martin за код.)
Задание
Вы должны написать программу или функцию, которая задает целое число в качестве входных данных или возвращает строку, представляющую программу StickStack, которая выводит данное число.
счет
- Ваша основная оценка - это общая длина программ StickStack для приведенных ниже тестов. Чем ниже балл, тем лучше.
- Ваша заявка действительна, только если вы выполнили свою программу во всех тестовых случаях и подсчитали свой балл.
- Ваш вторичный (tiebreaker) балл - это длина вашей генерирующей программы или функции.
Входные тесты
(Каждый номер - это отдельный контрольный пример.)
-8607 -6615 -6439 -4596 -4195 -1285 -72 12 254 1331 3366 3956 5075 5518 5971 7184 7639 8630 9201 9730
Ваша программа должна работать для любых целых чисел (которые может обрабатывать ваш тип данных), а не только для заданных тестовых случаев. Решения для тестовых номеров не должны быть жестко запрограммированы в вашей программе. Если возникнут сомнения в жестком кодировании, номера тестов будут изменены.
источник
Ответы:
Python 2 - 5188
Довольно эффективный по времени, и, кажется, (вероятно) оптимальное решение. Я заметил, что такой шаблон, как
|||||-|||-|-|-|------
(оптимальное решение для 25)можно выделить как
где каждое общее значение в конце является суммой (значение каждого уровня умножается на число '|'). Так, например, выше, у нас есть
-1*1 + 2*1 - 3*1 + 4*2 - 5*1 + 6*4 = 25
. Используя это, я написал это решение, которое выдает схожие результаты с другими ответами, и в тривиальное время.Я считаю, что это оптимальное решение, так как я проверяю каждую возможную оптимальную высоту (на самом деле я проверяю много больше, чем необходимо), и я почти уверен, что решение всегда включает в себя не более одного слоя с двумя символами |, кроме последнего (я могу гарантируйте это для положительных чисел, но не на 100% уверены в отрицательных).
Вот код, который я использовал для его тестирования
источник
Ява, 5208
524053066152Это рекурсивная функция, которая подходит ближе к цели, с базовыми случаями, когда она попадает в пределы 5 (что часто составляет всего один шаг).
В принципе, вы можете получить
(a*b)+(a/2)
для(a+b)*2
палок с простым рисунком. Еслиa
нечетно, результат будет отрицательным, что приводит к некоторой странной логике.Это займет минуту или около того для 2 31 -1, с длиной 185,367 в результате. Тем не менее, он работает практически мгновенно для всех тестовых случаев. Это баллы
4*(sqrt|n|)
в среднем. Самый длинный индивидуальный тестовый пример9730
, в результате которого получается стек флеш длиной 397:Обновить:
Нашел более короткий способ сложения / вычитания из основного шаблона. Вернуться в лидеры (пока)!
С помощью жгута и тестовых случаев:
Будет ли гольф (больше) в маловероятном случае точного галстука.
источник
JavaScript (ES6) 5296
6572Редактировать Как я уже говорил в своем объяснении, я не очень хорошо решаю целочисленные уравнения. Мое предположение о значении b было не очень хорошим, поэтому я расширил диапазон значений, которые нужно попробовать.
И (вау) я сейчас веду.Редактировать 2 Исправление ошибки, те же результаты. У меня есть идея, но я не могу ее закрепить.
Байт: ~ 460, вполне гольф. Он работает на 32-битных целых числах, время выполнения около 0.
Код представляет собой функцию F (скрыт во фрагменте) ниже.
Запустите фрагмент для проверки (в FireFox).
Показать фрагмент кода
объяснение
Положительные числа, для начала. Начните с "базы" (попробуйте в CJam, если хотите, пробелы разрешены)
Резюме: 1 палка, затем b * 2 палочки, затем b * 2 тире
Затем попробуйте добавить один или несколько '- |' в середине раскола. Каждый из них добавляет фиксированный прирост, который в два раза превышает начальную базу и может повторяться много раз. Итак, у нас есть формула с b = base и r = инкрементный коэффициент повторения
Видеть? Значение addes быстро увеличивается, и каждое добавление по-прежнему составляет всего 2 символа. Базовый прирост дает еще 4 символа каждый раз.
Учитывая v и нашу формулу v = b + r * 2 * b, нам нужно найти 2 целых числа b и r. Я не эксперт в такого рода уравнениях, но b = int sqrt (v / 2) - хорошее начальное предположение.
Тогда у нас есть r и b, которые вместе дают значение около v. Мы достигаем v точно с повторным увеличением (|| -) или уменьшением (| -).
Следуйте тому же рассуждению для отрицательных чисел, увы формула похожа, но не равна.
источник
JavaScript, 398710
94 байта / символы кода
Я придумал решение! ... а затем прочитайте ответ Спарра, и он был точно таким же.
Подумал, что я все равно опубликую, так как js допускает немного меньшее число символов.
Вот незавершенная версия кода:
источник
Python, 398710 (71 байт)
Я думаю, самое простое решение. Использует 4 * n (+/- 1) символа стика для представления n.
источник