9 ms·
The fact that the search works impressed me more than anything. Of course, like every great magic trick, it seems so simple once it is explained. For the curio
by tobyjsullivan 2y ago
The fact that the search works impressed me more than anything. Of course, like every great magic trick, it seems so simple once it is explained.
For the curious, here's the linked blog post describing how the project works: https://eieio.games/blog/writing-down-every-uuid/ https://eieio.games/blog/writing-down-every-uuid/
Edit to add: I'd only tried searching for an exact UUID when I wrote this comment. I didn't realize it supports full text search! Now I'm even more impressed.
- writtenAnswer 2y agoCool Blogpost
- InsideOutSanta 2y agoYeah, I at first, I though I knew exactly how it worked. Then I saw the search field, and I suddenly had no idea what the hell was going on. Now, the big question, do I want to spoil the magic trick and read how this was done, or should I keep being astonished and flabbergasted?
- manmal 2y agoAs with any magic trick, reading the explanation might leave you a little disappointed here.
- noman-land 2y agoI'm the opposite. The magic is not in what the magician shows, but in what they elegantly manage to hide.
- sameoldtune 2y agoI disagree with my sibling comment. The trick is beautiful. If you generate UUIDs such that each bit in the result can be reliably traced back to a single bit in the input, then you can take a substring of the UUID and use that to infer which bits of the input integer must be set to produce that substring. So you can produce a whole list of input bytes that meet the criteria and those become your search results. The real magic trick here is that the uuids on the page only look random to us because of some bit twiddling and XOR trickery. If we had a better intuition for such things we would notice that successive UUIDs are just as correlated as successive integers. Elegant stuff
- thaumasiotes 2y ago> I disagree with my sibling comment. The trick is beautiful. If you generate UUIDs such that each bit in the result can be reliably traced back to a single bit in the input, then you can take a substring of the UUID and use that to infer which bits of the input integer must be set to produce that substring. ...but that has nothing to do with what the website is doing. The accompanying article specifically calls out the fact that it can't be done while maintaining the appearance of an unordered list, and therefore it isn't attempted.
- kirubakaran 2y agoIf you're an Everettian, roll https://www.jrussellhuffman.com/quantumdice/ https://www.jrussellhuffman.com/quantumdice/ and read it only if the die is odd. You can have your cake and eat it too.
- InsideOutSanta 2y agoGenius.
- eieio 2y agoI'm really happy that the trick was magical to you - I was so surprised and delighted when I realized that this was possible, and I wasn't really sure if anyone else would feel the same way! And of course, I'm proud to be providing so much utility here - finally we can find and use UUIDs tailor-fit to our needs
- lxgr 2y agoMemorable UUIDs? I think you're on to something here! (Also, dibs on 00000000-0000-4321-abcd-000000000001!)
- Nihilartikel 2y agoWe can just make an NFT of each one to make sure they stay unique too!
- cubefox 2y agoCan we make one that says something funny? "B00B" could be included.
- kstrauser 2y agoThat’s amazing! I’ve got the same IPv6 address on my luggage!
- cubefox 2y agoThe most offensive sentence I could come up with leetspeak/hexspeak is this one: fe11a710-babe-4150-ace5-b19b1accd1cc (Yes it's a valid UUID) (I am so sorry)
- srockets 2y agoSearching is very similar to a common approach for building a naïve spellchecker: given an input, generate all the possible matches it can be part of. You're not searching in a corpus, you're using the input to generate indices into the corpus (list of UUIDs here, list of words in the dictionary in a spellchecker).
- lilyball 2y agoThe explanation for full-text search was actually slightly more intelligent than what I initially assumed. I figured it just generated UUIDs until it found one that was in the correct direction of search (for the next/previous button), since I had observed that walking forwards and backwards in search results was giving different results each time, but in fact the author did the slightly better thing which is to just generate a bunch of possible results and then pick the best (I wonder how many results it generates for this?).
- deleted 2y ago[deleted]
- re 2y agoThe full text search is a little confusing because it doesn't actually search them in order, though it appears to at first. And if you click "next" a few times and then "prev" the same number of times, you don't necessarily end up back at the same UUID you were at before. It's a neat-seeming trick though.
- cyanmagenta 2y agoIt’s an interesting question whether that could be fixed. I think the answer is Yes. If the author didn’t do any scrambling, and just displayed UUIDs in numeric order, then it’s trivial to enumerate search results in order. Likewise, if you do something like adding a constant mod 16 to each hex digit, you could do the same thing when you generate UUIDs matching a substring. So the question becomes whether you could find something like that that gives a sufficiently convincing illusion of entropy but is still reversibile when you hold a subset of the digits constant. And it seems like it should be.
- eieio 2y agoFWIW I am super interested in this question but feel like I don't know how to derive a satisfying answer, maybe because the one of my goals here (add "enough" entropy) is a real fuzzy "I know it when I see it" sort of thing. But I'm gonna try to get a few more crypto-knowledgeable friends to chat with me about this and write up what I learn!
- deleted 2y ago[deleted]
- movpasd 2y agoMy first thought was to use linear transformations over Z_2 as a field, as that would create a natural interpretation of fixing certain bits as taking a linear subspace. Interestingly this leads to the property that XOR is preserved. I implemented this in a very quick and hacky way for 32 bits. I generated a random boolean matrix M invertible in Z_2. To turn an input number x into a corresponding number y in an N-bit space, I convert x to binary and turn that into a vector of 1s and 0s, then multiply it by that randomized matrix to get y. Here are the first few y's corresponding to x=0, 1, ...: 00000000000000000000000000000000 0xx0x000xx00x0xx000xxx00xxx0x000 x0xx000xxxx0xxx00x000xxx0xx0xx0x xx0xx00x00x00x0x0x0xx0xxx0000x0x x0xx0x00xxx0xx0x00xx0x0xx0xx00x0 xx0xxx0000x00xx000x0x00x0x0xx0x0 00000x0x000000xx0xxx00x0xx0xxxxx 0xx0xx0xxx00x0000xx0xxx000xx0xxx ... (Hoping the non-monospace font doesn't ruin the alignment too much.) Which looks... random-ish? I expect that turning these into UUIDs may result in more random-looking sequences. Not sure how to solve the problem of search with this, but the hope would be that the linear structure gives you what you need, since fixing bytes on UUIDs should correspond to considering linear subspaces of the y vectors. Perhaps this can also be used to apply lexicographic order on the corresponding x vectors (i.e.: ordering the indexes), so that you could jump to each UUID matching the search in order.
- lxgr 2y agoA great example of Teller's observation that "sometimes magic is just someone spending more time on something than anyone else might reasonably expect."
- Terr_ 2y ago> Ninety per cent of most magic merely consists of knowing one extra fact. -- Night Watch by Terry Pratchett
- shwouchk 2y agoThanks for this reference to one of my favorite books of all time, out of one of my favorite series of all time
- Dalewyn 2y agoSufficiently advanced technology is indistinguishable from magic, as the saying goes.
- dhosek 2y agoMy favorite of these was a trick where someone picked a card out of a deck and then Teller revealed a large version of that same card in an unexpected area in the vicinity, It turns out that what he had done was hide a complete set of large cards in the area before the trick and memorized the location of every one of them so, e.g., the king of hearts would be at the top of a palm tree, the three of spades under a drink tray, etc.
- instalabs 2y agoAwesome - this will be my new coding interview question
- Freedom2 2y agoAgreed. Everyone love puzzles that are worthy of an entire section in a blogpost for their interview questions, rather than stuff actually relevant to the job.
- ljm 2y agoSo I just brute forced every UUID in existence on my RTX GPU and loaded the dataset into a HA opensearch cluster on AWS. It took about 5 years of calling ‘uuid.Random()’ to effectively cover about 64% of the keyspace which is good enough. To facilitate full-text search I created a langchain application in python, hosted on kubernetes, that takes your search query and generates synonymous UUIDs via GPT o1-preview before handing over to opensearch. Opensearch returns another set of UUIDs, which I look up in my postgres database: “SELECT uuid FROM uuids WHERE id IN (…uuid_ids)”
- khana 2y ago[dead]
- saagarjha 2y agoDid future aliens send you their quantum GPUs or what?
- schobi 2y agoI could imagine some candidates starting with their default tools like this, and start complaining about the cluster performance after a few weeks. You need a certain way of thinking to have a gut feeling "this could be expensive" and then go back, question your assumptions and confirm your requirements. Not everyone does that - better to rule them out.
- moritzwarhier 2y agoLove both the project idea and the writing! The way that post explains each step in a unique laconic tone is very enjoyable to read. > Or maybe the site could feature “trending UUIDs” that are particular popular across the world right now.
- thaumasiotes 2y ago> The fact that the search works impressed me more than anything. Of course, like every great magic trick, it seems so simple once it is explained. > Edit to add: I'd only tried searching for an exact UUID when I wrote this comment. I didn't realize it supports full text search! Now I'm even more impressed. But the trick to the full-text search is that it doesn't work.
- nharada 2y agoThe blog write-up is incredible -- technically interesting, hilarious, and perfect in both tone and scope. Well done!
- mackieem 2y agoI searched for 1337, and then 13371337, and then 133713371337, and I was flabbergasted they've got a search setup for this (which ctrl-f opens up). Thanks for posting the blog post!
- vivzkestrel 2y agoFor the even more curious, UUID has 5316 decillion 911 nonillion 983 octillion 139 septillion 663 sextillion 491 quintillion 615 quadrillion 228 trillion 214 billion 121 million 397 thousand 304 values. Imagine the fact that there aren't as many kms to reach GN-Z11 (farthest known galaxy in the Universe I think) as there are digits above
- soheil 2y agoyet I was able to scroll through them like scrolling through a 800-word web page
- soheil 2y agofull-text search? you see the int next to the str on the left, no such thing.. reminds of me this daniel dennett quote Real magic, in other words, refers to the magic that is not real, while the magic that is real, that can actually be done, is not real magic.
- dietr1ch 2y agoThis is neat, although I pushed it later with incremental search and it seems to be skipping results as it only found ~50 when searching for `-000000000000`.
- belter 2y agoThe UIA (Universal Internet Authority) is worried that by using UUIDs we are left with only around 34 trillion UUIDs per star and planet in the observable Universe. So the cosmic router might become DHCP-leasing dark matter.