shuffling a list of blocks

brine123 · 2017-07-26 00:17:20

https://pastebin.com/Ys8FB7iA
Is there a way to use that to shuffle blocks that are placed by bots?
Like http://prntscr.com/g0a9nh

Vinyl Melody · 2017-07-26 00:40:21

Randomize the list.

Random rand = new Random();
var shuffledBlocks = blocks.OrderBy(x => (rand.Next())).ToList();

or turn it into a void

public static List<T> RandomizeList<T>(List<T> list) {
    Random rand = new Random();
    return list.OrderBy(x => (rand.Next())).ToList();
}

and then just do

block = RandomizeList(block); // Randomizes the list

p.s. I have this code on my helper class

hummerz5

Latif · 2017-07-26 00:51:25

I just checked Capasha's code and it seems perfect so why don't you just use that?

Also, this isn't really EE related so you could also search this in google.

I wanted to post some code, but it was probably going to look like Medoly's one

XxAtillaxX · 2017-07-26 02:16:33

Vinyl Melody wrote:

public static List<T> RandomizeList<T>(List<T> list) {
Random rand = new Random();
return list.OrderBy(x => (rand.Next())).ToList();
}

That's one of the worst possible things you can do.

You're instantiating a new Random() every time, which means every list will be shuffled exactly the same.
If you look at the source code of Random, there's a seed built in by default, which you can override yourself in the constructor.

It's much more reliable and sensible to use a simple Fisher-Yates shuffle, rather than using the OrderBy method in Linq.
OrderBy uses a variant of the quick sort algorithm, which is O(N log(N)) compared to the Fisher-Yates shuffle which is O(N).

Swarth100

Tomahawk · 2017-07-26 02:29:37

Ok I was gonna write a long post about lists and shuffling but then I saw that Capasha's code has literally everything you need.

If you don't know how to loop through a list of blocks and send them then you're not ready to code a bot. Go do a tutorial.

Vinyl Melody

den3107 · 2017-07-26 02:45:15

I personally always enjoyed the following:

private static Random rng = new Random();  

// Just put a list of any type in here, don't worry about all the arrows and "T"s
public static List<T> Shuffle<T>(List<T> list)  
{  
    int n = list.Count;  
    while (n-- > 1)
    {
        int k = rng.Next(n + 1);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  

    return list;
}

I personally prefer to evade Linq because I find them challenging to read and write due to their nature of "one-liner"-nes (and stretching it over multiple lines generally doesn't help).
You also don't really know what's happening in the back. This makes it hard to optimize code containing Linq.

▼To prevent the "premature" optimization rant

Nonetheless, Linq would offer sweet one-liners and keeps your code from bloating and, if used correctly, can help here and there to evade some spaghettification.

EDIT: Didn't bother checking code given by OP earlier, turns out it's mostly the same code as mine... Well, guess I still got to talk about Linq tho c:

hummerz5, LukeM

LukeM · 2017-07-26 11:47:58

XxAtillaxX wrote:

Vinyl Melody wrote:
public static List<T> RandomizeList<T>(List<T> list) {
Random rand = new Random();
return list.OrderBy(x => (rand.Next())).ToList();
}
That's one of the worst possible things you can do.
You're instantiating a new Random() every time, which means every list will be shuffled exactly the same.
If you look at the source code of Random, there's a seed built in by default, which you can override yourself in the constructor.

Well... it wouldnt give the same order every time as long as youre not running them one after the other without any time between them because Random uses the system clock to determine a seed if one is not specified, but yes, it technically could, so you probably shouldnt do it

Edit: Also, why doesnt capashas code work for you, it just seems like all the answers are basically the same as that code, is the 'like' thing your current code? If so I would advise either using lists for storing your blocks to place, then you can just use one of the above methods to shuffle it.

Edit 2:

den3107 wrote:

I know EE bot sizes won't require any kind of optimization (unless written VERY poorly).
I also have barely any experience with Linq, so it'd probably take me quite some trouble to learn it (since I have a hard time reading it).
So why not stick to solutions I already have made and can just paste right in, and keep my future important code (hopefully) easier to optimize?
The most concerning problem for optimization Linq would give, is that you don't know how many Lists it's making in the background, how many actions it's performing on those lists and what kind of collection it's using anyway!
About ordering in general (so not this randomization example): it might also be relevant to choose a certain method to reach a higher average sorting time or lower space complexity (see "Big O notation").
As far as I know, you cannot change the sorting algorithm Linq uses (it probably uses quicksort, just like Java (for primitive types)).

I think its 'linear optimisation' that most people complain about. IMO if you can, its always better to get the 'big O value' down as low as possible, as thats what causes major problems later when you assume a list of size 1000 will only take 10x as long as a list of size 100, and it in fact takes 100 or 1000 times longer

den3107 · 2017-07-26 13:38:33

destroyer123 wrote:

Well... it wouldnt give the same order every time as long as youre not running them one after the other without any time between them because Random uses the system clock to determine a seed if one is not specified, but yes, it technically could, so you probably shouldnt do it

To give a bit more information:
So long the shuffle method is called every once in a while, yeah, it'll be random.
The reason why you generally still want to have your random declared as a field during initialization, is because with this way of programming, you are more prone to accidentally declare the random inside the loop (resulting in same values) instead of outside (resulting in different values, so long the random isn't initialized too quickly one after another).

Possible overhead could also be a reason why you want to declare it as a field (threading into the "premature optimization" region, so generally you can ignore this).
Yes, a field would result in more "permanent" memory usage, but initializing it over and over would result in higher CPU load. It's all down to what you have most of, compared to the rest of the application.

Vinyl Melody · 2017-07-26 13:56:47

XxAtillaxX wrote:

Vinyl Melody wrote:
public static List<T> RandomizeList<T>(List<T> list) {
Random rand = new Random();
return list.OrderBy(x => (rand.Next())).ToList();
}
That's one of the worst possible things you can do.
You're instantiating a new Random() every time, which means every list will be shuffled exactly the same.
If you look at the source code of Random, there's a seed built in by default, which you can override yourself in the constructor.
It's much more reliable and sensible to use a simple Fisher-Yates shuffle, rather than using the OrderBy method in Linq.
OrderBy uses a variant of the quick sort algorithm, which is O(N log(N)) compared to the Fisher-Yates shuffle which is O(N).

Random() pretty much does it for me so, *shrug*

Processor · 2017-07-26 14:21:50

Random actually relies on the system time for its seed so no,
it wont return the same order every time.

den3107 wrote:

private static Random rng = new Random();  
// Just put a list of any type in here, don't worry about all the arrows and "T"s
public static List<T> Shuffle<T>(List<T> list)  
{  
    int n = list.Count;  
    while (n-- > 1)
    {
        int k = rng.Next(n + 1);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  

    return list;
}

That's worse than creating a new random every time. The random class is not thread safe and so it's a very very very bad idea to make a static instance for it.

LukeM · 2017-07-26 14:36:51

Vinyl Melody wrote:

▼XxAtillaxX wrote:
Vinyl Melody wrote:
public static List<T> RandomizeList<T>(List<T> list) {
Random rand = new Random();
return list.OrderBy(x => (rand.Next())).ToList();
}
That's one of the worst possible things you can do.
You're instantiating a new Random() every time, which means every list will be shuffled exactly the same.
If you look at the source code of Random, there's a seed built in by default, which you can override yourself in the constructor.
It's much more reliable and sensible to use a simple Fisher-Yates shuffle, rather than using the OrderBy method in Linq.
OrderBy uses a variant of the quick sort algorithm, which is O(N log(N)) compared to the Fisher-Yates shuffle which is O(N).
Random() pretty much does it for me so, *shrug*

Its not a problem if you have some delay after you shuffle the list, but if, for example you had something like this, then it could cause problems:

list1 = some list
list2 = RandomizeList(list1);
list3 = RandomizeList(list1); // Would be exactly the same as list2

I guess this wouldnt be a problem with EE bots, as nobody would notice if blocks were placed in the same order two times in a row, but this could be a problem if you also used it for something else.

And about the big O notation things:
It doesnt matter with small lists, but if you used it for bigger ones, you could run in to problems, for example, if both methods shuffle a list of size 2 in 1 ms (ik it would be much faster, but this means easier numbers), when shuffling a list of size 1024, the O(n) method would take 512ms, while the O(nlogn) method would take around 5120 ms, which is 10x longer (scale this up to a whole EE world, and there could start to be problems)

Swarth100 · 2017-07-26 21:06:02

BUMP:

XxAtillaxX wrote:

You're instantiating a new Random() every time, which means every list will be shuffled exactly the same.
If you look at the source code of Random, there's a seed built in by default, which you can override yourself in the constructor.
It's much more reliable and sensible to use a simple Fisher-Yates shuffle, rather than using the OrderBy method in Linq.
OrderBy uses a variant of the quick sort algorithm, which is O(N log(N)) compared to the Fisher-Yates shuffle which is O(N).

I see no need to post any code whatsoever, as thorough, excellent, and unbiased shuffling algorithms (such as the afore mentioned Fisher-Yates) can be found with the most basic of google searches.

Bumping Attila's advice, just do not re-instantiate Random every single time

LukeM

John · 2017-07-26 21:38:45

I use the fisher yates method.

Official Everybody Edits Forums

#1 2017-07-26 00:17:20

shuffling a list of blocks

#2 2017-07-26 00:40:21, last edited by Vinyl Melody (2017-07-26 00:41:44)

Re: shuffling a list of blocks

#3 2017-07-26 00:51:25

Re: shuffling a list of blocks

#4 2017-07-26 02:16:33

Re: shuffling a list of blocks

#5 2017-07-26 02:29:37

Re: shuffling a list of blocks

#6 2017-07-26 02:45:15, last edited by den3107 (2017-07-26 02:47:42)

Re: shuffling a list of blocks

#7 2017-07-26 11:47:58, last edited by LukeM (2017-07-26 12:17:15)

Re: shuffling a list of blocks

#8 2017-07-26 13:38:33

Re: shuffling a list of blocks

#9 2017-07-26 13:56:47

Re: shuffling a list of blocks

#10 2017-07-26 14:21:50

Re: shuffling a list of blocks

#11 2017-07-26 14:36:51, last edited by LukeM (2017-07-26 14:37:43)

Re: shuffling a list of blocks

#12 2017-07-26 21:06:02, last edited by Swarth100 (2017-07-26 21:06:48)

Re: shuffling a list of blocks

#13 2017-07-26 21:38:45

Re: shuffling a list of blocks

Board footer