Cách hiệu quả nhất để tạo ra tất cả các kết hợp có thể có của potrim (PC Game) là gì?

Question

Vì vậy, mỗi thành phần có 4 hiệu ứng http://www.uesp.net/wiki/Skyrim:Ingredients

Nếu tôi kết hợp hai thành phần. Các potions sẽ có tác dụng tiền thưởng của nơi hai bộ giao nhau. Tôi không thể sử dụng cùng một thành phần hai lần. Để tạo ra tất cả 2 khả năng thành phần tôi vừa tạo ra một danh sách các thành phần để tạo ra các cặp. Tôi lấy đầu của danh sách và so sánh nó với phần còn lại của danh sách cho mỗi phần tử trong danh sách xóa đầu mỗi lần lặp lại. Điều đó tránh lừa đảo.

Tôi bị kẹt mặc dù. Tôi không biết làm thế nào để tạo ra 3 thành phần kết hợp mà không có dupes. Bất kỳ đề xuất?

Answer 1

Âm thanh như một công việc cho ngôn ngữ lập trình yêu thích của mọi người, 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 

Sử dụng lệnh write.csv để lưu bảng dưới dạng tệp csv.

/Chỉnh sửa: Để giải thích những gì tôi đang làm: Gói XML chứa hàm readHTMLTable, kéo tất cả các bảng html từ trang web dưới dạng data.frames và lưu chúng dưới dạng danh sách. Bảng đầu tiên trong danh sách này là bảng chúng tôi muốn. Hàm combn tìm tất cả các cách 2 chiều, 3 chiều và n combinations của các tên potion và trả về kết quả dưới dạng ma trận. Tôi sử dụng hàm t để chuyển đổi ma trận này, do đó, mỗi kết hợp là một hàng và sau đó chuyển đổi nó thành một khung dữ liệu. Điều này dễ dàng mở rộng đến sự kết hợp của các thành phần n.

/Chỉnh sửa 2: Tôi đã viết một hàm để lưu bảng n-way vào tệp csv do người dùng chỉ định. Tôi cũng đã làm việc lại một chút, bởi vì việc chuyển đổi các ma trận lớn là tốn kém tính toán. Phiên bản này sẽ cho phép bạn tính toán bảng 4 chiều, mặc dù phải mất một thời gian dài và tôi không biết liệu nó có liên quan đến trò chơi hay không.

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

/Chỉnh sửa 3: Dưới đây là một số mã để tìm potions làm việc thực tế. Nó không phải là rất hiệu quả và có thể có thể được cải thiện rất nhiều:

#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

Đây là một số C#.

Nó thực hiện tra cứu thành phần theo tên hiệu ứng tiềm năng. Sau đó, nó sử dụng tra cứu đó để xác định nguyên liệu nào có thể phù hợp với công thức hiện tại. Cuối cùng, nó tạo ra công thức nấu ăn và loại bỏ các bản sao khi nó tạo ra chúng bằng cách sử dụng một hashset.

mã hoàn chỉnh (không đầy đủ danh sách thành phần)

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

Vì vậy, tôi đã suy nghĩ, "cách tiết kiệm chi phí hiệu quả nhất để đạt được tất cả các kiến ​​thức thành phần là gì?" tức là tôi muốn tất cả các hiệu ứng của các thành phần được biết đến trong trò chơi, nhưng tôi không muốn dành mười hai Daedra Hearts để làm điều đó.

Nếu bạn sử dụng giải pháp tìm kiếm truyền thống (A *, vv) thì hệ số phân nhánh là khủng khiếp (có 22000 hiệu ứng có thể có hiệu quả). Tôi đã thử một cách tiếp cận ủ nhưng không nhận được kết quả tốt. Cuối cùng tôi đã đi tìm kiếm thông tin; nó là subobptimal nhưng nó sẽ có được công việc làm.

Dưới đây là đoạn code nhập khẩu-and-combinatorize: puts "Nhập khẩu nguyên liệu ..."

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

Các tập tin đầu vào là sao chép pasta'd từ một trong những wiki, vì vậy nếu bạn đang sử dụng một mod hoặc một cái gì đó bạn có thể thả ngay. Từ đây bạn có tất cả các dữ liệu nhập khẩu và các potions hiệu quả tạo ra, do đó, làm những gì bạn muốn!

Vì mục đích ban đầu của tôi ("học tập" hiệu quả), tôi đã sử dụng mã sau đây. Về cơ bản nó bắt đầu với thành phần còn lại đắt nhất, loại bỏ tác dụng của nó với giá rẻ nhất có thể, sau đó di chuyển xuống. Một số thành phần hiếm hơn có giá rẻ (ngoại trừ thịt người), vì vậy tôi "goosed" tập tin dữ liệu của tôi để tăng giả tạo giá trị của họ. Tất cả đã nói, chương trình này chạy trong khoảng 45 phút trên máy tính xách tay của tôi, nhưng nó là một ngôn ngữ giải thích ...