Trying to wrap my head around this but not able to come up with the algorithm. Maybe someone can help? The question is as follows:

You’re writing part of the code for an online card game. In the game, players pass cards right and left around a table. In your online version, you want to allow users to set up a game with some number of human players and some number of “bot” (automated) players. In order to be fair, you want to spread out the bots as evenly as possible around the table; for example, if there are 6 total players and 3 are bots, every third seat should be a bot, and the rest should be humans. Example Input: "6 3" Output "HHBHHBHHB"

Basically given the input of "6 3" (where first number is number of humans and second number is number of bots) I need to return the seating arrangement that spaces out the bots as evenly as possible. "H" represents Human and "B" represents bots.

I can't think of the logic to implement this. I get a feeling it's embarrassingly simple but I'm drawing a blank. Can someone help please? Doesn't matter what coding language you use. I'm more interested in the algorithm and solution.

EDIT: Found out how to do it when Humans and Bots are nice numbers that divide into each other (Humans divided by bots: 9 and 3, 6 and 2, 10 and 5, etc.) but how about for any combination?

Example: Input "6 4" You would think that the following will work: HHBHHBHBHB

but that is not as evenly as possible. The following is the better solution:

HHBHBHHBHB

CodePudding user response：

Here is a generic approach for any number of different classes of participants. I decided to offer an example with (E)xperts, (H)umans and (B)ots. It tries to be even no matter what.

It isn't perfectly optimal in the general case, but it is optimal in the simple case.

import random

def distribute (count_dict):
    total = sum(count_dict.values())
    freq = {}
    state = {}
    for key, count in count_dict.items():
        freq[key] = count/total
        state[key] = random.random() # Start randomly

    answer = []
    for i in range(total):
        best_state = -1
        best_key = None
        for key, cur_state in state.items():
            cur_state  = freq[key]
            state[key] = cur_state

            if best_state < cur_state:
                best_state = cur_state
                best_key = key

        answer.append(best_key)
        state[best_key] -= 1

    return answer


print(distribute({"E": 3, "B": 7, "H": 11}))

CodePudding user response：

I've got a fun algorithm for this.

Let's say you need to distribute H humans and B bots...

First divide the big number by the small one and get the remainder. Let's say that H is bigger, so we get q = floor(H/B) and r = H-q*B. Now you know that you can distribute q humans for each bot, but you will have r humans left over.

To figure out what to do with the leftover humans, we can just call the function recursively to figure out how to distribute the leftover humans among the bots, and then add the q humans per bot back in.

I think this is a great example of how you can use recursion to make an algorithm and know it works, without having to really understand how it works.

Here it is in python:

def distribute(h,b):
    if h < 1:
        return "B"*b
    if b < 1:
        return "H"*h
    ans=""
    if h > b:
        q = h//b
        r = h-q*b
        hperb = "H"*q
        for x in distribute(r, b):
            if x == "B":
                ans  = hperb
            ans =x
    else:
        q = b//h
        r = b-q*h
        bperh = "B"*q
        for x in distribute(h, r):
            if x == "H":
                ans  = bperh
            ans =x
    return ans

This algorithm is actually a disguised form of Euclid's algorithm for finding the greatest common divisor of two numbers, dividing largest by the smallest and recursing until the remainder is 0. The last q value we calculate is the GCD of the h and b parameters.

Try it online: https://ideone.com/Mqa8dK