Qual è il modo più efficiente di generare tutte le possibili combinazioni di pozioni skyrim (gioco per PC)?

Question

Quindi ogni ingrediente ha 4 effetti http://www.uesp.net/wiki/Skyrim:Ingredients

Se combino due ingredienti. Le pozioni avranno gli effetti bonus di dove si intersecano i due set. Non posso usare lo stesso ingrediente due volte. Per generare tutte le 2 possibilità di ingredienti ho appena creato un elenco di ingredienti per effettuare coppie. Prendo la testa della lista e la confronta con il resto della lista per ogni elemento nella lista eliminando la testa ogni iterazione. Questo evita i dupes.

Sono bloccato però. Non so come generare 3 combinazioni di ingredienti senza dupes. Eventuali suggerimenti?

Answer 1

Sembra un lavoro per il linguaggio di programmazione preferito di tutti, 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 

utilizzare il comando write.csv per salvare le tabelle come file CSV.

/Modifica: Per spiegare cosa sto facendo: Il pacchetto XML contiene la funzione readHTMLTable, che estrae tutte le tabelle html da un sito Web come data.frames e le salva come elenco. La prima tabella in questa lista è quella che vogliamo. La funzione combn trova tutti i modi a 2 vie, 3 vie e n combinations di nomi di pozioni e restituisce il risultato come matrice. Io uso la funzione t per trasporre questa matrice, quindi ogni combinazione è una riga e quindi convertirla in un frame di dati. Questo si estende facilmente alle combinazioni di n ingredienti.

/Modifica 2: Ho scritto una funzione per salvare la tabella n-way in un file csv specificato dall'utente. L'ho anche rielaborato un po ', perché la trasposizione di enormi matrici è computazionalmente costosa. Questa versione dovrebbe consentire di calcolare la tabella a 4 vie, anche se richiede molto tempo e non so se è rilevante per il gioco.

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') 

/Edit 3: Ecco alcuni codice per trovare le pozioni di lavoro effettivi. Non è molto efficiente e probabilmente può essere notevolmente migliorata:

#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

Ecco alcuni C#.

Fa una ricerca dell'ingrediente con il nome di potenziali effetti. Quindi usa quella ricerca per determinare quali ingredienti possono corrispondere alla ricetta corrente. Infine, genera ricette e scarta i duplicati mentre li genera utilizzando un hashset.

completo del codice (lista degli ingredienti 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

Così ho avuto l'idea, "Qual è il modo più conveniente per acquisire tutte le conoscenze ingrediente?" Voglio che tutti gli effetti degli ingredienti siano noti nel gioco, ma non voglio spendere dodici Daedra Hearts per farlo.

Se si utilizza una soluzione di ricerca tradizionale (A *, ecc.) Il fattore di diramazione è orribile (ci sono 22000 possibili pozioni efficaci). Ho provato un approccio di ricottura ma non ho ottenuto buoni risultati. Alla fine sono andato con una ricerca informata; è subobptimal ma farà il lavoro.

Ecco il codice di import-e-combinatorize: puts "Importazione ingredienti ..."

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..." 

Il file di input è copia-pasta'd da uno dei wiki, quindi se si sta utilizzando una mod o qualcosa che puoi rilasciare direttamente. Da qui hai tutti i dati importati e le pozioni efficaci generate, quindi fai quello che vuoi!

Per il mio scopo originale ("apprendimento" efficace), ho usato il seguente codice. Fondamentalmente inizia con l'ingrediente rimanente più costoso, esaurisce i suoi effetti nel modo più economico possibile, quindi si sposta verso il basso. Alcuni ingredienti più rari sono economici (forex, carne umana), quindi ho "drogato" il mio file di dati per gonfiare artificialmente il loro valore. Tutto sommato, questo programma viene eseguito in circa 45 minuti sul mio portatile, ma è un linguaggio interpretato ...