What's the most efficient way of generating all possible combinations of skyrim (PC Game) potions?

Question

So each ingredient has 4 effects http://www.uesp.net/wiki/Skyrim:Ingredients

If I combine two ingredients. The potions will have the bonus effects of where the two sets intersect. I can't use the same ingredient twice. To generate all 2 ingredient possibilities I just made a list of ingredient to effect pairs. I take the head of the list and compare it to the rest of the list for each element in the list deleting the head every iteration. That avoids dupes.

I'm stuck though. I don't know how to generate 3 ingredient combinations without dupes. Any suggestions?

Answer 1

Sounds like a job for everybody's favorite programming language, 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

Use the write.csv command to save the tables as csv files.

/Edit: To explain what I'm doing: The XML package contains the readHTMLTable function, which pulls all the html tables from a website as data.frames and saves them as a list. The first table in this list is the one we want. The combn function finds all the 2-way, 3-way, and n way combinations of potion names, and returns the result as a matrix. I use the t function to transpose this matrix, so each combination is one row, and then convert it to a data frame. This easily extends to combinations of n ingredients.

/Edit 2: I wrote a function to save the n-way table to a user-specified csv file. I also re-worked it a bit, because transposing huge matricies is computationally expensive. This version should allow you to calculate the 4-way table, although it takes a long time and I don't know if it's relevant to the game.

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: Here's some code to find the actual working potions. It's not very efficient and can probably be greatly improved:

#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

Here's some c#.

It makes a lookup of the ingredient by the name of potential effects. Then it uses that lookup to determine which ingredients can match the current recipe. Finally, it generates recipes and discards duplicates as it generates them by using a hashset.

Complete code (incomplete ingredient list)

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;
        }
    }
}