Начиная с положительного целого числа N , найдите наименьшее целое число N ', которое можно вычислить путем многократного деления N на одну из его цифр (в базе-10). Каждая выбранная цифра должна быть делителем N больше 1 .
Пример № 1
Ожидаемый выход для N = 230 составляет N '= 23 :
Пример № 2
Ожидаемый выход для N = 129528 составляет N '= 257 :
Остерегайтесь неоптимальных путей!
Мы могли бы начать с 129528/9 = 14392 , но это не привело бы к наименьшему возможному результату. Лучшее, что мы можем сделать, если сначала разделить на 9, это:
правила
- Входные данные могут быть приняты в любом разумном формате (целое число, строка, массив цифр, ...).
- Это код-гольф , поэтому выигрывает самый короткий ответ в байтах!
Контрольные примеры
1 --> 1
7 --> 1
10 --> 10
24 --> 1
230 --> 23
234 --> 78
10800 --> 1
10801 --> 10801
50976 --> 118
129500 --> 37
129528 --> 257
8377128 --> 38783
655294464 --> 1111
code-golf
integer
optimization
division
Arnauld
источник
источник
Ответы:
Haskell ,
6761 байтПопробуйте онлайн!
Объяснение:
read.pure<$>show n
преобразует входное целое числоn
в список цифр.d
из этого списка мы проверяемd>1
иmod n d<1
то,d
делится лиn
.n
наd
и рекурсивно применяютсяf
:f$div n d
.n
.n
к нему и возвращаемminimum
список.источник
Желе , 8 байт
Попробуйте онлайн!
Альтернативная версия, намного быстрее, 9 байт
Попробуйте онлайн!
Как это работает
источник
Python 2 , 59 байт
Попробуйте онлайн!
источник
Рубин ,
5247 байтКонкуренция за группу неэкзотических языков! (Примечание: хорошая идея, если не игра в гольф, это добавить
.uniq
после,.digits
потому что все похожие ветви имеют схожие результаты)Попробуйте онлайн!
объяснение
источник
x<2|n%x?n:f[n/x]
чтобы сохранить два или три байта (в зависимости от того, нужен ли вам один|
или два)?value%zero
как деление на ноль, поэтому короткое замыкание не сработает. Кроме того,0
это истинное значение в ruby (единственные значения false - false и nil).||
с?>0
, но тогда это тот же счетчик символов.0
приходит, если вы не используете|
?Common Lisp , 136 байт
Попробуйте онлайн!
Читаемая версия:
источник
Желе , 21 байт
Попробуйте онлайн!
источник
Wolfram Language (Mathematica) , 44 байта
-7 байт благодаря Мише Лаврову.
Попробуйте онлайн!
источник
⋂
символа дляIntersection
. Но есть большие случаи, которые он больше не может обработать, потому что у него заканчивается генерация памятиRange[#-1]
.Most@Divisors@#
вместо,Range[#-1]
чтобы избежать проблемы с памятью, но результат составляет 49 байтов .JavaScript (Firefox 30-57), 49 байт
ES6-совместимая версия, 52 байта:
Первоначально я попытался отфильтровать нерелевантные цифры, но оказалось, что он немного длиннее - 54 байта:
источник
Котлин ,
10099 байтукрашенный
Тест
Правки
источник
Желе , 15 байт
Попробуйте онлайн!
Я должен признать, что
߀
часть заимствована из ответа Эрика . Остальное разрабатывается отдельно, отчасти потому, что я даже не понимаю, как работает остальная часть этого ответа: P.Как это работает?
* Я приятно удивлен, что так
¡
работает в списках, потому что его обычное значение - применить это n раз .После того, как Деннис объяснил, почему
߀
не нужно условное выражение , у нас есть этот 12-байтовый или его 8-байтовый вариант: P.источник
R ,
10198 байтПопробуйте онлайн!
Тонна байтов идет на извлечение цифр, а какие делятся
x
; возможно, нужен другой подход.источник
Excel Vba, 153 байта
Первый в истории код-гольф на единственном языке, который я знаю :( Не совсем подходит для гольфа ...
Звоните так:
Я понятия не имею, где проверить это онлайн.
источник
And N > 0
сN = S
на предыдущей строке. (Кроме того, если бы у меня был способ проверить это, моим первым инстинктом было бы проверить, можно ли удалить какие-либо пробелы.)APL (Dyalog) , 33 байта
Попробуйте онлайн!
Как?
⍎¨⍕⍵
- захватить цифрыn
1~⍨
- исключая1
сo/⍨
- Сортировать по0=⍵|⍨o
- делимостьn
на цифру⍬≡...:⍵
- если пусто, вернутьn
⌊/
- в противном случае вернуть минимум∇¨
- рекурсия для каждого номера в⍵÷d
- делениеn
на каждую из отфильтрованных цифр вышеисточник
Perl 5, 87 + 1 (
-p
) = 88 байтпопробуйте это онлайн
источник
PHP, 120 байт
Попробуйте онлайн!
источник
Par / GP , 49 байтов
Попробуйте онлайн!
источник