S'agit-il d'un numéro Calvin candidat?

27

Ce défi est un hommage à notre légendaire Challenge Writer ™, Calvin's Hobbies - désormais renommé Helka Homba -, dans le même esprit que Generate Dennis Numbers .

Calvin est un contributeur assez impressionnant à PPCG, avec la 6ème plus grande réputation dans l'ensemble et probablement les meilleures compétences en écriture de défis de nous tous. Cependant, bien sûr, pour ce défi, nous nous concentrerons sur son ID utilisateur.

26997 pourrait ne pas sembler très intéressant au premier abord. En fait, c'est presque intéressant à plusieurs égards. Par exemple, voici un graphique de 26997 mod <n>pour certaines valeurs de n:

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

Cependant, 26997 est l'un des rares nombres pouvant être représentés par , où est un entier> 0.(n * 10)n - nn

Voici les premiers nombres qui peuvent être exprimés de cette façon, que nous appellerons désormais Calvin Numbers :

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

Ces nombres Calvin ont des propriétés intéressantes. Plus de modèles émergent lorsque nous les alignons à droite et mettons en évidence tous les 9s:

capture d'écran

Ceux qui nous intéressent pour ce défi sont:

  • Peu importe n, chaque nombre Calvin se termine par .10n - n

    Ainsi, Calvin (1) se termine par 9Calvin (2) se termine par 98, et la tendance se poursuit 997, 9996, 99995, etc., chaque successive Nombre Calvin compte à rebours et en ajoutant un supplément 9au début.

  • Pour les valeurs de nn % 10 == 0(c'est-à n- dire est divisible par 10), Calvin (n) se termine par .102n - n

    Autrement dit, le motif s'étend sur deux fois plus de chiffres que la normale, avec un nombre supplémentaire de 9s au début égal à n.

  • Quand nest une puissance de 10( 10, 100, 1000, etc.), le modèle va encore plus loin, chaque chiffre est soit un 9ou 0.

    Ce modèle est le suivant: neuf et zéros. C'est plus facile à comprendre dans un graphique (votre solution ne devra de toute façon gérer que des nombres jusqu'à 10000, donc c'est tout ce dont vous avez besoin):(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
    

    Le nombre de neuf présente même plusieurs propriétés de Calvin Numbers lui-même, mais c'est trop de détails pour ce défi.

Défi

Les nombres de Calvin deviennent beaucoup trop gros, beaucoup trop rapidement, pour qu'un «obtenir le nième défi de nombre de Calvin soit réalisable dans les langues sans nombres entiers de précision arbitraire. Par conséquent, le défi consiste à déterminer si un nombre correspond aux modèles ci-dessus - c'est-à-dire un nombre est un "nombre Calvin candidat" ou non.

Voici les critères pour qu'un numéro soit considéré comme un numéro Calvin candidat (ci-après dénommé CCN en abrégé):

  • Il se termine par un nombre qui correspond au modèle d'un entier .10n - nn

    Donc, pour être un CCN, un nombre doit se terminer par 9, ou 98, ou 997, 9996, 99995, etc.

  • Si le dernier chiffre est 0, il doit également se terminer par , comme pour le point précédent.102n - nn

    Cela signifie que ce 12312312399999999999999999999999999999999999980n'est pas un CCN, mais l' 10485759999999999999999999999999999999999999980est (c'est le bon, en fait).

  • Si la valeur de ndans les deux étapes précédentes est une puissance de 10, le nombre entier doit correspondre au troisième modèle décrit ci-dessus.

Entrée sortie

L'entrée sera fournie sous la forme d'une chaîne et elle représentera toujours un nombre inférieur à Calvin(10000) + 10000(qui peut également être exprimé comme ). (Pour clarifier, la plus grande entrée possible est de 50000 neuf et la moins possible est .)10500001

La sortie doit être une valeur vraie si l'entrée représente un nombre qui est un CCN, et une valeur fausse sinon. Pour les définitions de ces termes, voir méta .

Cas de test

Entrées qui devraient donner une valeur vraie:

9
26997
99999999999999999990
437893890380859374999999999999985
10485759999999999999999999999999999999999999980
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999900
259232147948794494594485446818048254863271026096382337884099237269509380022108148908589797968903058274437782549758243999867043174477180579595714249308002763427793979644775390624999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999850
1027092382693614216458468213549848274267264533712122209400214436472662418869004625362768700557725707157332451380426829473630485959339004149867738722096608953864534215649211386152032635755501464142277508289403434891444020975243742942368836579910208098242623061684967794815600266752580663281483595687307649904776800899000484103534573979334062832465904049046104660220505973505050538180250643437654409375728443182380726453925959886901573523090619465866810938078629561306599174923972607310649219442207992951278588892681161967770532314854195892941913447519131828356181219857012229150315613569162930098836696593474888020746503116685472977764615483225628639443918309216648893055765917642528801571387940219884056021782642758517893124803355573565644666880920219871370649806723296262307899148031362558110611562055614190049332906933360406981359187305353360484377948591528385990255894034369523166777375785900198782250651053530165824984161319460372145229568890321167955690544235365954748429659526071133879976348254667755220636244075595290123987745560038255541751251200827018722242010925729483977388235141539109139120069464709993781356334885359200734157439642935779132120725231008699003342908280056975158266782782304550273268246184659474285971272532354920744956064671379745219778013465792544241259691493098443741845166419905920702654683993902052727208789915748213660571390107102976665776293366616518962323688316843422737162297255648351087284877987537325761187239807598009767936409247247417410607537333841650998421607775989879490006136112078031237742552602618996017404602674987181629319060214150458746352191115606789019875790921190573561400752476956787515392210098071407806221412149732955903681690377998882038499470092453400748916257640501488510563314141992573250882286817352407459053866180642034662845694338400386823496563185664221362457851894843439705365082614359220653285052800751906334000698723288454227654466240011140570190301931122357632719033275258503935182047714841766010764632214069382579660602964184231995352310981811428980530707871661256260926759509418970021224649566130995825802676411575264295689037775857674060557127369881379685432291930869072749065675720647595081516460449973211035071920099349836074945813885239767788449030051892470053308048906746273036871919251738920141071153777908913021898541658119513188402271468288293408246833819954990709460114510017598873554406350044072275643892449218394225569069468466660333869360644718801813500285081977089623921689922204185138003164149106921903053243405307546841149889662566529697217181329051855403329741409045760789280950603184354320839342588593832348459938736210265795978675460906504449491132656307256451707333439200130425932724262464823848348296787445624028385464112471408499986690593095395244034885421580844176161027627954578726208600199909963055422192706751708210693468639072881081717288837393188012794669089175022406897622823484220002211676520484520241135615999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999028

Entrées qui devraient entraîner une valeur fausse:

1
26897
79999999999999999990
437893890380859374299999999999985
12312312399999999999999999999999999999999999980
999998999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999900
259232147948794494594485446818048254863271026096382337884099237269509380022108148908589797968903058274437782549758243999867043174477180579595714249308002763427793979644775390624999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999911111
1027092382693614216458468213549848274267264533712122209400214436472662418869004625362768700557725707157332451380426829473630485959339004149867738722096608953864534215649211386152032635755501464142277508289403434891444020975243742942368836579910208098242623061684967794815600266752580663281483595687307649904776800899000484103534573979334062832465904049046104660220505973505050538180250643437654409375728443182380726453925959886901573523090619465866810938078629561306599174923972607310649219442207992951278588892681161967770532314854195892941913447519131828356181219857012229150315613569162930098836696593474888020746503116685472977764615483225628639443918309216648893055765917642528801571387940219884056021782642758517893124803355573565644666880920219871370649806723296262307899148031362558110611562055614190049332906933360406981359187305353360484377948591528385990255894034369523166777375785900198782250651053530165824984161319460372145229568890321167955690544235365954748429659526071133879976348254667755220636244075595290123987745560038255541751251200827018722242010925729483977388235141539109139120069464709993781356334885359200734157439642935779132120725231008699003342908280056975158266782782304550273268246184659474285971272532354920744956064671379745219778013465792544241259691493098443741845166419905920702654683993902052727208789915748213660571390107102976665776293366616518962323688316843422737162297255648351087284877987537325761187239807598009767936409247247417410607537333841650998421607775989879490006136112078031237742552602618996017404602674987181629319060214150458746352191115606789019875790921190573561400752476956787515392210098071407806221412149732955903681690377998882038499470092453400748916257640501488510563314141992573250882286817352407459053866180642034662845694338400386823496563185664221362457851894843439705365082614359220653285052800751906334000698723288454227654466240011140570190301931122357632719033275258503935182047714841766010764632214069382579660602964184231995352310981811428980530707871661256260926759509418970021224649566130995825802676411575264295689037775857674060557127369881379685432291930869072749065675720647595081516460449973211035071920099349836074945813885239767788449030051892470053308048906746273036871919251738920141071153777908913021898541658119513188402271468288293408246833819954990709460114510017598873554406350044072275643892449218394225569069468466660333869360644718801813500285081977089623921689922204185138003164149106921903053243405307546841149889662566529697217181329051855403329741409045760789280950603184354320839342588593832348459938736210265795978675460906504449491132656307256451707333439200130425932724262464823848348296787445624028385464112471408499986690593095395244034885421580844176161027627954578726208600199909963055422192706751708210693468639072881081717288837393188012794669089175022406897622823484220002211676520484520241135615999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999027

Règles

  • Vous ne pouvez pas , à aucun moment de votre programme, gérer des entiers supérieurs à 18446744073709551615( ), si votre langue prend en charge les entiers de précision arbitraire (ou les types de nombres avec une précision suffisamment élevée pour permettre le stockage de nombres supérieurs à cela).264

    Il s'agit simplement d'empêcher les solutions qui bouclent sur tous les nombres Calvin possibles (ou toutes les valeurs possibles de ).10n - n

  • Il s'agit de , donc le code le plus court en octets gagnera.

Poignée de porte
la source
"Si la valeur de n dans les deux étapes précédentes est une puissance de 10, le nombre entier doit correspondre au troisième modèle décrit ci-dessus." À quoi se réfère le «troisième modèle»?
feersum
@feersum Il y a une liste à puces de trois choses - c'est la dernière.
Poignée de porte
Je ne comprends pas pourquoi l'avant-dernier cas de test de falsification est falsifié. Quelle règle viole-t-elle?
Alexis King
@AlexisKing Bonne prise; tout ce qui se termine 9doit être véridique. Fixé.
Poignée de porte
@Doorknob Même avec ce changement, le nombre semble toujours correspondre aux critères. Un nombre se terminant par 845 ne devrait-il pas avoir 152 neuf? Il semble en avoir plus qu'assez. Était-il censé être la moitié du nombre?
Alexis King

Réponses:

8

Raquette, 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))))))

Accepte un nombre de stdin, sorties #tou #f.

Version non golfée:

(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)))

Normalement, je ne fais pas de golf de code, et Racket n'est certainement pas le langage le plus approprié pour cela, mais personne n'avait encore répondu, alors j'ai pensé que je lui donnerais une chance. ;)

Alexis King
la source
Ils attendaient peut-être que je réponde, mais étant donné mon historique de publication, il est probablement préférable que vous n'attendiez pas;)
Calvin's Hobbies