I've seen people suggest using pi as a "database." In this instance you could map ranges of pi to characters. Then you search pi until you find the right range. The URL would contain the range(s) needed.
This is terrible and so computationally wasteful. But it's interesting to think about.
Seems technically possible - example.com/12_3456 would calculate out pi, read 12 digits starting at position 3456, then convert those digits to ascii and you'd have your result. Given how far into the digits pi you'd have to go to find the exact right sequence that matches, eg, https://google.com, though, I suspect the resulting position number would be longer than the original url!
Also, conceptually, it seems like you're not so much using pi as a database as you are using it as an encoding mechanism: turning "abc.com" into a string of numbers whose length is relative to the original string. At that point you might as well pick an easier encoding, like base64. :)
You could add a short one or two character long identifier that changed the digits-of-pi to ascii map then select the mapping that results in the lowest index. In this case part of the "database" would exist within the URL shortener itself.
"X in pi" is an interesting thought experiment, but practically speaking, the least efficient way to do anything, since finding a string of N digits in pi will require a search space exponentially much larger than N on average, so it ends up just being an extremely inefficient encoding. A huffman coding + base32/base64 is a better "databaseless" short URL system.
In a similar vein, almost every algorithm can be converted into a O(1) space version simply by converting it into the dumbest possible search algorithm over the solution space: just sample from the solution space randomly (with a seeded PRNG or something) until you get the right answer.
Interestingly, bogosort cannot actually be implemented in constant space -- at least, not if you're talking about a deterministic algorithm. In order for your PRNG to have a large enough state space to cover all possible permutations, it needs O(n log n) bits.
In the Turing machine model of computation, algorithms that use O(1) space are theoretically equivalent to finite state machines (potentially with a very large number of states). Logarithmic space is where things start to get interesting, because it's enough to store a constant number of pointers into an arbitrarily large input.
Haha this is fantastic. Are the IDs still coming from that single counter lambda? Or put another way, do you now have 1,750,785 lambdas in your AWS account? :)
Yeeeeeeep. :) Someone automated spinning up new IDs at some point and flooded this service with urls. I wrote a script to delete old ones, but it takes a few days to run and I haven't gotten around to letting it finish.
