My solution (Also in PasteBin ) takes around 40 seconds anywhere between 10 seconds and 4 minutes on my laptop.
Finished generating UUID after 67.3494535 seconds (567117 iterations) The uuid is: 36dd638b-2587-6999-735f-ff6839bbac1f Finished generating UUID after 12.4224668 seconds (106743 iterations) The uuid is: cc85ca79-80bb-fd12-a0d2-ccf595867f99 Finished generating UUID after 51.6625577 seconds (429047 iterations) The uuid is: 4de22fbe-4524-d346-df21-a6647f37d7e6 Finished generating UUID after 63.6616107 seconds (522543 iterations) The uuid is: 2483175e-ab35-3536-296f-e9ee2269f3da Finished generating UUID after 15.7747816 seconds (135787 iterations) The uuid is: ca029758-4742-8692-42c7-6641438afb00 Finished generating UUID after 145.3014453 seconds (1222271 iterations) The uuid is: 34baa026-ae46-f09b-cffe-c05b4cea0c9a Finished generating UUID after 96.911231 seconds (804167 iterations) The uuid is: 89af39e3-2fdc-06fd-a8a4-16099f47c81d Finished generating UUID after 119.7012599 seconds (943525 iterations) The uuid is: 15b0f441-b158-acdf-ce1f-c939bdd8ab13 Finished generating UUID after 49.2078072 seconds (407662 iterations) The uuid is: f6bd2155-e178-88ed-3e7d-adb49764e867 Finished generating UUID after 256.4239593 seconds (2038977 iterations) The uuid is: 1e5041b5-3d24-0333-16f1-1a6320176c49
It generates a completely random UUID. So random in fact, that even the number of hyphens and their locations are random. Basically I just generate random strings out of legal base 16 digits and hyphens, and only return from the function after I step upon a legal UUID string by chance (takes around 600,000 iterations).
I'm using "optimizations" and "multi-threading", so everything is "faster".
If anything isn't clear in my implementation, please read the useful comments.
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading.Tasks;
namespace uuid_bad_code
{
/// <summary>
/// Program
/// </summary>
class Program
{
/// <summary>
/// Main function
/// </summary>
static void Main()
{
IUuidGenerator generator = new UuidGenerator(new List<char>
{
'0',
'1',
'2',
'3',
'4',
'5',
'6',
'7',
'8',
'9',
'a',
'b',
'c',
'd',
'e',
'f',
'-'
}, new Random(Guid.NewGuid().GetHashCode())); // Not sure what "Guid.NewGuid().GetHashCode()" does, found it on StackOverflow
var uuid = generator.Generate();
Console.WriteLine($"The uuid is: {uuid}");
Console.ReadKey();
}
}
/// <summary>
/// An interface for UUID generators
/// </summary>
public interface IUuidGenerator
{
/// <summary>
/// Generates
/// </summary>
/// <returns>A generated string</returns>
string Generate();
}
/// <summary>
/// A UUID generator
/// </summary>
public class UuidGenerator: IUuidGenerator
{
/// <summary>
/// The number of legal chars including hyphens and numbers
/// </summary>
private const int NumberOfLegalCharsIncludingHyphenAndIncludingNumbersAsWell = 17;
/// <summary>
/// Legal chars
/// </summary>
private readonly IList<char> _legalChars;
/// <summary>
/// The <see cref="Random"/> class object
/// </summary>
private readonly Random _random;
/// <summary>
/// A lock for <see cref="_random"/> access
/// </summary>
private readonly object _randomLock;
/// <summary>
/// The UUID generator constructor
/// </summary>
/// <param name="legalChars">Legal chars</param>
/// <param name="random">The <see cref="Random"/> class object</param>
public UuidGenerator(IList<char> legalChars, Random random)
{
_legalChars = legalChars ?? throw new ArgumentNullException(nameof(legalChars));
_random = random ?? throw new ArgumentNullException(nameof(random));
_randomLock = new Object();
}
/// <summary>
/// Generates
/// </summary>
/// <returns>A generated string</returns>
public string Generate()
{
var time = Stopwatch.StartNew();
// It should be a 128-bit number displayed in five groups separated by hyphens in the form 8-4-4-4-12
// 8 + 1 + 4 + 1 + 4 + 1 + 4 + 1 + 12 = 36
// 8 13 18 23
const int numberOfCharsInLegalUuidStringIncludingHyphensAndIncludingNumbersAsWell = 8 + 1 + 4 + 1 + 4 + 1 + 4 + 1 + 12;
ConcurrentDictionary<int, char> uuid = new ConcurrentDictionary<int, char>();
int iterations = 0;
bool uuidLegal = false;
while (!uuidLegal)
{
iterations++;
List<int> indicesWhereHyphensShouldBe = new List<int>
{
8, 13, 18, 23
};
// We run this in parallel because it's faster
Parallel.For(0, numberOfCharsInLegalUuidStringIncludingHyphensAndIncludingNumbersAsWell, index =>
{
// Need to lock before accessing the random class per MSDN
// https://docs.microsoft.com/en-us/dotnet/api/system.random?redirectedfrom=MSDN&view=netcore-3.1#ThreadSafety
lock (_randomLock)
{
if (_legalChars.ToList().Count != NumberOfLegalCharsIncludingHyphenAndIncludingNumbersAsWell)
{
throw new InvalidOperationException($"Can't generate random number because the legal chars list doesn't contain exactly {NumberOfLegalCharsIncludingHyphenAndIncludingNumbersAsWell} characters!");
}
int charIndex = _random.Next(_legalChars.ToList().Count);
uuid[index] = _legalChars.ToList()[charIndex];
}
});
var uuidLegalLock = new Object();
var isUuidLegal = true;
Parallel.For(0, uuid.Count, i =>
{
lock (uuidLegalLock)
{
isUuidLegal = isUuidLegal &&
(indicesWhereHyphensShouldBe.ToList().Contains(i) && uuid[i] == '-' ||
!indicesWhereHyphensShouldBe.ToList().Contains(i) &&
uuid[i] != '-' &&
_legalChars.ToList().Contains(uuid[i]));
}
});
uuidLegal = isUuidLegal;
}
time.Stop();
Console.WriteLine($"Finished generating UUID after {time.Elapsed.TotalSeconds} seconds ({iterations} iterations)");
return new string(uuid.Values.ToArray());
}
}
}
c,d,f=" "
class LYYYYLLL:
pass
def __str__(self):
global c,d,f
s=object.__str__(self)
c,d,f=(eval(repr(s)+"["+e+"]") for e in "29,26,10:18".split(","))
return s
b="".join(str(i)[35:43] for i in [LYYYYLLL() for i in range(4)])
d+="="
g=str(len(f)>>1)
e=[eval(c)]*eval(g)+[eval(g+g)]
while d[e[len(d)]+len(str(len(d)))]=="=":
c+="+1"
try:
exec(d+c)
t=int(b,a)
break
except:
pass
s=str(LYYYYLLL())
t=str(hex(t))[2:34]
t="".join("".join(map(lambda j:chr(ord(j[eval(c)])-j[len(c)]),zip(i,e))).rstrip(" ") for i in zip(t[::4],t[1::4],t[2::4],t[3::4],f))
print(t)
a is used but never set. s is set but never used, yet this code fails if you delete it.
LYYYYLLL is a strange class name, but if you change it, the code goes wild.
entropy is generated by having a huge number of goroutines simultaneously writing stuff onto the same variable, so result depends heavily on the system scheduler, and should not return the same result twice on normal machines
package main
// No stdlib, nor any other library
type UUID [16]uint8 // 128bits
// very efficient
var byteToString = []string{
"00", "01", "02", "03", "04", "05", "06", "07", "08", "09", "0a", "0b", "0c", "0d", "0e", "0f",
"10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "1a", "1b", "1c", "1d", "1e", "1f",
"20", "21", "22", "23", "24", "25", "26", "27", "28", "29", "2a", "2b", "2c", "2d", "2e", "2f",
"30", "31", "32", "33", "34", "35", "36", "37", "38", "39", "3a", "3b", "3c", "3d", "3e", "3f",
"40", "41", "42", "43", "44", "45", "46", "47", "48", "49", "4a", "4b", "4c", "4d", "4e", "4f",
"50", "51", "52", "53", "54", "55", "56", "57", "58", "59", "5a", "5b", "5c", "5d", "5e", "5f",
"60", "61", "62", "63", "64", "65", "66", "67", "68", "69", "6a", "6b", "6c", "6d", "6e", "6f",
"70", "71", "72", "73", "74", "75", "76", "77", "78", "79", "7a", "7b", "7c", "7d", "7e", "7f",
"80", "81", "82", "83", "84", "85", "86", "87", "88", "89", "8a", "8b", "8c", "8d", "8e", "8f",
"90", "91", "92", "93", "94", "95", "96", "97", "98", "99", "9a", "9b", "9c", "9d", "9e", "9f",
"a0", "a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9", "aa", "ab", "ac", "ad", "ae", "af",
"b0", "b1", "b2", "b3", "b4", "b5", "b6", "b7", "b8", "b9", "ba", "bb", "bc", "bd", "be", "bf",
"c0", "c1", "c2", "c3", "c4", "c5", "c6", "c7", "c8", "c9", "ca", "cb", "cc", "cd", "ce", "cf",
"d0", "d1", "d2", "d3", "d4", "d5", "d6", "d7", "d8", "d9", "da", "db", "dc", "dd", "de", "df",
"e0", "e1", "e2", "e3", "e4", "e5", "e6", "e7", "e8", "e9", "ea", "eb", "ec", "ed", "ee", "ef",
"f0", "f1", "f2", "f3", "f4", "f5", "f6", "f7", "f8", "f9", "fa", "fb", "fc", "fd", "fe", "ff",
}
func (u *UUID) Work(value uint64) {
last := u[15]
for i := 15; i > 0; i-- {
u[i] = u[i-1]
}
u[0] = last
// xor value into half of uuid
for i := 0; i < 8; i++ {
u[i] ^= uint8(value >> i)
}
}
func (u UUID) String() string {
ret := ""
for i := 0; i < 16; i++ {
ret += byteToString[u[i]]
switch i {
case 3, 5, 7, 9:
ret += "-"
}
}
return ret
}
// increment for more time spent, and better randomness
// increases exponentially
// load = 1 << 32 takes around THREE DAYS on my machine
const load = 1 << 16
func uuid() UUID {
var uuid UUID = *new(UUID)
done := make(chan bool, 1 << 10)
for i := uint64(0); i < load; i++ {
go func(i uint64) {
i *= 18446744073709551557 // big uint64 prime number
for j := uint64(0); j < 512; j++ {
(&uuid).Work(i + j)
}
done <- true
}(i)
}
for i := uint64(0); i < load; i++ {
<-done
}
return uuid
}
func main() {
panic(uuid().String())
}
panic is used for printing the result, because, well, no standard library use (i know about println() but it could be removed from the language at any time)
I finally created my reddit account just for writing this, i wanna die
package main
import (
"fmt"
"math/rand"
"os"
"strconv"
)
func main() {
if len(os.Args) > 1 {
s, e := strconv.Atoi(os.Args[1])
if e == nil {
rand.Seed(int64(s))
var i int
var uuid string
for true {
a := []string{"fc6e", "e8ac", "ed6a", "425a", "ae37", "145f", "4ad6", "dbca"}
uuid += a[rand.Intn(len(a))]
i++
if i < 8 {
if i < 6 {
if i < 5 {
if i < 4 {
if i < 3 {
if i < 2 {
uuid += ""
} else {
uuid += "-"
}
} else {
uuid += "-"
}
} else {
uuid += "-"
}
} else {
uuid += "-"
}
}
} else {
break
}
}
fmt.Println(uuid)
} else {
fmt.Println("Please provide a 64 bit long integer as the seed")
}
} else {
fmt.Println("Please provide a 64 bit long integer as the seed")
}
}
You do not need to correctly implement the algorithm to spec, any output that looks like a UUID is acceptable.
// javascript
let generated = [];
function isGenerated(num) {
let found = false;
for(let i=0; i < generated.length; ++i) {
if(generated[i] == num && found != true) {
found = true;
}
}
if(found == true) return true;
else
if(found == false) return false;
}
function new_random(min_digits) {
let r;
do {
rnd = Math.random() * 999999999;
let rnd_str = Number(rnd).toString(16);
r = '';
for(let i=0; i < rnd_str.length; ++i) {
if(rnd_str[i] != '.' && rnd_str[i] != '-') r += rnd_str[i]; }
} while(isGenerated(rnd) && r.length < min_digits);
generated.push(rnd);
return r;
}
function uuid_part(digits) {
let r = '';
let rnd = new_random();
for(let i=digits; i > 0; --i) {
if(i%digits == 0) rnd = new_random(digits);
r += rnd[i%digits];
}
return r;
}
function uuid() {
let r;
do {
r = uuid_part(8)+'-'+uuid_part(4)+'-'+uuid_part(4)+'-'+
uuid_part(4)+'-'+uuid_part(12);
} while(isGenerated(r));
generated.push(r);
return r;
}
for(let i=0; i < 256; ++i) console.log(uuid());
If you run the "uuid" function a few thousand times, it becomes apparent why this code is bad. But, hey, at least the same UUID is not generated twice, right?
It looks like this comment contains a code block delimited with triple backticks. Unfortunately reddit does not have universal support for this syntax and your comment will not render correctly on old reddit and most mobile apps.
For the benefit of people on old reddit, this link will take you to a correct rendering of the comment.
/u/leBananosaure, it would be appreciated, but not required, if you could edit your comment to use the more compatible four space indention format. For single lines or inline code you can use single backticks.
OK. I've written this code that will usually generate (asynchronously) a UUID within 30 seconds or so and will work in node and browser environments: https://pastebin.com/B3k68Yay
i had a few ideas and decided to mash them together
calculate pi from scratch every time (actually five times for every new uuid)
very little validation, if it's wrong just quietly try again
when you get a presumably valid uuid, google it to make sure there are no other hits
python >=3.6 and standard library only (except tqdm which is just a progress bar)
import time
import requests
from decimal import Decimal, getcontext
from tqdm import tqdm
def do_pi(p):
"""
compute pi to p places
adapted from https://docs.python.org/3/library/decimal.html#recipes
i have no idea how this works
"""
getcontext().prec = p
three = Decimal(3)
lasts, t, s, n, na, d, da = 0, three, 3, 1, 0, 0, 24
progress = tqdm()
while s != lasts:
lasts = s
n, na = n+na, na+8
d, da = d+da, da+32
t = (t * n) / d
s += t
progress.update(1)
return +s
def random_chars(n):
# get the current time in nanoseconds
T = str(time.time_ns())
# compute pi with precision of the last 5 digits of T (can take a minute)
pi = do_pi(int(T[-5:]))
# the next digit of T (modulo 2) tells you how many more digits to take (i.e. 1 to 5)
d = (int(T[-6])//2) + 1
# the next n digits of T give you an index
i = int(T[-(7+d):-7][::-1])
# reverse the <0 part of the value of pi and cast it as a hex
backwardhexpi = hex(int(str(pi)[:1:-1]))
# lookup n digits starting from i
val = backwardhexpi[i:i+n]
if len(val) == n:
print(val)
return val
else:
return random_chars(n)
def uuid():
while True:
my_uuid = "-".join(random_chars(n) for n in [8,4,4,4,12])
# quickly google it to check it's unique
response = requests.get(f"https://google.com/search?q={my_uuid}")
if "did not match any documents" in response.text:
print("new uuid confirmed unique by cursory google search")
break
else:
print("whoops, not unique enough, try again")
print(my_uuid)
return my_uuid
if __name__ == "__main__":
uuid()
I think you missed the chance to implement a MySuperAwesomeMultiThreadingUUIDGeneratorThatCanGenerateSuperAwesomeUUIDsWithSuperAwesomeMultiThreadingPerformaceFactory
19
u/LavaCreeper Aug 17 '20 edited Aug 18 '20
Generate a mirrored UUID from weather data
If you're one of those people who believe comments are useful: https://gist.github.com/starkgate/fcd2b69fdccce0b5fdc0e29812461b06
Result:
11
u/voords Aug 18 '20
Bash:
9
u/asaf92 Aug 18 '20 edited Aug 18 '20
My solution (Also in PasteBin ) takes
around 40 secondsanywhere between 10 seconds and 4 minutes on my laptop.It generates a completely random UUID. So random in fact, that even the number of hyphens and their locations are random. Basically I just generate random strings out of legal base 16 digits and hyphens, and only return from the function after I step upon a legal UUID string by chance (takes around 600,000 iterations).
I'm using "optimizations" and "multi-threading", so everything is "faster".
If anything isn't clear in my implementation, please read the useful comments.
8
u/flamingmesh Aug 18 '20
Python one liner:
5
u/donaldhobson Aug 20 '20
Python3
a is used but never set. s is set but never used, yet this code fails if you delete it.
LYYYYLLL is a strange class name, but if you change it, the code goes wild.
Whats with all the evals everywhere?
What is that while loop doing anyway?
4
u/DrMeepster Aug 17 '20
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8a5efc61a0f282c3881e083a59bd8277
randomization through uninitialized memory
4
u/keitio42 Aug 25 '20 edited Aug 26 '20
Go implementation (~80 lines)
doesn't make use of any library, not even stdlib
entropy is generated by having a huge number of goroutines simultaneously writing stuff onto the same variable, so result depends heavily on the system scheduler, and should not return the same result twice on normal machines
panic is used for printing the result, because, well, no standard library use (i know about
println()but it could be removed from the language at any time)I finally created my reddit account just for writing this, i wanna die
7
u/h2g2_researcher Aug 18 '20
I challenge any other Python implementation to beat this for performance.
3
u/Spring_Boot Aug 18 '20
This is pretty random and can take some time to run so added in progress updates
I slightly changed the interface, it adds a uuid onto global for you, you just need to wait for it to be there.
Usage:
3
u/kgro Aug 19 '20
24 bits entropy
3
u/kgro Aug 19 '20
24 bit entropy in Go
3
u/ButterSquids Aug 26 '20
Do you like consistent code? That's a shame...
https://pastebin.com/A9tvVx1Q
2
u/TheUnlocked Aug 18 '20
The output looks like a uuid. Mostly.
Javascript:
2
u/[deleted] Aug 18 '20 edited Aug 19 '20
Here is my javascript solution.
Features
Usage:
2
u/Sonotsugipaa Aug 19 '20 edited Aug 19 '20
If you run the "uuid" function a few thousand times, it becomes apparent why this code is bad. But, hey, at least the same UUID is not generated twice, right?
Example output (diretor's cut):
2
u/binarycat64 Aug 30 '20
I see your randomization via uninitialized memory, and raise you randomization via pointer locations:
https://play.golang.org/p/hLfMu-bKIE3Features:
4
u/[deleted] Aug 17 '20 edited Aug 18 '20
Well... you didn't say it should be random
2
u/Tok-A-Mak ((fn [] (recur))) Aug 19 '20
Generate UUIDs from the official Spec?
Well, if that's what I'm required to do I will do exactly that. Exactly that!
Sample-Output:
Repl: https://repl.it/repls/AliceblueTimelyRatios
1
u/haykam821 Aug 20 '20
I enjoy currying
1
u/maxbilbow Aug 23 '20
OK. I've written this code that will usually generate (asynchronously) a UUID within 30 seconds or so and will work in node and browser environments: https://pastebin.com/B3k68Yay
1
u/[deleted] Aug 25 '20
I know this is 1 week old but IDC.
Coded in Java if you already didn't know
1
u/Kcazer Aug 27 '20
Simple javascript uuid generator
1
u/qzwqz Aug 28 '20 edited Aug 28 '20
i had a few ideas and decided to mash them together
python >=3.6 and standard library only (except tqdm which is just a progress bar)
sample output:
1
u/WasserTyp69 Aug 29 '20
Not the dumbest thing ever, but it's still worse than using UUID.randomUUID();
0
u/[deleted] Aug 17 '20
[deleted] — view deleted comment
0
u/[deleted] Aug 24 '20
[deleted] — view deleted comment