Organize array in certain way (roulette wheel items)

Question

I'm struggling with (probably simple) array shuffling/generating algorithm.

I'm creating simple backend (PHP/MySQL) for a roulette wheel game (JS/HTML). The roulette doesn't have numeric values as usual instead there are 4 prizes user can win, distributed within 12 segments of a roulette wheel.

I need an array like this:

// Note that PRIZE4 is listed only once as it is valuable prize.
// PRIZE3 is less valuable so it is listed twice, etc.
// Prizes are skipping each other so you should never see two identic prizes next each other.
var items = [PRIZE1, PRIZE2, PRIZE1, PRIZE2, PRIZE1, PRIZE2, PRIZE1, PRIZE2, PRIZE1, PRIZE3, PRIZE4, PRIZE3];

And I have prizes in a SQL table like this:

+----+------------+--------------+
| id | name       | giveaway_cap |
+----+------------+--------------+
|  1 | PRIZE1     |          255 |
|  2 | PRIZE2     |          300 |
|  3 | PRIZE3     |           30 |
|  4 | PRIZE4     |           15 |
+----+------------+--------------+
4 rows in set (0.00 sec)

Column giveaway_cap determines how many of each prize can be won (I'm storing these counts in different table) but could be used as weight of each prize.

I need some algorithm (preferably PHP) which will generate an array as described above based on this table.

Thanks.

Answer 1

I found this really nice algorithm searching on SO. It generates random numbers based on weight. Using it, one approach to your problem could be as follows:

// This is the function that generates random numbers based on weigth.
function getRandomWeightedElement(array $weightedValues) {
    $rand = mt_rand(1, (int) array_sum($weightedValues));
    foreach ($weightedValues as $key => $value) {
        $rand -= $value;
        if ($rand <= 0) {
            return $key;
        }
    }
}

$items = [ "PRIZE1" => 255, "PRIZE2" => 300, "PRIZE3" => 30, "PRIZE4" => 15];// Array of available prizes. It can be retrieved from the DB.
$total = (int) array_sum($items);// Total. I use it to work out the weight.
$items_w = [ "PRIZE1" => (255 / $total) * 1000, "PRIZE2" => (300 / $total) * 1000, "PRIZE3" => (30 / $total) * 1000, "PRIZE4" => (15 / $total) * 1000];// find out the weight somehow. I just divide number of available items by the total.
$res = [];
$previous = NULL;
while ( count(array_diff(array_keys($items), $res))) {// Loop until the result has all available prizes.
    $res = [];
    for ($i = 0; $i < 12; $i++) {
        while ($previous == ($new = getRandomWeightedElement($items_w))) {}// Two consecutive prizes of the same type aren't allowed.
        $res[] = $new;
        $previous = $new;
    }
}

echo implode(',', $res);

It's just a solution, I'm sure there are multiple ways of solving the problem.

Note: I'm using php 5.4 short array syntax, if your PHP version is lower than PHP 5.4, substitute [] by array(). Also have in mind that there can be problems in certain situations such as there's only one type of prize left or if it's impossible to create an array of prizes without two consecutive prizes being the same. You'd have to control those situations anyhow.

Hope it helps.

Answer 2

<?php
$connect=mysqli_connect("localhost","my_user","my_password","my_db");

$sql="SELECT id,name,giveaway_cap FROM table";
$result=mysqli_query($connect,$sql);

$prizes = array();
while($row=mysqli_fetch_array($result)) //iterate 4 times on caps != to 0
{
$count = $row['giveaway_cap'];
    if($count != '0')
    {
    $prizename = $row['name'];
    $prizes[$prizename]=$count;
    }
}

$prizewheel = array();
foreach ($prizes as $prize=>$value) // iterate 600 times if caps !=0
{
$prizewheel = array_merge($prizewheel, array_fill(0, $value, $prize));
}

$finalprize=array();

$f = 0;
while($f < 12) //iterate 12 times is # of caps >= 12,final array
{
$prizename = $prizewheel[array_rand($prizewheel)];
$finalprize[] = $prizename;
$f++;
}
?>

Answer 3

You could generate a random array like this:

$rows = array(
    array(
        'id' => 1,
        'name' => 'PRIZE1',
        'giveaway_cap' => 255,
    ),
    array(
        'id' => 2,
        'name' => 'PRIZE2',
        'giveaway_cap' => 300,
    ),
    array(
        'id' => 3,
        'name' => 'PRIZE3',
        'giveaway_cap' => 30,
    ),
    array(
        'id' => 4,
        'name' => 'PRIZE4',
        'giveaway_cap' => 15,
    ),
);

$output = array();

foreach ($rows as $row) {
    for ($i = 0; $i < $row['giveaway_cap']; $i++) {
        $output[] = $row['name'];
    }
}

shuffle($output);

//to get the next prize
$nextPrizeKey = array_rand($output);
$nextPrize = $output[$nextPrizeKey];

//remove the won prize
unset($output[$nextPrizeKey]);

What this does is creates a separate element in the array for each of the prizes giveaway_caps. Then as prizes are won you reduce the number of the giveaway_cap and this will reduce the chance that a user will hit that prize again.

If you wanted the array to be static you could save it after the initial generation, either in a database or caching (APC, Memcahche). Then you would just remove each entry that the users land on until there are none left. You could get the next prize with array_rand and then remove the key from the array.

I hope this helps.

Mic