Breaking down chain of item creation equation chain (possibly with recursion)

Question

I have been meddling with an idea in C# to create a piece of software (for pseudo-personal usage) but ran into implementation problems. Well... maybe they are design problems I am unaware of, but I just simply can't figure out.

The idea, expectation and general pseudo algorithm

Consider we have the following "database":

Foo + Bar = Foobar
Baz + Qux = Bazqux
Foobar + Bazqux = Foobarbazqux

These are recipes for creating the said items. Using one Foo and one Bar, we create a Foobar result which can further be an ingredient for another recipe.

Now think that we need to figure out the full recipe for the item Foobarbazqux. For the human mind and intelligence, it's relatively easy:

We need Foobarbazqux
Foobarbazqux = Foobar + Bazqux
    Foobar = Foo + Bar
    Bazqux = Baz + Qux

Foobarbazqux = Foo + Bar + Baz + Qux

And of course, if and when we have all ingredients at our disposal, we can "run" the recipe and create the items with executing each recipe in the order a few paragraphs above. (So like: we first create Foobar, then Bazqux, then combine the two to get the final result.)

But in real time, the database is a lot bigger. That's where, I suppose, computers should come in. With a working software, the machine could easily find all the ingredients and execution (crafting) steps and give it to the user, so we don't need to read through ALL the entries by hand.

The implementation (... attempt)

I have thought about using C# for achieving this piece of software. Command-line project, nothing shiny or anything, just pure stdio.

First, of course, I needed to define the item. (Note: Right now I think about using structs, but if needed, I can "upgrade" them to classes. The "database" is initialized from some sort of sequential text file which will be made later. The "database" is not altered or written in any manner during or after execution, once it is loaded, it's read-only.) And of course, I needed to define the recipe.

struct Item
{
    public string Name;
}

struct Recipe
{
    public Item Result;
    public Item[] Ingredients;
}

These two structs are held in a generic, static List<> field of Program (the default class).

At entry point, we define some items and some recipes for testing:

items.Add(new Item { Name = "Foo" });
items.Add(new Item { Name = "Bar" });
items.Add(new Item { Name = "Baz" });
items.Add(new Item { Name = "Qux" });
items.Add(new Item { Name = "Foobar" });
items.Add(new Item { Name = "Bazqux" });
items.Add(new Item { Name = "Foobarbazqux" });

recipes.Add(new Recipe
{
    Result = GetItem("Foobar"),
    Ingredients = new Item[] { GetItem("Foo"), GetItem("Bar") }
});

recipes.Add(new Recipe
{
    Result = GetItem("Bazqux"),
    Ingredients = new Item[] { GetItem("Baz"), GetItem("Qux") }
});

recipes.Add(new Recipe
{
    Result = GetItem("Foobarbazqux"),
    Ingredients = new Item[] { GetItem("Foobar"), GetItem("Bazqux") }
});

Because items are primary keyed by their Name field, GetItem is simply a List.Find<> shortcut:

private static Item GetItem(string _name)
{
    return Program.Items.Find(match => match.Name == _name);
}

So right now, the database is set. I have realized that I need to make some sort of recursive method to fetch all the ingredients, but this is where I came to problem.

Consider the following, first attempt (this is not recursive, only goes "one level deep"):

string search = "Foobarbazqux";
SearchRecipe(search);

private static void SearchRecipe(string _search)
{
    List<Recipe> item_recipes = Program.Recipes.FindAll(match => match.result.Name == GetItem(search).Name);

    foreach (Recipe recp in item_recipes)
    {
        Console.WriteLine("-------------");
        Console.WriteLine("Ingredients: ");

        foreach (Item ingredient in recp.Ingredients)
        {
            Console.WriteLine(ingredient.Name);
        }
    }
}

This produces the following output, which is, without recursion, is pretty fine and expected:

-------------
Ingredients:
Foobar
Bazqux

So for the recursion, I modified the code like this:

    foreach (Item ingredient in recp.Ingredients)
    {
+++     if (recipes.FindAll(match2 => match2.Result.name == Ingredient.name).Count != 0)
+++     {
+++         SearchRecipe(ingredient.Name);
+++     }

        Console.WriteLine(ingredient.Name);
    }

Now the output is the following:

| -------------
| Ingredients: 
* -------------
* Ingredients: 
* Foo
* Bar
| Foobar
@ -------------
@ Ingredients:
@ Baz
@ Qux
| Bazqux

I see what happens as I understand my code right now. Lines marked with * are recursions for Foobar, @ are recursions for Bazqux and | are the output of the original method call. But this isn't... kinda the output I would want to implement, as it fails to be understood easily and... isn't generally right.

The expected output and the question

The output I visualized is something like the following (of course the "extra" status lines are ignorable):

Searching for: Foobarbazqux
1 recipe found.
-----
1 Foobarbazqux = 1 Foobar + 1 Bazqux
1 Foobar = 1 Foo + 1 Bar
1 Bazqux = 1 Baz + 1 Qux
1 Foobarbazqux = 1 Foo + 1 Bar + 1 Baz + 1 Qux

1 Foo + 1 Bar => 1 Foobar
1 Baz + 1 Qux => 1 Bazqux
1 Foobar + 1 Bazqux => 1 Foobarbazqux
-----
Exit.

This is what I call as breaking down the chain of item creation recipes... or... I don't call, but imagine so, in reference to the question's title. So the program works as:

1. User enters the "final" item they are searching for (this is Foobarbazqux in our example)
2. The program ravages the database enough times so first the ingredients of the searched item are found, and then it recurses(?) deeper until it finds only subatomic ingredients that cannot be "crafted" from others: they are not a Result for any Recipe.
3. (While working so) output is shown.

Note: Fits the real scenario better, but makes an extra implementation gap: Much of the items have more than one recipes from which they can be created.

What I would like to ask for is advices and help. I am slowly wanting to convince myself that this program is unwritable (which is only some sort of desperate outcry) and that my idea has design issues. But I still hope that, within boundaries, we don't need fancy, yet-to-be-created AI systems to solve this... kinda underestimatable problem.

Thank you.

Answer 1

Second answer, for the "rewrite from scratch" approach. This is more-or-less how I'd do it if just given the problem statement with no prior code.

abstract class Item
{
    public string Name { get; private set; }
    public abstract IEnumerable<Item> Ingredients { get; }
    public abstract IEnumerable<Item> ParseRecipe();

    protected Item(string name)
    {
        Name = name;
    }

    public static Item GetItem(string _name)
    {
        return items.Find(match => match.Name == _name);
    }
}

class Atom : Item
{
    public Atom(string name) : base(name) { }

    public override IEnumerable<Item> Ingredients { get { return null; } }
    public override IEnumerable<Item> ParseRecipe()
    {
        return new[] { this };
    }
}

class Recipe : Item
{
    public Recipe(string name, params Item[] ingredients) : base(name)
    {
        _ingredients = ingredients;
    }
    public Recipe(string name, params string[] ingredients) : base(name)
    {
        _ingredients = ingredients.Select(x => Item.GetItem(x));
    }
    private IEnumerable<Item> _ingredients;
    public override IEnumerable<Item> Ingredients { get { return _ingredients;} }
    public override IEnumerable<Item> ParseRecipe()
    {
        Console.WriteLine("1 " + this.Name + " = " 
                                 + String.Join(" + ", this.Ingredients.Select(x => "1 " + x.Name)));
        var components = new List<Item>();
        foreach(var ing in Ingredients)
        {
            components.AddRange(ing.ParseRecipe());
        }

        return components;
    } 
}

Used like:

void Main()
{
    items.Add(new Atom("Foo"));
    items.Add(new Atom("Bar"));
    items.Add(new Atom("Baz"));
    items.Add(new Atom("Qux" ));
    items.Add(new Recipe("Foobar", "Foo", "Bar"));
    items.Add(new Recipe( "Bazqux", "Baz", "Qux" ));
    items.Add(new Recipe( "Foobarbazqux", "Foobar", "Bazqux" ));

    string search = "Foobarbazqux";
    var item = Item.GetItem(search);
    Console.WriteLine("1 " + item.Name + " = " 
                            + String.Join(" + ", item.ParseRecipe().Select(x => "1 " + x.Name)));

}

Results in:

1 Foobarbazqux = 1 Foobar + 1 Bazqux
1 Foobar = 1 Foo + 1 Bar
1 Bazqux = 1 Baz + 1 Qux
1 Foobarbazqux = 1 Foo + 1 Bar + 1 Baz + 1 Qux

---

The main advantage to this method over your original code has to do with the abstract class Item. With this, we only care about the differences between Atoms and Recipes during initialization. After that, everything is treated as an Item. This means that the recursion becomes much simpler, because we don't care whether the current item's Ingredients are atomic, recipies, or a mix thereof. It also means you can call SearchRecipe() on anything, without having to check that it's actually a Recipe first. (Note that I edited the code above slightly for better output in this case.)

This is not possible with a struct, because they can't inherit from each other, and thus can't be treated as the parent type. You could declare an interface they would both implement, but per this, you lose most of the memory advantages to a struct when you cast it to the interface, which we would be doing all the time.

Answer 2

I would load all ingredient = ingredient[] in memory when solving. That shouldn't be much of a problem I think.

The first thing that comes to mind is that you need a shortest path algorithm: since a recipe can be split into multiple other recipe's, you're probably looking for the least number of ingredients and want to make sure it finishes.

A standard implementation of Dijkstra's algorithm that solves all leafs as targets will do nicely for that I suppose (or is that a variation?) and will also make sure you don't run in circles.

And then... you can use the path to generate the output you want I suppose.

Answer 3

I'm sure there's a better design overall, but here's a minor modification which produces the output you want (more or less):

public static IEnumerable<IEnumerable<Item>> SearchRecipe(string _search)
{
    List<Recipe> item_recipes = recipes.FindAll(match => match.Result.Name == Item.GetItem(_search).Name);

    var ingredients = new List<IEnumerable<Item>>();

    foreach (Recipe recp in item_recipes)
    {

        foreach (Item ingredient in recp.Ingredients)
        {
            if (recipes.FindAll(match2 => match2.Result.Name == ingredient.Name).Count != 0)
            {
                ingredients.Add(SearchRecipe(ingredient.Name).SelectMany(x => x));
            }
            else
            {
                ingredients.Add(new[] { ingredient });
            }
        }
        Console.WriteLine(recp.Result.Name + " = " + String.Join(" + ", ingredients.SelectMany(x => x.Select(y => y.Name))));
    }
    return ingredients;
}

Produces:

Foobar = Foo + Bar
Bazqux = Baz + Qux
Foobarbazqux = Foo + Bar + Baz + Qux