¿Cuál es la forma más eficiente de generar todas las combinaciones posibles de pociones skyrim (PC Game)?

Question

Así que cada ingrediente tiene efectos

Si combino dos ingredientes. Las pociones tendrán los efectos adicionales de donde los dos conjuntos se cruzan. No puedo usar el mismo ingrediente dos veces. Para generar las 2 posibilidades de ingredientes, acabo de hacer una lista de ingredientes para efectuar pares. Tomo la cabecera de la lista y la comparo con el resto de la lista para cada elemento de la lista, borrando el encabezado cada iteración. Eso evita tontos.

Estoy atrapado. No sé cómo generar 3 combinaciones de ingredientes sin engaños. ¿Alguna sugerencia?

Answer 1

¡Parece un trabajo para el lenguaje de programación favorito de todos, R!

library(XML) 
tables <- readHTMLTable('http://www.uesp.net/wiki/Skyrim:Ingredients', 
    stringsAsFactors=FALSE) 
potions <- tables[[1]] 
twoway <- data.frame(t(combn(potions$Name,2))) 
threeway <- data.frame(t(combn(potions$Name,3))) 

BAM!

> head(twoway) 
       X1     X2 
1 Abecean Longfin   Bear Claws 
2 Abecean Longfin     Bee 
3 Abecean Longfin  Beehive Husk 
4 Abecean Longfin  Bleeding Crown 
5 Abecean Longfin   Blisterwort 
6 Abecean Longfin Blue Butterfly Wing 
> head(threeway) 
       X1   X2     X3 
1 Abecean Longfin Bear Claws     Bee 
2 Abecean Longfin Bear Claws  Beehive Husk 
3 Abecean Longfin Bear Claws  Bleeding Crown 
4 Abecean Longfin Bear Claws   Blisterwort 
5 Abecean Longfin Bear Claws Blue Butterfly Wing 
6 Abecean Longfin Bear Claws  Blue Dartwing 

utilizar el comando write.csv para guardar las tablas como archivos CSV.

/Editar: Para explicar lo que estoy haciendo: El paquete XML contiene la función readHTMLTable, que extrae todas las tablas html de un sitio web como data.frames y las guarda como una lista. La primera tabla en esta lista es la que queremos. La función combn encuentra todos los nombres bidiónicos, tridireccionales yn combinations de pociones, y devuelve el resultado como una matriz. Utilizo la función t para transponer esta matriz, por lo que cada combinación es una fila, y luego la convierto en un marco de datos. Esto se extiende fácilmente a combinaciones de n ingredientes.

/Editar 2: escribí una función para guardar la tabla n-way en un archivo csv especificado por el usuario. También volví a trabajar un poco, porque la transposición de grandes matrículas es computacionalmente costosa. Esta versión debería permitirle calcular la tabla de 4 vías, aunque lleva mucho tiempo y no sé si es relevante para el juego.

nway <- function(n, filepath, data=potions) { 
    nway <- combn(data$Name, n, simplify = FALSE) 
    nway <- do.call(rbind,nway) 
    write.csv(nway,filepath, row.names=FALSE) 
} 
nway(4,'~/Desktop/4way.csv') 

/Editar 3: Aquí hay algo de código para encontrar las pociones de trabajo reales. No es muy eficiente y probablemente se puede mejorar mucho:

#Given an ingredient, lookup effects 
findEffects <- function(Name) { #Given a name, lookup effects 
    potions[potions$Name==Name,3:6] 
} 

#2-way potions 
intersectTwoEffects <- function(x) { 
    Effects1 <- findEffects(x[1]) 
    Effects2 <- findEffects(x[2]) 
    Effects <- unlist(intersect(Effects1,Effects2)) 
    Effects <- c(x[1],x[2],Effects) 
    length(Effects) <- 6 
    names(Effects) <- NULL 
    c(Effects,sum(is.na(Effects))) 

} 
twoway <- lapply(twoway,intersectTwoEffects) 
twoway <- do.call(rbind,twoway) 
twoway <- twoway[twoway[,7]<4,-7] #remove combos with no effect 
write.csv(twoway,'~/Desktop/twoway.csv',row.names=FALSE) 

#3-way potions 
intersectThreeEffects <- function(x) { 
    Effects1 <- findEffects(x[1]) 
    Effects2 <- findEffects(x[2]) 
    Effects3 <- findEffects(x[3]) 
    Effects <- c(intersect(Effects1,Effects2),intersect(Effects1,Effects3),intersect(Effects2,Effects3)) 
    Effects <- unlist(unique(Effects)) 
    Effects <- c(x[1],x[2],x[3],Effects) 
    length(Effects) <- 8 
    names(Effects) <- NULL 
    c(Effects,sum(is.na(Effects))) 

} 
threeway <- lapply(threeway,intersectThreeEffects) 
threeway <- do.call(rbind,threeway) 
threeway <- threeway[threeway[,9]<5,-9] #remove combos with no effect 
write.csv(threeway,'~/Desktop/threeway.csv',row.names=FALSE) 

Answer 2

Aquí hay algunos C#.

Hace una búsqueda del ingrediente con el nombre de efectos potenciales. Luego utiliza esa búsqueda para determinar qué ingredientes pueden coincidir con la receta actual. Finalmente, genera recetas y descarta duplicados a medida que los genera utilizando un hashset.

Código completo (lista de ingredientes incompleta)

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Combinations 
{ 

    public class Ingredient 
    { 
     public List<string> Effects { get; set; } 
     public string Name { get; set; } 
     public Ingredient(string name, params string[] effects) 
     { Name = name; Effects = new List<string>(effects); } 
    } 

    public class Recipe 
    { 
     public List<Ingredient> Ingredients {get;set;} 
     public Recipe(IEnumerable<Ingredient> ingredients) 
     { Ingredients = ingredients.OrderBy(x => x.Name).ToList(); } 
     public override string ToString() 
     { return string.Join("|", Ingredients.Select(x => x.Name).ToArray()); } 
    } 

    class Program 
    { 
     static void Main(string[] args) 
     { 
      List<Ingredient> source = GetIngredients(); 

      ILookup<string, Ingredient> byEffect = (
       from i in source 
       from e in i.Effects 
       select new { i, e } 
       ).ToLookup(x => x.e, x => x.i); 

      List<Recipe> oneIng = source.Select(x => new Recipe(new Ingredient[] { x })).ToList(); 
      List<Recipe> twoIng = oneIng.SelectMany(r => GenerateRecipes(r, byEffect)).ToList(); 
      List<Recipe> threeIng = twoIng.SelectMany(r => GenerateRecipes(r, byEffect)).ToList(); 

      Console.WriteLine(twoIng.Count); 
      foreach(Recipe r in twoIng) { Console.WriteLine(r); } 
      Console.WriteLine(threeIng.Count); 
      foreach(Recipe r in threeIng) { Console.WriteLine(r); } 
      Console.ReadLine(); 
     } 

     static IEnumerable<Recipe> GenerateRecipes(Recipe recipe, ILookup<string, Ingredient> byEffect) 
     { 
      IEnumerable<string> knownEffects = recipe.Ingredients 
       .SelectMany(i => i.Effects) 
       .Distinct(); 

      IEnumerable<Ingredient> matchingIngredients = knownEffects 
       .SelectMany(e => byEffect[e]) 
       .Distinct() 
       .Where(i => !recipe.Ingredients.Contains(i)); 

      foreach(Ingredient i in matchingIngredients) 
      { 
       List<Ingredient> newRecipeIngredients = recipe.Ingredients.ToList(); 
       newRecipeIngredients.Add(i); 
       Recipe result = new Recipe(newRecipeIngredients); 
       string key = result.ToString(); 
       if (!_observedRecipes.Contains(key)) 
       { 
        _observedRecipes.Add(key); 
        yield return result; 
       } 
      } 
     } 

     static HashSet<string> _observedRecipes = new HashSet<string>(); 

     static List<Ingredient> GetIngredients() 
     { 
      List<Ingredient> result = new List<Ingredient>() 
      { 
       new Ingredient("Abecean Longfin", "Weakness to Frost", "Fortify Sneak", "Weakness to Poison", "Fortify Restoration"), 
       new Ingredient("Bear Claws", "Restore Stamina", "Fortify Health", "Fortify One-handed", "Damage Magicka Regen"), 
       new Ingredient("Bee", "Restore Stamina", "Ravage Stamina", "Regenerate Stamina", "Weakness to Shock"), 
       new Ingredient("Beehive Husk", "Resist Poison", "Fortify Light Armor", "Fortify Sneak", "Fortify Destruction"), 
       new Ingredient("Bleeding Crown", "Weakness to Fire", "Fortify Block", "Weakness to Poison", "Resist Magic"), 
       new Ingredient("Blisterwort", "Damage Stamina", "Frenzy", "Restore Health", "Fortify Smithing"), 
       new Ingredient("Blue Butterfly Wing", "Damage Stamina", "Fortify Conjuration", "Damage Magicka Regen", "Fortify Enchanting"), 
       new Ingredient("Blue Dartwing", "Resist Shock", "Fortify Pickpocket", "Restore Health", "Damage Magicka Regen"), 
       new Ingredient("Blue Mountain Flower", "Restore Health", "Fortify Conjuration", "Fortify Health", "Damage Magicka Regen"), 
       new Ingredient("Bone Meal", "Damage Stamina", "Resist Fire", "Fortify Conjuration", "Ravage Stamina"), 
      }; 

      return result; 
     } 
    } 
} 

Answer 3

Así que tuve el pensamiento: "¿Cuál es la forma más rentable de obtener todo el conocimiento ingrediente?" es decir, quiero que se conozcan todos los efectos de los ingredientes en el juego, pero no quiero gastar doce Daedra Hearts para hacerlo.

Si utiliza una solución de búsqueda tradicional (A *, etc.) el factor de ramificación es horrible (hay 22000 posibles posibles pociones). Probé un enfoque de recocido pero no estaba obteniendo buenos resultados. Finalmente fui con una búsqueda informada; es subobptimal pero hará el trabajo.

Aquí está el código de importación-y-combinatorize: pone "Importación de ingredientes ..."

fd = File::open('ingr_weighted.txt', 'r') 
dbtext = fd.read 
fd.close 
ingredients = [] 
cvg = [] 
id = 0 
dbtext.each_line { |line| 
    infos = line.split("\t") 
    ingredients << {:id => id, :name => infos[0], :effects => [infos[2],infos[3],infos[4],infos[5]], 
        :eff1 => infos[2], :eff2 => infos[3], :eff3 => infos[4], :eff4 => infos[5], 
        :weight => infos[6], :cost => infos[7].to_i+1} 
    id += 1 
    cvg << [false, false, false, false] 
} 


puts "Building potions..." 
potions = [] 
id = 0 
for a in 0..ingredients.length-2 
    for b in a+1..ingredients.length-1 
     # First try two-ingredient potions 
     uses = ingredients[a][:effects] & ingredients[b][:effects] 
     cost = ingredients[a][:cost] + ingredients[b][:cost] 
     if (uses.length > 0) 
      coverage = [ingredients[a][:effects].map{|x| uses.include? x}, 
         ingredients[b][:effects].map{|x| uses.include? x}] 
      potions << {:id => id, :effects => uses, :coverage => coverage, :ingredients => [a, b], :cost => cost} 
      id = id + 1 
     end 
     # Next create three-ingredient potions 
     for c in b+1..ingredients.length-1 
      uses = ingredients[a][:effects] & ingredients[b][:effects] | 
        ingredients[a][:effects] & ingredients[c][:effects] | 
        ingredients[b][:effects] & ingredients[c][:effects] 
      cost = ingredients[a][:cost] + ingredients[b][:cost] + ingredients[c][:cost] 
      if (uses.length > 0) 
       coverage = [ingredients[a][:effects].map{|x| uses.include? x}, 
          ingredients[b][:effects].map{|x| uses.include? x}, 
          ingredients[c][:effects].map{|x| uses.include? x}] 
       # Prune potions that contain a superfluous ingredient 
       if (coverage.inject(true) { |cum, cvgn| 
              cum = cum && cvgn.inject { |cum2,ef| cum2 = cum2 || ef} 
              }) 
        potions << {:id => id, :effects => uses, :coverage => coverage, :ingredients => [a,b,c], :cost => cost} 
        id = id + 1 
       end 
      end 
     end 
    end 
end 
# 22451 
puts "#{potions.count} potions generated!" 
puts "Searching..." 

El archivo de entrada es copia-pasta'd de uno de los wikis, por lo que si se está utilizando un mod o algo que puedes usar directamente. Desde aquí tienes todos los datos importados y las pociones efectivas generadas, ¡así que haz lo que quieras!

Para mi propósito original ("aprendizaje eficiente"), utilicé el siguiente código. Básicamente, comienza con el ingrediente restante más caro, agota sus efectos lo más barato posible y luego avanza hacia abajo. Algunos ingredientes más raros son baratos (forex, carne humana), así que "gasté" mi archivo de datos para inflar artificialmente su valor. En total, este programa se ejecuta en unos 45 minutos en mi ordenador portátil, pero es un lenguaje interpretado ...