Siguiente número con k cinco

8

Desafío:

Su programa tomará dos enteros ny kcomo entrada, y generará el entero más pequeño mayor que (pero no igual a) nque contiene al menos kocurrencias del dígito 5.

Puedes asumir 1 ≤ k ≤ 15y 1 ≤ n < 10**15.

Este es un desafío de . Su programa debe ejecutarse en TIO para todos los casos de prueba y completarse en 10 segundos en total.

Reglas generales:

  • Este es el , por lo que gana la respuesta más corta en bytes.
    No permita que los lenguajes de code-golf lo desanimen a publicar respuestas con lenguajes que no sean codegolf. Intenta encontrar una respuesta lo más breve posible para cualquier lenguaje de programación.

  • Las reglas estándar se aplican a su respuesta con las reglas de E / S predeterminadas , por lo que puede usar STDIN / STDOUT, funciones / método con los parámetros adecuados y programas completos de tipo retorno. Tu llamada. Los parámetros de la función pueden tomarse en cualquier orden, pero especifique en su respuesta.

  • Las lagunas predeterminadas están prohibidas.
  • Debe agregar un enlace con una prueba para su código (es decir, TIO ).
  • El encabezado de respuesta debe enumerar la puntuación en bytes, pero también el tiempo total necesario para todos los casos de prueba en TIO
  • Si su idioma no está en TIO, el código debería terminar mucho menos de 10 segundos en su máquina para que esté seguro de que es lo suficientemente rápido en cualquier computadora razonable.
  • Agregar una explicación para su respuesta es muy recomendable.

Casos de prueba:

(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

Ejemplo de programa:

Este programa es correcto.

vaquero
fuente
1
Tenga en cuenta que la sincronización en TIO no es perfectamente confiable , aunque es insuficiente para el código más rápido , probablemente sea suficiente para el tiempo restringido .
Laikoni
Supongo que la respuesta correcta para (n, k) = (45, 1)es 50? Algunas de las respuestas se equivocan.
Neil

Respuestas:

5

R + stringr, 85 84 76 bytes, .062s en 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)

Pruébalo en línea!

-1 byte gracias a Robert S.
-8 bytes gracias a Giuseppe.

Una solución recursiva simple sería incrementar en 1 hasta que se encuentre la respuesta, pero esto no cumpliría con la restricción de tiempo. Para cumplir con la restricción de tiempo, esta función hace uso del hecho de que si faltan 5s p, podemos aumentar en 2 * 10 ^ (p-2).

Tenga en cuenta que cuando p = 1, el incremento se convierte en 0.2. Esto está bien, ya que después de 5 pasos volvemos a un número entero, y ninguno de los números decimales encontrados en el tiempo medio tiene un 5. extra. En cambio, si aumentamos en 5 * 10 ^ (p-2) o en 1 * 10 ^ (p-2), entonces encontraríamos f (24, 1) = 24.5 en lugar de 25 por ejemplo.

Robin Ryder
fuente
2
Ahorre 1 byte utilizando una ifvariante de función.
Robert S.
@RobertS. Gracias. No sabía sobre esa variante; ¿Hay algún lugar donde pueda leer más al respecto?
Robin Ryder
1
También puede hacer preguntas en el chat de golfistas R que no es muy activo pero es mejor que nada :-)
Giuseppe
2
76 bytes : no estoy muy seguro de lo que aestaba haciendo, así que lo eliminé y parece estar bien.
Giuseppe
3

Jelly , 37 bytes 0.113 s en TIO

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

Pruébalo en línea!

Esto funciona por

  1. calcular el número máximo de dígitos en la entrada más uno ky hacer un número con tantos cinco
  2. Restando la entrada de ese número
  3. Generando todos los sufijos de ese número
  4. También genera todas las potencias de diez desde 1 hasta la siguiente mayor que la entrada
  5. Agrega cada uno de los números en 3 y 4 a la entrada
  6. Elimina respuestas con muy pocos 5
  7. Filtra la entrada de las respuestas.
  8. Y devuelve el mínimo
Nick Kennedy
fuente
@KevinCruijssen lo siento, quise decir que muchos cinco
Nick Kennedy
1
Hmm .. Parece que falla [557,1](resultados en 558lugar de 560); El caso de prueba en la descripción parece incorrecto, ya que [557,2]debería resultar en su 558lugar.
Kevin Cruijssen
3
@KevinCruijssen Le pregunté acerca de esto: es al menos k 5s no exactamente k.
Nick Kennedy
Ah ok, entonces es correcto. :)
Kevin Cruijssen
2

05AB1E , 33 32 bytes

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

El sorprendente enfoque de PortNickKennedy en su respuesta de Jelly , ¡así que asegúrate de votarlo!

kn

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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
fuente
2

Stax , 17 bytes (6.861 segundos totales en TIO)

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

Ejecutar y depurarlo

Este programa toma ky nen la entrada estándar separados por un espacio. Stax no tiene una forma conveniente de ejecutar múltiples casos de prueba en TIO, por lo que ejecuté cada entrada por separado y sumé el tiempo. El 99% del tiempo está en el inicio del proceso de interpretación. Usando el intérprete de JavaScript en staxlang.xyz, todos los casos de prueba se ejecutan en 50 milisegundos.

Último caso de prueba en ¡Pruébelo en línea!

Procedimiento :

  1. Incremento de entrada
  2. Si hay suficientes 5s, finalice e imprima
  3. t= número de 5s finales en el número
  4. Añadir 10 ** t
  5. Ir a 2
recursivo
fuente
2

Python 2 , 70 68 bytes (.025 segundos en TIO)

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

Pruébalo en línea!

Esto podría ser un poco exagerado; es correcto en todos los casos y termina en un tiempo insignificante para los casos de prueba, pero no termina en un tiempo razonable para otros casos. Sin embargo, técnicamente cumple los requisitos.

En resumen, si el número más pequeño con kcinco es mayor que n, usamos ese número ya que obviamente es la solución correcta. Si no es así, recurrimos al enfoque recursivo estándar.

ArBo
fuente
Siempre aprecio las reglas de flexión en el golf.
recursivo el
1

Perl 5 -pl , 44 bytes

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

Pruébalo en línea!

Encuentra cuál es el número sin sus 5s finales. Incrementa esa porción en 1. Continúa hasta que haya suficientes 5s en el número. Toma alrededor de .012s en TIO para ejecutar todos los casos de prueba.

Xcali
fuente
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

Pruébalo en línea!

O(k)

El algoritmo consiste en redondear cada dígito (comenzando por el menos significativo) al valor más cercano de 5 hasta que la representación decimal del nuevo número tenga el recuento deseado.

El enfoque original utilizaba una comprensión de lista abortable (D = iter (rango (k)) y lista (D) en el trabajo aquí), pero @ ASCII-only me ha convencido de que nunca ganará el código golf. No me gusta la recursividad, pero si el algoritmo está escrito para minimizar la profundidad de recursión, entonces un futuro compilador / intérprete será lo suficientemente inteligente como para volver a implementarlo como un ciclo while.

SmileAndNod
fuente
94?
Solo ASCII
93?
Solo ASCII
88?
Solo ASCII
86?
Solo ASCII
1
está (-(-~n//l+5))%10es la razón
ASCII de sólo
0

Python 3 , 59 bytes

Solución recursiva. La profundidad de recursión es un problema (debe cambiarse para números más altos), pero es correcta.

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

Pruébalo en línea!

jaaq
fuente
44
¿Cumple esto con la restricción de tiempo si la profundidad de recursión es lo suficientemente alta? No puedo imaginar que completaría el último caso de prueba en 10 segundos en una máquina razonable.
Nick Kennedy el
0

Python 3, 72 bytes

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

Pruébalo en línea!

Henry T
fuente
Esto no cumple con el requisito de tiempo restringido.
Nick Kennedy el
0

Java 8, 69 bytes, más de 60 segundos en TIO con el último caso de prueba, ~ 1.5 segundos sin.

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


¿Alguien tiene alguna idea sobre cómo pasar el último caso de prueba?

Benjamin Urquhart
fuente
0

PHP ,109 97 bytes, (<0.03s en TIO)

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

Pruébalo en línea!

Basado en el algoritmo de @ recursive .

640 KB
fuente
0

Retina , 63 bytes

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

Pruébalo en línea! Toma ny ken líneas separadas, pero el enlace incluye un encabezado que convierte el conjunto de pruebas al formato apropiado. Explicación:

.+$
*

Convierte ka unario.

^.+
$.(*__

Incremento n. El *repite su argumento derecho (aquí el primer _carácter) el número de veces dado por su argumento izquierdo (que, como aquí, por defecto es la coincidencia). Esto da como resultado una cadena de esa longitud. El $((el )está implícito) luego concatena eso con el segundo _y .hace que se tome la longitud resultante. (En realidad, Retina 1 es más inteligente que eso y solo realiza el cálculo en las longitudes subyacentes en primer lugar).

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

Pruebe si 5se pueden encontrar suficientes s npara coincidir con los _s de la representación unaria de k. Esta prueba ha sido desarrollada y sería tres veces más rápida si se ^agrega después de la inicial /y aún más rápida si [^5]se usara en lugar de ..

^+`

Hasta que pase la prueba ...

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

... incrementa npero excluye los 5s finales .

1G`

Eliminar k.

Neil
fuente
0

Almeja , 30 bytes, ~ 0.2s en TIO

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

Transpiles a este JS (conjunto de pruebas completo agregado para el tiempo, por supuesto), donde inputshay una matriz de las entradas ( nprimero, ksegundo)

Gracias @ArBo por el enfoque

Explicación

=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
fuente
0

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

Emite la respuesta a STDOUT, con ceros a la izquierda.

-3 bytes gracias a 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);}

Pruébalo en línea!

gastropner
fuente