A coding puzzle

[httpwebwitch]

Here's an interesting challenge I've come against. Any ideas how to solve it elegantly?

I need to generate a globally unique "coupon code". Here are the specs:

- it must be globally unique
- it must have the appearance of being random, ie not easy to guess and it mustn't just be 0001, 0002, 0003, etc.
- it's a string of case-insensitive letters and numbers, like "G263782" OR "IIW99D8".
- it should be not too short, but not too long either. If it's too long, it's more likely someone is going to typo trying to punch it in.
- they mustn't be sequential. We don't want AAAAA to be followed by AAAAB and AAAAC

As for globally unique... you can assume we won't be generating more than one of these per microsecond so something that uses microtime() would be acceptable.

But to be really unique it would be nice to hit the MySQL database and use the Primary key id of the inserted row (autoincrementing integer).

Best answer will receive an awesome little banner made by me to put on their website saying how awesome you are.

[httpwebwitch]

this produces something not-too-bad:

strtoupper(base_convert(microtime(true)*100,10,36))

the result is codes that are not strictly sequential, but they act like incrementing numbers. Here are some, taken a few seconds apart:

1OFRH7H9
1OFRH7XF
1OFRH8ED
1OFRH8WY
1OFRH9H0

They don't feel entropic enough to me

[httpwebwitch]

strtoupper(base_convert(uniqid(),16,36))

not much better. It still produces what looks like sequential strings.

DKZT9L1S5J
DKZT9QVRYN
DKZT9V0VWD
DKZT9YA4A1
DKZTA2XPBZ
DKZTA7BS5R

[brotherhood of LAN]

If you want to guarantee no collisions when generating a new code:

mysql_connect('localhost','root','root'); mysql_select_db('test'); mysql_query('CREATE TABLE IF NOT EXISTS coupon_codes ( id int(10) unsigned NOT NULL AUTO_INCREMENT, code char(8) NOT NULL, PRIMARY KEY ( id ), UNIQUE KEY code ( code )) ENGINE=InnoDB'); // Delete this when table is made function generate_code($length) { $query = mysql_query('SELECT COALESCE(MAX(id),0) + 1 AS id FROM coupon_codes'); $row = mysql_fetch_array($query,MYSQL_ASSOC); $data = array($row['id'],strtoupper(substr(base_convert(substr(md5($row['id']),1),16,36),0,$length))); mysql_query('INSERT INTO coupon_codes (id,code) VALUES ('.$row['id'].',\''.$data[1].'\')'); return $data; } $data = generate_code(8); print_r($data);

Possible collisions:

function generate_code($length) { while(1) { $code = strtoupper(substr(base_convert(substr(md5(microtime()),1),16,36),0,$length)); if(mysql_num_rows(mysql_query('SELECT 1 FROM coupon_codes WHERE code = \''.$code.'\''))) continue; mysql_query('INSERT IGNORE coupon_codes (code) VALUES (\''.$code.'\')'); return $code; } } echo generate_code(8),"\n";

Since 8 alphanumeric characters amounts to 2821109907456 permutations, it's probably quite safe to go down that route. Shorter combinations might result in more collisions and thus extra queries to find a unique slot.

[Key_Master]

I would look at a solution that uses some type of encryption. Something that uses microtime and browser info (ie, IP) as the string/salt.

Md5 would be safest but a 32 character coupon code is probably out of the question. You could use DES or Extended DES but the odds of collision go up. Merging two unique 11 digit DES strings (without the salt) would lessen the odds of collision and give you a 22 character coupon code.

[penders]

How many "coupon codes" are to be generated? How many per time period? Do they expire? Just wondering, as the chance of collision could be greatly reduced.

[httpwebwitch]

b'o'Lan, that's brilliant.
Can you post an example of say 20 codes generated by that?

I had an idea on my drive home today.

strtoupper(base_convert(uniqid(),16,36))

produces some nice sized strings, with no collisions. What I don't like about them is how they all start with "DKZT" (or at least today they do) and they look like sequential strings

To make them *look* more unpredictable, I could shuffle the letters in a predictable way... like:

ABCDEFGHIJ => JAIBHCGDFE

this would turn my previous examples into:

DKZT9L1S5J -> JD5KSZ1TL9
DKZT9QVRYN -> NDYKRZVTQ9
DKZT9V0VWD -> DDWKVZ0TV9
DKZT9YA4A1 -> 1DAK4ZATY9
DKZTA2XPBZ -> ZDBKPZXT2A
DKZTA7BS5R -> RD5KSZBT7A

[httpwebwitch]

I'm considering switching to base 26 instead of 36, to avoid typo similarities between "1" and "I", "0" and "O".

[brotherhood of LAN]

They'd be totally random alphanumeric characters by nature of MD5.

[httpwebwitch]

OK brotherhood, you win. I've implemented something that uses base_convert(uniqid()) instead of md5(), but enforcing uniqueness in post-processing using the technique you've suggested.

Sticky me and I'll send you that banner

[brotherhood of LAN]

I'll save you the time of making that banner and propose you donate the time/money to a charity instead ;o)

I think penders raises an important point about how often these codes are going to be generated.

[httpwebwitch]

Why would a charity want a banner saying how awesome you are? LOL