Quão pequeno pode ficar?

42

Começando com um número inteiro positivo N , encontre o menor número inteiro N ' que pode ser calculado dividindo repetidamente N por um de seus dígitos (na base 10). Cada dígito selecionado deve ser um divisor de N maior que 1 .

Exemplo 1

A saída esperada para N = 230 é N '= 23 :

230/2 = 115, 115/5 = 23

Exemplo 2

A saída esperada para N = 129528 é N '= 257 :

129528/8 = 16191, 16191/9 = 1799, 1799/7 = 257

Cuidado com caminhos não ideais!

Poderíamos começar com 129528/9 = 14392 , mas isso não levaria ao menor resultado possível. O melhor que podemos fazer se primeiro dividirmos por 9 é:

129528/9 = 14392, 14392/2 = 7196, 7196/7 = 1028, 1028/2 = 514 -> errado!

Regras

  • A entrada pode ser obtida em qualquer formato razoável (número inteiro, string, matriz de dígitos, ...).
  • Isso é , então a resposta mais curta em bytes vence!

Casos de teste

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
Arnauld
fonte
1
Gostaria de saber se esta série (1, 1, ..., 10, 11, 1, 13, ..., 1, ...) tem uma entrada OEIS
Draco18s
Ainda não, AFAICS.
GNiklasch

Respostas:

11

Haskell , 67 61 bytes

f n=minimum$n:[f$div n d|d<-read.pure<$>show n,d>1,mod n d<1]

Experimente online!

Explicação:

  • read.pure<$>show ntransforma o número inteiro de entrada nem uma lista de dígitos.
  • Para cada dígito ddesta lista, verificamos d>1e mod n d<1, ou seja, se ddivide n.
  • Se as verificações forem bem sucedidas, dividimos npor de recursivamente aplicar f: f$div n d.
  • No total, isso gera uma lista dos números mínimos mínimos de todas as subárvores de n.
  • Como a lista pode estar vazia, anexamos na ela e retornamos minimuma lista.
Laikoni
fonte
11

Gelatina , 8 bytes

÷DfḶ߀Ṃo

Experimente online!

Versão alternativa, muito mais rápida, 9 bytes

÷DfÆḌ߀Ṃo

Experimente online!

Como funciona

÷DfḶ߀Ṃo  Main link. Argument: n

 D        Decimal; yield the digits of n.
÷         Divide n by each of its digits.
   Ḷ      Unlength; yield [0, ..., n-1].
  f       Filter; keep quotients that belong to the range.
    ߀    Recursively map this link over the resulting list.
      Ṃ   Take the minimum. This yields 0 if the list is empty.
       o  Logical OR; replace 0 with n.
Dennis
fonte
5

Ruby ,52 47 bytes

Competindo pelo grupo de idiomas não exóticos! (Observação: uma boa idéia, se não jogar golfe, é adicionar .uniqdepois .digitsporque todos os ramos semelhantes têm resultados semelhantes)

f=->n{n.digits.map{|x|x>1&&n%x<1?f[n/x]:n}.min}

Experimente online!

Explicação

f=->n{      # Function "f" n ->
   n.digits # n's digits (in reverse order (<- doesn't matter))
            # fun fact: all numbers always have at least one digit
    .map{|x|# Map function for every digit "x" ->
       x>1&&    # x is 2-9 and
       n%x<1    # n mod x == 0, or, "n is divisible by x"
       ? f[n/x] # then recursively find smallest of f[n/x]
       : n      # otherwise: n (no shortest path in tree)
     }.min  # Smallest option out of the above
            # if we reach a dead end, we should get n in this step
}
Unihedron
fonte
Você pode usar x<2|n%x?n:f[n/x]para salvar dois ou três bytes (dependendo se você precisa de um |ou dois)?
27417 Neil
@ Neil Infelizmente, ruby ​​trata value%zerocomo divisão por zero, então o curto-circuito não funciona. Além disso, 0é um valor verdadeiro em ruby ​​(os únicos valores de falsey são falsos e nulos).
Unihedron
Então funcionaria com dois ||s?
Neil
Não, porque 0 é considerado verdadeiro, seria com >0, mas é a mesma contagem de caracteres.
Unihedron
Desculpe, não estou vendo de onde 0vem se você não estiver usando |?
Neil
5

Lisp comum , 136 bytes

(defun f(n)(apply 'min(or(loop for z in(map'list #'digit-char-p(write-to-string n))if(and(> z 1)(<(mod n z)1))collect(f(/ n z)))`(,n))))

Experimente online!

Versão legível:

(defun f (n)
  (apply 'min
         (or (loop for z in (map 'list
                                 #'digit-char-p
                                 (write-to-string n))
                   if (and (> z 1)
                           (< (mod n z) 1))
                   collect (f (/ n z)))
             `(,n))))
Traut
fonte
3
Bem-vindo ao PPCG!
Laikoni
@Laikoni thanks! Não a menor submissão, mas ainda um muito divertido
Traut
@Laikoni meu erro, corrigido. obrigado!
Traut
@ Arnauld obrigado por perceber! Corrigi o trecho e mudei o link.
Traut
@Laikoni de fato! Eu reduzi para 205b.
Traut
4

Wolfram Language (Mathematica) , 44 bytes

-7 bytes graças a Misha Lavrov.

Min[#0/@(#/IntegerDigits@#⋂Range[#-1]),#]&

Experimente online!

alefalpha
fonte
1
Um tanto golfista é essa solução de 44 bytes baseada no uso do caractere Intersection. Mas existem casos grandes com os quais ele não pode mais lidar, porque fica sem geração de memória Range[#-1].
Misha Lavrov
1
Podemos usar em Most@Divisors@#vez de Range[#-1]evitar o problema de memória, mas o resultado é 49 bytes .
Misha Lavrov
4

JavaScript (Firefox 30-57), 49 bytes

f=n=>Math.min(...(for(c of''+n)c<2|n%c?n:f(n/c)))

Versão compatível com ES6, 52 bytes:

f=n=>Math.min(...[...''+n].map(c=>c<2|n%c?n:f(n/c)))
<input type=number oninput=o.textContent=f(this.value)><pre id=o>

Originalmente, tentei filtrar dígitos irrelevantes, mas acabou sendo um pouco mais longo, com 54 bytes:

f=n=>Math.min(n,...(for(c of''+n)if(c>1&n%c<1)f(n/c)))
Neil
fonte
3

Kotlin , 100 99 bytes

fun f(i:Int):Int{return i.toString().map{it.toInt()-48}.filter{it>1&&i%it<1}.map{f(i/it)}.min()?:i}

Embelezado

fun f(i:Int):Int{
    return i.toString()
        .map { it.toInt()-48 }
        .filter { it >1 && i % it < 1}
        .map { f(i/it) }
        .min() ?: i
}

Teste

fun f(i:Int):Int{return i.toString().map{it.toInt()-48}.filter{it>1&&i%it<1}.map{f(i/it)}.min()?:i}

val tests = listOf(
        1 to 1,
        7 to 1,
        10 to 10,
        24 to 1,
        230 to 23,
        234 to 78,
        10800 to 1,
        10801 to 10801,
        50976 to 118,
        129500 to 37,
        129528 to 257,
        8377128 to 38783,
        655294464 to 1111)

fun main(args: Array<String>) {
    for ( test in tests) {
        val computed = f(test.first)
        val expected = test.second
        if (computed != expected) {
            throw AssertionError("$computed != $expected")
        }
    }
}

Edições

jrtapsell
fonte
3

Gelatina , 15 bytes

ÆDḊfD
:Ç߀µÇ¡FṂ

Experimente online!

Devo admitir que a ߀parte é emprestada da resposta de Erik . O resto é desenvolvido separadamente, em parte porque nem mesmo entendo como o restante dessa resposta funciona: P.

Como funciona?

ÆDḊfD ~ Helper link (monadic). I'll call the argument N.

ÆD    ~ Take the divisors.
  Ḋ   ~ Dequeue (drop the first element). This serves the purpose of removing 1.
   fD ~ Take the intersection with the decimal digits.

:Ç߀µÇ¡FṂ ~ Main link.

 Ç        ~ Apply the helper link to the first input.
:         ~ And perform element-wise integer division.
     Ç¡   ~ If the helper link applied again is non-empty*, then...
  ߀µ     ~ Apply this link to each (recurse).
       FṂ ~ Flatten and get the maximum.

* Fico agradavelmente surpreso que ¡funcione dessa maneira nas listas, porque seu significado normal é aplicado algumas vezes .

Depois Dennis explicou por que ߀não precisa de uma condicional, temos este 12 Byter , ou sua versão de 8 bytes: P.

Mr. Xcoder
fonte
3

R , 101 98 bytes

f=function(x,e=(d=x%/%10^(0:nchar(x))%%10)[d>1])"if"(sum(y<-which(!x%%e)),min(sapply(x/e[y],f)),x)

Experimente online!

Uma tonelada de bytes é usada para extrair os dígitos e quais são divididos x; talvez outra abordagem seja necessária.

Giuseppe
fonte
3

Excel Vba, 153 bytes

Primeiro código de golfe na única língua que conheço :( Não é exatamente favorável ao golfe ...

Function S(X)
S = X
For I = 1 To Len(CStr(X))
A = Mid(X, I, 1)
If A > 1 Then If X Mod A = 0 Then N = S(X / A)
If N < S And N > 0 Then S = N
Next I
End Function

Ligue assim:

Sub callS()

result = S(655294464)

MsgBox result

End Sub

Não faço ideia de onde testar isso online.

Durielblood
fonte
1
Bem-vindo ao PPCG! Eu realmente não conheço Vba, mas suspeito que você pode substituir And N > 0 por um N = Sem uma linha anterior. (Além disso, se eu tivesse uma maneira de testá-lo, meu primeiro instinto seria verificar se algum dos espaços pode ser removido.) #
Ørjan Johansen
2

APL (Dyalog) , 33 bytes

{⍬≡do/⍨0=⍵|⍨o1~⍨⍎¨⍕⍵:⍵⋄⌊/∇¨⍵÷d}

Experimente online!

Quão?

⍎¨⍕⍵ - pegue dígitos de n

1~⍨- excluindo 1s

o/⍨ - filtrar por

0=⍵|⍨o- divisibilidade npelo dígito

⍬≡...:⍵ - se vazio, retorne n

⌊/ - caso contrário, retorne no mínimo

∇¨ - recursão para cada número em

⍵÷d- a divisão de ncada um dos dígitos filtrados acima

Uriel
fonte
2

Perl 5, 87 + 1 ( -p) = 88 bytes

$r=0,map{$\=$_,$r++if!$\|$_<$\;for$i(/[2-9]/g){$_%$i||$h{$_/$i}++}}$_,keys%h;$r&&redo}{

experimente online

Nahuel Fouilleul
fonte
2

PHP, 120 bytes

<?php function f($n){$r=array_map(function($x)use($n){return$x>1&&!($n%$x)?f($n/$x):$n;},str_split($n));return min($r);}

Experimente online!

Zerquix18
fonte
3
Bem vindo ao site! :)
DJMcMayhem
2
Você pode omitir as tags PHP abertura e salvar 6 bytes :-)
Daniel W.