Tri des nombres de 1 à 999 999 999 en mots sous forme de chaînes

Question

Intéressant puzzle de programmation:

Si les entiers de 1 à 999,999,999 sont écrits les mots, triés par ordre alphabétique, et concaténés, ce qui est le 51 milliardième lettre?

Pour être plus précis: si les entiers de 1 pour 999,999,999 sont exprimés en mots (en omettant les espaces, "et", et la ponctuation - voir la note ci-dessous pour le format), et triés par ordre alphabétique, de sorte que les six premiers les entiers sont

• huit
• dix-huit
• eighteenmillion
• eighteenmillioneight
• eighteenmillioneighteen
• eighteenmillioneighteenthousand

et la dernière est

• twothousandtwohundredtwo

puis la lecture de haut en bas, de gauche à à droite, le 28 lettre complète le l'orthographe de l'entier "eighteenmillion".

51 milliardième lettre complète l'orthographe d'un entier. Dont l'un, et quelle est la somme de toutes les entiers à ce point?

Remarque: Par exemple, 911,610,034 est écrit "ninehundredelevenmillionsixhundredtenthousandthirtyfour"; 500,000,000 est écrit "fivehundredmillion"; 1,709 est écrit "onethousandsevenhundrednine".

Je suis tombé sur ça sur un blog de programmation ğ Occasionnellement Raisonnable", et ne pouvait pas penser à un moyen sympa de le faire, l'auteur du message concerné , raconte sa première tentative mangé par 1,5 GO de mémoire en 10 minutes, et il n'avait fait jusqu'à 20 000 000 d' ("twentymillion").

Quelqu'un peut-il penser à venir avec de les partager avec le groupe un roman/approche astucieuse pour cela?

Answer 1

Edit: Résolu!

Vous pouvez créer un générateur qui génère les nombres dans l'ordre de tri. Il existe quelques règles pour la comparaison de chaînes concaténées que je pense que la plupart d'entre nous savent implicitement:

• < a+b, où b est non nulle.
• a+b < a+c, où b < c.
• a+b < c+d, où a < c, et n'est pas un sous-ensemble de c.

Si vous commencez avec une liste triée des 1000 premiers numéros, vous pouvez facilement générer le reste en ajoutant des "mille" ou "m" et de la concaténation d'un autre groupe de 1000.

Voici le code complet, en Python:

import heapq

first_thousand=[('', 0), ('one', 1), ('two', 2), ('three', 3), ('four', 4),
                ('five', 5), ('six', 6), ('seven', 7), ('eight', 8),
                ('nine', 9), ('ten', 10), ('eleven', 11), ('twelve', 12),
                ('thirteen', 13), ('fourteen', 14), ('fifteen', 15),
                ('sixteen', 16), ('seventeen', 17), ('eighteen', 18),
                ('nineteen', 19)]
tens_name = (None, 'ten', 'twenty', 'thirty', 'forty', 'fifty', 'sixty',
             'seventy','eighty','ninety')
for number in range(20, 100):
    name = tens_name[number/10] + first_thousand[number%10][0]
    first_thousand.append((name, number))
for number in range(100, 1000):
    name = first_thousand[number/100][0] + 'hundred' + first_thousand[number%100][0]
    first_thousand.append((name, number))

first_thousand.sort()

def make_sequence(base_generator, suffix, multiplier):
    prefix_list = [(name+suffix, number*multiplier)
                   for name, number in first_thousand[1:]]
    prefix_list.sort()
    for prefix_name, base_number in prefix_list:
        for name, number in base_generator():
            yield prefix_name + name, base_number + number
    return

def thousand_sequence():
    for name, number in first_thousand:
        yield name, number
    return

def million_sequence():
    return heapq.merge(first_thousand,
                       make_sequence(thousand_sequence, 'thousand', 1000))

def billion_sequence():
    return heapq.merge(million_sequence(),
                       make_sequence(million_sequence, 'million', 1000000))

def solve(stopping_size = 51000000000):
    total_chars = 0
    total_sum = 0
    for name, number in billion_sequence():
        total_chars += len(name)
        total_sum += number
        if total_chars >= stopping_size:
            break
    return total_chars, total_sum, name, number

Il a fallu un certain temps pour s'exécuter, à environ une heure. 51 milliardième de caractère est le dernier caractère de sixhundredseventysixmillionsevenhundredfortysixthousandfivehundredseventyfive, et la somme des entiers jusqu'à ce point est 413,540,008,163,475,743.

Answer 2

Je voudrais trier les noms des 20 premiers nombres entiers et les noms des dizaines, des centaines et des milliers, combien de numéros de commencer par chacun de ceux-ci, et à partir de là.

Par exemple, les premiers sont [ eight, eighteen, eighthundred, eightmillion, eightthousand, eighty, eleven, ....

Les numéros commençant par "huit" 8. Avec "eighthundred", 800-899, 800,000-899,999, 800,000,000-899,999,999. Et ainsi de suite.

Le nombre de lettres dans la concaténation de mots pour 0 ( représenté par la chaîne vide ) à 99 peuvent être trouvés et ont totalisé, ce qui peut être multipliée par "mille"=8 ou "m"=7 ajoutée pour les gammes supérieures. La valeur de 800-899 sera 100 fois la longueur de la "eighthundred" plus la longueur de 0 à 99 ans. Et ainsi de suite.

Answer 3

Ce gars a une solution au puzzle écrit en Haskell. Apparemment, Michael Borgwardt avait raison d'utiliser un Trie pour trouver la solution.

Answer 4

Ces chaînes vont avoir beaucoup, beaucoup de préfixes communs - cas d'utilisation parfait pour un trie , ce qui réduirait considérablement l'utilisation de la mémoire et probablement aussi le temps d'exécution.

Answer 5

(De la première tentative de ce qui est mal, mais je vais le laisser comme il est plus utile de voir les erreurs sur la façon de résoudre quelque chose, plutôt que de simplement la réponse finale.)

Je voudrais tout d'abord générer les chaînes de 0 à 999 et de les stocker dans un tableau appelé thousandsStrings. L'élément 0 est "" et "" représente un passage à vide dans les listes ci-dessous.

Le thousandsString le programme d'installation utilise les éléments suivants:

Units: "" one two three ... nine

Teens: ten eleven twelve ... nineteen

Tens: "" "" twenty thirty forty ... ninety

Le thousandsString l'installation est quelque chose comme ceci:

thousandsString[0] = ""

for (i in 1..10)
   thousandsString[i] = Units[i]
end

for (i in 10..19)
   thousandsString[i] = Teens[i]
end

for (i in 20..99)
   thousandsString[i] = Tens[i/10] + Units[i%10]
end

for (i in 100..999)
   thousandsString[i] = Units[i/100] + "hundred" + thousandsString[i%100]
end

Ensuite, je voudrais trier ce tableau par ordre alphabétique.

Ensuite, en supposant t1 t2 t3 sont des chaînes de caractères pris de thousandsString, toutes les chaînes ont la forme

t1

OU

t1 + m + t2 + mille + t3

OU

t1 + mille + t2

De sortie dans le bon ordre, je voudrais traiter les différentes cordes, suivi par des millions de chaînes de suivi de la chaîne + des milliers de chaînes de caractères.

foreach (t1 in thousandsStrings)

   if (t1 == "")
     continue;

   process(t1)

   foreach (t2 in thousandsStrings)
      foreach (t3 in thousandsStrings)
         process (t1 + "million" + t2 + "thousand" + t3)
      end
   end

   foreach (t2 in thousandsStrings)
       process (t1 + "thousand" + t2)
   end
end

où le processus implique le magasin de la précédente somme de la longueur, puis ajouter la nouvelle longueur de la chaîne de la somme et si la nouvelle somme est >= à votre cible somme, vous cracher les résultats, et peut-être de retour ou de sortir de la boucle, tout ce qui vous rend heureux.

=====================================================================

Deuxième tentative, les autres réponses étaient justes que vous avez besoin pour utiliser 3k des chaînes au lieu de 1k chaînes comme base.

Démarrer avec le thousandsString à partir de ci-dessus, mais baisse de la vierge "" pour zéro. Qui laisse 999 éléments et d'appeler cette uStr (unités de la chaîne).

Créer deux ensembles:

tStr = the set of all uStr + "thousand"

mStr = the set of all uStr + "million"

Maintenant, créez deux autres ensemble des syndicats:

mtuStr = mStr union tStr union uStr

tuStr = tStr union uStr

Afin uStr, tuStr, mtuStr

Maintenant, la boucle et la logique ici sont un peu différente de celle d'avant.

foreach (s1 in mtuStr)
   process(s1)

   // If this is a millions or thousands string, add the extra strings that can
   // go after the millions or thousands parts.

   if (s1.contains("million"))
      foreach (s2 in tuStr)
         process (s1+s2)          

         if (s2.contains("thousand"))
            foreach (s3 in uStr)
               process (s1+s2+s3)
            end
         end
      end
   end

   if (s1.contains("thousand"))
      foreach (s2 in uStr)
         process (s1+s2)
      end
   end
end