6
\$\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\$
  • \$\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\$ – aditsu Jun 23 '14 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 '14 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\$ – aditsu Jun 23 '14 at 17:07
  • \$\begingroup\$ A close duplicate: codegolf.stackexchange.com/q/20363 \$\endgroup\$ – primo Jun 24 '14 at 11:37
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\$
  • 3
    \$\begingroup\$ openssl_random_pseudo_bytes? That's.. verbose. PHP keeps amazing me - in the wrong way. \$\endgroup\$ – seequ Jun 23 '14 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\$
  • \$\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 '14 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\$
  • \$\begingroup\$ That bug is pretty. \$\endgroup\$ – seequ Jun 23 '14 at 18:33
  • \$\begingroup\$ Was pretty atleast. \$\endgroup\$ – seequ Jun 23 '14 at 19:02
  • \$\begingroup\$ Is "rand" in GS a cryptographic quality random number generator? \$\endgroup\$ – billpg Jun 27 '14 at 8:22
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\$
  • 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 '14 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 '14 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 '14 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\$
  • \$\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 '14 at 19:01
  • \$\begingroup\$ Whoops, yes you do need to set it. Sorry! The rest still works though. \$\endgroup\$ – seequ Jun 23 '14 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\$ – aditsu Jun 23 '14 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 '14 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 '14 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\$
  • \$\begingroup\$ Doesn't f=x=> work as the function definition? I've never used ES6 though. \$\endgroup\$ – seequ Jun 24 '14 at 11:51
  • \$\begingroup\$ @TheRare Nope.. \$\endgroup\$ – Spedwards Jun 25 '14 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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