Проблемы с игрой в перспективе (Poker)Оптимизация алгоритма [компилировать готовый код]
Игрок имеет 2 зеленых фишки (5 баллов) и 1 синие (10 баллов). Это составляет 20 очков. Теперь игрок хочет купить игровой значок, который стоит 16 очков. У игрока достаточно денег, чтобы купить предмет. Таким образом, игрок платит 16 очков, но какие очки он даст магазину, чтобы заплатить правильно.
Теперь я написал рабочий пример со всей выполненной работой.
Код
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;
}
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 counter = 1;
for (ChipSet a : combos) {
System.out.printf("\nCombo " + counter + ": " + Arrays.toString(a.getChips()));
counter++;
}
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, counterRed = 0, counterGreen = 0, counterBlue = 0, 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 counter = 1;
System.out.printf("\n\n---- Calculate differences between players stack and it's variations ----");
for (ChipSet cs : chipSetCombos) {
int amountWhite = cs.getChips()[0];
int amountRed = cs.getChips()[1];
int amountGreen = cs.getChips()[2];
int amountBlue = cs.getChips()[3];
int amountBlack = cs.getChips()[4];
int differenceWhite = Math.abs(chipSetWaardes[0] - amountWhite);
int differenceRed = Math.abs(chipSetWaardes[1] - amountRed);
int differenceGreen = Math.abs(chipSetWaardes[2] - amountGreen);
int differenceBlue = Math.abs(chipSetWaardes[3] - amountBlue);
int differenceBlack = Math.abs(chipSetWaardes[4] - amountBlack);
int totalDifference = differenceWhite + differenceRed + differenceGreen + differenceBlue + differenceBlack;
chipSetCombosDifferenceValues[counter - 1] = totalDifference;
System.out.printf("\nCombo " + counter + ": " + Arrays.toString(cs.getChips()) + " = " + totalDifference);
counter++;
}
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 currentValue = array[0];
int smallestIndex = 0;
for (int j = 1; j < array.length; j++) {
if (array[j] < currentValue) {
currentValue = 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;
}
}
Некоторые Объяснение:
- Создать комбинации
Мы создаем некоторое submethods торговлю фишки для его ниже чипа. Итак, например, черный = 2 блюза. Затем мы создаем 5 петель в порядке. Первые проверяют, есть ли еще черные чипы, если так уменьшить 1 черный добавить 2 блюза. Сохраните эту новую комбинацию в списке, если сумма чипов в новом ChipSet равна исходному значению ChipSets. Loop продолжается до тех пор, пока нет черных. Затем проверьте, есть ли блюз и повторяет тот же процесс, пока нет красных . Теперь у нас есть список со всеми возможными вариациями значения X в чипах .
- комбинации фильтров
Вы фильтровать чипсеты на , если вы можете заплатить X точек с ними без обмена. Мы перебираем все возможные комбинации ChipSets, созданные в предыдущей части. Если вы с можете оплатить с помощью ChipSet без обмена, добавьте его в filterList ChipSets. Результатом является поданный список с действительными ChipSets.
- разница Вычислить
Для каждого ChipSet мы считаем количество чипов всех цветов в чипсете и вычитать оригинальный чипсет количество чипов с ним. Вы принимаете абсолютное значение этого и делаете сумму всех этих отличий от оригинала и цветов комбо. Теперь у нас есть номер , который представляет собой отличие от оригинала. Теперь все, что нам нужно сделать, это сравнить все номера ChifSets для прослушивания. Один из с наименьшей разницей, которую мы используем для назначения игроку.
Итак, что он в основном делает: он проверяет сначала, если текущий ChipSet можно использовать для оплаты и возвращает логическое значение, как вы просили. Если это возможно, это ничего не делает, в противном случае оно проходит через 3 под-алгоритма и определяет лучший ChipSet (тот, который можно использовать для оплаты и наименее отличающийся) и меняет игроков ChipSet его
Итак, теперь в чем мой вопрос, как бы я начал оптимизировать это? Я спрашиваю об этом, потому что когда есть большие входы, алгоритм легко использует несколько секунд.
Проверьте, если вход не большой, и пусть другой алгоритм справиться с этим;.)', Если (вход <большой) { alg0();} else {alg1();} – Charlie
Lol Charlie, вы меня смеетесь: p – ManyQuestions
Ну, вы сказали «Простой ха», да, это действительно просто – Charlie