Pick a number of unique entries from a map/array or similar

ereinion

ereinion

Member
So I made this code-snippet in order to buff 5 random people every day, and I think it works as intended (at least it seemed to do so from todays test of it):
Code: 
void main() {
    boolean[int, string] peopleToUseTheSkillOn; int index; string who;
    peopleToUseTheSkillOn[0, "a"] = true;
    peopleToUseTheSkillOn[1, "b"] = true;
    peopleToUseTheSkillOn[2, "c"] = true;
    peopleToUseTheSkillOn[3, "d"] = true;
    peopleToUseTheSkillOn[4, "e"] = true;
    peopleToUseTheSkillOn[5, "f"] = true;
    peopleToUseTheSkillOn[6, "g"] = true;
    
    while (have_skill($skill[The Smile of Mr. A.]) && get_property("_smilesOfMrA") < 5 && count(peopleToUseTheSkillOn) >= 5) {
        repeat {
            index = random(count(peopleToUseTheSkillOn));
            foreach key in peopleToUseTheSkillOn[index] {
                who = key;
            }
        } until(peopleToUseTheSkillOn[index, who]);
        
        if (peopleToUseTheSkillOn[index, who]) {
            use_skill(1, $skill[The Smile of Mr. A.], who);
            peopleToUseTheSkillOn[index, who] = false;
        }
    }
}
However I find that it seems overly complex, and wonder if any of the more experienced coders here have any suggestions on how I can make the picking of the 5 random players more efficient. Any help will be much appreciated :)
 
Last edited:
Crowther

Crowther

Active member
ereinion said:
However I find that it seems overly complex, and wonder if any of the more experienced coders here have any suggestions on how I can make the picking of the 5 random players more efficient. Any help will be much appreciated :)
Click to expand...
Here you go:
Code: 
void main() {
    while (have_skill($skill[The Smile of Mr. A.]) && get_property("_smilesOfMrA") < 5) {
            use_skill(1, $skill[The Smile of Mr. A.], "Crowther");
        }
    }
}
I'm surprised you find your code too slow. Sure it doesn't scale well, but with such small lists who cares? Things like reservoir sampling exist for handling the very large lists. If you're regularly selecting more than half your list, you can do it the other way and select the ones you don't want to buff (picking 1 of 6 is faster than 5 of 6).
 
ereinion

ereinion

Member
Oh, I don't find it to be slow, but it kinda surprises me that there isn't a simpler way to do it. I was thinking of using an array instead, and then remove the entries as they were I guess I could have a look at reservoir sampling, but if it is not normally used for small lists I guess it is rather complex to implement? I'm also not certain how I'd go about removing entries from the map - if I want to access the entries by "index number", I'd have to find some way to update those after each entry removed (unless the entry removed was the one with the highest index number) after each removal. I suspect this would be more resource-intensive than my current implementation, as would most other solutions I can think of.

Anyway, thanks a lot for your reply :) I guess I'll be happy enough with having a working solution, and not worry too much about how it looks :)
 
Winterbay

Winterbay

Active member
Well you can always sort the map with some random seed and then always use the last 3 entries or so.
 
ereinion

ereinion

Member
But how do I make the function only access the last three entries? As far as I understood it from what I read on the wiki you can't access a map by index? Though I guess that'd be an option for an array... Or I could make a counter inside the loop I suppose...

Thanks for your input, you certainly gave me some food for thought :)
 
Winterbay

Winterbay

Active member
I've never been able to get my head around multi dimensional maps. I would've made a integer indexed record with two values instead but that's just me :)
 
ereinion

ereinion

Member
Heh, and I've never really worked with records :) Maybe it's time I did.

Anyway, from what I understand about maps, what I made was really a map of maps i.e. boolean[int, string] == boolean[string[int]]? Or would that be the other way round? :-D
 
Razorsoup

Razorsoup

Member
Question, would this work for what ereinion is trying to accomplish?

Code: 
void main() {
	string[int] peopleToUseTheSkillOn;
	peopleToUseTheSkillOn[0] = "a";
	peopleToUseTheSkillOn[1] = "b";
	peopleToUseTheSkillOn[2] = "c";
	peopleToUseTheSkillOn[3] = "d";
	peopleToUseTheSkillOn[4] = "e";
	peopleToUseTheSkillOn[5] = "f";
	peopleToUseTheSkillOn[6] = "g";
	
	sort peopleToUseTheSkillOn by random(1000000);
	
	while (have_skill($skill[The Smile of Mr. A.]) && get_property("_smilesOfMrA") < 5 && count(peopleToUseTheSkillOn) > get_property("_smilesOfMrA")) {
		use_skill(1, $skill[The Smile of Mr. A.], peopleToUseTheSkillOn[get_property("_smilesOfMrA").to_int()]);
	}
}

This is what I would have come up to try to do what ereinion is doing. I think this should sort the list of players randomly and then cast the buff on numbers 0-4 (the first five players in the list). I don't know how efficient it would be though, so any insight into that would also be appreciated.
 
ereinion

ereinion

Member
That does indeed work. I do feel a bit silly for not thinking about it earlier (I wasn't aware you could use all those methods on arrays as well) :) Thanks for your help!

Code: 
void main() {
    string[7] peopleToUseTheSkillOn;
    peopleToUseTheSkillOn[0] = "a";
    peopleToUseTheSkillOn[1] = "b";
    peopleToUseTheSkillOn[2] = "c";
    peopleToUseTheSkillOn[3] = "d";
    peopleToUseTheSkillOn[4] = "e";
    peopleToUseTheSkillOn[5] = "f";
    peopleToUseTheSkillOn[6] = "g";
    
    sort peopleToUseTheSkillOn by random(100000);
    
    while (have_skill($skill[The Smile of Mr. A.]) && get_property("_smilesOfMrA") < 5 && count(peopleToUseTheSkillOn) >= 5) {
        use_skill(1, $skill[The Smile of Mr. A.], peopleToUseTheSkillOn[get_property("_smilesOfMrA")]]);
    }
}
 
Last edited:
Razorsoup

Razorsoup

Member
ereinion said:
That does indeed work. I do feel a bit silly for not thinking about it earlier (I wasn't aware you could use all that methods on arrays as well) :) Thanks for your help!
Click to expand...

No problem. I'm just glad to have finally been helpful to somebody else instead of asking for help myself. It doesn't happen very often. :)
 
Crowther

Crowther

Active member
Razorsoup said:
sort peopleToUseTheSkillOn by random(1000000);
Click to expand...
You have to be careful sorting by a random function. I'm not 100% sure how ash evaluates this. I pretty sure it would be okay, but this is very similar to what Jick did to randomize bang potions and it wasn't properly random. The big difference is he passed a random comparison function, which won't work as expected.
 
ereinion

ereinion

Member
The sorting method in question is described towards the end of the description on aggregate.sort here: http://wiki.kolmafia.us/index.php?title=Data_Structures#Sort

I'm curious what you mean by it not being properly random though, do you mean random enough for most purposes or not very random at all? Cause as far as I can recall it is almost impossible to make something truly random? And can you remember where the sorting problem with the bang potions were discussed?
 
Bale

Bale

Minion
Jezebus! If you really want a greater simulation of randomness you don't have to wrack your brain too hard. Just do random( gametime_to_int() )
 
xKiv

xKiv

Active member
I think that what crowther is refering to is something else entirely.
There are two possible ways to interpet "sort array by f(x)".

1) use generic sort algorithm, give it a comparator that will call f(x) (twice) any time it wants to compare two values from the array. If f(x) is random(1000000), then you don't know how the randomized sort will work - you are certainly doing something that no sort algorithm expects (your values are changing during the sort operation), and your random values have effect on what comparisons will be done in the future, which has effect on how many random values will be generated and when they will be used ... it will be messy, and you will get "surprising" results, like certain permutations being much more likely to occur.

2) first generate an array of [index, f(x)] for the entire input array (calling f(x) exactly once for each index), then sort that, then use the result to reorganize your original array - this gets you what you probably expected, and seems to be what mafia does (in SortBy)

ETA:
ereinion said:
The sorting method in question is described towards the end of the description on aggregate.sort here: http://wiki.kolmafia.us/index.php?title=Data_Structures#Sort
Click to expand...

This wiki article even spells it out: "It is evaluated once for every entry in the aggregate,"
 
Last edited:
Crowther

Crowther

Active member
Yeah, that's what I was talking about. Like I said, I figured (without bothering to check the wiki to be sure) that the above ASH code would work. However, it's good to keep in mind that this "trick" can give something less than random if used improperly like Jick did. I'd forgotten the tower had the same bugs as bang potions.
 
lostcalpolydude

lostcalpolydude

Developer
Staff member
The gallery still has that bug, but by now I expect it's considered a feature (and people would complain if it was made properly random).
 
You must log in or register to reply here.
Top