Задача действительно проста: учитывая число, вы разбиваете его цифры на массив меньших чисел, так что результирующие числа не убывают. Уловка в том, что вы должны разделить его так, чтобы длина массива была максимальной.
Смущенный?
- Вам предоставляется положительное целое число через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции в любом удобном, однозначном формате ввода.
- Вы должны разделить десятичные цифры числа на смежные, непересекающиеся группы.
- Массив чисел, представленных этими группами цифр, должен быть отсортирован (в обычном неубывающем порядке) без перестановки групп .
- В тех случаях, когда существует более одного такого раздела, вы должны разбить входные данные на максимально возможное число. В случае связей верните один такой результат.
- Вы можете вывести массив в STDOUT (или ближайшую альтернативу) или в качестве возвращаемого значения функции. В случае STDOUT (или ближайшей альтернативы), массив должен быть напечатан в любом удобном, однозначном формате списка.
- Разделенные числа не должны иметь начальных нулей. Так, например,
1002003
не может быть напечатан как или[1, 002, 003]
или[1, 2, 3]
и единственный правильный ответ для этого является[100, 2003]
.
Тестовые случаи:
123456 -> [1, 2, 3, 4, 5, 6]
345823 -> [3, 4, 5, 8, 23]
12345678901234567890 -> [1, 2, 3, 4, 5, 6, 7, 8, 90, 123, 456, 7890]
102 -> [102]
302 -> [302]
324142 -> [3, 24, 142] OR [32, 41, 42]
324142434445 -> [32, 41, 42, 43, 44, 45]
1356531 -> [1, 3, 5, 6, 531]
11121111111 -> [1, 1, 1, 2, 11, 11, 111]
100202003 -> [100, 202003]
счет
Это код-гольф, поэтому выигрывает самый короткий код в байтах.
источник
aY
вместо~Y]
a
. Не знаю почему.int("01")
что это ошибка в Pyth (этого не происходит в Python).n
это длина ввода.Mathematica,
134127 байтовЭто довольно неэффективно, поскольку генерирует намного больше разделов, чем допустимых.
324142434445
Тест выполняется в течение нескольких секунд, но я бы не попробовать12345678901234567890
.Это определяет безымянную функцию, которая принимает целое число и возвращает список целых чисел.
объяснение
Порядок чтения этого кода немного повсюду, поэтому я приведу порядок, в котором он должен быть прочитан (и оценен по большей части):
d=IntegerDigits@#
получить десятичные цифры ввода и назначить этот списокd
.SetPartitions
(что требуетNeeds@"Combinatorica`";
) дает мне все разделы этого. Тем не менее, он возвращает намного больше, чем я на самом деле хочу, так как обрабатывает входные данные как набор . Это то, что делает его неэффективным, но я использую это, потому что самый короткий путь, который я знаю, чтобы получить все разделы списка, намного длиннее. Например, если бы список был,{1, 2, 3}
функция вернула бы:Обратите внимание, что a) все последовательные разделы расположены в правильном порядке, и b) разделы отсортированы от самого грубого до самого прекрасного.
Select[...,...&]
затем фильтрует этот список по анонимной функции, переданной в качестве второго аргумента.Join @@ # == d
проверяет, что мы получили раздел списка вместо раздела общего набора.#~FreeQ~{0, __}
проверяет, что ни один раздел не начинается с начального нуля.0 <= ## & @@ f /@ #
немного неясен. Сначала мы сопоставляемFromDigits
каждый список в разделе, чтобы восстановить числа, представленные цифрами. Затем мы применим0 <= ##
к тем числам, где##
относится ко всем числам. Если раздел,{1, 23, 45}
то это расширяется до0 <= 1 <= 23 <= 45
, поэтому он проверяет, что массив отсортирован.Last@
затем дает мне последний раздел, оставшийся после фильтрации - это работает, потому чтоSetPartitions
уже отсортированы разделы, так что самые лучшие находятся в конце.f/@
восстанавливает числа из списков цифр.источник
Python 3, 134 байта
Это немного грязно, ну да ладно. Программа просто рекурсивно генерирует все допустимые разделы. Интересно то, что для запрета ведущих нулей все, что было необходимо, было дополнительным
or "1">s[i:]>""
условием.Принимает ввод как
f("12345678901234567890")
и возвращает список целых.источник
Pyth,
626160объяснение
Алгоритм работает, генерируя все двоичные числа между
0
(включительно) и2^(n-1)
(исключительно), гдеn
длина ввода.Затем двоичные цифры каждого сопоставляются с разделителем (
N
) для 1 и ничем для 0.Эти символы затем вставляются между каждым входным символом, и результат разделяется на
N
, получая список.Значения в списках затем анализируются в целые числа, а списки сортируются по длине. Тогда все, что осталось, это отфильтровать несортированные и те, которые были разбиты по лидирующим нулям, после чего выбирается самый длинный список.
источник
(Неконкурентный) Pyth, 25 байтов
Попробуйте онлайн!
Как это устроено:
источник
J, 109 байт
Очень долго, но, по крайней мере, занимает O (n * (2n)!) Памяти и O (n * log (n) * (2n)!) Время, где n - длина входа. (Так что не пытайтесь запустить его с более чем 5 цифрами.)
Функция принимает входные данные в виде строки.
Примеры:
Метод:
источник
Haskell, 161 байт
Тестовый забег:
Как это работает: вспомогательная функция
f
разбивает входной список на все возможные списки подсписков.g
сначала отбрасываются те, у кого начинается подсписок,0
а затем те, у которых нет правильного порядка. Соедините каждый оставшийся список с его длиной, возьмите максимум и снова отбросьте часть длины.источник