I'd like to put in my two cents too.

# Storing types and creating names

Your current code is based on strings e.g. you look for types by names that you both store in a dictionary and in the list. I find this duplication is not a good idea. Try to use strong types whereever possible and I think it is here. What if you have two `Problem1` but in different namespaces? The application wouldn't work anymore.

Solution: we'll store everything in the `ListBox` but first you need to create a new type to store everything you need. The listbox can keep more then just a string.

    class ProblemInfo
    { 
        public ProblemInfo(Type problemType)
        {
            ProblemId = ((Problem)Activator.CreateInstance(problemType)).Id;
            ProblemType = problemType;
        }
        
        public int ProblemId { get; }
        
        public Type ProblemType { get; }
        
        public string FullName => $"Problem {ProblemId,0:00}";
    }

With this new type we encapsulate the view-logic. It is now responsible for creating a string for the `Problem.Id` and additionaly it'll store the type of the problem. No more strings.

---

Next we want to improve the problems themselves.

Instead of an interface I suggest using an `abstract class` that can retrieve the `Id` which we now store as an attribute. The `Id` shouldn't part of the implementation.

    abstract class Problem
    {
        public int Id  => GetType().GetCustomAttribute<IdAttribute>();

        public abstract ProblemOutput Solve();
    }

And this is the attribute:

    [AttributeUsage(AttributeTargets.Class)]
    class IdAttribute : Attribute
    {
        private readonly int _value;
        public IdAttribute(int value) { _value = value; }
        public static implicit operator int(IdAttribute idAttribute) => idAttribute._value;
    }

You use it to decorate each problem and you can give them more meaningful names.

    [Id(1)]
    class SomeProblem : Problem { }
    
    [Id(10)]
    class AnotherProblem : Problem { }
    
    [Id(2)]
    class DifferentProblem : Problem { }

Later you may decide to add descriptions to the problems so create another attribute for it and use the `ProblemInfo` class to retrieve it and display it e.g. in a textbox upon selection.

---

# Creating the ListBox

But how do we create the `ListBox` now? Like this. We set the `MultiColumn = false` and tell it to use the `FullName` for the display.

    var listBox = new MyListbox();
    listBox.MultiColumn = false;
    listBox.DisplayMember = nameof(ProblemInfo.FullName);
    
    listBox.BeginUpdate();
    listBox.Items.Add(new ProblemInfo(typeof(DifferentProblem)));
    listBox.Items.Add(new ProblemInfo(typeof(SomeProblem)));
    listBox.Items.Add(new ProblemInfo(typeof(AnotherProblem)));    
    listBox.EndUpdate();
    
    listBox.Sorted = true;
    
I used _hard-coded_ types but you of course will have a loop there to add the items.

You probably noticed that I have some kind of a `MyListBox` there. Yes, I created this to implement the natural-sort logic. This is no longer based on names and strings but on the `Id`.

    class MyListbox : ListBox
    {
        protected override void Sort()
        {
            if (Items.Count == 0) { return; }
            var swapped = false;
            do
            {
                var counter = Items.Count - 1;
                swapped = false;
                while (counter > 0)
                {
                    var isLessThen = ((ProblemInfo)Items[counter]).ProblemId < ((ProblemInfo)Items[counter - 1]).ProblemId;
                    if (isLessThen) 
                    {
                        var tmp = Items[counter];
                        Items[counter] = Items[counter - 1];
                        Items[counter - 1] = tmp;
                        swapped = true;
                    }
                    counter--;
                }
                
            } while (swapped);
        }
    }

The custom `MyListBox` overrides the `Sort` method and works with the `Id` so that you can format the string however you like and it'll still work.

---

# Selecting problems

With all those improvements you can now modify also the `SelectedIndexChange` event handler to do this:

    private void ProblemSelector_SelectedIndexChanged(object sender, EventArgs e)
    {
        var selectedProblem = ((MyListbox)sender).SelectedItem as ProblemInfo;
    
    }

Now you can store it and have a direct access to the `Type` which you can use to instantiate without regex and strings.

---

# Benchmarking

The `Problem`s shouldn't measure thier execution time. What if you want to run it more then once? You cannot measure the entire execution time.

Instead create a `ProblemSolver`.

    class ProblemSolver
    { 
        public ProblemResult Solve(Problem problem)
        {
            // measure time etc...
        }    
    }

This means that the `ProblemOutput` looses it's execution time and you move it into the new type `ProblemResult` which should contain both values.

Should you want to create other benchmarks then you can extend the `ProblemSolver` with other algorithms but no longer need to modify the problems themselves. They should just solve the problem and don't do anything else.