Числа в скобках предоставляют простой способ выразить большие целые числа, используя только левую скобку, пробел и правую скобку ( [ ]).
Номер скобки определяется как строка из одной или нескольких пар совпадающих скобок, [...]называемых чанками , каждая из которых отделена от своих соседей нулем или несколькими пробелами.
Количество пробелов между каждым фрагментом определяет гипероперацию между ними. Отсутствие пробелов означает сложение, 1 пробел означает умножение, 2 пробела означает возведение в степень, 3 пробела означает тетрацию и так далее. Гипероперации более высокого порядка имеют приоритет, поэтому тетрация происходит до возведения в степень, возведение в степень происходит до умножения и т. Д. Они также являются ассоциативными справа, поэтому a^b^cвычисляется как a^(b^c). (Но a^b*cвсе еще (a^b)*c.)
Каждый кусок может быть пустым ( []) или содержать другой номер скобки. Пустые чанки имеют значение 0. Непустые чанки имеют значение содержащихся в них скобок плюс 1.
Примеры: ( ^^это тетрация, ^^^это пенсия )
[[]]имеет значение 1, потому что это 0 ([]) увеличивается на 1[[[]]]имеет значение 2, но так же,[[]][[]]так как два[[]]добавлены ( )[[[]]] [[[[]]] [[[[]]]]][[[]]]имеет значение 20 = (2 * ((2 ^ 3) +1)) + 2[[[]]] [[[[]]]]имеет значение 65536 = 2 ^^^ 3 = 2 ^^ (2 ^^ 2) = 2 ^^ 4 == 2 ^ (2 ^ (2 ^ 2))[[[[]]]] [[[]]] [[]]имеет значение 7625597484987 = 3 ^^^ (2 ^^^ 1) = 3 ^^^ 2 = 3 ^^ 3 = 3 ^ (3 ^ 3)
В действительных скобках:
- Там никогда не будет ведущих или конечных пробелов.
- Всегда будет хотя бы одна пара совпадающих скобок.
- Все левые скобки будут иметь соответствующую правую скобку.
- Пробел никогда не появится прямо справа
[или слева от]. - Значение всегда является неотрицательным целым числом.
Вызов
Обратите внимание, что может быть много форм для номера скобки, которые дают одинаковое значение. [[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]и [[[]]] [[[[]]]]оба представляют 16, но последний намного короче.
Ваша задача - написать алгоритм, который пытается найти представление кратчайшего числа скобок для заданного значения. Например, я считаю, что самый короткий способ представить 16 - это 17 символов [[[]]] [[[[]]]].
Оценка (Обновлено)
Пусть S будет набором целых чисел от 1 до 256 (включительно), а также следующими десятью значениями:
8191 13071 524287 2147483647 1449565302 1746268229 126528612 778085967 1553783038 997599288
(Первые 4 - простые числа Мерсенна, остальные случайные.)
Представление, которое генерирует самый короткий набор номеров скобок для всего в S , выиграет. Ваша оценка - это сумма длин ваших чисел в скобках для всех значений в S (чем меньше, тем лучше).
С вашим кодом, пожалуйста, отправьте список номеров ваших скобок для всех S , точный порядок не очень важен. например:
1=[[]]
2=[[[]]]
3=[[[[]]]]
...
2147483647=[...]
...
(Я знаю, что это не оптимальный метод подсчета очков, но я не настроен на запуск набора случайных эвристических тестов при каждой отправке. Извините :()
правила
- Вы не можете жестко закодировать любые числа скобок, кроме тривиальных пошаговых решений (
[], [[]], [[[]]], ...). Ваша программа на самом деле должна искать оптимально короткие представления. (Хотя результаты могут быть неоптимальными.) - Ваш алгоритм должен работать для всех неотрицательных целых чисел ниже 2 147 483 648 (2 ^ 31). Вы не можете конкретно сосредоточиться на значениях S .
- Для любого конкретного ввода ваш алгоритм должен работать не более 10 минут на приличном современном компьютере (~ 2,5 ГГц процессор, ~ 6 ГБ ОЗУ).
- В (на первый взгляд) редкой вероятности ничьей побеждает победитель, получивший наибольшее количество голосов.
- Если вы копируете другое решение или пересматриваете его без указания авторства, вы будете дисквалифицированы.
источник
Ответы:
Python 11455b
Это решение использует жадный подход к поиску способов разбиения простых чисел, а не исчерпывающий подход. Мне нужно 9875b для 1-256 по сравнению с 8181 для, вероятно, оптимального решения Мартина в этом пространстве.
Большая таблица результатов умножения и возведения в степень дает небольшие улучшения в больших тестовых случаях. Решение ниже заняло около 7 минут. Увеличение времени работы свыше 30 минут оказывает минимальное влияние на производительность.
У меня, как и у Мартина, была проблема с приоритетом. Мое решение в ограничении выбора операций может быть неоптимальным.
Выход:
источник
Mathematica
Замечания: Этот алгоритм никогда не сможет приблизиться к большим числам тестов. Мне нужен существенно другой подход, поэтому я просто оставлю это для других, чтобы они сверяли свои меньшие цифры. Вы можете считать это представление недействительным.
Вот начало для первых 256 номеров (остальные были добавлены после того, как я начал, и мне, вероятно, нужно найти отдельное решение для них)
Общая длина первых 256 цифр составляет 7963 символа. Я не знаю, является ли это оптимальным.
Игнорируя сложение, результаты для 8191 и 13071 были найдены через несколько секунд, а 524387 - через пару минут.
на 164 символов вместе.
Вот код:
Я использовал исчерпывающий поиск до возведения в степень. Там нет тетрации или операции более высокого порядка. Я только что попробовал операции высшего порядка вручную, и есть только несколько комбинаций, которые на самом деле дают числа ниже 2 31 , поэтому я просто жестко запрограммировал те, которые работают.
Редактировать: мое предыдущее решение не беспокоиться о приоритете, он просто сложил вещи вместе.
Теперь я думаю, что мой новый код исправляет это,но ни одно из первых 256 чисел не изменилось, ни 8191 (который был действителен прежде, я проверил) ... и сейчас слишком поздно, чтобы я мог сказать, действительно ли мой код это исправил , Завтра я еще раз посмотрю и добавлю объяснение, потому что теперь с проверкой приоритетов это немного запутанно (хотя, надеюсь, это должно сократить время поиска).Редактировать: Хорошо, были некоторые ошибки, как и ожидалось. Я думаю, что я исправил это сейчас, увеличив общую длину от 1 - 256 до 7963 . Я не уверен, что это уже оптимально, потому что может быть возможно найти более короткие решения из неоптимальных частей, если они позволяют операции более высокого порядка. Объяснение будет следовать, когда мне удастся немного очистить код.
источник
Python 9219b
Это моя вторая запись. Я начал с нуля и попробовал новое расположение данных, включая использование пакета blist для отсортированных списков и диктов, а также некоторые новые подходы для поиска больших решений. Я думаю, что у меня есть оптимальный 1-256. Увеличение времени выполнения с 30 с до 4 м сокращало большие тестовые случаи примерно на 30 байт.
Выход:
7944b для 1-256
1275b для больших случаев
источник