CalcTest.cs

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using SolverTest;

namespace SolverTest
{

    public class Program
    {
        

        public static List<List<IMove>> Permute(int nbOfMoves, List<IMove> allowedMoves)
        {
            if (nbOfMoves == 0)
            {
                return new List<List<IMove>>();
            }
            if (allowedMoves.Count == 0)
            {
                throw new ArgumentException();
            }
            if (nbOfMoves == 1)
            {
                return allowedMoves.Select(move => new List<IMove> { move }).ToList();
            }

            var shorter = Permute(nbOfMoves - 1, allowedMoves);

            var result = new List<List<IMove>>();

            foreach (var list in shorter)
            {
                foreach (var move in allowedMoves)
                {
                    var copy = new List<IMove>(list);
                    copy.Add(move);
                    result.Add(copy);
                }
            }
            return result;
        }

        public static List<IMove> Solve(int start, int goal, int nbOfMoves, ISet<IMove> allowedMoves)
        {
            var permutations = Permute(nbOfMoves, allowedMoves.ToList());

            if (start == goal && nbOfMoves == 0)
            {
                return new List<IMove>(); ;
            }
            var solutions = permutations.Where(possibleSolution =>
                goal == possibleSolution.Aggregate(start, (current, move) => move.DoOperation(current))
            ).ToList();
            Console.WriteLine($"Number of solutions: {solutions.Count}");
            return solutions[0];
        }
    }

    public interface IMove
    {
        int DoOperation(int original);
    }

    public class Add : IMove
    {

        private readonly int _numberToAdd;

        public Add(int numberToAdd)
        {
            _numberToAdd = numberToAdd;
        }

        public int DoOperation(int original)
        {
            return original + _numberToAdd;
        }

        public override String ToString()
        {
            return $"+{_numberToAdd}";
        }
    }

    public class Divide : IMove
    {
        private readonly int _numberToDevide;

        public Divide(int numberToDevide)
        {
            _numberToDevide = numberToDevide;
        }

        public int DoOperation(int original)
        {
            return original / _numberToDevide;
        }

        public override String ToString()
        {
            return $"/{_numberToDevide}";
        }
    }

    public class Replace : IMove
    {
        private readonly int _from;
        private readonly int _to;

        public Replace(int from, int to)
        {
            _from = from;
            _to = to;
        }

        public int DoOperation(int original)
        {
            return int.Parse(original.ToString().Replace(_from.ToString(), _to.ToString()));
        }

        public override String ToString()
        {
            return $"{_from}=>{_to}";
        }
    }
}

[TestClass]
public class UnitTest1
{
    public static void Main(string[] args)
    {
        new UnitTest1().BoardTest();
    }
    [TestMethod]
    public void TestNoMoves()
    {
        AssertResult(0, 0, 0, Program.Solve(0, 0, 0, new HashSet<IMove>()));
    }

    [TestMethod]
    public void Test1Move()
    {
        AssertResult(0, 1, 1, Program.Solve(0, 1, 1, new HashSet<IMove>() { new Add(1) }));
    }

    [TestMethod]
    public void Test2PossibleMoves()
    {
        var add1 = new Add(1);
        var add2 = new Add(2);
        AssertResult(0, 1, 1, Program.Solve(0, 1, 1, new HashSet<IMove>() { add2, add1 }));
    }

    [TestMethod]
    public void Test2Steps()
    {
        AssertResult(0, 2, 2, Program.Solve(0, 2, 2, new HashSet<IMove>() { new Add(1) }));
    }

    [TestMethod]
    public void BoardTest()
    {
        AssertResult(11, 3100, 9, Program.Solve(11, 3100, 9, new HashSet<IMove>() { new Divide(2), new Add(3), new Replace(1, 2), new Replace(2, 9), new Add(2), new Add(1), new Replace(2, 10), new Replace(10, 100) }));
    }

    private void AssertResult(int start, int goal, int nbOfMoves, List<IMove> moves)
    {
        Assert.AreEqual(nbOfMoves, moves.Count);
        Assert.AreEqual(goal, moves.Aggregate(start, (current, move) => move.DoOperation(current)));
        Console.WriteLine(String.Join(" ", moves));
    }
}