Jaki jest najbardziej efektywny sposób generowania wszystkich możliwych mikstur mikstur skyrim (gry na PC)?

Question

Więc każdy składnik ma 4 efekty http://www.uesp.net/wiki/Skyrim:Ingredients

Jeśli połączę dwa składniki. Mikstury będą miały dodatkowe efekty, gdy dwa zestawy przecinają się. Nie mogę użyć tego samego składnika dwa razy. Aby wygenerować wszystkie 2 możliwości składników, właśnie stworzyłem listę składników, aby uzyskać efekt par. Biorę głowę listy i porównuję ją z resztą listy dla każdego elementu na liście, usuwając nagłówek każdej iteracji. To pozwala uniknąć podróbek.

Utknąłem. Nie wiem, jak wygenerować 3 kombinacje składników bez duplikatów. Jakieś sugestie?

Answer 1

Brzmi jak zadanie dla każdego ulubionego języka programowania, 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 

Użyj polecenia write.csv, aby zapisać tabele jako pliki CSV.

/Edytuj: Aby wyjaśnić, co robię: Pakiet XML zawiera funkcję readHTMLTable, która pobiera wszystkie tabele html ze strony internetowej jako dane.frames i zapisuje je jako listę. Pierwsza tabela na tej liście jest tą, której chcemy. Funkcja combn znajduje wszystkie nazwy dwukierunkowe, 3-drogowe i n-combinations nazw mikstur i zwraca wynik jako macierz. Używam funkcji t do transpozycji tej macierzy, więc każda kombinacja to jeden wiersz, a następnie przekształcenie go w ramkę danych. To łatwo rozciąga się na kombinacje n składników.

/Edytuj 2: napisałem funkcję, aby zapisać tabelę n-way do pliku csv określonego przez użytkownika. Trochę go też przerobiłem, ponieważ transpozycja ogromnych matriksów jest kosztowna pod względem obliczeniowym. Ta wersja powinna pozwolić ci obliczyć tabelę 4-stronną, chociaż zajmuje to dużo czasu i nie wiem, czy jest ona istotna dla gry.

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

/Edytuj 3: Oto kod do znajdowania rzeczywistych mikstur roboczych. Nie jest to zbyt wydajne i można go znacznie poprawić:

#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

Oto niektóre C#.

Dokonuje wyszukiwania składnika pod nazwą potencjalnych efektów. Następnie używa tego wyszukiwania, aby określić, które składniki mogą pasować do aktualnej receptury. Na koniec generuje receptury i odrzuca duplikaty, generując je za pomocą hashsetu.

Kompletny kod (niepełna lista składnik)

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

Miałem więc pomyślałem: „Co jest najbardziej opłacalnym sposobem, aby zdobyć całą wiedzę składnik?” tj. chcę, aby wszystkie efekty składników były znane w grze, ale nie chcę wydawać dwunastu Daedrycznych Serc, aby to zrobić.

Jeśli używasz tradycyjnego rozwiązania wyszukiwania (A *, itp.) Współczynnik rozgałęzienia jest przerażający (jest 22000 możliwych możliwych mikstur). Próbowałem zastosować wyżarzanie, ale nie uzyskiwałem dobrych wyników. W końcu poszedłem z świadomym wyszukiwaniem; jest subobtimalna, ale wykona zadanie.

Oto kod import-and-combinatorize: puts "Importowanie składników ..."

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

Plik wejściowy jest kopiowaniem pasta'd jednej z wiki, więc jeśli używasz mod lub coś, do czego możesz wpaść. Stąd masz wszystkie zaimportowane dane i skuteczne mikstury, więc rób to, co chcesz!

Dla mojego pierwotnego celu (wydajne "uczenie się") użyłem następującego kodu. Zasadniczo zaczyna się od najdroższego pozostałego składnika, wyczerpuje swoje efekty tak tanio, jak to tylko możliwe, po czym przesuwa się w dół. Niektóre rzadsze składniki są tanie (na rynku ludzkim), więc "udałem się" do pliku z danymi, aby sztucznie zawyżać ich wartość. W sumie, to program działa w około 45 minut na moim laptopie, ale jest językiem interpretowanym ...