Coin exchange algorithm

Question

I'm building a poker game. In my application I have a class ChipSet. A ChipSet is basically an array of 5 ints (one for each color poker chip).

public class ChipSet {

    public static final int WHITE_VALUE = 1;
    public static final int RED_VALUE = 2;
    public static final int GREEN_VALUE = 5;
    public static final int BLUE_VALUE = 10;
    public static final int BLACK_VALUE = 20;

    public static final int[] VALUES = new int[]{WHITE_VALUE, RED_VALUE, GREEN_VALUE, BLUE_VALUE, BLACK_VALUE};

    protected int[] chips;

    public ChipSet(int[] chips) {
        if (chips == null || chips.length != 5)
            throw new IllegalArgumentException("ChipSets should contain exactly 5 integers!");

        // store a copy of passed array
        this.chips = new int[5];
        for (int i = 0; i < this.chips.length; i++) {
            this.chips[i] = chips[i];
        }
    }

    public int getSum() {
        return chips[0] * WHITE_VALUE +
                chips[1] * RED_VALUE +
                chips[2] * GREEN_VALUE +
                chips[3] * BLUE_VALUE +
                chips[4] * BLACK_VALUE;
    }
}

Now what if I have for example a ChipSet with an array [0,0,2,1,0] (5+5+10 = 20) and I want to use my ChipSet to pay something that costs 16 units. I would have to exchange chips to make this possible.

What I need is an algorithm that exchanges as efficient as possible (exchange as few chips as possible) to make such a payment possible. A payment would just subtract the amount of chips from the array so the leftovers will still be in the ChipSet after the payment. How would I do this?

What I need is this kind of method:

public boolean exchangeToMakeAvailable(int goal) {
    // algorithm to exchange chips as efficient as possible

    // store the new values in the array, making sure the sum is still the same

    // return whether it has succeeded (false when the sum is less than the requested amount)
}

Would greatly appreciate it if you could help me figure this out.

For example:

Before the algorithm I have a ChipSet with an array [0,0,2,1,0] which has a sum of 20. I want to pay something that costs 16 units. After using the algorithm, I would have the most efficient exchange as possible, in this case the algorithm would change the array to [1,2,1,1,0] which also has a sum of 20, but now I can make a payment of 16. After the payment the ChipSet would have the array [0,2,0,0,0].

I hope my problem is clear and if it's not, leave a comment and I will explain further.

Answer 1

This is an edit, I completely reworked my answer.

**Problem from game perspective ** The player has 2 green chips (5 points) and 1 blue (10 points). This totals 20 points. Now the player want to buy a ingame icon that costs 16 points. The player has enough money to buy the item. So the player pays 16 points, but what points will he give to the shop to pay correctly.

Now I've written a working example with all of the work done.

Code

Program.java

import java.util.Arrays;

public class Program {

    public static void main(String[] args) {
        // Setting up test environment
        Player player = new Player("Borrie", new int[]{0,0,0,0, 230});
        int itemCost = 16626;
        // Pay for item
        System.out.printf("First we check if the player can pay with it's current ChipSet");
        if (!player.canPayWithChipSet(player.getChips(), 5)) {
            if (player.exchangeChips(5)) {
                System.out.printf("\n\nThe players ChipSet:" + Arrays.toString(player.getChips().chips));
                System.out.printf("\nThe players ChipSet has been succesfully exchanged.");
            } else {
                System.out.printf("\n\nThe players ChipSet:" + Arrays.toString(player.getChips().chips));
                System.out.printf("\nThe players ChipSet was not able to be exchanged.\n");
            }
        } else {
            System.out.printf("\n\nThe player can pay exact with it's original ChipSet. No need to exchange.");
        }

    }
}

Player.java

    import java.util.ArrayList;
import java.util.Arrays;

public class Player {

    private String name;
    private ChipSet chips;
    private int points = 0;

    public Player(String name, int[] chips) {
        this.name = name;
        this.chips = new ChipSet(chips);
        this.points = this.chips.getSum();
    }

    public boolean exchangeChips(int cost) {
        ChipSet newChipSet = exchangePlayerChipSet(this.chips.getChips(), cost);
        if (newChipSet == null) {
            return false;
        } else {
            this.chips = newChipSet;
            return true;
        }
    }

    public ChipSet exchangePlayerChipSet(int[] originalChipValues, int cost) {
        ChipSet newChipSet = null;
        // Create possible combinations to compare
        ArrayList<ChipSet> chipSetCombos = createCombinations(this.chips.getChips());
        // Filter the chipset based on if it's able to pay without changing chips
        System.out.printf("\n\n---- Filter which of these combinations are able to be payed with without changing chips ----");
        ArrayList<ChipSet> filteredCombos = filterCombinations(chipSetCombos, cost);
        // Compare the filtered chipsets to determine which one has changed the least
        if (!filteredCombos.isEmpty()) {
            newChipSet = compareChipSets(originalChipValues, filteredCombos);
        }
        return newChipSet;
    }

    private ArrayList<ChipSet> createCombinations(int[] array) {
        ArrayList<ChipSet> combos = new ArrayList<>();
        int[] startCombo = array;
        System.out.printf("Player has " + getTotalPoints(startCombo) + " points in chips.");
        System.out.printf("\nPlayer has these chips (WHITE,RED,GREEN,BLUE,BLACK): " + Arrays.toString(startCombo));

        while (startCombo[4] != 0) {
            startCombo = lowerBlack(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        while (startCombo[3] != 0) {
            startCombo = lowerBlue(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        while (startCombo[2] != 0) {
            startCombo = lowerGreen(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        while (startCombo[1] != 0) {
            startCombo = lowerRed(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        System.out.printf("\n\n---- Creating variations on the players chips ----");
        System.out.printf("\nVariation (all worth " + getTotalPoints(startCombo) + " points):\n");
        int teller = 1;
        for (ChipSet a : combos) {
            System.out.printf("\nCombo " + teller + ": " + Arrays.toString(a.getChips()));
            teller++;
        }
        return combos;
    }

    private ArrayList<ChipSet> filterCombinations(ArrayList<ChipSet> combinations, int cost) {
        ArrayList<ChipSet> filteredChipSet = new ArrayList<>();
        combinations.stream().filter((cs) -> (canPayWithChipSet(cs, cost))).forEach((cs) -> {
            filteredChipSet.add(cs);
        });
        return filteredChipSet;
    }

    // This method has be worked out
    public boolean canPayWithChipSet(ChipSet cs, int cost) {
        ChipSet csOrig = new ChipSet(cs.chips);
        ChipSet csCopy = new ChipSet(cs.chips);
        int counterWhite = 0;
        int counterRed = 0;
        int counterGreen = 0;
        int counterBlue = 0;
        int counterBlack = 0;

        while (20 <= cost && cost > 0 && csOrig.getChips()[4] != 0) {
            csOrig.getChips()[4] -= 1;
            cost -= 20;
            counterBlack++;
        }
        while (10 <= cost && cost > 0 && csOrig.getChips()[3] != 0) {
            csOrig.getChips()[3] -= 1;
            cost -= 10;
            counterBlue++;
        }
        while (5 <= cost && cost > 0 && csOrig.getChips()[2] != 0) {
            csOrig.getChips()[2] -= 1;
            cost -= 5;
            counterGreen++;
        }
        while (2 <= cost && cost > 0 && csOrig.getChips()[1] != 0) {
            csOrig.getChips()[1] -= 1;
            cost -= 2;
            counterRed++;
        }
        while (1 <= cost && cost > 0 && csOrig.getChips()[0] != 0) {
            csOrig.getChips()[0] -= 1;
            cost -= 1;
            counterWhite++;
        }
        if (cost == 0){
            System.out.printf("\nCombo: %s can pay exact. With %d white, %d red, %d green, %d blue an %d black chips", Arrays.toString(csCopy.chips),counterWhite,counterRed,counterGreen,counterBlue,counterBlack);
            return true;
        } else {
            System.out.printf("\nCombo: %s cannot pay exact.\n\n\n", Arrays.toString(csCopy.chips));
            return false;
        }    
    }

    private ChipSet compareChipSets(int[] originalChipValues, ArrayList<ChipSet> chipSetCombos) {
        ChipSet newChipSet;
        int[] chipSetWaardes = originalChipValues; // originele chipset aantal van kleur
        int[] chipSetCombosDifferenceValues = new int[chipSetCombos.size()];
        int teller = 1;

        System.out.printf("\n\n---- Calculate differences between players stack and it's variations ----");
        for (ChipSet cs : chipSetCombos) {
            int aantalWhite = cs.getChips()[0];
            int aantalRed = cs.getChips()[1];
            int aantalGreen = cs.getChips()[2];
            int aantalBlue = cs.getChips()[3];
            int aantalBlack = cs.getChips()[4];
            int differenceWhite = Math.abs(chipSetWaardes[0] - aantalWhite);
            int differenceRed = Math.abs(chipSetWaardes[1] - aantalRed);
            int differenceGreen = Math.abs(chipSetWaardes[2] - aantalGreen);
            int differenceBlue = Math.abs(chipSetWaardes[3] - aantalBlue);
            int differenceBlack = Math.abs(chipSetWaardes[4] - aantalBlack);
            int totalDifference = differenceWhite + differenceRed + differenceGreen + differenceBlue + differenceBlack;
            chipSetCombosDifferenceValues[teller - 1] = totalDifference;
            System.out.printf("\nCombo " + teller + ": " + Arrays.toString(cs.getChips()) + " = " + totalDifference);
            teller++;
        }
        newChipSet = chipSetCombos.get(smallestValueOfArrayIndex(chipSetCombosDifferenceValues));
        System.out.printf("\n\nThe least different ChipSet is: " + Arrays.toString(newChipSet.getChips()) + " ");
        return newChipSet;
    }

    private int smallestValueOfArrayIndex(int[] array) {
        int huidigeWaarde = array[0];
        int smallestIndex = 0;
        for (int j = 1; j < array.length; j++) {
            if (array[j] < huidigeWaarde) {
                huidigeWaarde = array[j];
                smallestIndex = j;
            }
        }
        return smallestIndex;
    }

    private int[] lowerBlack(int[] array) {
        return new int[]{array[0], array[1], array[2], array[3] + 2, array[4] - 1};
    }

    private int[] lowerBlue(int[] array) {
        return new int[]{array[0], array[1], array[2] + 2, array[3] - 1, array[4]};
    }

    private int[] lowerGreen(int[] array) {
        return new int[]{array[0] + 1, array[1] + 2, array[2] - 1, array[3], array[4]};
    }

    private int[] lowerRed(int[] array) {
        return new int[]{array[0] + 2, array[1] - 1, array[2], array[3], array[4]};
    }

    private int getTotalPoints(int[] array) {
        return ((array[0] * 1) + (array[1] * 2) + (array[2] * 5) + (array[3] * 10) + (array[4] * 20));
    }

    public String getName() {
        return this.name;
    }

    public int getPoints() {
        return this.points;
    }

    public ChipSet getChips() {
        return chips;
    }

}

ChipSet.java

public class ChipSet {

    public static final int WHITE_VALUE = 1;
    public static final int RED_VALUE = 2;
    public static final int GREEN_VALUE = 5;
    public static final int BLUE_VALUE = 10;
    public static final int BLACK_VALUE = 20;

    public static final int[] VALUES = new int[]{WHITE_VALUE, RED_VALUE, GREEN_VALUE, BLUE_VALUE, BLACK_VALUE};

    protected int[] chips;

    public ChipSet(int[] chips) {
        if (chips == null || chips.length != 5) {
            throw new IllegalArgumentException("ChipSets should contain exactly 5 integers!");
        }

        // store a copy of passed array
        this.chips = new int[5];
        for (int i = 0; i < this.chips.length; i++) {
            this.chips[i] = chips[i];
        }
    }

    public int getSum() {
        return chips[0] * WHITE_VALUE
                + chips[1] * RED_VALUE
                + chips[2] * GREEN_VALUE
                + chips[3] * BLUE_VALUE
                + chips[4] * BLACK_VALUE;
    }

    public int[] getChips() {
        return this.chips;
    }
}

Some explanation:

• Create combinations

We create some submethods the trade a chip in for it's lower chip. So for example black = 2 blues. Then we create 5 loops in order. The first ones checks if there are still black chips, if so reduce 1 black add 2 blues. Save this new combination in a list if the sum of the chips in the new ChipSet equals the original ChipSets value. Loop continues until there are no blacks anymore. Then it check if there are blues and repeats the same process until there are no reds anymore. Now we have list with all possible variations of X value in chips.

• Filter combinations

You filter the ChipSets based on if you can pay X points with them without exchanging. We loop over all possible combinations of ChipSets created in the previous part. If you can pay with the ChipSet without exchanging add it to the filteredList of ChipSets. The result is a filered list with only valid ChipSets.

• Calculate difference

For each ChipSet we count the number of chips of all colors in a ChipSet and substract the original chipset number of chips with it. You take the absolute value of that and make a sum of all those differences of the original and the combos colors. Now we have a number that represents the difference from the original. Now all we have to do is compare all the ChipSets ´difference number´. The one with the least difference we use to assign to the player.

Simple huh