Official Everybody Edits Forums

HeyNK

Member

Joined: 2017-04-07

Posts: 1,318

The Vending Machine Problem

Alternate title: Random choice without replacement.

▼Hidden text

This is a vending machine of n = 4, there are 4 items in it. When you go in, you get a random prize. After you get the prize, it takes you out.

However, there is a problem with this vending machine. You can get the same prize twice and that leads to disapointment.

Here is a vending machine that solves this problem.

▼Hidden text

However, there is another problem with this new vending machine.

▼Hidden text

If you are randomly assigned to get the blue coin in slot 3, you will get the coin in slot 2 instead. This ruins the equal chance to get each item, as that item now has chance 2/4 instead of the desired 1/3. So let's try another desing.

▼Hidden text

This vending machine solvs that problem, because now if an already-picked item is chosen, it is re-rolled until an OK item is chosen.

However there is another problem.

This vending machine is only reasonable for low items inside. For greater numbers of items, it is not OK to use such a design, as rerolling will take a very long time.

(It is also worth noting that it is trivially easy to prevent an infinite-rerolling scenario by putting in a gate to check right after the entry portal.)

Is there any elegant solution to this problem for large n (number of items in the machine)?

It is also obviously not feasible to build a random choice for (n, n-1, n-2 ... 2) different items as items get taken out due to space constraints., so what might we be able to do to make a large vending machine eficently for large n?

Can you design the best vending machine that works for large n?

Slabdrill

Formerly 12345678908642

From: canada

Joined: 2015-08-15

Posts: 3,402

Website

Re: The Vending Machine Problem

does it have to be equal distribution for the entire time

bc otherwise im not sure what a good way would be

---

suddenly random sig change

HeyNK

Member

Joined: 2017-04-07

Posts: 1,318

Re: The Vending Machine Problem

equal distribution the whole time! Chance to get each remaining item is always 1 in [items remaining] !

Slabdrill

Formerly 12345678908642

From: canada

Joined: 2015-08-15

Posts: 3,402

Website

Re: The Vending Machine Problem

Is there any elegant solution to this problem for large n (number of items in the machine)?

no; if you need equal chances for each, you NEED the continuous random switching.

---

suddenly random sig change

HeyNK

Member

Joined: 2017-04-07

Posts: 1,318

Re: The Vending Machine Problem

but can you do better then n! size?

Slabdrill

Formerly 12345678908642

From: canada

Joined: 2015-08-15

Posts: 3,402

Website

Re: The Vending Machine Problem

getting O(n) for both time (or O(n log n) cumulative time) (average) and size is easy enough though...

(yes i made two)

---

suddenly random sig change

Vinyl Melody

Formerly BananaMilkShake

Joined: 2016-06-19

Posts: 616

Re: The Vending Machine Problem

Here's my attempt

World

Edit: Since I did a boost before letting the player in the machine, the gap between the portal and the gravity block could be removed.
Edit 2: nvm slabdrill already did it lol

---

Thanks to: Ernesdo (Current Avatar), Zoey2070 (Signature)

Very inactive, maybe in the future, idk.

LukeM

Member

From: England

Joined: 2016-06-03

Posts: 3,009

Website

Re: The Vending Machine Problem

I guess if you can do it in real life programming then you can do it in EE, maybe by switching the selected slot with the last slot that hasnt been opened so all filled slots are grouped together, and using a lookup table to get the rewards from the 'reward id', althought this is massively overcomplicating it...

Might try to do this later, althought it probably would never be worth it unless you had thousands of rewards

Edit: I think using this technique would mean you could do it in O(log n) time, but with a massive amount of overhead

Edit 2: Here is an algorithm for how to do it that should be fully implementable in EE which I think is O(log n):

items <- array of items in vending machine
n <- no of items - 1
slots <- array of numbers 0 to n

To get item:
	item <- remove last item from slots
	selected <- false
	while not selected:
		i <- random number of the same number of bits as is needed to store n
		if i = n:
			selected <- true
		else if i < n:
			switch item and i in slots
			selected <- true
	n <- n - 1
	return item in items

HeyNK

Member

Joined: 2017-04-07

Posts: 1,318

Re: The Vending Machine Problem

yeah its easy to use code but can you use ee-block-code?

Slabdrill

Formerly 12345678908642

From: canada

Joined: 2015-08-15

Posts: 3,402

Website

Re: The Vending Machine Problem

I'm creating one that's should be O(log n) time and smaller than lukes (cant guarantee faster though) and more switch ID-friendly (~3n + 2*log2(n) as opposed to ~(n+3)log2(n))

thanks to muffin for idea, luke pls get your bot up

i guess the big thing is that my idea is O(n) worst-case but i think its O(log n) average-case so i should be fine

---

suddenly random sig change

LukeM

Member

From: England

Joined: 2016-06-03

Posts: 3,009

Website

Re: The Vending Machine Problem

luke pls get your bot up

Sorry, BT man was in fixing my phone line, should be back up now

Edit: Seems it wasnt that... I think it was something I updated causing it to crash whenever I closed the console, fixed now

LukeM

Member

From: England

Joined: 2016-06-03

Posts: 3,009

Website

Re: The Vending Machine Problem

Sort of finished my vending machine thing :
PWRG9TzKGNcEI

It seems that the resetters occasionally dont work, and im not sure why, so ill fix this when I know how to...

And this solutions complexity is:
O(log n) in time
O(n log n) in switches
O(n) in portals

It fills probably 2/3 of a large world, and contains 32 items (coins)
It works by using a second table of item ids, which means you can basically move around the items in a list, this means that rather than leaving gaps when you take an item, you can keep it so that all remaining items are at the start of the list, and all used items are at the end. This means that you can do the trial and error technique, but with the minimum number of bits to be able to select every item, which means there is always a chance of >50% of picking a new item, so you rarely get rerolls, (and have an upper bound on the average number of rerolls, which is 2)

HeyNK

Member

Joined: 2017-04-07

Posts: 1,318

Re: The Vending Machine Problem

this is very happy and I like to see it! I appriecate your help in making cool stuff!