main.cpp

#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>

#include <arpa/inet.h>
#include <endian.h>

unsigned to_num(const std::string& ip) {
	return be32toh(inet_addr(ip.c_str())); // faster than manual parsing, heh
}

constexpr int tree_depth = 15;

struct Range {
	unsigned from, to;
	unsigned range; // width
	std::string name;
};

struct Node {
	Node(int depth, unsigned min, unsigned max)
		: mid(((long long)max + (long long)min) / 2)
		, children(nullptr)
	{
		if (depth < tree_depth) {
			children = new Node[2] {
				Node(depth + 1, min, mid),
				Node(depth + 1, mid, max)
			};
		}
	}
	~Node() {
		delete[] children;
	}

	void load(const Range & range) {
		if (!children) {
			ranges.push_back(range);
		} else {
			if (range.to < mid)
				children[0].load(range);
			else if (range.from > mid)
				children[1].load(range);
			else
				ranges.push_back(range);
		}
	}

	void sort() {
		std::sort(ranges.begin(), ranges.end(),
			[](const Range &l1, const Range &l2){
				return l1.range < l2.range;
			}
		);
		if (children) {
			children[0].sort();
			children[1].sort();
		}
	}

	const Range* search(unsigned num) const {
		if (children) {
			int index = num < mid ? 0 : 1;
			const Range *best = children[index].search(num);
			for (const Range &range : ranges) {
				if (best && range.range > best->range)
					return best;
				if (range.from <= num && num <= range.to)
					return &range;
			}
			return best;
		} else {
			for (const Range &range : ranges)
				if (range.from <= num && num <= range.to)
					return &range;
			return nullptr;
		}
	}

	unsigned mid;
	Node *children;
	std::vector<Range> ranges;
};

int main() {
	Node node(0, 0, 4294967295u); // 255.25.255.255

	std::ifstream input("range_1M.txt");
	std::string from_s, to_s, name;
	while (input >> from_s >> to_s) {
		input.ignore();
		std::getline(input, name);
		unsigned from = to_num(from_s), to = to_num(to_s);
		node.load(Range{from, to, to-from, name});
	}

	node.sort();

	std::ifstream queries("query_10k.txt");
	std::string query_s;
	while (queries >> query_s) {
		unsigned query = to_num(query_s);
		const Range *best = node.search(query);
		std::cout
			<< query_s << " "
			<< (best ? best->name : "<unknown>")
			<< "\n";
	}
}

main.py

import datetime, sys, socket, struct

data = open("range_1M.txt").read().splitlines()
lookups = open("query_10k.txt").read().splitlines()

def to_num(ip):
    return struct.unpack("!L", socket.inet_aton(ip))[0] # faster than manual parsing, heh

class Node:
    def __init__(self, depth, min, max):
        self.mid = (max + min) // 2
        self.children = None
        self.ranges = []
        if depth < 15:
            self.children = (Node(depth+1, min, self.mid), Node(depth+1, self.mid, max))

    def load(self, range):
        if not self.children:
            self.ranges.append(range)
        else:
            if range[1] < self.mid:
                self.children[0].load(range)
            elif range[0] > self.mid:
                self.children[1].load(range)
            else:
                self.ranges.append(range)

    def sort(self):
        self.ranges.sort(key=lambda range: range[3])
        if self.children:
            self.children[0].sort()
            self.children[1].sort()

    def search(self, num):
        if self.children:
            if num < self.mid:
                best = self.children[0].search(num)
            else:
                best = self.children[1].search(num)
            for range in self.ranges:
                if best and range[3] > best[3]:
                    return best
                if range[0] <= num <= range[1]:
                    return range
            return best
        else:
            for range in self.ranges:
                if range[0] <= num <= range[1]:
                    return range

node = Node(0, 0, to_num('255.255.255.255'))

for line in data:
    start, end, name = line.split(maxsplit=2)
    start = to_num(start)
    end = to_num(end)
    range = (start, end, name, end-start)
    node.load(range)

node.sort()

for ip in lookups:
    num = to_num(ip)
    best = node.search(num)
    print(ip, best[2] if best else '<unknown>')

output_10k_ranges.txt

113 - Loans SRL
112 - Caret Southwards International
110 - Armenians Corona SRL
109 - Photostat Romany
103 - University of Evil Commentator
98 - Capricorns Anchorage
93 - Republic of Turrets Hairsbreadth
93 - University of Myriad
92 - Enhancer Association
91 - Elmo Navahoes
91 - Ottoman Bedouins
90 - Democratic Republic of Sensuousness
90 - National Center for Cravings Cypher
84 - Democratic Republic of Swanks
83 - Schmoozing Sunlit Committee
82 - Queens McCall
82 - United Brogan Bud
82 - Broadsided PLC
82 - People's Republic of Squirrels
80 - Republic of Chuckle
79 - Republic of Inconsiderately Convoying
79 - Democratic Republic of Specializations Redeemed
79 - Amparo Hindi
77 - Shields Opposite PLC
72 - Prudential Rutan
72 - People's Republic of Crucially
72 - Margie Patsy
72 - Center for Dogies
70 - First Analogies
69 - Rifts Committee
68 - Dished Endorses International
68 - Permed Almighty Union
67 - Hemmed Amoco Institute
67 - United Precipitate Factotums
66 - First Thrusts
66 - Mercies Contemplate International
65 - University of Pew
65 - Cables Union
65 - Hausa Windsors
63 - Hilbert Invite LLC
63 - United Jaunting
63 - Dandruff Word Union
63 - People's Republic of Render
63 - People's Republic of Reconfigured Buglers
62 - Republic of Corollary Pigments
62 - Tango Worldlier International
61 - Valeria Mombasa
60 - Face Institute
60 - Center for Undesirables
58 - Petting Burial PLC
58 - Forefronts LLC
57 - University of Dismissing Enormity
56 - Stevenson Beardmore
56 - Kikuyu Thimbu
55 - Center for Merchandising Doped
55 - First Curdles
55 - Center for Marquises
55 - People's Republic of Wigs
55 - Everett Alamogordo
55 - Fonda Institute
55 - Heidi Imodium
54 - Untimely Semantics LLC
54 - People's Republic of Disabled
54 - Muss Lifelike Committee
54 - Siting Party
54 - First Rehashing
53 - Strudels Association
53 - Variable Union
53 - National Center for Egghead Learned
53 - Humpbacked Secretariat Association
53 - University of Butterier Kindest
52 - Subtly Bunt LLC
52 - University of Mischief Heifer
52 - Center for Heisted
52 - University of Mountainsides
52 - Lends International
52 - Ecuador Association
51 - Democratic Republic of Jig
51 - Republic of Thirsty Canonized
51 - Assertively Gyp Association
50 - Rotten Association
50 - People's Republic of Myna Thickened
49 - People's Republic of Redirecting Kibbutz
49 - Burbank Orizaba
48 - Margery LLC
48 - Democratic Republic of Ablutions
48 - Jockey Siren Institute
47 - Democratic Republic of Straggled
47 - Coalitions Prensa International
47 - Hornblower Chekhov
46 - People's Republic of Hostelling Overdressed
46 - Center for Dogs Motherhood
45 - First Deputation Umps
45 - Salish Puritan
45 - Nazca Libyan Association
45 - Unionization Reconstituting Committee
44 - Republic of Liquefying
44 - Democratic Republic of Pained
44 - Imposing Entangling Party
44 - Worded Infrared SRL
44 - Bombastic Committee
44 - National Torqued Mods
43 - Olivier Nepal
43 - Center for Staler
42 - Trailers Catholic International
41 - National Propagandize Skylights
41 - Republic of Vicar
41 - Summarizes LLC
41 - People's Republic of Extenuation
41 - University of Harem Rarest
40 - First Persuading
40 - Saxon Lorie
40 - Republic of Censers
40 - Latisha Inc
40 - Adolfo Robbie
39 - Homophones International
39 - Excessively Inc
39 - Democratic Republic of Pussycat Orphanage
39 - Republic of Wispy Cuspid
38 - Capsizing Americans Party
38 - Systematic Geed Inc
38 - Republic of Dealings Wearable
38 - Swedish Moorish
37 - University of Epoxying
37 - Jointed Aventine International
37 - Democratic Republic of Kind Porringers
36 - People's Republic of Joust
36 - Openings Fells PLC
36 - Bangalore Paganini
36 - Protest Vaulter LLC
35 - Jitneys PLC
35 - First Skylarked
35 - Ingenious Bungles Union
35 - Grads Association
34 - Stephens Christ
33 - Fijians Sundays
33 - Ila Jamal
33 - Psychedelic LLC
33 - Bayonne Rn
33 - Republic of Talon Mobilizes
33 - Democratic Republic of Fabled
32 - People's Republic of Gaffe
32 - National Center for Macaronis
31 - Epicurean Union
31 - Corey Navratilova
31 - Solidification Union
31 - Ideologist Committee
30 - Sunk LLC
30 - University of Succulence
30 - Madrid Pointillism PLC
30 - People's Republic of Rivalries
30 - National Transliterations Crazing
30 - University of Splits Spotlighted
29 - Speaking International
29 - Center for Wifelier Yore
29 - National Calcified
29 - People's Republic of Rally
29 - Democratic Republic of Obliterate
29 - Astaire Alpert
29 - Mealtimes Locale Inc
28 - University of Spindle
28 - Lodge Bobbing Institute
28 - Sufficing Inc
28 - Alta Kalahari
27 - Republic of Pianists Interned
26 - National Center for Spelled Assassination
26 - United Disarms
26 - Ehrlich Armand
26 - Nehru Wake
26 - Republic of Imperturbable Harrows
25 - Center for Zany Menstruate
25 - Toner Muggier Committee
25 - Exterminating Union
25 - Demon Inc
24 - Appall Committee
24 - Sediments SRL
24 - Craft Hellenisms
23 - Democratic Republic of Insurer
23 - Democratic Republic of Shackles
23 - National Center for Affront
23 - Discomposed Committee
23 - Proxy Chronic Party
23 - Manure LLC
22 - Quetzalcoatl Inc
21 - Republic of Scullion Biweeklies
21 - University of Audiophile
21 - National Center for Caprices Ooze
20 - National Center for Recommences Manipulator
20 - Efficiency Connoisseur Committee
20 - Pynchon Onto Association
20 - First Tatty
19 - United Psychotherapy Proselytizing
19 - Mr Edison
19 - Midwest Jensen
18 - Previous Knoll Union
18 - Andrew Lithuanian
18 - Subservient Verlaine International
18 - Showbiz SRL
17 - Murderers Union
17 - Tinned Histamines PLC
17 - People's Republic of Undecipherable Pumices
17 - National Differentiated
17 - Republic of Goatskin
16 - Obstinately SRL
16 - Elliptic Dalton Committee
16 - Torqued Association
16 - Grandee Ideological Institute
16 - Toscanini International
16 - Rattrap Partial Committee
15 - Dine Inc
15 - Center for Misers
14 - United Mutilating
14 - Derisive Union
14 - Lagoons Union
13 - Pisa Guzman
13 - Postdating Party
13 - Reprinted SRL
13 - Cassiopeia Jewishness
13 - Enlisting Grimes LLC
12 - Varlets Emanations SRL
12 - Shawna Propagandize SRL
12 - Tolstoy Arneb
12 - Republic of Relearned
11 - People's Republic of Inland Inertia
11 - Crowley Jamaicans
11 - Babur Magnitogorsk
11 - Mordred Roqueforts
11 - United Pronounceable Trivially
10 - Center for Examining Grandly
10 - Hollywood Jayapura
10 - Republic of Hurry
10 - University of Pioneering
10 - Lopez Madeiras
10 - United Snivelling
10 - Republic of Workmen Incomparable
9 - Shylockian Irrawaddy
9 - United Morning Inanimate
9 - United Knockout Cassettes
9 - Presuming Toques Association
8 - University of Absurdity Immensity
7 - Duty Dewdrops SRL
7 - Formidably Cleaved International
6 - First Recklessly Sugars
6 - People's Republic of Soliloquizes
5 - Ashkenazim Carnegie
5 - Interstellar Union
3 - Tapioca Antipersonnel International
3 - United Hanging Righter
3 - National Lapped
1 - National Center for Brazen

output_1M_ranges.txt

62 - National Center for Foetus
60 - Democratic Republic of Squishiest Particularization
59 - Menuhin Sheba
57 - United Transsexual Inimitably
56 - Republic of Defining Clucking
55 - Brimming Elwood Inc
55 - University of Throttled Intense
54 - Lvov Patrice
54 - Center for Watercress Amaranth
54 - Center for Angstrom
54 - Ousts Abbeys Association
53 - Goons Falsification Inc
53 - Secretariat Gomez
53 - Arraigned Impotent Party
53 - Heifetz Quisling
52 - Republic of Paraprofessional
51 - United Misgoverning Christen
51 - Republic of Vatted
51 - Pillowed Babylonian Inc
51 - People's Republic of Poling Chairperson
50 - Episcopalian Rubik
50 - Tsimshian Olympic
49 - National Deplorable
49 - Uncontrollable Institute
49 - Democratic Republic of Recessive Forsooth
49 - Ape Hettie SRL
49 - Muawiya Griffith
49 - Hitchhiking Nab International
48 - Democratic Republic of Medulla
47 - United Swung Swatted
47 - United Manumitting Dewlaps
47 - First Slaving
47 - Speaking Haler Institute
47 - People's Republic of Physicist Languished
47 - Union Decommissioned Party
46 - Brenda Annam
46 - Volta Mercurochrome
46 - Yvonne Anglophile
46 - Putrescent Reformulates Institute
46 - Democratic Republic of Indorse Perpetrate
46 - Magnolias Association
46 - Deadhead Ines
46 - Electroplate Association
46 - First Tinkles
46 - Republicans Leola
46 - Glorify Union
46 - Center for Forecaster Wrenching
45 - Lint Unconstitutional SRL
45 - National Holy Sympathize
45 - Epics Committee
45 - Soundless Committee
45 - National Perspires
44 - Knudsen Alisha
44 - Pole Olivier
44 - National Moor Humbugging
44 - National Chit
44 - First Impersonates Reappeared
44 - Esau Strainer Committee
44 - Graciela Miriam
44 - People's Republic of Tributes Flown
44 - People's Republic of Pollinate Bequeath
44 - Israelis LLC
44 - United Demoniac
44 - Patagonia Boasted PLC
44 - Chandragupta Sensurround
44 - Jefferson Guinevere
44 - Republic of Boning Sheikh
44 - Backus Impressively LLC
44 - Sweetbrier LLC
44 - First Brownout Collocating
43 - Goodman Twinkies
43 - United Threescore
43 - Sitar Buildings Association
43 - Musketeers Institute
43 - Audion Ordovician
43 - Democratic Republic of Glued
43 - Unbounded PLC
43 - Democratic Republic of Disavowals Doffing
43 - Procreative Union
43 - United Ascendents Repaying
43 - Shapiro Tswana
43 - National Ductile Pronouncements
43 - National Center for Beanbags Starchiest
43 - First Constituted Preparatory
42 - People's Republic of Tabus
42 - People's Republic of Epaulettes
42 - United Speedy According
42 - Binary Psychoanalyzes Committee
42 - First Soupçon Protestors
42 - National Center for Readouts Oxides
42 - First Dinette Translate
42 - Clio Sid
42 - Republic of Muckraked
41 - Center for Unlimited Emulsifying
41 - Democratic Republic of Longhorn
41 - Protestantism Pilate
41 - Republic of Breadbaskets
41 - Democratic Republic of Condominiums Pillory
41 - Realtor LLC
41 - Knowledgeable Acutes PLC
41 - Democratic Republic of Generals Bites
41 - Zillions Grammarians PLC
41 - Organizer Tamara Institute
41 - Republic of Blow Respected
41 - Hooey Knoll LLC
41 - Rochester Americanism
41 - Vijayanagar Nice
41 - Eugenie Levy
40 - National Center for Ascendency Styluses
40 - Democratic Republic of Whizzes
40 - Kansas LLC
40 - Tinderboxes Mar PLC
40 - Democratic Republic of Combs
40 - Eastbound Retaking PLC
40 - United Tripled
40 - Connoisseur LLC
40 - Center for Collectivists Inexperienced
40 - Voluminously Committee
40 - People's Republic of Merger
40 - Treadling Eliza Party
40 - Seaports Benz Institute
40 - Municipally Concerting PLC
40 - Frowns Inc
40 - National Center for Penny
40 - Drama Gougers International
39 - Beneficially Featherier International
39 - People's Republic of Dogcatchers Preambled
39 - Avenger Union
39 - National Center for Drunkest
39 - Francisco Wiggins
39 - Democratic Republic of Courtrooms
39 - Kristy Pennzoil
39 - Counterattack Union
39 - Valkyrie Kempis
39 - University of Epilogs
39 - Conjoined Prohibitory Inc
39 - Megalomaniac Drouths International
39 - Olympia Packard
39 - National Center for Prior
39 - Center for Underemployed
39 - University of Prearranging
39 - National Gushier
39 - National Euphemistically
39 - First Humidors Unambiguous
38 - National Brisker Dint
38 - Precociousness Reinterpret Committee
38 - Stewart Wu
38 - Cloven Marketable Party
38 - Bruckner Cabrini
38 - Embolden Relativistic Inc
38 - Concertinas Mathews Committee
38 - Americanizing Unitarians
38 - Nichole Benito
38 - Crawford Boomerang Union
38 - National Opts
38 - Toto Fermi
38 - Pygmalion Semitics
38 - Democratic Republic of Analogue
38 - Misrepresenting Limitations Union
38 - Loanwords SRL
38 - Prado Rodin
38 - Miguel Ferrell
38 - Center for Clefs Enveloped
38 - University of Convoked Cranny
37 - First Pasha Swiftness
37 - Center for Overlooks
37 - Pynchon Annapurna
37 - Republic of Uninstalls Sextants
37 - Lapp International
36 - Whoosh Tarawa PLC
36 - United Intagli Feminists
36 - National Projection
36 - Center for Swapping Ragamuffin
36 - Venn Adler
36 - Slating Institute
36 - Inkiest Brunched Inc
36 - National Center for Fluoridation
36 - Markab Noninterference International
36 - University of Rheum
36 - Regimented Association
36 - Viewings International
36 - Republic of Wailing Kills
36 - Giblet Catafalque Association
35 - Celeste Western
35 - Khulna Johnston
35 - University of Adequacy
35 - Codependency SRL
35 - National Replied
35 - Inquisition Aztecs
35 - Tannhäuser Juliette
35 - Mother Committee
35 - Sicilians Cockney
35 - Democratic Republic of Coincidentally Egregiously
35 - Democratic Republic of Latching Townsmen
35 - Toil Prepaying Committee
35 - Mike Adonises
35 - National Center for Prickle
35 - First Thwarts
35 - National Flambeing
35 - First Burly Dribble
35 - People's Republic of Nudest
34 - National Center for Highlands
34 - Center for Gill
34 - Mindfulness Lambrusco SRL
34 - Tints SRL
34 - University of Torpedoed Trip
34 - Reilly Affair Inc
34 - United Outspokenness
34 - Yawning Inc
34 - Republic of Transcends
34 - First Showboating
33 - United Blotters
33 - Barbers Party
33 - Carissa Twizzlers
33 - Republic of Beachheads
33 - Iscariot Pushkin
33 - Center for Constraints Momentousness
33 - National Center for Fended Incurious
33 - Turkmenistan Cousteau
33 - Center for Anthology
32 - Mohican Okays LLC
32 - Molokai Bushido
32 - Turks SRL
32 - Commutative Bygone Party
31 - Center for Congruous Retaliates
31 - Gaiety Schmuck Union
31 - Republic of Sputtered
31 - Democratic Republic of Compartmentalize Rapture
31 - United Censoriously Frolicking
31 - Antidepressants Blondest Association
31 - Eden Inc
30 - People's Republic of Hoedown
30 - Gloriously Institute
30 - First Haste Purged
30 - National Captions
30 - Sculled Kiowa Inc
30 - Ulnae Union
30 - Takeovers Polysyllables Institute
30 - Republic of Dictum
29 - Republic of Gherkin
29 - Poppins Schopenhauer
29 - University of Magistrate
28 - United Misstate Disclosures
28 - Center for Scatterbrain
28 - Leona Dominick
28 - Amicability Committee
26 - Falasha Trey
26 - People's Republic of Preparation
26 - Apostrophe Borders LLC
25 - Rhee Luzon

output_converter.py

from collections import defaultdict
import sys

data = sys.stdin.readlines()
out = defaultdict(list)
for line in data:
	ip, name = line.strip().split(maxsplit=1)
	out[name] += [ip]

for k, v in sorted(out.items(), key=lambda kv: len(kv[1]), reverse=True):
	print(len(v), '-', k)