Fix and improve BestPriceCalculator

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));
     }
 }