Сортировка чисел от 1 до 999 999 999 слов в виде строк

Ответ 1

Изменить: разрешено!

Вы можете создать генератор, который выводит числа в отсортированном порядке. Существует несколько правил сравнения конкатенированных строк, которые, как мне кажется, большинство из нас знают неявно:

• a < a + b, где b не равно null.
• a + b < a + c, где b < с.
• a + b < c + d, где a < c, a не является подмножеством c.

Если вы начинаете с отсортированного списка первых 1000 номеров, вы можете легко сгенерировать остальные, добавив "тысячу" или "миллион" и объединив еще одну группу из 1000.

Здесь полный код в 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

Прошло немного времени, около часа. 51-й миллионный персонаж является последним персонажем шестисотдесятидесяти миллисекундсостоящих столетий, а сумма целых чисел до этой точки - 413,540,008,163,475,743.

Ответ 2

Я бы отсортировал имена первых 20 целых чисел и имена десятков, сотен и тысяч, выяснил, сколько чисел начинается с каждого из них, и оттуда.

Например, первые несколько [ eight, eighteen, eighthundred, eightmillion, eightthousand, eighty, eleven, ....

Числа, начинающиеся с "восьмерки", равны 8. С "восьмеркой", 800-899, 800 000-899999, 800 000 000-899 999 999. И так далее.

Число букв в конкатенации слов для 0 (представленное пустой строкой) до 99 может быть найдено и суммировано; это можно умножить на "тыс." = 8 или "млн." = 7 для более высоких диапазонов. Значение 800-899 будет в 100 раз больше длины "восьмерки" плюс длина 0-99. И так далее.

Ответ 3

У этого парня есть решение головоломки, написанной в Haskell. По-видимому, Майкл Боргвардт был прав в использовании Trie для поиска решения.

Ответ 4

Эти строки будут иметь множество и множество общих префиксов - идеальный вариант использования trie, который резко сократит память использование и, возможно, также время работы.

Ответ 5

(Первая попытка в этом неверна, но я оставлю ее, потому что более полезно видеть ошибки на пути к решению чего-то, а не только окончательного ответа.)

Сначала я бы сгенерировал строки от 0 до 999 и сохранил их в массиве, называемом тысячами. Элемент 0 является ", а" " представляет пробел в списках ниже.

Настройка тысячString использует следующее:

Units: "" one two three ... nine

Teens: ten eleven twelve ... nineteen

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

Настройка тысячString выглядит примерно так:

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

Затем я отсортировал бы этот массив в алфавитном порядке.

Тогда, если t1 t2 t3 - это строки, взятые из тысячString, все строки имеют вид

t1

ИЛИ

t1 + million + t2 + тыс. + t3

ИЛИ

t1 + тыс. + t2

Чтобы выводить их в правильном порядке, я обрабатывал отдельные строки, за которыми следуют миллионы строк, за которыми следуют строки + тысячи.

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

где процесс означает сохранение предыдущей суммы, а затем добавляет новую длину строки к сумме, и если новая сумма равнa >= ваша целевая сумма, вы выплевываете результаты и, возможно, возвращаетесь или выходите из циклов, независимо от того, делает тебя счастливым.

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

Вторая попытка, другие ответы были правильными, что вам нужно использовать 3k строки вместо строк 1k в качестве базы.

Начните с тысячиString сверху, но оставьте пустой "" для нуля. Это оставляет 999 элементов и вызывает это uStr (строка единиц).

Создайте еще два набора:

tStr = the set of all uStr + "thousand"

mStr = the set of all uStr + "million"

Теперь создайте еще два объединения:

mtuStr = mStr union tStr union uStr

tuStr = tStr union uStr

Закажите uStr, tuStr, mtuStr

Теперь цикл и логика здесь немного отличаются от предыдущих.

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

Ответ 6

Здесь мое решение python, которое выдает правильный ответ за долю секунды. Я вообще не программист на питоне, поэтому приношу извинения за любые вопиющие ошибки стиля кода.

#!/usr/bin/env python

import sys

ONES=[
    "",         "one",      "two",      "three",        "four", 
    "five",     "six",      "seven",    "eight",        "nine",
    "ten",      "eleven",   "twelve",   "thirteen",     "fourteen",
    "fifteen",  "sixteen",  "seventeen","eighteen",     "nineteen",
]
TENS=[
    "zero",     "ten",      "twenty",   "thirty",       "forty",
    "fifty",    "sixty",    "seventy",  "eighty",       "ninety",
]

def to_s_h(i):
    if(i<20):
        return(ONES[i])
    return(TENS[i/10] + ONES[i%10]) 

def to_s_t(i):
    if(i<100):
        return(to_s_h(i))
    return(ONES[i/100] + "hundred" + to_s_h(i%100))

def to_s_m(i):
    if(i<1000):
        return(to_s_t(i))
    return(to_s_t(i/1000) + "thousand" + to_s_t(i%1000))

def to_s_b(i):
    if(i<1000000):
        return(to_s_m(i))
    return(to_s_m(i/1000000) + "million" + to_s_m(i%1000000))


def try_string(s,t):
    global letters_to_go,word_sum
    l=len(s)
    letters_to_go -= l
    word_sum += t
    if(letters_to_go == 0):
        print "solved: " + s
        print "sum is: " + str(word_sum)
        sys.exit(0)
    elif(letters_to_go < 0):
        print "failed: " + s + " " + str(letters_to_go)
        sys.exit(-1)

def solve(depth,prefix,prefix_num):
    global millions,thousands,ones,letters_to_go,onelen,thousandlen,word_sum
    src=[ millions,thousands,ones ][depth]
    for x in src:
        num=prefix + x[2]
        nn=prefix_num+x[1]
        try_string(num,nn)
        if(x[0] == 0):
            continue
        if(x[0] == 1):
            stl=(len(num) * 999) + onelen
            ss=(nn*999) + onesum
        else:
            stl=(len(num) * 999999) + thousandlen + onelen*999
            ss=(nn*999999) + thousandsum
        if(stl < letters_to_go):
            letters_to_go -= stl
            word_sum += ss
        else:
            solve(depth+1,num,nn)


ones=[]
thousands=[]
millions=[]
onelen=0
thousandlen=0
onesum=(999*1000)/2
thousandsum=(999999*1000000)/2



for x in range(1,1000):
    s=to_s_b(x)
    l=len(s)
    ones.append( (0,x,s) )
    onelen += l
    thousands.append( (0,x,s) )
    thousands.append( (1,x*1000,s + "thousand") )
    thousandlen += l + (l+len("thousand"))*1000
    millions.append( (0,x,s) )
    millions.append( (1,x*1000,s + "thousand") )
    millions.append( (2,x*1000000,s + "million") )

ones.sort(key=lambda x: x[2])
thousands.sort(key=lambda x: x[2])
millions.sort(key=lambda x: x[2])

letters_to_go=51000000000
word_sum=0

solve(0,"",0)

Он работает, предварительно вычисляя длину чисел от 1.999 и 1.999999, чтобы он мог пропускать целые поддеревья, если не знает, что ответ лежит где-то внутри них.

Ответ 7

Что я сделал: 1) Итерация через 1 - 999 и генерация слов для каждого из них. По мере создания: 2) Создайте 3 структуры данных, где каждый node имеет указатель на дочерние элементы, а каждый node имеет значение символа и указатель на Siblings. (Двоичное дерево, на самом деле, но мы не хотим думать об этом таким образом обязательно - для меня это легче концептуализировать как список братьев и сестер со списками детей, зависающих, но если вы думаете об этом (нарисуйте рис. } вы поймете, что это на самом деле двоичное дерево). Эти 3 структуры данных создаются следующим образом: а) первый со словом, сгенерированным (т.е. 1-999, отсортированным по алфавиту) б) все значения в первом + все значения с добавлением "тыс." (т.е. 1-999 и 1000-999 000 (шаг 1000) (всего значений в 1998 г.) c) все значения в B + все значения в с миллионом прилагаемых (всего 2997 значений) 3) Для каждого листа node в (b) добавьте Child as (a). Для каждого листа node в (c) добавьте ребенка как (b). 4) Пройдите по дереву, подсчитав, сколько персонажей мы проходим и останавливаемся на 51 миллиард.

ПРИМЕЧАНИЕ. Это не суммирует значения (я не читал этот бит, когда я изначально это сделал), и работает чуть более 3 минут (около 192 секунд обычно, используя С++). ПРИМЕЧАНИЕ 2: (в случае, если это не очевидно) хранится только 5 994 значения, но они хранятся таким образом, что через дерево

Я сделал это примерно год-два назад, когда я наткнулся на него, и с тех пор понял, что существует множество оптимизаций (самый длинный бит - это движение по дереву - ДОЛГОЙ ПУТЬ). Есть несколько оптимизаций, которые, по моему мнению, значительно улучшат этот подход, но я никогда не буду беспокоиться об этом, кроме как оптимизировать избыточные узлы в дереве, чтобы они сохраняли строки, а не символы

Я видел, как люди утверждают, что они решили его менее чем за 5 секунд....

Ответ 8

странная, но забавная идея.

постройте разреженный список длин числа от 0 до 9, затем 10-90 на десятки, затем 100, 1000 и т.д., до миллиарда, индексы - это значение целой части, длина которой сохраняется.

напишите функцию для вычисления числа в виде длины строки, используя таблицу. (разбивая число на части и просматривая длину aprts, никогда не создавая строку).

тогда вы выполняете математику только по мере прохождения чисел, вычисляя длину из таблица после суммирования для вашей суммы.

с суммой и значением конечного целого числа, определите целое число, которое будет записано, и volia, вы закончили.

Ответ 9

Да, я снова, но совершенно другой подход.

Просто, вместо того, чтобы хранить слова "onethousandeleventyseven", вы пишете сортировку, чтобы использовать ее при сравнении.

Crude java POC:

public class BillionsBillions implements Comparator {
    public int compare(Object a, Object b) {
        String s1 = (String)a; // "1234";
        String s2 = (String)b; // "1235";

        int n1 = Integer.valueOf(s1);
        int n2 = Integer.valueOf(s2);

        String w1 = numberToWords(n1);
        String w2 = numberToWords(n2);

        return w1.compare(w2);
    }

    public static void main(String args[]) {
        long numbers[] = new long[1000000000]; // Bring your 64 bit JVMs

        for(int i = 0; i < 1000000000; i++) {
            numbers[i] = i;
        }

        Arrays.sort(numbers, 0, numbers.length, new BillionsBillions());

        long total = 0;

        for(int i : numbers) {
            String l = numberToWords(i);
            long offset = total + l - 51000000000;

            if (offset >= 0) {
                String c = l.substring(l - offset, l - offset + 1);
                System.out.println(c);
                break;
            }
         }
    }
}

"numberToWords" оставлен как упражнение для читателя.

Ответ 10

Вам нужно сохранить всю строку в памяти?

Если нет, просто сохраните, сколько символов вы уже добавили. Для каждой итерации вы проверяете длину следующего текстового представления. Если он превышает букву, которую вы ищете, буква должна быть в этой строке, поэтому извлеките ее им индексированием, распечатайте и остановите выполнение. В противном случае добавьте длину строки в число символов и перейдите к следующему номеру.

Ответ 11

Все строки начинаются с одной, десяти, двух, двадцать, трех, тридцати, четырех и т.д., поэтому я начну с выяснения, сколько из них в каждом из ковши, Тогда вы должны хотя бы знать, в каком ведре вам нужно подойти ближе.

Затем я бы посмотрел на подразделение ведер дальше на основе возможных префиксов. Например, в течение девятисот, вы будете иметь все те же самые ведра, с которыми вам приходилось начинать, только для чисел, начинающихся с 900.

Ответ 12

Вопрос заключается в эффективном хранении данных, а не в строковых манипуляциях. Создайте enum для представления слов. слова должны отображаться в упорядоченном порядке, так что когда придет время сортировать, это простое сравнение. Теперь создайте список и выполните сортировку. используйте тот факт, что вы знаете, как долго каждое слово связано с перечислением, чтобы добавить персонажа, который вам нужен.

Ответ 13

Честно говоря, я бы позволил RDBMS, как SQL Server или Oracle, сделать для меня работу.

• Вставьте миллиарды строк в индексированную таблицу.
• Вычислить столбец длины строки.
• Начните снимать верхние X-записи за раз с SUM, пока я не доберусь до 51 миллиарда.

Мог бы немного побить сервер, так как ему нужно было бы сделать много дискового ввода-вывода, но в целом я думаю, что я мог бы найти ответ быстрее, чем тот, кто напишет программу для этого.

Иногда просто делать это - это то, что действительно хочет клиент, и может заботиться о том, какой фантастический шаблон дизайна или структура данных вы использовали.

Ответ 14

У вас есть один миллиард чисел и 51 миллиард символов - есть хороший шанс, что это трюк, так как в каждом из них в среднем 51 символ. Суммируйте конверсии всех чисел и посмотрите, добавляет ли она до 51 миллиарда.

Изменить: оно добавляет до 70 305 000 000 символов, поэтому это неправильный ответ.

Ответ 15

Код выигрывает...

#!/bin/bash
n=0
while [ $n -lt 1000000000 ]; do
   number -l $n | sed -e 's/[^a-z]//g'
   let n=n+1
done | sort > /tmp/bignumbers
awk '
BEGIN {
    total = 0;
}
{
    l = length($0); 
    offset = total + l - 51000000000;
    print total " " offset
    if (offset >= 0) {
        c = substr($0, l - offset, 1);
        print c;
        exit;
    }
    total = total + l;
}' /tmp/bignumbers

Протестировано для гораздо меньшего диапазона;-). Требуется много дискового пространства, сжатая файловая система будет, ммм, ценной, но не так много памяти.

У сортировки есть опции для сжатия рабочих файлов, а также вы можете загружать gzip для прямого сжатия данных.

Не самое крутое решение.

Но он работает.

Ответ 16

укажите длины для 1-999 и включите длину для 0 как 0.

Итак, теперь у вас есть массив для 0-999, а именно uint32 sizes999 [1000]; (не собираюсь вдаваться в подробности создания этого) также требуется массив из тысячи последних букв last_letters [1000] (опять же не собираюсь вдаваться в подробности генерации этого, поскольку это еще проще даже сотни d даже десятки y, за исключением 10, которые n других циклов, хотя последний из e через nin e ноль невозможен)

uint32 sizes999[1000];

uint64 totallen = 0;
strlen_million = strlen("million");
strlen_thousand = strlen("thousand");
for (uint32 i = 0; i<1000;++i){
    for (uint32 j = 0; j<1000;++j){
        for (uint32 j = 0; j<1000;++j){ 
           total_len += sizes999[i]+strlen_million + 
                        sizes999[j]+strlen_thousand +
                        sizes999[k];
           if totallen == 51000000000 goto done;
           ASSERT(totallen <51000000000);//he claimed  51000000000 was not intermediate
        }
    }
}
done:

//теперь используйте я j k для получения последней буквы с помощью last_letters999

//думаем о i, j, k как цифре base 1000

//если k = 0 и j == 0, то буква n millio n

//если только k = 0, то буква d тыс. d

//другой разумно использовать массив last_letters, поскольку

//единица цифр 1000, то есть k, не равна нулю

//для суммы чисел i, j, k - цифры номера базы 1000, поэтому

n = i*1000000 + j*1000 + k;

//представляем номер и используем

sum = n*(n+1)/2;

если вам нужно сделать это для номера, отличного от 51000000000, а затем рассчитать sums_sizes999 и использовать его естественным образом.

общая память: 0 (1000);

общее время: 0 (n), где n - число

Ответ 17

Это то, что я сделал бы:

• Создайте массив из 2 997 строк: "один" через "девяностотничный", "onethousand" через "девяностотничный" и "onemillion" через "девяностотнинунемиллион".
• Сохраните следующую информацию о каждой строке: length (это может быть вычислено, конечно), целочисленное значение, представленное строкой, и некоторое перечисление, чтобы указать, являются ли это "те", "тысячи" или "миллионы".
• Сортировка по 2979 строк в алфавитном порядке.

При создании этого массива просто найти все 999,999,999 строк в алфавитном порядке на основе следующих наблюдений:

• Ничто не может следовать за строкой "те"
• Либо ни одна, ни "одна" строка может следовать за строкой "тысячи"
• Ничего, ни одна строка, строка "тысячи" или строка "тысячи", а не "одна", могут следовать за "миллионной" строкой.

Построение слов в основном предполагает создание одно-трехбуквенных "слов" на основе этих 2,997 токенов, следя за тем, чтобы порядок токенов делал действительное число в соответствии с вышеприведенными правилами. Учитывая определенное "слово" , следующее "слово" выглядит следующим образом:

• Увеличьте "слово" , добавив маркер в алфавитном порядке, если это возможно.
• Если это невозможно сделать, продвиньте самый правый токен до следующего по алфавиту, если это возможно.
• Если это тоже невозможно, удалите самый правый токен и, если это возможно, продвиньте второй правый крайний токен до следующего по алфавиту.
• Если это тоже невозможно, все готово.

На каждом шаге вы можете рассчитать общую длину строки и сумму чисел, просто сохранив два текущих итога.

Ответ 18

Важно отметить, что существует много дублирующих и двойных подсчетов, если вы перебираете все 100 миллиардов возможных чисел. Важно понимать, что количество строк, начинающихся с "восьмерки", - это такое же количество чисел, которое начинается с "nin" или "seven" или "six" и т.д....

Для меня это требует решения динамического программирования, в котором количество строк для десятков, сотен, тысяч и т.д. вычисляется и хранится в некоторой таблице поиска. Конечно, будут специальные случаи для одного против одиннадцати, два против двенадцати и т.д.

Я обновлю это, если смогу быстро найти решение.

Ответ 19

НЕПРАВИЛЬНО!!!!!!!!! Я ПРОЧИТАЛ ПРОБЛЕМУ НЕПРАВИЛЬНО. Я думал, что это означает "какая последняя буква из последнего числа в алфавитном порядке"

что случилось с:

public class Nums {

// if overflows happen, switch to an BigDecimal or something
// with arbitrary precision
public static void main(String[] args) {
    System.out.println("last letter: " + lastLetter(1L, 51000000L);
    System.out.println("sum: " + sum(1L, 51000000L);
}    

static char lastLetter(long start, long end) {
   String last = toWord(start);
   for(long i = start; i < end; i++)
      String current = toWord(i);
      if(current.compareTo(last) > 1)
         last = current;

   return last.charAt(last.length()-1);
}

static String toWord(long num) {
   // should be relatively easy, but for now ...
   return "one";
}

static long sum(long first, long n) {
   return (n * first + n*n) / 2;
}
}

на самом деле не попробовали это:/LOL

Ответ 20

Я решил это на Java когда-то в 2008 году как часть приложения для работы в ITA Software.

Код длинный, и теперь, через три года, я смотрю на него с ужасом... Поэтому я не буду публиковать его.

Но я опубликую цитаты из некоторых заметок, которые я включил в приложение.

Проблема с этой головоломкой, конечно же, размер. Наивный подход заключался бы в сортировке списка в порядке номеров слов, а затем для итерации по отсортированным символам и суммированию списка. Со списком размером 999,999,999 это, конечно, займет довольно много времени, и сортировка, скорее всего, не будет выполнена в памяти.

Но в упорядочении есть естественные шаблоны, которые позволяют сочетать ярлыки.

Сразу же после любой записи (скажем, номер X), заканчивающейся "миллион", вы получите 999999 записей, начиная с того же текста, представляя все числа из X +1 к X + 10 ^ 6 -1.

Сумма всех этих чисел может быть вычислена по классической формуле ( "арифметический ряд" ), а счетчик символов может быть вычислен с помощью простой формулы, основанной на префиксе (X выше) и однократно вычисленном символе count для чисел от 1 до 999,999. Оба зависят только от "миллионной" части числа в базе диапазона. Таким образом, если количество символов для всего диапазона будет содержать весь счет ниже цели поиска, отдельные записи не должны проходить.

Подобные ярлыки применяются к "тысячам", и действительно могут быть применены к "сотне" или "миллиарду", хотя я не беспокоился о ярлыках на уровне сотен, а уровень миллиардов выходит за пределы этой проблемы.

Чтобы применить эти ярлыки, мой код создает и сортирует список из 2997 объектов, представляющих числа:

от 1 до 999 с шагом 1   1000 до 999000, шаг за шагом 1000   1000000 до 999000000, шаг за шагом 1000000

Этот код повторяется через этот список, накапливая суммы и количество символов, рекурсивное создание, сортировку и перемещение похожих, но меньших списков по мере необходимости.

Явный подсчет и добавление нужны только ближе к концу.

Я не получил работу, но позже использовал код как "образец кода" для другого задания, которое я получил.

Код Java, использующий эти методы, пропускает большую часть явного подсчета и добавления в течение примерно 8 секунд.