8
\$\begingroup\$

The type 4 GUID is described by Wikipedia, quoth:

Version 4 UUIDs use a scheme relying only on random numbers. This algorithm sets the version number (4 bits) as well as two reserved bits. All other bits (the remaining 122 bits) are set using a random or pseudorandom data source. Version 4 UUIDs have the form xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx where x is any hexadecimal digit and y is one of 8, 9, A, or B (e.g., f47ac10b-58cc-4372-a567-0e02b2c3d479).

Write a program that loads 488 bits (61 bytes) of cryptographic quality randomness and output them as 4 GUIDs using the format quoted above.

  • Do not waste randomness.
    • All random bits must appear in the encoded output.
    • All encoded bits must be traceable to either a single random bit or one of the six fixed bits that must appear in each GUID.
  • Use the cryptographic quality random number generator supplied by your language's standard library.
  • Do not use a library or external resource that generates GUIDs.
  • The hyphens must appear in their correct positions.
  • The fixed bits of this form of GUID must appear in their correct positions.
  • You may use a standard library function designed to output a GUID from 128 bits.
  • Normal code-golf rules apply.

For example...

> gentype4
6FA53B63-E7EA-4461-81BE-9CD106A1AFF8
856970E9-377A-458E-96A7-43F587724573
E4F859AC-0004-4AA1-A3D2-AECB527D1D24
766811C5-0C44-4CC8-8C30-E3D6C7C6D00B

Update:
I asked for four GUIDs in order to allow a whole number of random bytes to be gathered without leaving any remainder. I also specified that none of the bits should be wasted in order to avoid the easy answer of getting 16 random bytes and dropping the 4 in. (No, shift the other bits along first.)

Update 2:
If your language's standard library doesn't have a cryptographic quality random byte generator, you may instead assume that there is a 61 byte file present with enough random bytes for you to use when the program starts. The file should be called "/dev/urandom" or another filename with 12 characters.

\$\endgroup\$
4
  • \$\begingroup\$ If my language doesn't have a way to request a certain number of random bits/bytes, but can get a random number from 0 to n-1 using something like random(n), can I just use random(1<<k) as a way to get k random bits? Also, is it ok to get them in small pieces (e.g. 4 or 2 bits at a time) through multiple calls? \$\endgroup\$ Jun 23, 2014 at 16:48
  • \$\begingroup\$ I was hoping to see how different languages can access cryptographic quality randomness. I'll add an exception for those languages without such means. \$\endgroup\$
    – billpg
    Jun 23, 2014 at 16:52
  • \$\begingroup\$ Well, now you're assuming it can read external files :p What I could use is a sequence of numbers (separated by space) given through the standard input.. but maybe I'm asking too much and should just not participate (in that language). And an unrelated note: the wikipedia quote refers to UUIDs, not GUIDs. \$\endgroup\$ Jun 23, 2014 at 17:07
  • \$\begingroup\$ A close duplicate: codegolf.stackexchange.com/q/20363 \$\endgroup\$
    – primo
    Jun 24, 2014 at 11:37

10 Answers 10

1
\$\begingroup\$

PHP, 338 bytes

<?php $r=openssl_random_pseudo_bytes(61);$b="";$s="substr";for($i=0;$i<61;)$b.=str_pad(decbin(ord($r[$i++])),8,0,0);function p($B,$L){return str_pad(dechex(bindec($B)),$L,0,0);}for($i=0;$i<4;$i++)echo p($s($b,$p=122*$i,32),8)."-".p($s($b,$p+32,16),4)."-4".p($s($b,$p+48,12),3)."-".p("10".$s($b,$p+60,14),4)."-".p($s($b,$p+74,48),12)."\n";

Some output

> php 32309.min.php
635fa088-4a66-47fc-9e50-2ccb2445b643
6e5c23c7-ba16-427e-960b-5316980ce4e3
fdb570ca-2e5e-4594-ab2e-db8446599b8f
203f2538-b5f4-47f0-89ac-012ca14b2f99
> php 32309.min.php
a6981255-0ab2-4d82-aab4-d1c64d2bb7eb
c348e728-f817-45d2-9bbf-b40426baa461
9b2baed2-e58b-41ef-a6fb-57e96db74a68
63e464e7-ab55-4e2a-a2a0-abdc535481dc
> php 32309.min.php
af7e68d3-b3ed-4e19-85b2-280270f746c6
0a86c610-8d0c-4c0a-bafe-44a6886d71f8
98c742b8-6a3b-47ff-97c7-ccab70d79a3c
59a93afc-ff81-4c97-a57b-72f0de384acb
> php 32309.min.php
72b352fc-0174-4051-969e-cacc0adbf941
50e4f859-76fe-45f6-baf5-d5fcceb41f72
5a18408e-6e7e-43a6-bd71-09d22a0fbf14
ae5a1391-5367-467e-8ecc-785ca72cbf95

Ungolfed

<?php
$r = openssl_random_pseudo_bytes(61);
$b = "";
$s = "substr";
for($i=0 ; $i<61 ;) $b .= str_pad(decbin(ord($r[$i++])), 8, 0, 0);

function p($B, $L) {
    return str_pad(dechex(bindec($B)), $L, 0, 0);
}

for($i=0 ; $i<4 ; $i++) {
    echo p($s($b, 122*$i, 32), 8)."-";
    echo p($s($b, 122*$i+32, 16), 4)."-4";
    echo p($s($b, 122*$i+48, 12), 3)."-";
    echo p("10".$s($b, 122*$i+60, 14), 4)."-";
    echo p($s($b, 122*$i+74, 48), 12)."\n";
}
\$\endgroup\$
1
  • 3
    \$\begingroup\$ openssl_random_pseudo_bytes? That's.. verbose. PHP keeps amazing me - in the wrong way. \$\endgroup\$
    – seequ
    Jun 23, 2014 at 17:26
1
\$\begingroup\$

J - 114 bytes

I took the simplest approach available. The function takes amount of GUID's required (you could replace the ] near the end with 4: to make it return 4 always) and outputs that many of them, separated by newlines.

Edit: I missed that no generated bits must go to waste... This answer doesn't comply and I don't know how to make it to.

f=:[:}.(,LF,(x@8:,'-',x@4:,'-4',x,'-',('89AB'{~?@4:),x,'-',(x=:'0123456789ABCDEF'{~?@$&16)@(12"_))@3:)^:(]`(''"_))

If an extra newline is allowed after the output, this could be written in 111 bytes.

f=:(,LF,~(x@8:,'-',x@4:,'-4',x,'-',('89AB'{~?@4:),x,'-',(x=:'0123456789ABCDEF'{~?@$&16)@(12"_))@3:)^:(]`(''"_))

Example:

   f 4
B23B10E3-6593-40F7-A5B0-D25A2763D781
3901709C-654E-4AF0-B23E-7252E859D35B
91E8D566-8E84-48CD-9B9D-EFC4E3F62C4E
F4578389-097C-4C38-A3C0-31EABFDCD630
   f 5
AF234012-8A9F-47A3-9BF5-4B28AF580E9C
A3FE1785-8B40-44E9-8D69-CFF1BE06AC06
84A2CEB9-744F-4B86-B37F-747D0FD3F3FC
0FD8B7A6-9642-42C3-89ED-DB4A35D83CF8
4F860D9B-6E20-4AF8-B6BF-0F8CB307B9B0
\$\endgroup\$
1
  • \$\begingroup\$ @billpg This version generates a 32-bit integer for each necessary hexadecimal digit (for everything but the 4, - and linefeed). Is that okay? \$\endgroup\$
    – seequ
    Jun 23, 2014 at 17:19
1
\$\begingroup\$

Golfscript, 75

Fixed now!

{{'0123456789ABCDEF'{.,rand>1<}:|~}:&8*'-':^&&&&^4&&&^'89AB'|&&&^{&}12*n}4*

Output example:

>ruby golfscript.rb p.gs
140BC879-EAC4-4170-B349-A616523458DB
E26B34A4-8E86-4508-9EE5-3C76BF7456B6
89F9B995-CC9E-4EF0-AA25-70703B80AF82
5F6A513C-9E97-45A4-A9D1-E9D3DF71EF99

>ruby golfscript.rb p.gs
38D7A76B-BEEB-4C98-A148-D1EA8C31E85F
807373E4-5CFE-4953-9D5E-671205EE1E8F
8BD88B76-5890-4543-9787-2753AB15D24B
CD7DF25F-632B-4902-A46C-A1E10BE83EC5

You can test it yourself here.

\$\endgroup\$
3
  • \$\begingroup\$ That bug is pretty. \$\endgroup\$
    – seequ
    Jun 23, 2014 at 18:33
  • \$\begingroup\$ Was pretty atleast. \$\endgroup\$
    – seequ
    Jun 23, 2014 at 19:02
  • \$\begingroup\$ Is "rand" in GS a cryptographic quality random number generator? \$\endgroup\$
    – billpg
    Jun 27, 2014 at 8:22
1
\$\begingroup\$

Python, 287 bytes

from random import choice
s="0123456789abcdef"
def gen4():
  for i in range(4):
    m,n="",""
    l = []
    d = choice(s[8:12])
    for k in range(30):
      l.append(choice(s))
    m="".join(l)
    n=m[:12]+"4"+m[12:15]+d+m[15:]
    print(n[:8]+"-"+n[8:12]+"-"+n[12:16]+"-"+n[16:20]+"-"+n[20:])  

There's already a Python answer, but that just used .uuid, so here's one without it. Wish i could get it shorter though.

Still beat PHP :P

\$\endgroup\$
0
\$\begingroup\$

Python (85)

import os,uuid
for i in [1]*4:print uuid.UUID(os.urandom(16).encode('hex'),version=4)

os.urandom(n): Return a string of n random bytes suitable for cryptographic use.

I assume generating more than 488 bits is ok?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Standard library function is part of the library that comes with your language. os and uuid both are part of it. \$\endgroup\$
    – seequ
    Jun 23, 2014 at 15:48
  • 1
    \$\begingroup\$ I added the "Don't waste any bits" rule because I wanted to see some bit fiddling. Just being able to drop in the 4 wiping out other bits seemed too simple a task. \$\endgroup\$
    – billpg
    Jun 23, 2014 at 16:25
  • \$\begingroup\$ That's also why I specified four GUIDs to be output, so you'd have a whole number of random bytes to deal with. \$\endgroup\$
    – billpg
    Jun 23, 2014 at 16:29
0
\$\begingroup\$

Python 2 - 188 / 182

This should obey the requirements faithfully:

import os
a=(ord(x)>>i&3for i in(0,2,4,6)for x in os.urandom(61))
h=lambda n:eval('"%X"%(a.next()*4+a.next())+'*n+'"-"')
exec'print h(8)+h(4)+"4"+h(3)+"%X"%(8+a.next())+h(3)+h(12)[:-1];'*4

If python's UUID is acceptable for outputting a nicely-formatted uuid from a 32-digit hex string, then this version has 182 bytes:

import os,uuid
a=(ord(x)>>i&3for i in(0,2,4,6)for x in os.urandom(61))
exec('s='+'"%X"%(a.next()*4+a.next())+'*30+'"";print uuid.UUID(s[3:15]+"4"+s[:3]+"%X"%(8+a.next())+s[15:]);')*4

a is a generator comprehension that gives 2 bits at a time from an initial source of 61 random bytes.

Thanks TheRare for tips

\$\endgroup\$
6
  • \$\begingroup\$ You don't need to set x in t, just return it. for i in range(n):s+="%X"%(t()*4+t()) could be written exec's+="%X"%(t()*4+t());'*n and thus function h could be written in one line. You can use the same trick in the following loop too, just replace n by 4. \$\endgroup\$
    – seequ
    Jun 23, 2014 at 19:01
  • \$\begingroup\$ Whoops, yes you do need to set it. Sorry! The rest still works though. \$\endgroup\$
    – seequ
    Jun 23, 2014 at 19:08
  • \$\begingroup\$ @TheRare exec also seems to interfere with global, but still there is something to gain, thanks for reminding me about it \$\endgroup\$ Jun 23, 2014 at 19:10
  • \$\begingroup\$ Ah, sorry. I completely forgot that global causes it to break. What if you changed it to something like this (didn't check if it's shorted, but global s is not needed): def h(n):s='';exec's+="%X"%(t()*4+t());'*4;return s+'-'<LINEFEED HERE>print'\n'.join(h(8)+h(4)+'4'+h(3)+"%X"%(8+t())+h(3)+h(12)for _ in 1,2,3,4) \$\endgroup\$
    – seequ
    Jun 23, 2014 at 19:17
  • \$\begingroup\$ Or even h=lambda n:''.join("%X"%(t()*4+t())for _ in[0]*n)+'-';print'\n'.join(h(8)+h(4)+'4'+h(3)+"%X"%(8+t())+h(3)+h(12)for _ in[0]*4) (both are untested) \$\endgroup\$
    – seequ
    Jun 23, 2014 at 19:21
0
\$\begingroup\$

Common Lisp

SBCL, 223

(define-alien-routine("arc4random_uniform"a)int(u
int))(labels((g(n)(a(expt 2 n)))(h()(g 16)))(dotimes(i 4)(format
t"~4,'0X~4,'0X-~4,'0X-~4,'0X-~4,'0X-~4,'0X~4,'0X~4,'0X~%"(h)(h)(h)(+
16384(g 12))(+ 32768(g 14))(h)(h)(h))))

CLISP, 299

(use-package :ffi)(def-call-out
a(:name"arc4random_uniform")(:arguments(u int))(:return-type
int)(:language :c)(:library :default))(labels((g(n)(a(expt 2
n)))(h()(g 16)))(dotimes(i 4)(format
t"~4,'0X~4,'0X-~4,'0X-~4,'0X-~4,'0X-~4,'0X~4,'0X~4,'0X~%"(h)(h)(h)(+
16384(g 12))(+ 32768(g 14))(h)(h)(h))))

About arc4random_uniform(3)

Both of these call the C function arc4random_uniform(3) in BSD libc. Some systems do not have this function.

Beware that my declaration of arc4random_uniform(3) is wrong. The correct declaration is

u_int32_t arc4random_uniform(u_int32_t);

where u_int32_t is an old BSDism for an unsigned 32-bit integer. (The standard type in C99 is uint32_t without the first underscore.) My wrong declaration is

int arc4random_uniform(int);

where int is a signed 32-bit integer. (I know systems where int only has 16 bits, but I would not run Lisp there.) I am wrong to use signed for unsigned, but my program works because I only pass small non-negative integers. In code golf, int is shorter than unsigned-int in SBCL or uint in CLISP.

To use arc4random_uniform(3) in Lisp, I define a Lisp function a. Here it is in SBCL:

; (use-package :sb-alien)  ; SBCL does this by default!
(define-alien-routine ("arc4random_uniform" a)
  int       ; return type
  (u int))  ; argument named u

And in CLISP:

(use-package :ffi)
(def-call-out a
  (:name "arc4random_uniform")
  (:arguments (u int))
  (:return-type int)
  (:language :c)
  (:library :default))

CLISP has two languages, :c for traditional K&R C and :stdc for C89, but I find no difference, so I use the shorter name.

Now (a u) returns a random integer at least 0 and less than u. If u is 2n, then I get exactly n bits. For example, (a (expt 2 14) provides 14 bits. Because of my wrong declaration, u must be less than 231. If I want 32 bits, I may call (a 16) twice.

Rest of program

; after defining A
(labels ((g (n) (a (expt 2 n)))
         (h () (g 16)))
  (dotimes (i 4)
    (format t
            "~4,'0X~4,'0X-~4,'0X-~4,'0X-~4,'0X-~4,'0X~4,'0X~4,'0X~%"
            (h) (h) (h) (+ 16384 (g 12)) (+ 32768 (g 14)) (h) (h) (h))))

I define two local functions. (g n) generates n random bits. (expt 2 n) is much shorter than a left shift: 1<<n in C would become (let((v 0))(setf(ldb(byte 1 n)v)1)v) in Common Lisp!

(h) is an alias for (g 16). This alias costs 13 characters: 11 in (h()(g 16)), plus 2 to upgrade flet to labels, because h needs g in scope. Each call to (h) saves 3 characters, and I have 6 calls, so I save 18 after I spend 13.

When formatting each GUID, (+ 16384(g 12)) is shorter than (logior #x4000 (g 12) and (+ 32768(g 14)) is shorter than (logior #x8000 (g 14)).

One can generate the long format string "~4,'0X~4,'0X-~4,'0X-~4,'0X-~4,'0X-~4,'0X~4,'0X~4,'0X~%" (56 characters) with the expression (format()"~{~A~}~~%"(mapcar(lambda(e)(if e(format()"~~4,'0X")'-))'(t t()t()t()t()t t t))) (89 characters), but the literal string is shorter.

\$\endgroup\$
0
\$\begingroup\$

Javascript (ES6) - 177 163 158

Removed .toUpperCase(), replaced substring with substr and substr(0,3) to substr(1)

function f(){g=()=>(((1+Math.random())*0x10000)|0).toString(16).substr(1);for(i=0;i<4;i++)alert((g()+g()+"-"+g()+"-4"+g().substr(1)+"-"+g()+"-"+g()+g()+g()))}

EcmaScript 5 version of the above script:

function f(){function g(){return (((1+Math.random())*0x10000)|0).toString(16).substr(1)}for(i=0;i<4;i++)alert((g()+g()+"-"+g()+"-4"+g().substr(1)+"-"+g()+"-"+g()+g()+g()))}
\$\endgroup\$
2
  • \$\begingroup\$ Doesn't f=x=> work as the function definition? I've never used ES6 though. \$\endgroup\$
    – seequ
    Jun 24, 2014 at 11:51
  • \$\begingroup\$ @TheRare Nope.. \$\endgroup\$
    – Spedwards
    Jun 25, 2014 at 10:34
0
\$\begingroup\$

05AB1E, 41 bytes

4F30F15ÝΩh}J•2,ÈĆ•13в£'-4и4DL7+hΩ‚.ιÁ.ιJ,

Try it online.

Explanation:

4F                  # Loop 4 times:
  30F               #  Inner loop 30 times:
     15Ý            #   Push the list [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
        Ω           #   Pop and push a random integer from this list
         h          #   Convert the integer to hexadecimal
          }J        #  After the inner loop: join the characters on the stack together
•2,ÈĆ•              #  Push compressed integer 40106286
      13в           #  Convert it to base-13 as list: [8,4,0,3,0,3,12]
         £          #  Split the string into parts of that size
                    #   i.e. "FBA4C1C6FE22479659019DA439B7D6"
                    #    → ["FBA4C1C6","FE22","","479","","659","019DA439B7D6"]
'-4и               '#  Push a list of 4 "-"s: ["-","-","-","-"]
    4               #  Push a 4
     DL             #  Duplicate it to create the list [1,2,3,4]
       7+           #  Add 7 to each: [8,9,10,11]
         h          #  Convert each to hexadecimal: [8,9,"A","B"]
          Ω         #  Pop and push a random value from this list
                    #   i.e. "B"
           ‚        #  Pair it together with the 4
            .ι      #  Interleave it with the list of "-": ["-",4,"-","B","-","-"]
              Á     #  Rotate it once towards the right: ["-","-",4,"-","B","-"]
               .ι   #  Interleave it with the earlier created list
                    #   → ["FBA4C1C6","-","FE22","-","",4,"479","-","","B","659","-","019DA439B7D6"]
                 J  #  Join this list together to a string
                    #   → "FBA4C1C6-FE22-4479-B659-019DA439B7D6"
                  , #  And output it with trailing newline

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why •2,ÈĆ• is 40106286 and •2,ÈĆ•13в is [8,4,0,3,0,3,12].

Without the requirement that no random bits must go to waste, this could have been 36 bytes, by utilizing the builtin ǝ (based on my answer here):

4FŽΣÌvy4*F15ÝΩh}'-}J¨4DL7+hΩ‚Ž5Ā2äǝ,

Try it online.

\$\endgroup\$
0
\$\begingroup\$

Coconut 1.4.1, 114 bytes

from random import*
for C in[->f'{randrange(16**_):0{_}x}']*4:print(C 8,C 4,'4'+C 3,choice'89ab'+C 3,C 12,sep='-')

Try it online!

This works on the old version on TIO, for newer versions you might need parentheses around '89ab'.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.