/* num.cpp : Solve the "Word Numbers" puzzle
 *
 * Copyright (c) 2008 Daniel Hartmeier <daniel@benzedrine.ch>
 * All rights reserved.
 *
 * See http://www.itasoftware.com/careers/puzzle_archive.html
 * and http://programming.reddit.com/info/2r7qw/comments
 *
 *   Word Numbers
 *
 *     "If the integers from 1 to 999,999,999 are written as words, sorted
 *      alphabetically, and concatenated, what is the 51 billionth letter?" 
 *
 *     To be precise: if the integers from 1 to 999,999,999 are expressed
 *     in words (omitting spaces, 'and', and punctuation[1]), and sorted
 *     alphabetically so that the first six integers are
 *
 *       eight
 *       eighteen
 *       eighteenmillion
 *       eighteenmillioneight
 *       eighteenmillioneighteen
 *       eighteenmillioneighteenthousand
 *
 *       twothousandtwohundredtwo
 *
 *     then reading top to bottom, left to right, the 28th letter completes
 *     the spelling of the integer "eighteenmillion".
 *
 *     The 51 billionth letter also completes the spelling of an integer.
 *     Which one, and what is the sum of all the integers to that point?
 *
 *     [1] For example, 911,610,034 is written
 *         "ninehundredelevenmillionsixhundredtenthousandthirtyfour";
 *         500,000,000 is written "fivehundredmillion";
 *         1,709 is written "onethousandsevenhundrednine".
 */

#include <errno.h>
#include <iostream>
#include <string>
#include <map>
#include <set>

using namespace std;

map<unsigned, string> n;
set<string> m;

string
w(unsigned u)
{
	string s;

	if (u >= 100)
		s += n[u / 100] + "hundred";
	if (u % 100)
		s += n[u % 100];
	return s;
}


// 911610034 -> "ninehundredelevenmillionsixhundredtenthousandthirtyfour"
// 500000000 -> "fivehundredmillion"
// 1709 -> "onethousandsevenhundrednine"
string
word(unsigned u)
{
	string s;
	unsigned a = u / 1000000;
	unsigned b = (u / 1000) % 1000;
	unsigned c = u % 1000;

	if (a > 0)
		s += w(a) + "million";
	if (b > 0)
		s += w(b) + "thousand";
	if (c > 0)
		s += w(c);
	return s;
}

int main(void)
{
	n[1] = "one";
	n[2] = "two";
	n[3] = "three";
	n[4] = "four";
	n[5] = "five";
	n[6] = "six";
	n[7] = "seven";
	n[8] = "eight";
	n[9] = "nine";
	n[10] = "ten";
	n[11] = "eleven";
	n[12] = "twelve";
	n[13] = "thirteen";
	n[14] = "fourteen";
	n[15] = "fifteen";
	n[16] = "sixteen";
	n[17] = "seventeen";
	n[18] = "eighteen";
	n[19] = "nineteen";
	n[20] = "twenty";
	n[30] = "thirty";
	n[40] = "forty";
	n[50] = "fifty";
	n[60] = "sixty";
	n[70] = "seventy";
	n[80] = "eighty";
	n[90] = "ninety";
	for (int i = 21; i <= 99; ++i)
		if (i % 10)
			n[i] = n[(i / 10) * 10] + n[i % 10];

	unsigned long long ull = 0;

	string s;
	FILE *f = NULL;
	unsigned nr = 1;
	for (unsigned i = 1; i <= 999999999; ++i) {
		if (f == NULL) {
			char fn[64];

			snprintf(fn, sizeof(fn), "file.%3.3u", nr++);
			cerr << "creating file " << fn << endl;
			if ((f = fopen(fn, "w")) == NULL) {
				cerr << "fopen: " << fn << ": " <<
				    strerror(errno) << endl;
				return 1;
			}
		}
		s = word(i);
		ull += s.length();
		fprintf(f, "%s\n", s.c_str());
		if (ull > 600000000) {
			cerr << "closing current file" << endl;
			fflush(f);
			fclose(f);
			f = NULL;
			ull = 0;
		}
		if (i % 1000000 == 1)
			cerr << i << ", " << ull << endl;
	}
	if (f != NULL) {
		cerr << "closing current file" << endl;
		fflush(f);
		fclose(f);
		f = NULL;
	}
	cerr << "number of files " << nr - 1 << endl;

/*
	cerr << m.size() << " strings" << endl;
	unsigned off = 1;
	for (set<string>::iterator i = m.begin(); i != m.end(); ++i) {
		cout << off << ": " << *i << endl;
		off += i->length();
	}
*/
	return 0;
}