Random Number and Array type tracking.

Hi All

I am trying to add an array type function to a random number generator.

Basically, I have written a script that secretly issues a random number to whomever touches the object (1-50).

However, I want the script to do a number of additional things:

1. remove numbers from an array once issued (so that they aren't issued repeatedly).
2. allow for numbers to be re-added to the array (given back to the object)
3. allow a report of all numbers to be issued.

The script will eventually be modified to give a finite number of objects to a group, in case you are wondering.

I'd appreciate any help, as I hit a wall finding any advice on array type tricks.

C

list llDeleteSubList(list src, integer start, integer end)

src = llDeleteSubList(src, 1, 1);

There are no arrays in LSL, only lists.

I wouldn't use a list for this. I'd use two 32 bit integers with bit logic. That may require also keeping a count of the number of unused numbers so that you can index without resampling over and over again, but I'd be willing to bet that's a lot less costly than tons of list operations. You could even use a list of integers if you don't want to hardcode the 1-50 range, but it's still a lot less wasteful to use all those bit positions.

Here's a generic example, that can go all the way from 1 to MAX_NUM (actually it uses 0 to MAX_NUM-1, but you can easily add one for the user). (This hasn't yet been compiled, so it may require some minor syntax fixes.)

integer MAX_NUM = 50;
integer BLOCK_SIZE = 32; // Must be <= size of int (32)

list blocks = [];
integer nBlocks = 0;
integer nAllocatedNums = 0;

initAllocation()
{
   blocks = [];
   nBlocks = (MAX_NUM+BLOCK_SIZE-1)/BLOCK_SIZE;

   integer blocksToAlloc = nBlocks;
   while (blocksToAlloc > 0)
   {
      blocks = (blocks=[])+blocks+[ 0 ];
      --blocksToAlloc;
   }

   nAllocatedNums = 0;
}

integer isAllocated(integer n)
{
   if (n < 0 || n >= MAX_NUM)
   {
      return TRUE;
   }

   integer index = n/BLOCK_SIZE;
   integer mask = 1<<(n%BLOCK_SIZE);

   integer block = llList2Integer(blocks, index);
   return (block & mask) != 0;
}

setAllocated(integer n, integer isAllocated)
{
   if (n < 0 || n >= MAX_NUM)
   {
      return;
   }

   integer index = n/BLOCK_SIZE;
   integer mask = 1<<(n%BLOCK_SIZE);

   integer block = llList2Integer(blocks, index);
   if (isAllocated && !(block & mask))
   {
      blocks = llListReplaceList(blocks, [ (block | mask) ], index);
      ++nAllocatedNums;
   } else if (!isAllocated && (block & mask))
   {
      blocks = llListReplaceList(blocks, [ (block & ~mask) ], index);
      --nAllocatedNums;
   }
}

// Returns a negative value if there are no numbers left
integer allocateRandomNum()
{
   if (nAllocatedNums >= MAX_NUM)
   {
      return -1;
   }

   integer num = 0;
   integer index = 0;
   integer mask = 1;
   integer block = llList2Integer(blocks, index);

   integer which = (integer)llFrand(MAX_NUM-nAllocatedNums);
   while (num < MAX_NUM)
   {
      if (block & mask)
      {
         ++num;

	 integer newIndex = num/BLOCK_SIZE;
	 if (newIndex != index)
	 {
	    index = newIndex;
	    mask = 1;
	    block = llList2Integer(blocks, index);
	 } else
	 {
	    mask = 1<<(mum%BLOCK_SIZE);
	 }
      } else if (which > 0)
      {
         --which;
      } else
      {
         blocks = llListReplaceList(blocks, [ (block | mask) ], index);
         ++nAllocatedNums;

         return num;
      }
   }

   return -1;
}

I'm not sure that allocateRandomNum is right. It doesn't seem to really do anything with the random number put into 'which' except loop until it's been decremented below zero.

If I'm understanding your intent, the idea is that if a number has already been allocated, then the next available number will be used. Won't this break the uniform distribution? For example, suppose you're allocating random numbers between 0 and 5, and the (integer)llFrand call results in 2, so you mark off that bit. The next time through, if llFrand results in either a 2 or a 3, you'll select 3 (since 2 has been taken), thus giving 3 twice the probability of being chosen over any other number.

It chooses the nth unallocated number and iterates to find it, with n being random. O(N), true, but with mostly integer arithmetic rather than list operations, and also WORST case O(N), rather than becoming expensive as the number of unallocated numbers shrinks--which is what iterated random selection does. There are some things that could be done to make it more efficient, but this is a simple enough solution, and will more than likely run in adequate time for the application.

This code supports 32 possible random numbers, it returns 1 to 32. If you want fewer then that, set usable to less then that. Additionally if it runs out of numbers and you try to take an additional number it will return zero.

integer available = -1;
integer usable = 32;

integer GiveRandom()
{
    if(!usable) return 0;
    integer index = (integer)llFrand(usable--);
    integer t = available; 
    if(index) do t = t & (t - 1); while(--index);
    available = available ^ (t = (t & -t));
    integer c = llCeil(llLog(t) / 0.69314718055994530941723212145818);
    return c + (((1 << c) - t) <= 0) << (5 * (t < 0));
}

TakeBack(integer a)
{
    ++usable;
    available = available | (1 << (a - 1));
}

Here's the List version. It's not as fast, eloquent or memory efficient as Strife's solution, but if you're used to thinking of things in terms of arrays then you might find it easier to follow:

list numberCache; // List of numbers
integer unallocatedCount; // Count of numbers still to be allocated
integer j; // Misc. working integer

init()
{
 // Create a Randomized list of numbers
 unallocatedCount = 50;
 for (j=1; j<= unallocatedCount;++j)
 {
    numberCache = [] + llListInsertList(numberCache,(list) j,j);    
 } 
 numberCache = llListRandomize(numberCache,1);
}

integer getNextNumber()
{
    // Pick the next entry and then remove it from the list
    if (unallocatedCount == 0) return -1; 
    
        j = llList2Integer(numberCache,0);
        numberCache = llDeleteSubList(numberCache,0,0);
        --unallocatedCount;
        return j; 
    
}

returnNumber(integer returned)
{
    // Add the number back onto the end of the list and Randomize
    numberCache = llListRandomize(llListInsertList(numberCache,(list) returned,unallocatedCount),1);
    ++unallocatedCount;
}

string reportUnusedNumbers()
{
 // Report the numbers still within the list
return llDumpList2String(llListSort(numberCache,1,TRUE),",");    
}

Thanks all, they were all very helpful, I will try both of the last two.. I am more familiar with arrays, but don't mind trying to stretch a little.

I really like the list version as it seems easier for me to read, will report my successes or failures when I run it.

You guys rock..!

I have to admit, I had fun writing my clever bit of code. Unless you enjoy a steep learning curve, stay away from clever code.

I'd say run with the list version, it will do you well. Though you should replace:
numberCache = [] + llListInsertList(numberCache,(list) j,j);
with:
numberCache = (numberCache = (list)j) + numberCache;

It will run faster (LSL executes right to left, which is why the above works).