Skip to content

Instantly share code, notes, and snippets.

@tcoopman
Created September 21, 2017 11:13
Show Gist options
  • Save tcoopman/c24da4fe64f3985118c6da9dc6627496 to your computer and use it in GitHub Desktop.
Save tcoopman/c24da4fe64f3985118c6da9dc6627496 to your computer and use it in GitHub Desktop.
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));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment