homepage Welcome to WebmasterWorld Guest from 54.145.183.126
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

WebmasterWorld Administrator httpwebwitch us a WebmasterWorld Top Contributor of All Time 10+ Year Member



 
Msg#: 4360695 posted 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

WebmasterWorld Administrator httpwebwitch us a WebmasterWorld Top Contributor of All Time 10+ Year Member



 
Msg#: 4360695 posted 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

WebmasterWorld Administrator httpwebwitch us a WebmasterWorld Top Contributor of All Time 10+ Year Member



 
Msg#: 4360695 posted 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

WebmasterWorld Administrator brotherhood_of_lan us a WebmasterWorld Top Contributor of All Time 10+ Year Member Top Contributors Of The Month



 
Msg#: 4360695 posted 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

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 4360695 posted 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

WebmasterWorld Senior Member penders us a WebmasterWorld Top Contributor of All Time 5+ Year Member Top Contributors Of The Month



 
Msg#: 4360695 posted 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

WebmasterWorld Administrator httpwebwitch us a WebmasterWorld Top Contributor of All Time 10+ Year Member



 
Msg#: 4360695 posted 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

WebmasterWorld Administrator httpwebwitch us a WebmasterWorld Top Contributor of All Time 10+ Year Member



 
Msg#: 4360695 posted 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

WebmasterWorld Administrator brotherhood_of_lan us a WebmasterWorld Top Contributor of All Time 10+ Year Member Top Contributors Of The Month



 
Msg#: 4360695 posted 6:23 am on Sep 10, 2011 (gmt 0)

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

httpwebwitch

WebmasterWorld Administrator httpwebwitch us a WebmasterWorld Top Contributor of All Time 10+ Year Member



 
Msg#: 4360695 posted 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

WebmasterWorld Administrator brotherhood_of_lan us a WebmasterWorld Top Contributor of All Time 10+ Year Member Top Contributors Of The Month



 
Msg#: 4360695 posted 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

WebmasterWorld Administrator httpwebwitch us a WebmasterWorld Top Contributor of All Time 10+ Year Member



 
Msg#: 4360695 posted 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