diff options
5 files changed, 149 insertions, 37 deletions
diff --git a/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/BestPriceCalculator.java b/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/BestPriceCalculator.java index 0cae3fe2..bde6dcb9 100644 --- a/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/BestPriceCalculator.java +++ b/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/BestPriceCalculator.java @@ -10,13 +10,26 @@ import org.luxons.sevenwonders.game.boards.Board; public class BestPriceCalculator { - private final Resources resources; + private final Resources resourcesLeftToPay; private final List<ResourcePool> pools; - private BestPriceCalculator(Resources resources, Table table, int playerIndex) { - this.resources = resources; + private final List<BoughtResources> boughtResources; + + private int pricePaid; + + private List<BoughtResources> bestSolution; + + private int bestPrice; + + private BestPriceCalculator(Resources resourcesToPay, Table table, int playerIndex) { + Board board = table.getBoard(playerIndex); + this.resourcesLeftToPay = resourcesToPay.minus(board.getProduction().getFixedResources()); this.pools = createResourcePools(table, playerIndex); + this.boughtResources = new ArrayList<>(); + this.pricePaid = 0; + this.bestSolution = null; + this.bestPrice = Integer.MAX_VALUE; } private static List<ResourcePool> createResourcePools(Table table, int playerIndex) { @@ -25,53 +38,76 @@ public class BestPriceCalculator { Board board = table.getBoard(playerIndex); TradingRules rules = board.getTradingRules(); - pools.add(new ResourcePool(board.getProduction(), null, rules)); + // we only take alternative resources here, because fixed resources were already removed for optimization + Set<Set<ResourceType>> ownBoardChoices = board.getProduction().getAlternativeResources(); + pools.add(new ResourcePool(null, rules, ownBoardChoices)); for (Provider provider : providers) { Board providerBoard = table.getBoard(playerIndex, provider.getBoardPosition()); - ResourcePool pool = new ResourcePool(providerBoard.getPublicProduction(), provider, rules); + ResourcePool pool = new ResourcePool(provider, rules, providerBoard.getPublicProduction().asChoices()); 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(); + BestPriceCalculator bestPriceCalculator = new BestPriceCalculator(resources, table, playerIndex); + bestPriceCalculator.computePossibilities(); + return bestPriceCalculator.bestPrice; } - private int bestPrice() { - if (resources.isEmpty()) { - return 0; + public static List<BoughtResources> bestSolution(Resources resources, Table table, int playerIndex) { + BestPriceCalculator bestPriceCalculator = new BestPriceCalculator(resources, table, playerIndex); + bestPriceCalculator.computePossibilities(); + return bestPriceCalculator.bestSolution; + } + + private void computePossibilities() { + if (resourcesLeftToPay.isEmpty()) { + updateBestSolutionIfNeeded(); + return; } - int currentMinPrice = Integer.MAX_VALUE; for (ResourceType type : ResourceType.values()) { - if (resources.getQuantity(type) > 0) { - int minPriceUsingOwnResource = bestPriceWithout(type); - currentMinPrice = Math.min(currentMinPrice, minPriceUsingOwnResource); + if (resourcesLeftToPay.getQuantity(type) > 0) { + for (ResourcePool pool : pools) { + boolean ownResource = pool.getProvider() == null; + if (ownResource) { + resourcesLeftToPay.remove(type, 1); + computePossibilitiesWhenUsing(type, pool); + resourcesLeftToPay.add(type, 1); + continue; + } + BoughtResources boughtRes = new BoughtResources(pool.getProvider(), Resources.of(type)); + int cost = pool.getCost(type); + + resourcesLeftToPay.remove(type, 1); + boughtResources.add(boughtRes); + pricePaid += cost; + computePossibilitiesWhenUsing(type, pool); + pricePaid -= cost; + boughtResources.remove(boughtRes); + resourcesLeftToPay.add(type, 1); + } } } - 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<ResourceType> choice : pool.getChoices()) { - if (choice.contains(type)) { - Set<ResourceType> temp = EnumSet.copyOf(choice); - choice.clear(); - currentMinPrice = Math.min(currentMinPrice, bestPrice() + resCostInPool); - choice.addAll(temp); - } + private void computePossibilitiesWhenUsing(ResourceType type, ResourcePool pool) { + for (Set<ResourceType> choice : pool.getChoices()) { + if (choice.contains(type)) { + Set<ResourceType> temp = EnumSet.copyOf(choice); + choice.clear(); + computePossibilities(); + choice.addAll(temp); } } - resources.add(type, 1); - return currentMinPrice; } + private void updateBestSolutionIfNeeded() { + if (pricePaid < bestPrice) { + bestPrice = pricePaid; + bestSolution = new ArrayList<>(boughtResources); + } + } } diff --git a/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/BoughtResources.java b/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/BoughtResources.java index ec261c8c..71293190 100644 --- a/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/BoughtResources.java +++ b/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/BoughtResources.java @@ -1,11 +1,21 @@ package org.luxons.sevenwonders.game.resources; +import java.util.Objects; + public class BoughtResources { private Provider provider; private Resources resources; + public BoughtResources() { + } + + public BoughtResources(Provider provider, Resources resources) { + this.provider = provider; + this.resources = resources; + } + public Provider getProvider() { return provider; } @@ -21,4 +31,26 @@ public class BoughtResources { public void setResources(Resources resources) { this.resources = resources; } + + @Override + public boolean equals(Object o) { + if (this == o) { + return true; + } + if (o == null || getClass() != o.getClass()) { + return false; + } + BoughtResources that = (BoughtResources) o; + return provider == that.provider && Objects.equals(resources, that.resources); + } + + @Override + public int hashCode() { + return Objects.hash(provider, resources); + } + + @Override + public String toString() { + return "BoughtResources{" + "provider=" + provider + ", resources=" + resources + '}'; + } } diff --git a/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/ResourcePool.java b/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/ResourcePool.java index ad368066..75a02afc 100644 --- a/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/ResourcePool.java +++ b/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/ResourcePool.java @@ -10,8 +10,8 @@ class ResourcePool { private final TradingRules rules; - ResourcePool(Production production, Provider provider, TradingRules rules) { - this.choices = production.asChoices(); + ResourcePool(Provider provider, TradingRules rules, Set<Set<ResourceType>> choices) { + this.choices = choices; this.provider = provider; this.rules = rules; } @@ -20,6 +20,10 @@ class ResourcePool { return choices; } + Provider getProvider() { + return provider; + } + int getCost(ResourceType type) { if (provider == null) { return 0; diff --git a/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/Resources.java b/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/Resources.java index 04278fea..1b263760 100644 --- a/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/Resources.java +++ b/game-engine/src/main/java/org/luxons/sevenwonders/game/resources/Resources.java @@ -13,6 +13,14 @@ public class Resources { private final Map<ResourceType, Integer> quantities = new EnumMap<>(ResourceType.class); + public static Resources of(ResourceType... types) { + Resources resources = new Resources(); + for (ResourceType type : types) { + resources.add(type, 1); + } + return resources; + } + public void add(ResourceType type, int quantity) { quantities.merge(type, quantity, (x, y) -> x + y); } @@ -88,4 +96,9 @@ public class Resources { public int hashCode() { return Objects.hash(quantities); } + + @Override + public String toString() { + return "Resources{" + "quantities=" + quantities + '}'; + } } diff --git a/game-engine/src/test/java/org/luxons/sevenwonders/game/resources/BestPriceCalculatorTest.java b/game-engine/src/test/java/org/luxons/sevenwonders/game/resources/BestPriceCalculatorTest.java index e6438789..9f43ec6b 100644 --- a/game-engine/src/test/java/org/luxons/sevenwonders/game/resources/BestPriceCalculatorTest.java +++ b/game-engine/src/test/java/org/luxons/sevenwonders/game/resources/BestPriceCalculatorTest.java @@ -1,6 +1,7 @@ package org.luxons.sevenwonders.game.resources; import java.util.Arrays; +import java.util.Collections; import org.junit.Test; import org.luxons.sevenwonders.game.api.Table; @@ -16,6 +17,7 @@ public class BestPriceCalculatorTest { Table table = TestUtils.createTable(3); Resources resources = new Resources(); assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 0)); + assertEquals(Collections.emptyList(), BestPriceCalculator.bestSolution(resources, table, 0)); } @Test @@ -26,10 +28,16 @@ public class BestPriceCalculatorTest { 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)); + resources.add(ResourceType.STONE, 2); + assertEquals(2, BestPriceCalculator.bestPrice(resources, table, 0)); + assertEquals(4, BestPriceCalculator.bestPrice(resources, table, 1)); + assertEquals(2, BestPriceCalculator.bestPrice(resources, table, 2)); + + BoughtResources stoneLeft = new BoughtResources(Provider.LEFT_PLAYER, Resources.of(ResourceType.STONE)); + BoughtResources stoneRight = new BoughtResources(Provider.RIGHT_PLAYER, Resources.of(ResourceType.STONE)); + assertEquals(Collections.singletonList(stoneLeft), BestPriceCalculator.bestSolution(resources, table, 0)); + assertEquals(Arrays.asList(stoneLeft, stoneRight), BestPriceCalculator.bestSolution(resources, table, 1)); + assertEquals(Collections.singletonList(stoneRight), BestPriceCalculator.bestSolution(resources, table, 2)); } @Test @@ -48,6 +56,13 @@ public class BestPriceCalculatorTest { assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 1)); assertEquals(2, BestPriceCalculator.bestPrice(resources, table, 2)); assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 3)); + + BoughtResources woodLeft = new BoughtResources(Provider.LEFT_PLAYER, Resources.of(ResourceType.WOOD)); + BoughtResources woodRight = new BoughtResources(Provider.RIGHT_PLAYER, Resources.of(ResourceType.WOOD)); + assertEquals(Collections.singletonList(woodRight), BestPriceCalculator.bestSolution(resources, table, 0)); + assertEquals(Collections.emptyList(), BestPriceCalculator.bestSolution(resources, table, 1)); + assertEquals(Collections.singletonList(woodLeft), BestPriceCalculator.bestSolution(resources, table, 2)); + assertEquals(Collections.emptyList(), BestPriceCalculator.bestSolution(resources, table, 3)); } @Test @@ -68,6 +83,11 @@ public class BestPriceCalculatorTest { assertEquals(1, BestPriceCalculator.bestPrice(resources, table, 0)); assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 1)); assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 2)); + + BoughtResources woodRight = new BoughtResources(Provider.RIGHT_PLAYER, Resources.of(ResourceType.WOOD)); + assertEquals(Collections.singletonList(woodRight), BestPriceCalculator.bestSolution(resources, table, 0)); + assertEquals(Collections.emptyList(), BestPriceCalculator.bestSolution(resources, table, 1)); + assertEquals(Collections.emptyList(), BestPriceCalculator.bestSolution(resources, table, 2)); } @Test @@ -75,7 +95,7 @@ public class BestPriceCalculatorTest { Board left = TestUtils.createBoard(ResourceType.WOOD); Board main = TestUtils.createBoard(ResourceType.WOOD); - main.getProduction().addChoice(ResourceType.ORE, ResourceType.CLAY); + main.getProduction().addChoice(ResourceType.CLAY, ResourceType.ORE); main.getTradingRules().setCost(ResourceType.CLAY, Provider.RIGHT_PLAYER, 1); Board right = TestUtils.createBoard(ResourceType.WOOD); @@ -92,5 +112,12 @@ public class BestPriceCalculatorTest { assertEquals(1, BestPriceCalculator.bestPrice(resources, table, 0)); assertEquals(0, BestPriceCalculator.bestPrice(resources, table, 1)); assertEquals(4, BestPriceCalculator.bestPrice(resources, table, 2)); + + BoughtResources oreLeft = new BoughtResources(Provider.LEFT_PLAYER, Resources.of(ResourceType.ORE)); + BoughtResources clayLeft = new BoughtResources(Provider.LEFT_PLAYER, Resources.of(ResourceType.CLAY)); + BoughtResources clayRight = new BoughtResources(Provider.RIGHT_PLAYER, Resources.of(ResourceType.CLAY)); + assertEquals(Collections.singletonList(clayRight), BestPriceCalculator.bestSolution(resources, table, 0)); + assertEquals(Collections.emptyList(), BestPriceCalculator.bestSolution(resources, table, 1)); + assertEquals(Arrays.asList(oreLeft, clayLeft), BestPriceCalculator.bestSolution(resources, table, 2)); } } |