Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/// <reference path="scripts/jquery.d.ts" />
module Trainline {
export var pointState = {
Available: "AVAILABLE",
Crossed: "CROSSED",
Unavailable: "UNAVAILABLE"
}
export var pointSide = {
Unknown: "UNKNOWN",
Left: "LEFT",
Right: "RIGHT",
Top: "TOP",
Bottom: "BOTTOM"
}
export class Point {
public x: number;
public y: number;
private state: string;
private entrySide: string;
private exitSide: string;
public propertyChangedCallback: { (changedPoint: Point): void; };
constructor(x: number, y: number) {
this.x = x;
this.y = y;
this.state = pointState.Available;
this.entrySide = pointSide.Unknown;
}
//Set the state without kicking off the property changed event
public SetUnavailable(): void {
this.state = pointState.Unavailable;
}
showPoint(): void {
if (!this.entrySide || this.entrySide === pointSide.Unknown) {
return;
}
if (!this.exitSide || this.exitSide === pointSide.Unknown) {
return;
}
$("#image" + this.x + this.y).attr("src", "content/" + this.entrySide + "_" + this.exitSide + ".png");
}
get EntrySide(): string {
return this.entrySide;
}
set EntrySide(value: string) {
this.entrySide = value;
this.showPoint();
this.propertyChangedCallback(this);
}
get ExitSide(): string {
return this.exitSide;
}
set ExitSide(value: string) {
this.exitSide = value;
this.showPoint();
this.propertyChangedCallback(this);
}
get State(): string {
return this.state;
}
set State(value: string) {
this.state = value;
this.propertyChangedCallback(this);
}
EntrySideFrom(fromPoint: Point): string {
if (Math.abs(fromPoint.x - this.x) > 1
|| Math.abs(fromPoint.y - this.y) > 1) {
//Not adjacent, so
return pointSide.Unknown;
}
if (fromPoint.x != this.x
&& fromPoint.y != this.y) {
return pointSide.Unknown;
}
if (fromPoint.x < this.x) {
return pointSide.Left;
}
if (fromPoint.x > this.x) {
return pointSide.Right;
}
if (fromPoint.y < this.y) {
return pointSide.Bottom;
}
return pointSide.Top;
}
public static OppositeOf(side: string): string {
switch (side) {
case pointSide.Bottom:
return pointSide.Top;
case pointSide.Top:
return pointSide.Bottom;
case pointSide.Left:
return pointSide.Right;
case pointSide.Right:
return pointSide.Left;
default:
return pointSide.Unknown;
}
}
}
export class Grid {
points: Point[][];
columnTotals: number[];
rowTotals: number[];
includePoints: Point[];
currentPoint: Point;
startPoint: Point;
endPoint: Point;
ignoreEvents: bool;
constructor(totals: number[], startY: number, endX: number) {
this.ignoreEvents = true;
this.columnTotals = totals.slice(0, 8);
this.rowTotals = totals.slice(8, 16);
this.points = this.createPoints();
this.setExtremePoints(0, startY, endX, 0);
this.ignoreEvents = false;
}
setExtremePoints(startX: number, startY: number, endX: number, endY: number): void {
this.startPoint = this.currentPoint = this.points[startX][startY];
this.startPoint.State = pointState.Crossed;
this.startPoint.EntrySide = pointSide.Left;
this.startPoint.ExitSide = pointSide.Right;
this.endPoint = this.points[endX][endY];
this.endPoint.State = pointState.Crossed;
this.endPoint.EntrySide = pointSide.Top;
this.endPoint.ExitSide = pointSide.Bottom;
}
public crossedPointsInColumn(column: number): number {
var crossedPoints = 0;
this.points[column].forEach(checkPoint =>
{
if (checkPoint.State == pointState.Crossed) {
crossedPoints++;
}
});
return crossedPoints;
}
private crossedPointsInRow(row: number): number {
var crossedPoints = 0;
this.points.forEach(column =>
{
column.forEach(checkPoint =>
{
if (checkPoint.y == row && checkPoint.State == pointState.Crossed) {
crossedPoints++;
}
});
});
return crossedPoints;
}
private setUnavailableInColumn(column: number): void {
for (var row = 0; row <= 7; ++row) {
if (this.points[column][row].State == pointState.Available) {
this.points[column][row].SetUnavailable();
}
}
}
private setUnavailableInRow(row: number): void {
for (var column = 0; column <= 7; ++column) {
if (this.points[column][row].State == pointState.Available) {
this.points[column][row].SetUnavailable();
}
}
}
pointPropertyChanged(changedPoint: Point) {
if (this.ignoreEvents) {
return;
}
var changedPointColumn = changedPoint.x;
var changedPointRow = changedPoint.y;
var columnCrossedPoints = this.crossedPointsInColumn(changedPoint.x);
//Have the max amount in this column
if (columnCrossedPoints >= this.columnTotals[changedPoint.x]) {
//Set all available to unavailable
this.setUnavailableInColumn(changedPoint.x);
}
var rowCrossedPoints = this.crossedPointsInRow(changedPoint.y);
//Have the max amount in this row
if (rowCrossedPoints >= this.rowTotals[changedPoint.y]) {
//Set all available to unavailable
this.setUnavailableInRow(changedPoint.y);
}
}
createPoints(): Point[][] {
var points: Point[][] = [];
for (var x = 0; x <= 7; ++x) {
points.push(new Point[]);
for (var y = 0; y <= 7; ++y) {
points[x].push(this.buildPoint(x, y));
}
}
return points;
}
buildPoint(x: number, y: number): Point {
var myPoint = new Point(x, y);
myPoint.propertyChangedCallback = p => this.pointPropertyChanged(p);
return myPoint;
}
clone(): Grid {
//TODO:MJ clone this properly
var clonedGrid = new Grid(this.columnTotals.concat(this.rowTotals), this.startPoint.y, this.endPoint.x);
this.points.forEach(origColumn => {
origColumn.forEach(origPoint => {
var clonedPoint = clonedGrid.points[origPoint.x][origPoint.y];
clonedPoint.EntrySide = origPoint.EntrySide;
clonedPoint.ExitSide = origPoint.ExitSide;
clonedPoint.State = origPoint.State;
})
});
clonedGrid.currentPoint = clonedGrid.points[this.currentPoint.x][this.currentPoint.y];
clonedGrid.endPoint = clonedGrid.points[this.endPoint.x][this.endPoint.y];
return clonedGrid;
}
public IsValid(): bool {
return this.NoColumnsToLeftHaveOnePointAvailable();
}
// if 1 point remains available in column and guesspoint is same side as the finish point from this row,
// then the track can't pass into and out of the column again to use the single point
private NoColumnsToLeftHaveOnePointAvailable(): bool {
var maxCheckCol = Math.min(this.endPoint.x, this.currentPoint.x) - 1;
for (var checkCol = 0; checkCol <= maxCheckCol; ++checkCol) {
if (this.columnTotals[checkCol] - this.crossedPointsInColumn(checkCol) == 1) {
return false;
}
}
return true;
}
IsSolved(): bool {
if (this.currentPoint.EntrySideFrom(this.endPoint) != pointSide.Bottom)
return false;
for (var index = 0; index <= 7; ++index) {
if (this.crossedPointsInColumn(index) != this.columnTotals[index] || this.crossedPointsInRow(index) != this.rowTotals[index])
return false;
}
return true;
}
}
export class AdjacentPointCalculator {
public getAvailableAdjacentPoints(startGrid: Grid): Point[] {
var adjacentPoints: Point[] = [];
var adjacentPoint: Point;
if ((adjacentPoint = AdjacentPointCalculator.pointToLeft(startGrid))) {
if (AdjacentPointCalculator.canBeUsed(adjacentPoint, pointSide.Right)) {
adjacentPoints.push(adjacentPoint);
}
}
if ((adjacentPoint = AdjacentPointCalculator.pointToRight(startGrid))) {
if (AdjacentPointCalculator.canBeUsed(adjacentPoint, pointSide.Left)) {
adjacentPoints.push(adjacentPoint);
}
}
if ((adjacentPoint = AdjacentPointCalculator.pointBelow(startGrid))) {
if (AdjacentPointCalculator.canBeUsed(adjacentPoint, pointSide.Top)) {
adjacentPoints.push(adjacentPoint);
}
}
if ((adjacentPoint = AdjacentPointCalculator.pointAbove(startGrid))) {
if (AdjacentPointCalculator.canBeUsed(adjacentPoint, pointSide.Bottom)) {
adjacentPoints.push(adjacentPoint);
}
}
return adjacentPoints;
}
static canBeUsed(adjacentPoint: Point, requiredEntrySide: string): bool {
return (adjacentPoint.State == pointState.Available &&
(adjacentPoint.EntrySide == requiredEntrySide || adjacentPoint.EntrySide == pointSide.Unknown));
}
static pointToLeft(startGrid): Point {
if (startGrid.currentPoint.x > 0 && startGrid.currentPoint.y < 7) {
return startGrid.points[startGrid.currentPoint.x - 1][startGrid.currentPoint.y];
}
return null;
}
static pointToRight(startGrid: Grid): Point {
if (startGrid.currentPoint.x < 7) {
return startGrid.points[startGrid.currentPoint.x + 1][startGrid.currentPoint.y];
}
return null;
}
static pointBelow(startGrid: Grid): Point {
if (startGrid.currentPoint.y > 0) {
return startGrid.points[startGrid.currentPoint.x][startGrid.currentPoint.y - 1];
}
return null;
}
static pointAbove(startGrid: Grid): Point {
if (startGrid.currentPoint.y < 7 && startGrid.currentPoint.x < 7) {
return startGrid.points[startGrid.currentPoint.x][startGrid.currentPoint.y + 1];
}
return null;
}
}
export class GridSolver {
solved: bool;
startGrid: Grid;
adjacentPointCalculator: AdjacentPointCalculator;
constructor(startGrid: Grid) {
this.startGrid = startGrid;
this.adjacentPointCalculator = new AdjacentPointCalculator();
}
private calcPossibleGrids(gridToSolve: Grid): Grid[] {
var guesses: Grid[] = [];
var startGrid = gridToSolve.clone();
startGrid.currentPoint.State = pointState.Crossed;
var adjacentPoints = this.adjacentPointCalculator.getAvailableAdjacentPoints(startGrid);
if (adjacentPoints.length == 0) {
return null;
}
adjacentPoints.forEach(point =>
{
var guessGrid = startGrid.clone();
var exitPoint = guessGrid.currentPoint;
if (exitPoint.EntrySideFrom(startGrid.endPoint) != pointSide.Bottom) {
guessGrid.currentPoint = guessGrid.points[point.x][point.y];
guessGrid.currentPoint.State = pointState.Crossed;
guessGrid.currentPoint.EntrySide = guessGrid.currentPoint.EntrySideFrom(startGrid.currentPoint);
exitPoint.ExitSide = Point.OppositeOf(guessGrid.currentPoint.EntrySide);
if (guessGrid.IsValid()) {
guesses.push(guessGrid);
}
}
});
return guesses;
}
public solve(): void {
this.recursePossibleGrids(this.startGrid);
}
public recursePossibleGrids(startGrid: Grid): void {
var possibleGrids = this.calcPossibleGrids(startGrid);
if (possibleGrids == null) {
return;
}
possibleGrids.forEach(guessGrid =>
{
if (this.solved) {
return;
}
if (guessGrid.IsSolved()) {
guessGrid.currentPoint.ExitSide = pointSide.Bottom;
//OnSolved(guessGrid);
this.solved = true;
return;
}
if (!this.solved) {
this.recursePossibleGrids(guessGrid);
}
});
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.