3

I have two arrays of objects (items) in the exact same format. Each item represents a wager, and each array represents one of two outcomes for that wager (ex: Team A vs Team B). Both arrays look like this to start with:

  {
    "_id": "55762b3de624f37d80d09b34",
    "value": 803,
    "owner": 923
  },
  {
    "_id": "55762b3dc73fad717a7173ed",
    "value": 1457,
    "owner": 897
  },
  ...

These arrays differ in length. Let's say array A has 1200 items and array B has 800 items with each item's value ranging from 4 to 5,000. In production each array will likely range from 1000-200,000 entries, so keep efficiency in mind. The goal is to take all the items in array B (lost wagers) and add them to array A (won wagers) so that the value of items in B are distributed evenly by sum of values grouped by user in A. So if you bet three items, you would get those items back plus any number of items from array B.

First I run through array A (winners) and handle the user grouping and summing. Array A is now Object A and looks like this:

  '997': // User ID
   { bet: 15090, // Summed value of all items wagered in the below array
     items: // Original item IDs from their wager
      [ '55762b3dd82338e9683eea9b',
        '55762b3dccd4800148eec868',
        '55762b3de495cbcd594ecc17',
        '55762b3daad995d207c506f0',
        '55762b3d2154c4c0e273fe94' ] },
  '998': 
   { bet: 5196,
     items: [ '55762b3da1e658e5cb37ede6', '55762b3d1fca60c0cdd21a2e' ] },
   ...

Then take the total value of each array and figure out the multiplier to use for each "bet" value (aka: calculate the odds). Using the same randomly generated data this works out to be: 

A Total Value: 2,439,112 (entire value of items bet on Team A)
B Total Value: 1,608,947 (entire value of items lost on Team B)
0.6596445755668456 value from B for each A

So, for instance, user 997's total bet of 15,090 would need to gain ~9,954 of value from array B. When the items from array B are used, they are removed and the _id field is added to the "items" array. Since the values are associated with individual items and not a divisible currency, they cannot be split in order to make perfect change. The values don't have to match up exactly, but should be relatively close. For example, if a user bets 100 and should gain 65.9, they can get items within the 62-68 range if needed. This also means that users who bet very little may end up getting nothing in return depending on the odds, since there is a minimum bet of 4. Ex: If you bet 4, your winnings would be 2.63, but the lowest item value to distribute is 4.

What type of algorithm would be most appropriate for this kind of task? It sounds like something straight out of a textbook, but I have no idea where to start my search.

All this data will eventually be in mongodb, so mongo-specific functions are welcomed as well!

Improve this question
1
  • 1
    If someone only bet an item of much higher value than anyone in the other team (e.g. team A-er bet a 5,000 value item, but team B items are less than half that), and the other team has fewer items, should the high roller get anything?
    – outis
    Jul 10, 2015 at 20:26

1 Answer 1

Reset to default
1

Hmm I guess the obvious one is to:

sort B desc
sort A asc

loop through A
    loop through B 
        if Value(B) <= RemainingValue(A)
           add B to A
           break if RemainingValue(A) == 0 OR you run out of B
    Next B
Next A

but this is not quick

Improve this answer
5
  • You're not wrong, but a greedy algorithm doesn't hold up too well in this case. I expanded my test data to include 70,000 items in each array and up to 20,000 users in each and ran it with your solution. Results: 352,814,909 iterations, 16195 ms run time, 0 perfect solutions, 19,401 users underpaid, 269 users received no new items, 1,400,893 of value failed to be distributed at all, -72.2 average value discrepancy, -3,612.6 largest single discrepancy.
    – rannmann
    Jun 9, 2015 at 23:05
  • My testing function was slightly off (forgot to round off decimals). Here are the corrections: 17492 perfect solutions, 1909 underpaid, 1,391,218 value failed to distribute.
    – rannmann
    Jun 10, 2015 at 21:06
  • Did you identify why it fails? i guess if you have many B greater than A they wont be distributed whatever algorithm you use
    – Ewan
    Jun 11, 2015 at 18:37
  • 1
    What about merge both arrays and sort, then loop through assigning nearest B.
    – Ewan
    Jun 11, 2015 at 18:41
  • Turns out my testing data wasn't reflective of my use case. I had too many items of high value and not enough low value, so it was much harder to get close-to-perfect change. Over 60% of items will have values of 4-49, so this is easier than expected and your original solution works pretty well. I think what I'm going to end up doing is splitting object A and array B by values under 100 and actually doing those first, since perfect change matters more at low levels (if you bet 50000 total you don't care if it's 20 shy). If it works well, I won't need to try merge/sort/nearest, but thanks!
    – rannmann
    Jun 15, 2015 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.