Próximo número com k fives

8

Desafio:

Seu programa utilizará dois números inteiros ne, kcomo entrada, e produzirá o menor número inteiro maior que (mas não igual a) nque contenha pelo menos kocorrências do dígito 5.

Você pode assumir 1 ≤ k ≤ 15e 1 ≤ n < 10**15.

Este é um desafio de . Seu programa deve ser executado no TIO para todos os casos de teste e concluído em 10 segundos no total.

Regras gerais:

  • Isso é , então a resposta mais curta em bytes vence.
    Não permita que idiomas com código de golfe o desencorajem a postar respostas com idiomas que não sejam codegolf. Tente encontrar uma resposta o mais curta possível para qualquer linguagem de programação.

  • As regras padrão se aplicam à sua resposta com as regras de E / S padrão , para que você possa usar STDIN / STDOUT, funções / método com os parâmetros adequados e programas completos do tipo retorno. Sua chamada. Os parâmetros da função podem ser obtidos em qualquer ordem, mas especifique na sua resposta.

  • As brechas padrão são proibidas.
  • Você deve adicionar um link com um teste para o seu código (ou seja, TIO ).
  • O cabeçalho da resposta deve listar a pontuação em bytes, mas também o tempo total gasto para todos os casos de teste no TIO
  • Se o seu idioma não estiver no TIO, o código deverá terminar em menos de 10 segundos na sua máquina, para que você tenha certeza de que é rápido o suficiente em qualquer computador razoável.
  • É altamente recomendável adicionar uma explicação para sua resposta.

Casos de teste:

(n, k) ->  output
(53, 2) -> 55
(55, 1) -> 56
(65, 1) -> 75
(99, 1) -> 105
(555, 3) -> 1555
(557, 1) -> 558
(5559, 3) -> 5565
(6339757858743, 5) -> 6339757859555
(99999999999999, 15) -> 555555555555555

Exemplo de programa:

Este programa está correto.

brim
fonte
1
Observe que o tempo no TIO não é perfeitamente confiável , embora, embora insuficiente para o código mais rápido, seja provavelmente suficiente por tempo restrito .
Laikoni 28/03/19
Presumo que a resposta correta para (n, k) = (45, 1)é 50? Algumas das respostas estão erradas.
Neil

Respostas:

5

R + stringr, 85 84 76 bytes, 0,062s no TIO

f=function(n,k,m=2+stringr::str_count(n+1,"5")-k)`if`(m<2,f(n+.1^m*2,k),n+1)

Experimente online!

-1 byte graças a Robert S.
-8 bytes graças a Giuseppe.

Uma solução recursiva simples seria aumentar em 1 até que a resposta seja encontrada, mas isso não atenderia à restrição de tempo. Para atender à restrição de tempo, essa função utiliza o fato de que, se houver p faltando 5s, podemos aumentar em 2 * 10 ^ (p-2).

Observe que quando p = 1, o incremento se torna 0,2. Tudo bem, pois após 5 etapas retornamos a um número inteiro e nenhum dos números decimais encontrados nesse período possui um extra de 5. Se, em vez disso, aumentarmos em 5 * 10 ^ (p-2) ou em 1 * 10 ^ (p-2), encontraríamos f (24, 1) = 24,5 em vez de 25, por exemplo.

Robin Ryder
fonte
2
Salve 1 byte usando uma ifvariante de função.
Robert S.
@RobertS. Obrigado. Eu não sabia sobre essa variante; existe algum lugar onde eu possa ler mais sobre isso?
Robin Ryder
2
Definitivamente. Confira as dicas para jogar golfe no R post !
Robert S.
1
Também você pode fazer perguntas no chat de R golfista que não é muito ativo, mas é melhor do que nada :-)
Giuseppe
2
76 bytes - Não tenho muita certeza do que aestava fazendo, por isso o removi e parece que está tudo bem.
Giuseppe
3

Geléia , 37 bytes 0,131 s em TIO

»DL‘Ɗ}©5xḌ_DḌÐƤ;®ŻṬ€UḌ¤+⁹D=5S>ʋƇ⁸’¤ḟṂ

Experimente online!

Isso funciona por

  1. calculando o máximo do número de dígitos na entrada mais um e k, e fazendo um número com esse número
  2. Subtraindo a entrada desse número
  3. Gerando todos os sufixos desse número
  4. Também gera todos os poderes de dez de 1 até o próximo maior que a entrada
  5. Adiciona cada um dos números 3 e 4 à entrada
  6. Remove respostas com poucos 5's
  7. Filtra a entrada das respostas
  8. E retorna o mínimo
Nick Kennedy
fonte
@KevinCruijssen desculpe, eu quis dizer que muitos cincos #
Nick Kennedy
1
Hmm .. Parece falhar em [557,1](resulta em em 558vez de 560); O caso de teste na descrição parece incorreto, pois [557,2]deve resultar em seu 558lugar.
Kevin Cruijssen 28/03/19
3
@KevinCruijssen Perguntei sobre isso: pelo menos k 5s não é exatamente k.
Nick Kennedy
Ah ok, então está correto. :)
Kevin Cruijssen 28/03/19
2

05AB1E , 33 32 bytes

sg>‚à©5s×α.s0š®Ý°0šâO+IKʒ§5¢¹@}ß

Porto da abordagem incrível de @NickKennedy em sua resposta Jelly , por isso não deixe de vota-lo!

kn

Experimente online ou verifique todos os casos de teste .

Explicação:

sg>                # Get the length+1 of the second (implicit) input-integer
   ‚à              # Pair it with the first input-integer, and leave the maximum
     ©             # Store this maximum in the register (without popping)
      5s×          # Create an integer (actually, create a string..) with that many 5s
         α         # Take the absolute difference with the second (implicit) input
          .s       # Get the prefixes of that number
            0ª     # Prepended with an additional 0
    ®              # Get the maximum from the register again
     Ý             # Create a list in the range [0, max]
      °            # Raise 10 to the power of each integer
       0ª          # And also prepend an additional 0 to this list
              â    # Then create each possible pair of these two lists
               O   # Sum each pair
                +  # Add the second input to each sum
IK                 # Then remove the second input from this list (if present)
  ʒ                # And filter this list by:
   §               #  Cast the number to a string (bug, shouldn't be necessary)
    5¢             #  Count the amount of 5s in the string
      ¹@           #  And check if this count is larger than or equal to the first input
                 # After the filter: only leave the lowest number
                   # (which is output implicitly as result)
Kevin Cruijssen
fonte
2

Stax , 17 bytes (6.861 segundos no TIO)

≈ª╞¥é£ôñτ←╝α┴╢JLd

Execute e depure

Este programa recebe ke nna entrada padrão separados por espaço. O Stax não possui uma maneira conveniente de executar vários casos de teste no TIO, portanto, executei cada entrada separadamente e adicionei o tempo. 99% do tempo está na inicialização do processo do intérprete. Usando o interpretador javascript no staxlang.xyz, todos os casos de teste são executados em 50 milissegundos.

Último caso de teste em Experimente online!

Procedimento :

  1. Entrada de incremento
  2. Se houver 5s suficientes , finalize e imprima
  3. t= número de 5s à direita no número
  4. Adicionar 10 ** t
  5. Ir para 2
recursivo
fonte
2

Python 2 , 70 68 bytes (0,025 segundos no TIO)

l=lambda n,k:'5'*k*(10**~-k>n)or-~n*(`n+1`.count('5')>=k)or l(n+1,k)

Experimente online!

Isso pode ser um pouco exagerado; está correto em todos os casos e termina em um tempo insignificante para os casos de teste, mas não termina em um tempo razoável para outros casos. Tecnicamente, ele atende aos requisitos.

Em resumo, se o menor número com kcinco for maior que n, usamos esse número, pois é obviamente a solução correta. Caso contrário, recorremos à abordagem recursiva padrão.

ArBo
fonte
Eu sempre aprecio a flexão de regras no golfe.
recursivo
1

Perl 5 -pl , 44 bytes

$k=<>;$_++;s/.*?(?=5*$)/1+$&/e while$k>y/5//

Experimente online!

Localiza qual é o número sem os 5s à direita. Incrementa essa parte em 1. Continua até 5s suficientes estarem no número. Leva cerca de 0,012s no TIO para executar todos os casos de teste.

Xcali
fonte
1

Python 3 , 144 98 86 75 bytes

f=lambda N,k,d=1:k>str(-~N).count("5")and f(N+-(-~N//d+5)%10*d,k,d*10)or-~N

Experimente online!

O(k)

O algoritmo deve arredondar cada dígito (começando pelo menos significativo) para o valor mais próximo de 5 até que a representação decimal do novo número tenha a contagem desejada.

A abordagem original usava uma compreensão de lista abortável (D = iter (intervalo (k)) e lista (D) no trabalho aqui), mas o @ ASCII apenas me convenceu de que nunca venceria o golfe de código. Não gosto de recursão, mas se o algoritmo for escrito para minimizar a profundidade da recursão, um futuro compilador / intérprete será inteligente o suficiente para reimplementá-lo como um loop while.

SmileAndNod
fonte
94?
somente ASCII
93?
somente ASCII
88?
somente ASCII
86?
somente ASCII
1
é (-(-~n//l+5))%10por isso
ASCII-only
0

Python 3 , 59 bytes

Solução recursiva. A profundidade da recursão é um problema (precisa ser alterada para números mais altos), mas está correta.

lambda x,k:eval(("f(x+1,k)","x+1")[str(x+1).count("5")==k])

Experimente online!

jaaq
fonte
4
Isso atende à restrição de tempo se a profundidade da recursão for alta o suficiente? Não consigo imaginar que concluiria o último caso de teste dentro de 10 segundos em qualquer máquina razoável.
Nick Kennedy
0

Python 3, 72 bytes

def f(n,k):
 while(1):
  n+=1
  if str(n).count('5')>=k:return n

Experimente online!

Henry T
fonte
Isso não atende ao requisito de tempo restrito.
Nick Kennedy
0

Java 8, 69 bytes, mais de 60 segundos no TIO com o último caso de teste, ~ 1,5 segundos sem.

(n,k)->{for(;(++n+"").chars().filter(i->i==53).count()<k;);return n;}


Alguém tem alguma idéia de como passar no último caso de teste?

Benjamin Urquhart
fonte
0

PHP ,109 97 bytes (<0,03s no TIO)

function($n,$k){++$n;do if(count_chars($n)[53]>=$k)return$n;while($n+=10**strspn(strrev($n),5));}

Experimente online!

Baseado no algoritmo de @ recursive .

640KB
fonte
0

Retina , 63 bytes

.+$
*
^.+
$.(*__
/((5)|.)+¶(?<-2>_)+$/^+`^.*?(?=5*¶)
$.(*__
1G`

Experimente online! Pega ne kem linhas separadas, mas o link inclui o cabeçalho que converte o conjunto de testes no formato apropriado. Explicação:

.+$
*

Converta kpara unário.

^.+
$.(*__

Incremento n. O *repete seu argumento correto (aqui o primeiro _caractere) o número de vezes dado por seu argumento esquerdo (que, como aqui, assume como padrão a correspondência). Isso resulta em uma sequência desse comprimento. O $((o )implícito) concatena isso com o segundo _e as .causas que o comprimento resultante deve ser obtido. (Na verdade, a Retina 1 é mais inteligente que isso e apenas realiza o cálculo nos comprimentos subjacentes.)

/((5)|.)+¶(?<-2>_)+$/

Teste se 5s suficientes podem ser encontrados npara corresponder aos _s da representação unária de k. Este teste foi jogado no golfe e seria três vezes mais rápido com ^adição após a inicial /e ainda mais rápido se [^5]fosse usado em vez de ..

^+`

Até o teste passar ...

^.*?(?=5*¶)
$.(*__

... incrementa, nmas exclui 5s à direita .

1G`

Excluir k.

Neil
fonte
0

Molusco , 30 bytes, ~ 0.2s no TIO

=Q+r1=qC5R1?<qQ[=qrw<n#:q5QqiQ

Transpiles para esse JS (suíte de testes completa adicionada para o tempo, inputsé claro), onde há uma matriz de entradas ( nprimeiro, ksegundo)

Obrigado @ArBo pela abordagem

Explicação

=Q+r1=qC5R1?<qQ[=qrw<n#:q5QqiQ - Implicit Q = first input
=Q+r1                          - Q = next input (1st input) + 1
     =qC5R1                    - q = 2nd input 5s (eg 555 for k=3)
           ?<qQ[               - if q < Q...
                =qr            -   q = next input (2nd input)
                   w           -   while...
                     n         -     length of...
                      #:q5Q    -       Q.filter(q=>q==5)
                    <          -     is less than...
                           q   -       q
                            iQ -     Increment Q
                               - Implicit output of Q
Skidsdev
fonte
0

C (gcc) , 159 158 152 150 150 149 bytes, ~ 0,04 s

Emite a resposta para STDOUT, com zeros à esquerda.

-3 bytes graças ao ceilingcat

m,j;f(n,k)long n;{char*t,s[17];for(t=s+sprintf(s,"%016ld",++n),m=n=0;m<k&--t>s;m<k&&*t-53?n=*t>53,*t=53:0)for(*t+=n,m=j=17;j--;)m-=s[j]!=53;puts(s);}

Experimente online!

gastropner
fonte