homepage Welcome to WebmasterWorld Guest from 54.224.179.98
register, free tools, login, search, pro membership, help, library, announcements, recent posts, open posts,
Become a Pro Member

Home / Forums Index / Code, Content, and Presentation / PHP Server Side Scripting
Forum Library, Charter, Moderators: coopster & jatar k

PHP Server Side Scripting Forum

    
A coding puzzle
httpwebwitch




msg:4360697
 8:28 pm on Sep 9, 2011 (gmt 0)

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




msg:4360702
 8:42 pm on Sep 9, 2011 (gmt 0)

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




msg:4360706
 8:51 pm on Sep 9, 2011 (gmt 0)

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




msg:4360716
 9:14 pm on Sep 9, 2011 (gmt 0)

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

<?php

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:

<?php
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




msg:4360723
 9:57 pm on Sep 9, 2011 (gmt 0)

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




msg:4360725
 10:22 pm on Sep 9, 2011 (gmt 0)

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




msg:4360775
 4:28 am on Sep 10, 2011 (gmt 0)

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




msg:4360777
 4:30 am on Sep 10, 2011 (gmt 0)

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

brotherhood of LAN




msg:4360793
 6:23 am on Sep 10, 2011 (gmt 0)

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

httpwebwitch




msg:4361147
 6:41 pm on Sep 11, 2011 (gmt 0)

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




msg:4361175
 7:46 pm on Sep 11, 2011 (gmt 0)

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




msg:4361202
 10:04 pm on Sep 11, 2011 (gmt 0)

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

Global Options:
 top home search open messages active posts  
 

Home / Forums Index / Code, Content, and Presentation / PHP Server Side Scripting
rss feed

All trademarks and copyrights held by respective owners. Member comments are owned by the poster.
Home ¦ Free Tools ¦ Terms of Service ¦ Privacy Policy ¦ Report Problem ¦ About ¦ Library ¦ Newsletter
WebmasterWorld is a Developer Shed Community owned by Jim Boykin.
© Webmaster World 1996-2014 all rights reserved