ASH Map error

[Tpj_4000]

For some reason, mafia is destroying the original map.

int[int] randomizeList(int[int] input, boolean readout){

	int elementCount = count(input);
	int randNum;
	int[int] rndList;

	if(readout){
		print("randomize function:","red");
		foreach i in input{
			print("input["+i+"]: "+input[i],"red");
		}
	}


	if(elementCount<2){
		rndList[0] = input[0];
		return rndList;
	}
	if(elementCount==2){
		randNum = random(2);
		rndList[0] = input[randNum];
		rndList[1] = input[1-randNum];
		return rndList;
	}

	### mafia enforces range min of 2, so need (elementCount-1)-1 = elementCount-2
	for i from 0 to (elementCount-2){
		randNum = random(elementCount-i);
		rndList[i] = input[randNum];

		### "remove" input[randNum] from rndList
		for j from randNum to (elementCount-i-1){
			input[j]=input[j+1];
		}
	}
	rndList[elementCount-1]=input[0];


	return rndList;
}

void main(){

	int[int] originalList;
	int[int] randomizedList;

	originalList[0] = 1000;
	originalList[1] = 1001;
	originalList[2] = 1002;
	originalList[3] = 1003;
	originalList[4] = 1004;
	originalList[5] = 1005;
	originalList[6] = 1006;

	cli_execute("cls");

	print("Original List:","blue");
	foreach i in originalList{
		print("originalList["+i+"]: "+originalList[i],"green");
	}

	print("#############");
	randomizedList = randomizeList(originalList,false);

	print("Randomized List 1:","blue");
	foreach i in randomizedList{
		print("randomizedList["+i+"]: "+randomizedList[i],"green");
	}

	print("Original List","blue");
	foreach i in originalList{
		print("originalList["+i+"]: "+originalList[i],"green");
	}


	print("############");
	randomizedList = randomizeList(originalList,true);

	print("Randomized List 2:","blue");
	foreach i in randomizedList{
		print("randomizedList["+i+"]: "+randomizedList[i],"green");
	}
	print(" ");
}

... which results as:

Original List:
originalList[0]: 1000
originalList[1]: 1001
originalList[2]: 1002
originalList[3]: 1003
originalList[4]: 1004
originalList[5]: 1005
originalList[6]: 1006
#############
Randomized List 1:
randomizedList[0]: 1004
randomizedList[1]: 1005
randomizedList[2]: 1000
randomizedList[3]: 1001
randomizedList[4]: 1002
randomizedList[5]: 1006
randomizedList[6]: 1003
Original List
originalList[0]: 1000 <--- (varies)
originalList[1]: 0
originalList[2]: 0
originalList[3]: 0
originalList[4]: 0
originalList[5]: 0
originalList[6]: 0
############
randomize function:
input[0]: 1000 <--- (varies)
input[1]: 0
input[2]: 0
input[3]: 0
input[4]: 0
input[5]: 0
input[6]: 0
Randomized List 2:
randomizedList[0]: 0
randomizedList[1]: 0
randomizedList[2]: 1000 <--- (varies)
randomizedList[3]: 0
randomizedList[4]: 0
randomizedList[5]: 0
randomizedList[6]: 0



So, the real problem is that 2 successive calls of 'randomize' destroys the original list in the main() function.

randomizedList = randomizeList(originalList,true);
randomizedList = randomizeList(originalList,true);

Can anyone help/explain?

 

[Theraze]

Believe you're... changing the original input here:

		### "remove" input[randNum] from rndList
		for j from randNum to (elementCount-i-1){
			input[j]=input[j+1];
		}

You're working with the original list and destroying it...

 

[Tpj_4000]

But if you notice, I don't ever 0 anything out. So, the fact that the original contains zeros means that can't be it (all it does is shuffle values around). I'm totally at a loss.

 

[Theraze]

With a bit more logging...

randomList[6]: 1002
Original List
originalList[0]: 1002
originalList[1]: 0

Also:

randomList[6]: 1000
Original List
originalList[0]: 1000
originalList[1]: 0

And:

randomList[6]: 1004
Original List
originalList[0]: 1004
originalList[1]: 0

You're wiping it out. The logging proves it... The "originalList[0]" is the "randomList[6]" in every case...

 

[Theraze]

So, here's a log using MY randomize function:

Original List:
originalList[0]: 1000
originalList[1]: 1001
originalList[2]: 1002
originalList[3]: 1003
originalList[4]: 1004
originalList[5]: 1005
originalList[6]: 1006
#############
Random List 1:
randomList[0]: 1005
randomList[1]: 1000
randomList[2]: 1003
randomList[3]: 1002
randomList[4]: 1001
randomList[5]: 1004
randomList[6]: 1006
Original List
originalList[0]: 1000
originalList[1]: 1001
originalList[2]: 1002
originalList[3]: 1003
originalList[4]: 1004
originalList[5]: 1005
originalList[6]: 1006
############
Random List 2:
randomList[0]: 1003
randomList[1]: 1005
randomList[2]: 1006
randomList[3]: 1001
randomList[4]: 1002
randomList[5]: 1000
randomList[6]: 1004

Entire code of track.ash:

int[int] randomizeList(int[int] input, boolean readout){

	int elementCount = count(input);
	int randNum;
	int[int] rndList;
        boolean[int] checked;

	if(readout){
		print("randomize function:","red");
		foreach i in input{
			print("input["+i+"]: "+input[i],"red");
		}
	}


	if(elementCount<2){
		return input;
	}

	### mafia enforces random range min of 2, so this takes anything with 2 or more elements
	for i from 0 to (elementCount - 1){
		randNum = random(elementCount);
		while (checked[randNum]) randNum = random(elementCount);
		rndList[i] = input[randNum];
		checked[randNum] = true;
	}
	return rndList;
}

void main(){

	int[int] originalList;
	int[int] randomList;

	originalList[0] = 1000;
	originalList[1] = 1001;
	originalList[2] = 1002;
	originalList[3] = 1003;
	originalList[4] = 1004;
	originalList[5] = 1005;
	originalList[6] = 1006;

	cli_execute("cls");

	print("Original List:","blue");
	foreach i in originalList{
		print("originalList["+i+"]: "+originalList[i],"green");
	}

	print("#############");
	randomList = randomizeList(originalList,false);

	print("Random List 1:","blue");
	foreach i in randomList{
		print("randomList["+i+"]: "+randomList[i],"green");
	}

	print("Original List","blue");
	foreach i in originalList{
		print("originalList["+i+"]: "+originalList[i],"green");
	}


	print("############");
	randomList = randomizeList(originalList,false);

	print("Random List 2:","blue");
	foreach i in randomList{
		print("randomList["+i+"]: "+randomList[i],"green");
	}
	print(" ");
}

Instead of changing my original input, I'm just marking it as already assigned...

I think your problem is thinking that, in ASH, your inputs are always safe. If you change things, we believe it's because you want to change them. If you HAVE to munge about with the original input, clone it first... or, y'know, use a boolean series to make sure you don't destroy your original.

Also, your comment is wrong... it's not that there's an enforced range minimum of 2, it's that you can't have a random number with less than 2 options. 1 option? 0 options? That's not random. As per this:

> ash random(1)

Random range must be at least 2 ()
Returned: void

> ash random(2)

Returned: 1

So you only needed to cancel out the elementcount < 2, not == 2. And it could be tightened up a bit as well... I'd suggest this:

	if(elementCount<2){
		return input;
	}

	### mafia enforces random range min of 2, so this takes anything with 2 or more elements
	for i from 0 to (elementCount - 1){

 

[Tpj_4000]

Also, your comment is wrong... it's not that there's an enforced range minimum of 2, it's that you can't have a random number with less than 2 options. 1 option? 0 options? That's not random. As per this:

You are correct that with less than two outcomes, philosophically speaking, there is no choice and hence no possibility of randomness. However, in the vein of good programming, I don't want my function to break because someone doesn't adhere to my philosophy. To my knowledge mafia aborts with a range < 2. So, I error check and fix things for a range less than 2. I also take care of the case of count == 2 because it is a simple toggle and much simpler than the loop I use for n outcomes and therefore quicker for that case.

I also want to point out, that my randomize function operates equivalent to pulling numbers out of a hat. It is sample without replace. Your function operates as a sample with replace and can, however unlikely, generate an infinite number of random numbers while never covering all the positions in the map.

while (checked[randNum]) randNum = random(elementCount);

I assume that java, like C++, passes a pointer to the map (array in C++) to the subfunction and does not pass the actual values through the stack. Modifying the map in the subfunction should therefore modify the values at the memory locations pointed to by the pointer that got passed in. If you look at my code, nowhere do I zero out any of the map values. All I do is make the value at map[idx] equal to the value at map[idx+1]. I stand by my original statement that the original map should never contain any zeros because I never set them as such and there is an error somewhere. It's like the pointer is getting hosed and/or a new map is getting created on top of the old one as soon as the subfunction modifies the original.

The logging proves it... The "originalList[0]" is the "randomList[6]" in every case...

Yes. Because of this line of code:

rndList[elementCount-1]=input[0];

But that still doesn't explain why the values in the rest of the map are 0.

 

[holatuwol]

But that still doesn't explain why the values in the rest of the map are 0.

That's because you're thinking of maps as arrays, so a coding mistake that would normally result in an index out of bounds exception doesn't happen. More explicitly:

input[j]=input[j+1];

What happens when 'j' is 6? You look at the value in input[7] which is not defined (and therefore zero). Thus, with your code, you set input[6] to zero. Eventually, you copy this zero that you put into input[6] all the way back to every other entry in the "input" map and effectively zero out everything.

 

[holatuwol]

Because it's vaguely relevant, the shuffling algorithm you're trying to implement is only O when the remove operation is O(1). The way you've implemented it, remove is O and therefore the algorithm winds up being O(n²). Personally, I'd use a simpler fake shuffle.

void shuffle( int[int] input )
{
	int count = count( input );

	if ( count < 2 )
	{
		return;
	}

	for i from 0 upto ( count - 1 )
	{
		int j = random( count );

		int tmp = input[i];
		input[i] = input[j];
		input[j] = tmp;
	}
}

Edit: But if you really want something that shuffles in O with the original algorithm you were trying to implement, you'd need to rethink how to implement the two partitions. This is an example where the partitions are implemented with O(1) swapping.

Edit 2: Moving comments here so you can compare it with the above. Elements 0 to i - 1 are the 'used' elements, and the elements i to count are the 'unused' elements. We randomly choose things that are in the 'unused' partition and move it into the next 'used' slot in order to implement the shuffle.

void shuffle( int[int] input )
{
	int count = count( input );

	if ( count < 2 )
	{
		return;
	}

	for i from 0 upto ( count - 2 )
	{
		int j = i + random( count - i );

		int tmp = input[i];
		input[i] = input[j];
		input[j] = tmp;
	}
}

 

[Tpj_4000]

What happens when 'j' is 6? You look at the value in input[7] which is not defined (and therefore zero). Thus, with your code, you set input[6] to zero. Eventually, you copy this zero that you put into input[6] all the way back to every other entry in the "input" map and effectively zero out everything.

'j' can never be 6. It can only be from 0 to 4. That is because of:

for i from 0 to (elementCount-2){

0 to (elementCount -1) just offests everything and treats it like a 0 offset array. 0 to (elementCount -2) ensures that map[j] = map[j+1] is always in bounds; which will never produce a 0 (unless the original input was zero, which it isn't). I think you maybe confused Theraze's code with mine.


In regards to your follow up post, I didn't fully digest it on the first skim (I'm at work) and will reply later when I get time.

 

[Winterbay]

This might help (some added printouts):

int[int] randomizeList(int[int] input, boolean readout){

	int elementCount = count(input);
	int randNum;
	int[int] rndList;

	if(readout){
		print("randomize function:","red");
		foreach i in input{
			print("input["+i+"]: "+input[i],"red");
		}
	}

	if(elementCount<2){
		rndList[0] = input[0];
		return rndList;
	}
	if(elementCount==2){
		randNum = random(2);
		rndList[0] = input[randNum];
		rndList[1] = input[1-randNum];
		return rndList;
	}
	print("elementCount: " + elementCount + ", input[1]: " + input[1]);
	### mafia enforces range min of 2, so need (elementCount-1)-1 = elementCount-2
	for i from 0 to (elementCount-2){
		randNum = random(elementCount-i);
		rndList[i] = input[randNum];

		### "remove" input[randNum] from rndList
		for j from randNum to (elementCount-i-1){
			print("randNum: " + randNum + ", input[j]: " + input[j] + ", input[j+1]: " + input[j+1] + ", j: " + j + ", i: " + i);
			input[j]=input[j+1];
		}
	}
	print("elementCount: " + elementCount + ", input[1]: " + input[1]);
	rndList[elementCount-1]=input[0];

	return rndList;
}

The printout in the foreach-loop gives:

elementCount: 7, input[1]: 1001
randNum: 3, input[j]: 1003, input[j+1]: 1004, j: 3, i: 0
randNum: 3, input[j]: 1004, input[j+1]: 1005, j: 4, i: 0
randNum: 3, input[j]: 1005, input[j+1]: 1006, j: 5, i: 0
randNum: 3, input[j]: 1006, input[j+1]: 0, j: 6, i: 0
randNum: 2, input[j]: 1002, input[j+1]: 1004, j: 2, i: 1
randNum: 2, input[j]: 1004, input[j+1]: 1005, j: 3, i: 1
randNum: 2, input[j]: 1005, input[j+1]: 1006, j: 4, i: 1
randNum: 2, input[j]: 1006, input[j+1]: 0, j: 5, i: 1
randNum: 2, input[j]: 1004, input[j+1]: 1005, j: 2, i: 2
randNum: 2, input[j]: 1005, input[j+1]: 1006, j: 3, i: 2
randNum: 2, input[j]: 1006, input[j+1]: 0, j: 4, i: 2
randNum: 3, input[j]: 1006, input[j+1]: 0, j: 3, i: 3
randNum: 0, input[j]: 1000, input[j+1]: 1001, j: 0, i: 4
randNum: 0, input[j]: 1001, input[j+1]: 1005, j: 1, i: 4
randNum: 0, input[j]: 1005, input[j+1]: 0, j: 2, i: 4
randNum: 0, input[j]: 1001, input[j+1]: 1005, j: 0, i: 5
randNum: 0, input[j]: 1005, input[j+1]: 0, j: 1, i: 5
elementCount: 7, input[1]: 0

As we can see when i = 0 we get to input[6] which gets set to input[6+1] which is 0 and so the list falls apart, i.e. the error is not in the first loop, but in the second where your elementCount - 2 won't save you...

 

[Tpj_4000]

Blah. That's what I get for skimming at work. As you point out, when:

elementCount=7 (for some reason in my last post I thought it was 6)
i=0

for j from randNum to (elementCount-i-1){

becomes:

for j from randNum to 6{

and input[j+1] is indeed out of bounds when j=6, and gives a 0.

The inside loop should be:

for j from randNum to (elementCount-2){

I have no idea why I left that i in there (perhaps before I changed it to a 0 indexed map and i started at 1?). I apologize, this whole time I was reading 'j' and looking at 'i' in my code.

That being said, the function then effectively fills the original map with the last value to be picked as that (with the exception of 1 instance of the second to last value to be picked [depending on the very last random number generated]) gets shuffled the most. So, to the original point by Theraze, a copy of the input map should be made if I am going to change it and I want to use it again. I got that, I just didn't know where the 0's where coming from.

Thanks for the help

 

[Tpj_4000]

I caught another situation where an out of bounds was introduced. Below is the fixed version, for anyone interested. I realize now, the (elementCount-i-1) was supposed to be in my random number generation, not the 'j' loop [facepalm].

int[int] randomizeList(int[int] masterInput){

	int[int] input;

	foreach i in masterInput{
		input[i] = masterInput[i];
	}

	int elementCount = count(input);
	int randNum;
	int[int] rndList;

	if(elementCount<2){
		rndList[0] = input[0];
		return rndList;
	}
	if(elementCount==2){
		randNum = random(2);
		rndList[0] = input[randNum];
		rndList[1] = input[1-randNum];
		return rndList;
	}

	for i from 0 to (elementCount-3){
		randNum = random(elementCount-i-1);
		rndList[i] = input[randNum];

		### "remove" input[randNum] from input
		for j from randNum to (elementCount-2){
			input[j]=input[j+1];
		}
	}
	rndList[elementCount-1]=input[0];

//	foreach k in rndList
//		print(rndList[k]);

        clear(input);
	return rndList;
}

 

[Tpj_4000]

Sped it up by changing:

for j from randNum to (elementCount-2){

to:

for j from randNum to (elementCount-2-i){

So, the final code is:

int[int] randomizeList(int[int] masterInput){

	int[int] input;

	foreach i in masterInput{
		input[i] = masterInput[i];
	}

	int elementCount = count(input);
	int randNum;
	int[int] rndList;

	if(elementCount<2){
		rndList[0] = input[0];
		return rndList;
	}
	if(elementCount==2){
		randNum = random(2);
		rndList[0] = input[randNum];
		rndList[1] = input[1-randNum];
		return rndList;
	}

	for i from 0 to (elementCount-3){
		randNum = random(elementCount-i-1);
		rndList[i] = input[randNum];

		### "remove" input[randNum] from input
		for j from randNum to (elementCount-2-i){
			input[j]=input[j+1];
		}
	}
	rndList[elementCount-1]=input[0];

//	foreach k in rndList
//		print(rndList[k]);

        clear(input);
	return rndList;
}

 

[holatuwol]

In regards to your follow up post, I didn't fully digest it on the first skim (I'm at work) and will reply later when I get time.

Ah, I was saying that your inner loop with the 'j' counter is slow because of how you shift the elements left. In simpler terms, if I threw the list of all 5600 items in the game at your shuffler, on average, the nested loop implementation would do something like 8 million shift operations (15 million if you were really unlucky and you got nothing but zeros from the random number generator). And it gets much nastier the bigger the list is.

To address that, I gave an alternative implementation for the 'remove the number from the available numbers to choose from' operation that works by partitioning. Here's a visual to help understand what it's doing:

[ | 1 2 3 4 5 ] => [ 3 | 2 1 4 5 ] => [ 3 2 | 1 4 5 ] => [ 3 2 5 | 4 1 ] => [ 3 2 5 1 | 4 ]

Think about choosing a random number from the right of the vertical bar. You then slide the vertical bar right, put the randomly chosen number into the spot that the vertical bar just slid by, and put the number that used to be in that spot into the spot where the randomly chosen number was. You've now "removed" the element from the list of available options in one swap instead of however many shifts you'd have needed to do the same.

In effect, you use the head end of the list as the 'randomized list so far' and the tail end of the list as the 'stuff still available to choose from'. When there's only one number left, well, that's the only place it can go.

If you do it that way, you don't have to keep shifting the 'unchosen numbers' over. As a result of not having to shift, if I threw the same list of 5600 items in the game at this shuffler the partitioning strategy would do 5600 swap operations. So in the thousands of operations instead of millions of operations.

 

[Tpj_4000]

Ok, work week over and time to sit and think straight:


After my last post I found another error, which is now fixed:

void randomizeList(int[int] input){

	int elementCount = count(input);
	int randNum;
	int[int] tmpList;

	if(elementCount<2){
		return;
	}

	foreach i in input{
		tmpList[i] = input[i];
	}

	if(elementCount>2){
		for i from 0 to (elementCount-3){
			randNum = random(elementCount-i-1);
			input[i] = tmpList[randNum];

			### "remove" tmpList[randNum] from tmpList
			for j from randNum to (elementCount-i-2){
				tmpList[j] = tmpList[j+1];
			}
		}
	}
	randNum = random(2);
	input[elementCount-2] = tmpList[randNum];
	input[elementCount-1] = tmpList[1-randNum];

	clear(tmpList);
	return;
}

holatuwol:

For the function I created, the total number of moves is: View attachment 6003

which results in O(.5N^2 +.5N):
View attachment 6004


After going through your randomizing function, I think that is very clever. I had never seen that before. The 3 moves per element will result in O(3N), which is dramatically quicker for large numbers of elements. Instead of shuffling all of my elements left, I could shuffle them all to the middle (lower offsets to the right and higher offsets to the left). That would results in halving the number of moves, however, O(.25N^2 + .25N) is still greater than O(3N). Not only that, but your method is cleaner.