CODEWITHSUNDEEP
java
JamesMwangi
JamesMwangi

Reputation: 31

Generate and distribute random numbers fairly in java

Hi I have been trying to figure this quiz out

A lottery company shares out prizes to winning contestants every week. Most weeks, more than one contestant wins, in which case they try to share out the prizes as fairly as possible. Their prize distribution office has hired you to write a program that they will use to distribute prizes in the fairest way possible.

The program you write should take two lines of input:

For example, the input could be: 100,800,200,500,400,1000 Joshua,Mahesh,Lilian

The program should then output the fairest possible distribution of prizes, by displaying one line for each winner, with the values of the prizes allocated to them. For example, given the input above, the output could be:

The example above gives a perfect solution, where all winners get the same value of prizes (total value of 1000 each). In many cases, this will not be possible, but all prizes must be distributed and cannot be divided. Part of your job is to decide how you define 'fair' for these cases. For example, given the input

400,400,500,600

Barry,Sheila,Onyango,Wekesa

The following would be acceptable output, because there is no fairer distribution possible:

I am using java and so far this is what I have come up with

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    private static String amounts;
    private static String names;

    public static void main(String[] args) {
        Scanner userInput = new Scanner(System.in);

        System.out.print(
                "Please enter the lottery amounts separated by commas: ");

        if (userInput.hasNext()) {
            amounts = userInput.next();
            // System.out.println("You entered: " + amounts);
        }

        System.out.print("Please enter the contestants names: ");

        if (userInput.hasNext()) {
            names = userInput.next();
            // System.out.println("You entered: " + names);
        }

        String amountArray[] = amounts.split(",");
        String nameArray[] = names.split(",");

        award(nameArray, amountArray);
    }

    // Method that awards the amounts to the winners
    public static void award(String names[], String amounts[]) {
        int randomAmount;
        int randomName;

        for (int i = 0; i < amounts.length; i++) {
            randomAmount = (int) (Math.random() * amounts.length);
            int usedValue[] = new int[amounts.length];
            usedValue[i] = randomAmount;
            if (checkValueUsed(randomAmount, usedValue)) {

                randomName = (int) (Math.random() * names.length);
                int usedName[] = new int[names.length];

                System.out.println(names[randomName] + " = "
                        + amounts[randomAmount]);
            } else {
                break;
            }
        }
    }

    private static boolean checkValueUsed(int currentState, int[] myArray) {
        boolean found = false;

        for (int i = 0; !found && (i < myArray.length); i++) {
            if (myArray[i] == currentState) {
                found = true;
            }
        }
        return found;
    }

    private void checkUsedValue(int currentState, int[] myArray) {
        for (int i = 0; (i < myArray.length); i++) {

            if (myArray[i] == currentState) {

            }
        }
    }
}

My idea of fair is to select a random amount and assign it to a random winner.

Upvotes: 3

Views: 963

Answers (2)

Anthony Grist
Anthony Grist

Reputation: 38345

For a "fair" distribution you could try something like this:

  1. Randomly order the winners.
  2. For each winner, assign them the current highest available prize; so using your first example, winner one gets 1000, winner two gets 800, winner three gets 500.
  3. If there are prizes left to distribute, for all but the first winner, assign them the current highest available prize that doesn't take them above the prize total of the first winner; winner two would get 200 (matching the 1000 of winner one), winner three gets 400 (to make 900).
  4. Repeat step three until there are no more prizes or no prizes have been allocated; winner three gets 100 to match the 1000 of the other two.
  5. If there are still prizes to allocate, sort the winners in descending order based on total prizes, and start allocating the lowest available prizes to all but the first winner.
  6. Repeat step five until all prizes are allocated.

Upvotes: 2

Ordous
Ordous

Reputation: 3884

1) This looks like an interview/exam question. I'm not to judge but... really?
2) Your idea of fair is NOT what is intended. By the examples given, fair means all prizes are distributed and each winners total is as close to each other as possible.
3) From the above - this is a known problem. A greedy algorithm is likely to perform well. (I can't really see why not, unless you get very specific on the optimization part of the problem)

Upvotes: 2

Related Questions