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 +- .../game/resources/BestPriceCalculatorTest.java | 69 ++++++++++++++ .../game/resources/ProductionTest.java | 51 +++++++++++ .../sevenwonders/game/resources/ResourcesTest.java | 22 +++++ .../game/resources/TradingRulesTest.java | 26 +++++- 10 files changed, 293 insertions(+), 26 deletions(-) create mode 100644 backend/src/main/java/org/luxons/sevenwonders/game/resources/BestPriceCalculator.java create mode 100644 backend/src/test/java/org/luxons/sevenwonders/game/resources/BestPriceCalculatorTest.java (limited to 'backend/src') 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); } diff --git a/backend/src/test/java/org/luxons/sevenwonders/game/resources/BestPriceCalculatorTest.java b/backend/src/test/java/org/luxons/sevenwonders/game/resources/BestPriceCalculatorTest.java new file mode 100644 index 00000000..bad611af --- /dev/null +++ b/backend/src/test/java/org/luxons/sevenwonders/game/resources/BestPriceCalculatorTest.java @@ -0,0 +1,69 @@ +package org.luxons.sevenwonders.game.resources; + +import java.util.Arrays; + +import org.junit.Test; +import org.luxons.sevenwonders.game.api.Table; +import org.luxons.sevenwonders.game.boards.Board; +import org.luxons.sevenwonders.game.test.TestUtils; + +import static org.junit.Assert.assertEquals; + +public class BestPriceCalculatorTest { + + @Test + public void bestPrice_0forEmptyResources() { + Table table = TestUtils.createTable(3); + Resources resources = new Resources(); + assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 0)); + } + + @Test + public void bestPrice_fixedResources_defaultCost() { + Board left = TestUtils.createBoard(ResourceType.STONE); + Board main = TestUtils.createBoard(ResourceType.STONE); + Board right = TestUtils.createBoard(ResourceType.WOOD); + Table table = new Table(Arrays.asList(main, right, left)); + + Resources resources = new Resources(); + resources.add(ResourceType.STONE, 1); + assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 0)); + assertEquals(2, BestPriceCalculator.bestPrice(resources, table, 1)); + assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 2)); + } + + @Test + public void bestPrice_fixedResources_overridenCost() { + Board left = TestUtils.createBoard(ResourceType.WOOD); + Board main = TestUtils.createBoard(ResourceType.STONE); + Board right = TestUtils.createBoard(ResourceType.WOOD); + Board opposite = TestUtils.createBoard(ResourceType.GLASS); + Table table = new Table(Arrays.asList(main, right, left, opposite)); + + main.getTradingRules().setCost(ResourceType.WOOD, Provider.RIGHT_PLAYER, 1); + + Resources resources = new Resources(); + resources.add(ResourceType.WOOD, 1); + assertEquals(1, BestPriceCalculator.bestPrice(resources, table, 0)); + assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 1)); + assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 2)); + assertEquals(2, BestPriceCalculator.bestPrice(resources, table, 3)); + } + + @Test + public void bestPrice_mixedResources_overridenCost() { + Board left = TestUtils.createBoard(ResourceType.WOOD); + Board main = TestUtils.createBoard(ResourceType.STONE); + Board right = TestUtils.createBoard(ResourceType.ORE); + right.getProduction().addChoice(ResourceType.WOOD, ResourceType.CLAY); + Table table = new Table(Arrays.asList(main, right, left)); + + main.getTradingRules().setCost(ResourceType.WOOD, Provider.RIGHT_PLAYER, 1); + + Resources resources = new Resources(); + resources.add(ResourceType.WOOD, 1); + assertEquals(1, BestPriceCalculator.bestPrice(resources, table, 0)); + assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 1)); + assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 2)); + } +} diff --git a/backend/src/test/java/org/luxons/sevenwonders/game/resources/ProductionTest.java b/backend/src/test/java/org/luxons/sevenwonders/game/resources/ProductionTest.java index c54209c1..2247147c 100644 --- a/backend/src/test/java/org/luxons/sevenwonders/game/resources/ProductionTest.java +++ b/backend/src/test/java/org/luxons/sevenwonders/game/resources/ProductionTest.java @@ -1,5 +1,9 @@ package org.luxons.sevenwonders.game.resources; +import java.util.EnumSet; +import java.util.HashSet; +import java.util.Set; + import org.junit.Before; import org.junit.Test; @@ -220,6 +224,53 @@ public class ProductionTest { assertTrue(production.contains(resources1Stone1Wood)); } + @Test + public void asChoices_empty() { + Production production = new Production(); + assertTrue(production.asChoices().isEmpty()); + } + + @Test + public void asChoices_onlyChoices() { + Production production = new Production(); + production.addChoice(ResourceType.STONE, ResourceType.WOOD); + production.addChoice(ResourceType.STONE, ResourceType.ORE); + production.addChoice(ResourceType.CLAY, ResourceType.LOOM, ResourceType.GLASS); + assertEquals(production.getAlternativeResources(), production.asChoices()); + } + + @Test + public void asChoices_onlyFixed() { + Production production = new Production(); + production.addFixedResource(ResourceType.WOOD, 1); + production.addFixedResource(ResourceType.CLAY, 2); + + Set> expected = new HashSet<>(); + expected.add(EnumSet.of(ResourceType.WOOD)); + expected.add(EnumSet.of(ResourceType.CLAY)); + expected.add(EnumSet.of(ResourceType.CLAY)); + + assertEquals(expected, production.asChoices()); + } + + @Test + public void asChoices_mixed() { + Production production = new Production(); + production.addChoice(ResourceType.STONE, ResourceType.ORE); + production.addChoice(ResourceType.CLAY, ResourceType.LOOM, ResourceType.GLASS); + production.addFixedResource(ResourceType.WOOD, 1); + production.addFixedResource(ResourceType.CLAY, 2); + + Set> expected = new HashSet<>(); + expected.add(EnumSet.of(ResourceType.STONE, ResourceType.ORE)); + expected.add(EnumSet.of(ResourceType.CLAY, ResourceType.LOOM, ResourceType.GLASS)); + expected.add(EnumSet.of(ResourceType.WOOD)); + expected.add(EnumSet.of(ResourceType.CLAY)); + expected.add(EnumSet.of(ResourceType.CLAY)); + + assertEquals(expected, production.asChoices()); + } + @Test public void equals_falseWhenNull() { Production production = new Production(); diff --git a/backend/src/test/java/org/luxons/sevenwonders/game/resources/ResourcesTest.java b/backend/src/test/java/org/luxons/sevenwonders/game/resources/ResourcesTest.java index a2bad8b9..1f260a11 100644 --- a/backend/src/test/java/org/luxons/sevenwonders/game/resources/ResourcesTest.java +++ b/backend/src/test/java/org/luxons/sevenwonders/game/resources/ResourcesTest.java @@ -21,6 +21,8 @@ public class ResourcesTest { for (ResourceType resourceType : ResourceType.values()) { assertEquals(0, resources.getQuantity(resourceType)); } + assertEquals(0, resources.size()); + assertTrue(resources.isEmpty()); } @Test @@ -28,6 +30,8 @@ public class ResourcesTest { Resources resources = new Resources(); resources.add(ResourceType.CLAY, 0); assertEquals(0, resources.getQuantity(ResourceType.CLAY)); + assertEquals(0, resources.size()); + assertTrue(resources.isEmpty()); } @Test @@ -35,6 +39,8 @@ public class ResourcesTest { Resources resources = new Resources(); resources.add(ResourceType.WOOD, 3); assertEquals(3, resources.getQuantity(ResourceType.WOOD)); + assertEquals(3, resources.size()); + assertFalse(resources.isEmpty()); } @Test @@ -43,6 +49,8 @@ public class ResourcesTest { resources.add(ResourceType.ORE, 3); resources.add(ResourceType.ORE, 2); assertEquals(5, resources.getQuantity(ResourceType.ORE)); + assertEquals(5, resources.size()); + assertFalse(resources.isEmpty()); } @Test @@ -53,6 +61,8 @@ public class ResourcesTest { resources.add(ResourceType.WOOD, 4); resources.add(ResourceType.GLASS, 2); assertEquals(5, resources.getQuantity(ResourceType.GLASS)); + assertEquals(10, resources.size()); + assertFalse(resources.isEmpty()); } @Test @@ -61,6 +71,8 @@ public class ResourcesTest { resources.add(ResourceType.WOOD, 3); resources.remove(ResourceType.WOOD, 2); assertEquals(1, resources.getQuantity(ResourceType.WOOD)); + assertEquals(1, resources.size()); + assertFalse(resources.isEmpty()); } @Test @@ -69,6 +81,8 @@ public class ResourcesTest { resources.add(ResourceType.WOOD, 3); resources.remove(ResourceType.WOOD, 3); assertEquals(0, resources.getQuantity(ResourceType.WOOD)); + assertEquals(0, resources.size()); + assertTrue(resources.isEmpty()); } @Test @@ -94,6 +108,8 @@ public class ResourcesTest { assertEquals(0, resources.getQuantity(ResourceType.ORE)); assertEquals(0, resources.getQuantity(ResourceType.GLASS)); assertEquals(0, resources.getQuantity(ResourceType.LOOM)); + assertEquals(4, resources.size()); + assertFalse(resources.isEmpty()); } @Test @@ -112,6 +128,8 @@ public class ResourcesTest { assertEquals(0, resources.getQuantity(ResourceType.ORE)); assertEquals(0, resources.getQuantity(ResourceType.GLASS)); assertEquals(0, resources.getQuantity(ResourceType.LOOM)); + assertEquals(4, resources.size()); + assertFalse(resources.isEmpty()); } @Test @@ -130,6 +148,8 @@ public class ResourcesTest { assertEquals(0, resources.getQuantity(ResourceType.ORE)); assertEquals(0, resources.getQuantity(ResourceType.GLASS)); assertEquals(0, resources.getQuantity(ResourceType.LOOM)); + assertEquals(12, resources.size()); + assertFalse(resources.isEmpty()); } @Test @@ -148,6 +168,8 @@ public class ResourcesTest { assertEquals(4, resources.getQuantity(ResourceType.ORE)); assertEquals(0, resources.getQuantity(ResourceType.GLASS)); assertEquals(0, resources.getQuantity(ResourceType.LOOM)); + assertEquals(14, resources.size()); + assertFalse(resources.isEmpty()); } @Test diff --git a/backend/src/test/java/org/luxons/sevenwonders/game/resources/TradingRulesTest.java b/backend/src/test/java/org/luxons/sevenwonders/game/resources/TradingRulesTest.java index 00400e7c..0fd1b52b 100644 --- a/backend/src/test/java/org/luxons/sevenwonders/game/resources/TradingRulesTest.java +++ b/backend/src/test/java/org/luxons/sevenwonders/game/resources/TradingRulesTest.java @@ -18,7 +18,7 @@ public class TradingRulesTest { @DataPoints public static int[] costs() { - return new int[] {0, 1, 2}; + return new int[]{0, 1, 2}; } @DataPoints @@ -31,6 +31,19 @@ public class TradingRulesTest { return ResourceType.values(); } + @Theory + public void setCost_overridesCost(int defaultCost, int overriddenCost, Provider overriddenProvider, + Provider provider, ResourceType type) { + assumeTrue(defaultCost != overriddenCost); + assumeTrue(overriddenProvider != provider); + + TradingRules rules = new TradingRules(defaultCost); + rules.setCost(type, overriddenProvider, overriddenCost); + + assertEquals(overriddenCost, rules.getCost(type, overriddenProvider)); + assertEquals(defaultCost, rules.getCost(type, provider)); + } + @Theory public void computeCost_zeroForNoResources(int defaultCost) { TradingRules rules = new TradingRules(defaultCost); @@ -61,7 +74,9 @@ public class TradingRulesTest { @Theory public void computeCost_defaultCostWhenOverrideOnOtherProviderOrType(int defaultCost, int overriddenCost, - Provider overriddenProvider, ResourceType overriddenType, Provider provider, ResourceType type) { + Provider overriddenProvider, + ResourceType overriddenType, Provider provider, + ResourceType type) { assumeTrue(overriddenProvider != provider || overriddenType != type); TradingRules rules = new TradingRules(defaultCost); rules.setCost(overriddenType, overriddenProvider, overriddenCost); @@ -71,7 +86,8 @@ public class TradingRulesTest { @Theory public void computeCost_oneDefaultAndOneOverriddenType(int defaultCost, int overriddenCost, - ResourceType overriddenType, Provider provider, ResourceType type) { + ResourceType overriddenType, Provider provider, + ResourceType type) { assumeTrue(overriddenType != type); TradingRules rules = new TradingRules(defaultCost); rules.setCost(overriddenType, provider, overriddenCost); @@ -81,7 +97,8 @@ public class TradingRulesTest { @Theory public void computeCost_oneDefaultAndOneOverriddenProvider(int defaultCost, int overriddenCost, - Provider overriddenProvider, Provider provider, ResourceType type) { + Provider overriddenProvider, Provider provider, + ResourceType type) { assumeTrue(overriddenProvider != provider); TradingRules rules = new TradingRules(defaultCost); rules.setCost(type, overriddenProvider, overriddenCost); @@ -92,5 +109,4 @@ public class TradingRulesTest { assertEquals(defaultCost + overriddenCost, rules.computeCost(boughtResources)); } - } -- cgit