¿Es este un candidato número de Calvin?

27

Este desafío es un tributo a nuestro Legendary Challenge Writer ™, Calvin's Hobbies , ahora renombrado como Helka Homba , en el mismo espíritu que Generate Dennis Numbers .

Calvin es un contribuyente bastante impresionante para PPCG, con la sexta mayor reputación en general y probablemente el mejor desafío de escritura de todos nosotros. Sin embargo, por supuesto, para este desafío, nos centraremos en su ID de usuario.

26997 podría no parecer muy interesante al principio. De hecho, es casi interesante en algunos aspectos. Por ejemplo, aquí hay una tabla de 26997 mod <n>ciertos valores de n:

n   |  26997 % n
----+-----------
3   |  0
4   |  1
5   |  2
6   |  3
7   |  5 :(
8   |  5
9   |  6
10  |  7

Sin embargo, 26997 es uno de los pocos números que puede representar , donde es un entero> 0.(n * 10)n - nn

Aquí están los primeros números que se pueden expresar de esta manera, que en adelante llamaremos Números de Calvin :

9
398
26997
2559996
312499995
46655999994
8235429999993
1677721599999992
387420488999999991
99999999999999999990
28531167061099999999989
8916100448255999999999988
3028751065922529999999999987
1111200682555801599999999999986
437893890380859374999999999999985
184467440737095516159999999999999984
82724026188633676417699999999999999983
39346408075296537575423999999999999999982
19784196556603135891239789999999999999999981
10485759999999999999999999999999999999999999980

Estos números de Calvin tienen algunas propiedades interesantes. Surgen más patrones cuando los alineamos a la derecha y resaltamos todos los 9s:

captura de pantalla

Los que nos interesan para este desafío son:

  • Independientemente de ncada número Calvin termina con .10n - n

    Por lo tanto, Calvin (1) con extremos 9, Calvin (2) con extremos 98, y el patrón continúa 997, 9996, 99995, etc, con cada sucesiva Número Calvin cuenta atrás y añadiendo un extra 9al principio.

  • Para los valores de nwhere n % 10 == 0( nes decir, es divisible por 10), Calvin (n) termina con .102n - n

    Es decir, el patrón se extiende por el doble de dígitos que lo normal, con un número adicional de 9s al principio igual a n.

  • Cuando nes una potencia de 10( 10, 100, 1000, etc.), el patrón se extiende aún más-cada solo dígito es o bien una 9o una 0.

    Este patrón es el siguiente: nueves y ceros. Esto es más fácil de entender en un gráfico (su solución solo tendrá que manejar números de hasta 10000 de todos modos, así que esto es todo lo que necesita):(n + 1) * 10n - nn

    n      |  Calvin(n)
    -------+-----------------------
    10     |  19 nines, 1 zero
    100    |  298 nines, 2 zeroes
    1000   |  3997 nines, 3 zeroes
    10000  |  49998 nines, 4 zeroes
    

    El número de nueves incluso exhibe varias propiedades de Calvin Numbers en sí, pero eso es demasiado detalle para este desafío.

Reto

Los números de Calvin se hacen demasiado grandes, demasiado rápidos para que un "obtener el enésimo desafío del número de Calvin sea ​​factible en idiomas sin enteros de precisión arbitraria. Por lo tanto, el desafío es determinar si un número se ajusta a los patrones anteriores, es decir, si un número es un "candidato número de Calvin" o no.

Estos son los criterios para que un número se considere un número de Calvin candidato (en adelante, CCN para abreviar):

  • Termina con un número que se ajusta al patrón de un entero .10n - nn

    Entonces, para ser un CCN, un número debe terminar con 9, o 98, o 997, 9996, 99995, etc.

  • Si el último dígito es 0, también debe terminar con , para el mismo que en el punto anterior.102n - nn

    Esto significa que 12312312399999999999999999999999999999999999980no es un CCN, pero lo 10485759999999999999999999999999999999999999980es (es el correcto, de hecho).

  • Si el valor de nen los dos pasos anteriores es una potencia de 10, el número entero debe ajustarse al tercer patrón descrito anteriormente.

De entrada y salida

La entrada se proporcionará como una cadena y siempre representará un número menor que Calvin(10000) + 10000(que también se puede expresar como ). (Para aclarar, la mayor entrada posible es 50000 nueves, y la menor entrada posible es ).10500001

La salida debe ser un valor verdadero si la entrada representa un número que es un CCN y un valor falso de lo contrario. Para las definiciones de estos términos, ver meta .

Casos de prueba

Entradas que deberían resultar en un valor verdadero:

9
26997
99999999999999999990
437893890380859374999999999999985
10485759999999999999999999999999999999999999980
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999900
259232147948794494594485446818048254863271026096382337884099237269509380022108148908589797968903058274437782549758243999867043174477180579595714249308002763427793979644775390624999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999850
1027092382693614216458468213549848274267264533712122209400214436472662418869004625362768700557725707157332451380426829473630485959339004149867738722096608953864534215649211386152032635755501464142277508289403434891444020975243742942368836579910208098242623061684967794815600266752580663281483595687307649904776800899000484103534573979334062832465904049046104660220505973505050538180250643437654409375728443182380726453925959886901573523090619465866810938078629561306599174923972607310649219442207992951278588892681161967770532314854195892941913447519131828356181219857012229150315613569162930098836696593474888020746503116685472977764615483225628639443918309216648893055765917642528801571387940219884056021782642758517893124803355573565644666880920219871370649806723296262307899148031362558110611562055614190049332906933360406981359187305353360484377948591528385990255894034369523166777375785900198782250651053530165824984161319460372145229568890321167955690544235365954748429659526071133879976348254667755220636244075595290123987745560038255541751251200827018722242010925729483977388235141539109139120069464709993781356334885359200734157439642935779132120725231008699003342908280056975158266782782304550273268246184659474285971272532354920744956064671379745219778013465792544241259691493098443741845166419905920702654683993902052727208789915748213660571390107102976665776293366616518962323688316843422737162297255648351087284877987537325761187239807598009767936409247247417410607537333841650998421607775989879490006136112078031237742552602618996017404602674987181629319060214150458746352191115606789019875790921190573561400752476956787515392210098071407806221412149732955903681690377998882038499470092453400748916257640501488510563314141992573250882286817352407459053866180642034662845694338400386823496563185664221362457851894843439705365082614359220653285052800751906334000698723288454227654466240011140570190301931122357632719033275258503935182047714841766010764632214069382579660602964184231995352310981811428980530707871661256260926759509418970021224649566130995825802676411575264295689037775857674060557127369881379685432291930869072749065675720647595081516460449973211035071920099349836074945813885239767788449030051892470053308048906746273036871919251738920141071153777908913021898541658119513188402271468288293408246833819954990709460114510017598873554406350044072275643892449218394225569069468466660333869360644718801813500285081977089623921689922204185138003164149106921903053243405307546841149889662566529697217181329051855403329741409045760789280950603184354320839342588593832348459938736210265795978675460906504449491132656307256451707333439200130425932724262464823848348296787445624028385464112471408499986690593095395244034885421580844176161027627954578726208600199909963055422192706751708210693468639072881081717288837393188012794669089175022406897622823484220002211676520484520241135615999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999028

Entradas que deberían resultar en un valor falso:

1
26897
79999999999999999990
437893890380859374299999999999985
12312312399999999999999999999999999999999999980
999998999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999900
259232147948794494594485446818048254863271026096382337884099237269509380022108148908589797968903058274437782549758243999867043174477180579595714249308002763427793979644775390624999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999911111
1027092382693614216458468213549848274267264533712122209400214436472662418869004625362768700557725707157332451380426829473630485959339004149867738722096608953864534215649211386152032635755501464142277508289403434891444020975243742942368836579910208098242623061684967794815600266752580663281483595687307649904776800899000484103534573979334062832465904049046104660220505973505050538180250643437654409375728443182380726453925959886901573523090619465866810938078629561306599174923972607310649219442207992951278588892681161967770532314854195892941913447519131828356181219857012229150315613569162930098836696593474888020746503116685472977764615483225628639443918309216648893055765917642528801571387940219884056021782642758517893124803355573565644666880920219871370649806723296262307899148031362558110611562055614190049332906933360406981359187305353360484377948591528385990255894034369523166777375785900198782250651053530165824984161319460372145229568890321167955690544235365954748429659526071133879976348254667755220636244075595290123987745560038255541751251200827018722242010925729483977388235141539109139120069464709993781356334885359200734157439642935779132120725231008699003342908280056975158266782782304550273268246184659474285971272532354920744956064671379745219778013465792544241259691493098443741845166419905920702654683993902052727208789915748213660571390107102976665776293366616518962323688316843422737162297255648351087284877987537325761187239807598009767936409247247417410607537333841650998421607775989879490006136112078031237742552602618996017404602674987181629319060214150458746352191115606789019875790921190573561400752476956787515392210098071407806221412149732955903681690377998882038499470092453400748916257640501488510563314141992573250882286817352407459053866180642034662845694338400386823496563185664221362457851894843439705365082614359220653285052800751906334000698723288454227654466240011140570190301931122357632719033275258503935182047714841766010764632214069382579660602964184231995352310981811428980530707871661256260926759509418970021224649566130995825802676411575264295689037775857674060557127369881379685432291930869072749065675720647595081516460449973211035071920099349836074945813885239767788449030051892470053308048906746273036871919251738920141071153777908913021898541658119513188402271468288293408246833819954990709460114510017598873554406350044072275643892449218394225569069468466660333869360644718801813500285081977089623921689922204185138003164149106921903053243405307546841149889662566529697217181329051855403329741409045760789280950603184354320839342588593832348459938736210265795978675460906504449491132656307256451707333439200130425932724262464823848348296787445624028385464112471408499986690593095395244034885421580844176161027627954578726208600199909963055422192706751708210693468639072881081717288837393188012794669089175022406897622823484220002211676520484520241135615999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999027

Reglas

  • Es posible que no , en cualquier punto de su programa, números enteros mango más grande que 18446744073709551615( ), si su idioma tiene soporte para números enteros de precisión arbitraria (o tipos de números con una alta precisión suficiente para permitir el almacenamiento de números mayores que esto).264

    Esto es simplemente para evitar soluciones que recorran todos los números de Calvin posibles (o todos los valores posibles de ).10n - n

  • Este es el , por lo que ganará el código más corto en bytes.

Pomo de la puerta
fuente
"Si el valor de n en los dos pasos anteriores es una potencia de 10, el número entero debe ajustarse al tercer patrón descrito anteriormente". ¿A qué se refiere el 'tercer patrón'?
feersum
@feersum Hay una lista con viñetas de tres cosas: es la última.
Pomo de la puerta
No entiendo por qué el penúltimo caso de prueba falso es falso. ¿Qué regla viola?
Alexis King
@AlexisKing Buena captura; todo lo que termine 9debe ser verdad. Fijo.
Pomo de la puerta
@Doorknob Incluso con ese cambio, el número todavía parece ajustarse a los criterios. ¿No debería un número que termina en 845 tener 152 nueves? Parece tener más que suficiente. ¿Se suponía que había la mitad del número?
Alexis King

Respuestas:

8

Raqueta, 353

(require srfi/13)(let([s(~a(read))])(for/or([n(range 1 999)])(and(let*([y(string-length(~a n))])(string-suffix?(string-append(make-string(-(if(=(modulo n 10)0)(* 2 n)n)y)#\9)(~r #:min-width y #:pad-string"0"(-(expt 10 y)n)))s))(let([n(inexact->exact(/(log n)(log 10)))])(or(not(integer? n))(string-prefix?(make-string(-(*(+ 1 n)(expt 10 n))n)#\9)s))))))

Acepta un número de stdin, salidas #to #f.

Versión sin golf:

(require srfi/13)

(define (calvin? str)
  (for/or ([n (in-range 1 10001)])
    (and (10^n-n$? n str)
         (or (not (integer? (/ (log n) (log 10))))
             (expt-of-ten-check? n str)))))

(define (10^n-n$? n str)
  (let* ([div-by-ten? (zero? (modulo n 10))]
         [digits (string-length (~a n))]
         [nines (- (if div-by-ten? (* 2 n) n) digits)]
         [suffix (string-append (make-string nines #\9)
                                (~r #:min-width digits #:pad-string "0" (- (expt 10 digits) n)))])
    (string-suffix? suffix str)))

(define (expt-of-ten-check? n str)
  (let* ([n (inexact->exact (/ (log n) (log 10)))]
         [nines (- (* (add1 n) (expt 10 n)) n)]
         [prefix (make-string nines #\9)])
    (string-prefix? prefix str)))

Normalmente no hago golf de código, y Racket ciertamente no es el lenguaje más adecuado para ello, pero nadie había respondido aún, así que pensé que lo intentaría. ;)

Alexis King
fuente
Es posible que hayan estado esperando que responda, pero dado mi historial de publicaciones, probablemente sea mejor que no hayas esperado;)
Calvin's Hobbies