Add proper algorithm to check if a card is playable

6 files changed, 130 insertions, 21 deletions

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<Production>, JsonDeserializer<Production> {
 
     @Override
     public JsonElement serialize(Production production, Type typeOfSrc, JsonSerializationContext context) {
         Resources fixedResources = production.getFixedResources();
-        List<Set<ResourceType>> choices = production.getAlternativeResources();
+        Set<Set<ResourceType>> choices = production.getAlternativeResources();
         if (fixedResources.isEmpty()) {
             return serializeAsChoice(choices, context);
         } else if (choices.isEmpty()) {
@@ -32,15 +30,15 @@ public class ProductionSerializer implements JsonSerializer<Production>, JsonDes
         }
     }
 
-    private static JsonElement serializeAsChoice(List<Set<ResourceType>> choices, JsonSerializationContext context) {
+    private static JsonElement serializeAsChoice(Set<Set<ResourceType>> 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<ResourcePool> pools;
+
+    private BestPriceCalculator(Resources resources, Table table, int playerIndex) {
+        this.resources = resources;
+        this.pools = createResourcePools(table, playerIndex);
+    }
+
+    private static List<ResourcePool> createResourcePools(Table table, int playerIndex) {
+        Provider[] providers = Provider.values();
+        List<ResourcePool> 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<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);
+                }
+            }
+        }
+        resources.add(type, 1);
+        return currentMinPrice;
+    }
+
+    private static class ResourcePool {
+
+        private final Set<Set<ResourceType>> 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<Set<ResourceType>> 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<Set<ResourceType>> alternativeResources = new ArrayList<>();
+    private final Set<Set<ResourceType>> 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<Set<ResourceType>> getAlternativeResources() {
+    public Set<Set<ResourceType>> getAlternativeResources() {
         return alternativeResources;
     }
 
+    Set<Set<ResourceType>> asChoices() {
+        Set<Set<ResourceType>> 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<Set<ResourceType>> alternatives) {
+    private static boolean containedInAlternatives(Resources resources, Set<Set<ResourceType>> alternatives) {
         if (resources.isEmpty()) {
             return true;
         }
@@ -75,8 +81,8 @@ public class Production {
         return false;
     }
 
-    private static Set<ResourceType> findFirstAlternativeContaining(List<Set<ResourceType>> alternatives,
-            ResourceType type) {
+    private static Set<ResourceType> findFirstAlternativeContaining(Set<Set<ResourceType>> 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);
     }