Official Everybody Edits Forums

Do you think I could just leave this part blank and it'd be okay? We're just going to replace the whole thing with a header image anyway, right?

You are not logged in.

#1 2017-12-17 05:51:14

HeyNK
Member
Joined: 2017-04-07
Posts: 1,318

The Vending Machine Problem

Alternate title: Random choice without replacement.

Hidden text

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

Offline

#2 2017-12-17 05:56:39, last edited by Slabdrill (2017-12-17 05:57:09)

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

Offline

#3 2017-12-17 06:11:05, last edited by HeyNK (2017-12-17 06:13:44)

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] !

Offline

#4 2017-12-17 06:18:05

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

Offline

#5 2017-12-17 06:20:38

HeyNK
Member
Joined: 2017-04-07
Posts: 1,318

Re: The Vending Machine Problem

but can you do better then n! size?

Offline

#6 2017-12-17 06:33:50, last edited by Slabdrill (2017-12-17 06:34:31)

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...

AufnK7p.png
(yes i made two)


suddenly random sig change

Offline

Wooted by:

#7 2017-12-17 06:46:47, last edited by Vinyl Melody (2017-12-17 06:49:48)

Vinyl Melody
Formerly BananaMilkShake
Joined: 2016-06-19
Posts: 616

Re: The Vending Machine Problem

Here's my attempt

G9XiLFK.png

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


cb0de83627.png
Thanks to: Ernesdo (Current Avatar), Zoey2070 (Signature)

Very inactive, maybe in the future, idk.

Offline

#8 2017-12-17 11:55:27, last edited by LukeM (2017-12-17 13:44:50)

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

Offline

#9 2017-12-17 17:36:47

HeyNK
Member
Joined: 2017-04-07
Posts: 1,318

Re: The Vending Machine Problem

yeah its easy to use code //forums.everybodyedits.com/img/smilies/tongue but can you use ee-block-code?

Offline

#10 2017-12-17 19:17:15, last edited by Slabdrill (2017-12-17 19:27:37)

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 //forums.everybodyedits.com/img/smilies/tongue

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

Offline

#11 2017-12-17 22:34:43, last edited by LukeM (2017-12-18 00:22:08)

LukeM
Member
From: England
Joined: 2016-06-03
Posts: 3,009
Website

Re: The Vending Machine Problem

Slabdrill wrote:

luke pls get your bot up //forums.everybodyedits.com/img/smilies/tongue

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

Offline

#12 2017-12-19 17:56:26, last edited by LukeM (2017-12-19 18:06:07)

LukeM
Member
From: England
Joined: 2016-06-03
Posts: 3,009
Website

Re: The Vending Machine Problem

Sort of finished my vending machine thing //forums.everybodyedits.com/img/smilies/big_smile:
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)

Offline

#13 2017-12-20 04:39:37

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!

Offline

Wooted by:
HeyNK1513741177686855

Board footer

Powered by FluxBB

[ Started around 1711695695.017 - Generated in 0.070 seconds, 15 queries executed - Memory usage: 1.53 MiB (Peak: 1.7 MiB) ]