Creating Library of Babel

Sivaraj Kumar
Jun 16, 2019
3 min read

In my previous article 'The Answer to EVERYTHING', I explained what is 'The Library of Babel' and I wrote little bit about how I made a mini-version of this library. If you haven't read that article wh are you doing in your life? Meaningful & NOT BORING things? 😏

Just go and read that article. Then come here.

My version is nothing when compared to the actual one but still it is a proof of concept. Anyway let's discuss my version in detail here.

STEPS IN CREATING LIBRARY OF BABEL

Writing a 'Generator Program' that generates all the possible combinations of different character lengths of a given set of strings.
Designing the library for different character lengths.
Storing the generated combinations according to the library designed in step 2.
Writing a 'Search Program' that browses through the files generated and prints the books that has the text entered by the user.

STEP 1 : WRITING GENERATOR PROGRAM

For different character lengths, the program will generate all the possible combinations of a given set of strings. I used 30 strings [ a-z , comma , period , white-space , newline]. First I used nested for loops to generate the combinations. For two character length I'll need two nested for loops. Similarly for 'n' character length I'll need 'n' nested for loops which is huge.

So instead I generated all the combinations of character length 1 first. Then for character length 2, I'll append the 30 strings to each combination that I made earlier. Similarly for character length 3, we can append the 30 strings to each combinations of character length 2.

Example :

Char Len 1

a, b, c

Char Len 2

The problem with this method is I have to switch to previous directory and current directory which makes the program slower and I need the combinations for char len 4 to generate combinations for char len 5.

STEP 2 : DESIGNING THE LIBRARY

Let me draw the structure of a library :

Below you can see the no. of books in each section of the library :

[ Scroll through the spreadsheet ]

It took me a while to put the appropriate numbers here and there to complete the design. Initially I thought I could make 15 character length books but later I realized it will take forever to generate 10^(22) combinations. I tried generating for 6 char len and it took nearly an hour and 25.8 GB of space.

STEP 3 : STORING THE GENERATED COMBINATIONS

Initially I thought I could store each combinations as separate text files. Since we are dealing with millions of files, computer couldn't handle them when I opened the folder containing the files. Also each file costs 13 KB of storage space which is ridiculous. One million of such files will be 13 GB.

Result of a test program that creates different combinations of 3 strings [ a, b, c ]

So the combinations can't be stored in text files. Instead I stored them in JSON (Java Script Object Notation) files. Each JSON file will hold 4 million combinations.

I stored the combinations in a dictionary. A dictionary in python has a 'Key' and an associated 'Value'. The values can be accessed using the keys.

'Keys' in this dictionary are the combinations I generated and their 'Values' are the corresponding locations of the combinations in the library, according to the design in STEP 2. The dictionary is dumped in a JSON when 4 million key-value pairs are updated.

Funny Encounter : Why 4 million? I used 6 million initially and my laptop ran out of memory😶.

An example of such JSON file is shown below :

A JSON file that has dictionary for character length 3

The format in which the values of the key stored is defined below :

"<Book No.> <Shelf Row> <Shelf Col> <Block Row> <Block Col> <Side> <Polygon No.> <Floor> <Library>"

STEP 4 : WRITING SEARCH PROGRAM

As I limited the maximum characters in a book to 4, the text entered by the user will be split by 4. Then the program will open a JSON file and will store the 'value' (Location) of the 'key' (combination) that matches the user-text. After all the books are found, the program will print the books and their locations as shown here.

A result of the Search program for the text "Avengers Assemble". It takes nearly 5.5 seconds to find the books.

Here I have used four cities for 4 character lengths. The city names are from immortal ancient Greek Gods.

1 - Hestia

2 - Demeter

3 - Hephaestus

4 - Tartarus

Why? Just for fun😉.

I know there are some other optimal ways to do this. I didn't want to refer the internet and use some else's way to solve the problem. That's why it took me few weeks and I wouldn't have gotten this satisfaction if I used internet for solutions.

Below I have linked my codes in Github :

1) Generator Program

2) Searching Program