Davo
BAN USERUse the A* Search Algorithm,
* Each node in the search tree represents a position on the board
* Depending on current position, the successor function will return the next 6 positions (6 possible moves based on the dice). If the successor is attached to a ladder or a snake, the Node should reflect the position after the ladder or snake has been taken into account.
* G = how many rolls has it taken me to get here
* H = heuristic to indicate how far away to my goal, ie. the finish square
* F = G + H, we pick Minimum(F(successor)) as the next move
public class Solver
{
public List<Square> Solve(Board board)
{
var prevStep = new Dictionary<Node, Node>();
var openList = new List<Node>();
var closedList = new List<Node>();
openList.Add(new Node { Position = board.Start });
Node current = null;
while (openList.Count > 0)
{
Node bestNode = PopBestNode(openList);
prevStep[bestNode] = current;
current = bestNode;
closedList.Add(current);
if (current.Position.Equals(board.Finish))
{
var path = new List<Node>();
path.Add(current);
while (prevStep[current] != null)
{
current = prevStep[current];
path.Insert(0, current);
}
return path.Select(n => n.Position).ToList();
}
IEnumerable<Node> successors = GetSuccessors(current, board);
foreach (Node successor in successors)
{
if (closedList.Contains(successor)) continue;
successor.G = GCalc(current, successor);
successor.H = HCalc(successor, board);
successor.F = successor.G + successor.H;
openList.Add(successor);
}
}
throw new Exception("Unable to find any path's to the finish.");
}
private Node PopBestNode(List<Node> nodes)
{
Node best = nodes.OrderBy(n => n.F).First();
nodes.Remove(best);
return best;
}
private IEnumerable<Node> GetSuccessors(Node current, Board board)
{
const int MaxDice = 6;
int distToFinish = Math.Abs(board.Finish.X - current.Position.X);
int max = MaxDice > distToFinish ? distToFinish : MaxDice;
for (int i = 1; i <= max; i++)
{
Square square = board.LandingSquareFor(current.Position, i);
yield return new Node { Position = square };
}
}
private double GCalc(Node current, Node successor)
{
return current.G + 1;
}
private double HCalc(Node successor, Board board)
{
return Math.Abs(board.Finish.X - successor.Position.X);
}
}
public class Square
{
public int X { get; set; }
public Square(int x)
{
this.X = x;
}
}
public class Snake
{
public Square Head { get; set; }
public Square Tail { get; set; }
}
public class Ladder
{
public Square Start { get; set; }
public Square End { get; set; }
}
public class Board
{
public Snake[] Snakes { get; internal set; }
public Ladder[] Ladders { get; internal set; }
public Square[] Squares { get; internal set; }
public Square Start { get { return Squares.First(); } }
public Square Finish { get { return Squares.Last(); } }
public Square LandingSquareFor(Square current, int diceValue)
{
Square landingSquare = null;
for (int i = 0; i < Squares.Length; i++)
{
if (Squares[i].Equals(current))
{
int landingIndex = i + diceValue;
if (landingIndex >= Squares.Length)
landingIndex = Squares.Length - 1 - (landingIndex - Squares.Length + 1);
if (landingIndex < 0) landingIndex = 0;
landingSquare = Squares[landingIndex];
break;
}
}
if (landingSquare == null) throw new Exception("Unable to find current square.");
Square snakeEnd = Snakes
.Where(s => s.Head.Equals(landingSquare))
.Select(s => s.Tail)
.SingleOrDefault();
if (snakeEnd != null) return snakeEnd;
Square ladderEnd = Ladders
.Where(l => l.Start.Equals(landingSquare))
.Select(l => l.End)
.SingleOrDefault();
if (ladderEnd != null)
return ladderEnd;
return landingSquare;
}
}
public class Node
{
public Node() { }
public Node(Square position)
{
this.Position = position;
}
public Square Position { get; set; }
public double F { get; set; }
public double G { get; set; }
public double H { get; set; }
public override bool Equals(object obj)
{
if (obj is Node)
return ((Node)obj).Position.X == Position.X;
return base.Equals(obj);
}
public override int GetHashCode()
{
return Position.X.GetHashCode();
}
}
[TestClass]
public class SolveTest
{
[TestMethod]
public void Solve_Basic_IsOptimal()
{
var squares = new[]
{
new Square(0),
new Square(1),
new Square(2),
new Square(3),
new Square(4),
new Square(5),
new Square(6),
new Square(7),
new Square(8),
new Square(9),
new Square(10),
new Square(11),
new Square(12),
new Square(13),
};
var board = new Board
{
Squares = squares,
Snakes = new[] {
new Snake { Head = squares[1], Tail = squares[0] } ,
},
Ladders = new [] { new Ladder { Start = squares[4], End = squares[11]}},
};
var solver = new Solver();
List<Square> bestpath = solver.Solve(board);
foreach (Square s in bestpath)
Console.WriteLine(s.X);
Assert.AreEqual(0, bestpath[0].X);
Assert.AreEqual(11, bestpath[1].X);
Assert.AreEqual(13, bestpath[2].X);
}
}
Here's my solution in C#, I look at my code then I look at Mr Python's 10 line solution and I feel sick. Damn, that's just showing off! :)
- Davo March 29, 2015