Am I Correct In Thinking That The Search Engine Cheats?
This topic contains 2 replies, has 2 voices, and was last updated by Joshua Barretto 2 months, 3 weeks ago.
October 24, 2017 at 5:01 pm #22606
I’m a programmer. Code is no stranger to me, and I take a particular interest in pseudorandom procedural generation.
So when I heard about this, I was initially not too bothered. Sure, it’s a cool idea. Use a static seed to produce random characters for each page. You can even use some slightly more complex (but not particularly difficult for someone with experience) methods to ensure that the algorithm will generate every possible permutation of pages. But then I encountered the search engine.
This is impressive. The library is generated with a reversible function that can take a page of data as input, and convert it back into a number that exactly indexes its location. It’s complex, but I can imagine it must be done through some kind of bitwise fiddling that preserves the integrity of the original index as it passes through the function.
What really, really shocked me was the ability to search for text within a page. This struck me as pretty amazing: after all, the text for each page is presumably generated with a recursive function based on its index. So the algorithm would have to predict the result of the future recursions of a near-infinite class of functions: an intractable problem.
Then, it struck me. There’s an easy solution. A back door. A cheat. The search algorithm doesn’t need to find the first instance of a piece of text, it only has to find an instance of it. So when searching for a piece of text less than 3,200 characters long, it simply pads the text out on both ends with pseudorandom characters (presumably using the search text as a seed, to ensure that all later searches of the same text will produce the same library index).
If this is so, then I must say: Congratulations on finding such a clever yet convincing cheat (although given the intractability of the original problem, I can hardly blame you for using it).October 24, 2017 at 10:10 pm #22607
Your assumption is correct! What a sight for sore eyes, having another programmer around here. Just a minor note: The search generates the seed from a page using the inverse PRNG algorithm; the page isn’t the seed itself. I’m not sure if that’s what you meant, but wanted to mention it just in case.
Fun fact: If your search consists of a full page of 3200 characters, your first result will always be in the same location.October 25, 2017 at 5:12 pm #22619
I’ve written a clean room re-implementation of the library (i.e: without looking at any Library of Babel code) that you can find here if anyone is interested: https://github.com/zesterer/babble
It allows you to find exact text matches in the library, find text within a page and read any page you care to look at.
Of course, the interface is command-line only and is abysmal. But as a point of theory, it’s an example that people can learn from.