From a447bc0969eec208397440357188cbbb48297e6b Mon Sep 17 00:00:00 2001 From: Joffrey BION Date: Tue, 9 May 2017 23:04:57 +0200 Subject: Add proper algorithm to check if a card is playable --- .../sevenwonders/game/cards/Requirements.java | 5 +- .../data/serializers/ProductionSerializer.java | 16 ++-- .../game/resources/BestPriceCalculator.java | 102 +++++++++++++++++++++ .../sevenwonders/game/resources/Production.java | 20 ++-- .../sevenwonders/game/resources/Resources.java | 6 +- .../sevenwonders/game/resources/TradingRules.java | 2 +- 6 files changed, 130 insertions(+), 21 deletions(-) create mode 100644 backend/src/main/java/org/luxons/sevenwonders/game/resources/BestPriceCalculator.java (limited to 'backend/src/main/java/org') diff --git a/backend/src/main/java/org/luxons/sevenwonders/game/cards/Requirements.java b/backend/src/main/java/org/luxons/sevenwonders/game/cards/Requirements.java index d0444233..e2a03767 100644 --- a/backend/src/main/java/org/luxons/sevenwonders/game/cards/Requirements.java +++ b/backend/src/main/java/org/luxons/sevenwonders/game/cards/Requirements.java @@ -5,6 +5,7 @@ import java.util.List; import org.luxons.sevenwonders.game.api.Table; import org.luxons.sevenwonders.game.boards.Board; import org.luxons.sevenwonders.game.boards.RelativeBoardPosition; +import org.luxons.sevenwonders.game.resources.BestPriceCalculator; import org.luxons.sevenwonders.game.resources.BoughtResources; import org.luxons.sevenwonders.game.resources.Resources; @@ -50,9 +51,7 @@ public class Requirements { if (producesRequiredResources(board)) { return true; } - Resources leftToPay = resources.minus(board.getProduction().getFixedResources()); - // TODO take into account resources buyable from neighbours - return false; + return BestPriceCalculator.bestPrice(resources, table, playerIndex) <= board.getGold(); } /** diff --git a/backend/src/main/java/org/luxons/sevenwonders/game/data/serializers/ProductionSerializer.java b/backend/src/main/java/org/luxons/sevenwonders/game/data/serializers/ProductionSerializer.java index 3fa6b720..5c833ff8 100644 --- a/backend/src/main/java/org/luxons/sevenwonders/game/data/serializers/ProductionSerializer.java +++ b/backend/src/main/java/org/luxons/sevenwonders/game/data/serializers/ProductionSerializer.java @@ -1,14 +1,9 @@ package org.luxons.sevenwonders.game.data.serializers; import java.lang.reflect.Type; -import java.util.List; import java.util.Set; import java.util.stream.Collectors; -import org.luxons.sevenwonders.game.resources.Production; -import org.luxons.sevenwonders.game.resources.ResourceType; -import org.luxons.sevenwonders.game.resources.Resources; - import com.google.gson.JsonDeserializationContext; import com.google.gson.JsonDeserializer; import com.google.gson.JsonElement; @@ -16,13 +11,16 @@ import com.google.gson.JsonNull; import com.google.gson.JsonParseException; import com.google.gson.JsonSerializationContext; import com.google.gson.JsonSerializer; +import org.luxons.sevenwonders.game.resources.Production; +import org.luxons.sevenwonders.game.resources.ResourceType; +import org.luxons.sevenwonders.game.resources.Resources; public class ProductionSerializer implements JsonSerializer, JsonDeserializer { @Override public JsonElement serialize(Production production, Type typeOfSrc, JsonSerializationContext context) { Resources fixedResources = production.getFixedResources(); - List> choices = production.getAlternativeResources(); + Set> choices = production.getAlternativeResources(); if (fixedResources.isEmpty()) { return serializeAsChoice(choices, context); } else if (choices.isEmpty()) { @@ -32,15 +30,15 @@ public class ProductionSerializer implements JsonSerializer, JsonDes } } - private static JsonElement serializeAsChoice(List> choices, JsonSerializationContext context) { + private static JsonElement serializeAsChoice(Set> choices, JsonSerializationContext context) { if (choices.isEmpty()) { return JsonNull.INSTANCE; } if (choices.size() > 1) { throw new IllegalArgumentException("Cannot serialize a production with more than one choice"); } - String str = choices.get(0) - .stream() + String str = choices.stream() + .flatMap(Set::stream) .map(ResourceType::getSymbol) .map(Object::toString) .collect(Collectors.joining("/")); diff --git a/backend/src/main/java/org/luxons/sevenwonders/game/resources/BestPriceCalculator.java b/backend/src/main/java/org/luxons/sevenwonders/game/resources/BestPriceCalculator.java new file mode 100644 index 00000000..df51fe4c --- /dev/null +++ b/backend/src/main/java/org/luxons/sevenwonders/game/resources/BestPriceCalculator.java @@ -0,0 +1,102 @@ +package org.luxons.sevenwonders.game.resources; + +import java.util.ArrayList; +import java.util.EnumSet; +import java.util.List; +import java.util.Set; + +import org.luxons.sevenwonders.game.api.Table; +import org.luxons.sevenwonders.game.boards.Board; + +public class BestPriceCalculator { + + private final Resources resources; + + private final List pools; + + private BestPriceCalculator(Resources resources, Table table, int playerIndex) { + this.resources = resources; + this.pools = createResourcePools(table, playerIndex); + } + + private static List createResourcePools(Table table, int playerIndex) { + Provider[] providers = Provider.values(); + List pools = new ArrayList<>(providers.length + 1); + + Board board = table.getBoard(playerIndex); + TradingRules rules = board.getTradingRules(); + pools.add(new ResourcePool(board.getProduction(), null, rules)); + + for (Provider provider : providers) { + Board providerBoard = table.getBoard(playerIndex, provider.getBoardPosition()); + ResourcePool pool = new ResourcePool(providerBoard.getProduction(), provider, rules); + pools.add(pool); + } + return pools; + } + + public static int bestPrice(Resources resources, Table table, int playerIndex) { + Board board = table.getBoard(playerIndex); + Resources leftToPay = resources.minus(board.getProduction().getFixedResources()); + return new BestPriceCalculator(leftToPay, table, playerIndex).bestPrice(); + } + + private int bestPrice() { + if (resources.isEmpty()) { + return 0; + } + int currentMinPrice = Integer.MAX_VALUE; + for (ResourceType type : ResourceType.values()) { + if (resources.getQuantity(type) > 0) { + int minPriceUsingOwnResource = bestPriceWithout(type); + currentMinPrice = Math.min(currentMinPrice, minPriceUsingOwnResource); + } + } + return currentMinPrice; + } + + private int bestPriceWithout(ResourceType type) { + resources.remove(type, 1); + int currentMinPrice = Integer.MAX_VALUE; + for (ResourcePool pool : pools) { + int resCostInPool = pool.getCost(type); + for (Set choice : pool.getChoices()) { + if (choice.contains(type)) { + Set temp = EnumSet.copyOf(choice); + choice.clear(); + currentMinPrice = Math.min(currentMinPrice, bestPrice() + resCostInPool); + choice.addAll(temp); + } + } + } + resources.add(type, 1); + return currentMinPrice; + } + + private static class ResourcePool { + + private final Set> choices; + + private final Provider provider; + + private final TradingRules rules; + + private ResourcePool(Production production, Provider provider, TradingRules rules) { + this.choices = production.asChoices(); + this.provider = provider; + this.rules = rules; + } + + Set> getChoices() { + return choices; + } + + int getCost(ResourceType type) { + if (provider == null) { + return 0; + } + return rules.getCost(type, provider); + } + } +} + diff --git a/backend/src/main/java/org/luxons/sevenwonders/game/resources/Production.java b/backend/src/main/java/org/luxons/sevenwonders/game/resources/Production.java index f85fb896..f2f7b840 100644 --- a/backend/src/main/java/org/luxons/sevenwonders/game/resources/Production.java +++ b/backend/src/main/java/org/luxons/sevenwonders/game/resources/Production.java @@ -1,9 +1,8 @@ package org.luxons.sevenwonders.game.resources; -import java.util.ArrayList; import java.util.Arrays; import java.util.EnumSet; -import java.util.List; +import java.util.HashSet; import java.util.Objects; import java.util.Set; @@ -11,7 +10,7 @@ public class Production { private final Resources fixedResources = new Resources(); - private final List> alternativeResources = new ArrayList<>(); + private final Set> alternativeResources = new HashSet<>(); public void addFixedResource(ResourceType type, int quantity) { fixedResources.add(type, quantity); @@ -35,10 +34,17 @@ public class Production { return fixedResources; } - public List> getAlternativeResources() { + public Set> getAlternativeResources() { return alternativeResources; } + Set> asChoices() { + Set> result = new HashSet<>(fixedResources.size() + alternativeResources.size()); + fixedResources.asList().stream().map(EnumSet::of).forEach(result::add); + result.addAll(alternativeResources); + return result; + } + public boolean contains(Resources resources) { if (fixedResources.contains(resources)) { return true; @@ -51,7 +57,7 @@ public class Production { return containedInAlternatives(resources, alternativeResources); } - private static boolean containedInAlternatives(Resources resources, List> alternatives) { + private static boolean containedInAlternatives(Resources resources, Set> alternatives) { if (resources.isEmpty()) { return true; } @@ -75,8 +81,8 @@ public class Production { return false; } - private static Set findFirstAlternativeContaining(List> alternatives, - ResourceType type) { + private static Set findFirstAlternativeContaining(Set> alternatives, + ResourceType type) { return alternatives.stream().filter(a -> a.contains(type)).findAny().orElse(null); } diff --git a/backend/src/main/java/org/luxons/sevenwonders/game/resources/Resources.java b/backend/src/main/java/org/luxons/sevenwonders/game/resources/Resources.java index 05bd7672..04278fea 100644 --- a/backend/src/main/java/org/luxons/sevenwonders/game/resources/Resources.java +++ b/backend/src/main/java/org/luxons/sevenwonders/game/resources/Resources.java @@ -65,7 +65,11 @@ public class Resources { } public boolean isEmpty() { - return quantities.values().stream().reduce(0, Integer::sum) == 0; + return size() == 0; + } + + public int size() { + return quantities.values().stream().reduce(0, Integer::sum); } @Override diff --git a/backend/src/main/java/org/luxons/sevenwonders/game/resources/TradingRules.java b/backend/src/main/java/org/luxons/sevenwonders/game/resources/TradingRules.java index e35e8e03..f785e665 100644 --- a/backend/src/main/java/org/luxons/sevenwonders/game/resources/TradingRules.java +++ b/backend/src/main/java/org/luxons/sevenwonders/game/resources/TradingRules.java @@ -14,7 +14,7 @@ public class TradingRules { this.defaultCost = defaultCost; } - private int getCost(ResourceType type, Provider provider) { + int getCost(ResourceType type, Provider provider) { return costs.computeIfAbsent(type, t -> new EnumMap<>(Provider.class)).getOrDefault(provider, defaultCost); } -- cgit